Gib deterministische endliche Automaten an, die folgende Sprachen über dem Alphabet ´{0, 1}´ akzeptieren:
- Die Menge aller Wörter, die mit ´00´ enden
- Die Menge aller Wörter mit drei aufeinander folgenden Nullen
- Die Menge aller Wörter, deren vorletztes Symbol eine Eins ist
Teil 1:
´A = ({0, 1}, {z_0, z_1, z_2}, z_0, {z_2}, delta)´
Dabei ist ´delta´ durch folgende Tabelle gegeben:
´delta´ ´z_0´ ´z_1´ ´z_2´ ´0´ ´z_1´ ´z_2´ ´z_2´ ´1´ ´z_0´ ´z_0´ ´z_0´ - In ´z_0´ ist als letztes keine ´0´
- In ´z_1´ ist eine ´0´ das letzte Zeichen
- In ´z_2´ sind zuletzt zwei Nullen als letzte Zeichen gelesen worden
Teil 2:
´A = ({0, 1}, {z_0, z_1, z_2, z_3}, z_0, {z_3}, delta)´
Dabei ist ´delta´ durch folgende Tabelle gegeben:
´delta´ ´z_0´ ´z_1´ ´z_2´ ´z_3´ ´0´ ´z_1´ ´z_2´ ´z_3´ ´z_3´ ´1´ ´z_0´ ´z_0´ ´z_0´ ´z_3´ In ´z_i´ sind ´i´ Nullen hintereinander gelesen worden. Der Automat bleibt nach dem Lesen von drei Nullen hintereinander in ´z_3´, da nun, unabhängig davon was nach den drei Nullen noch gelesen wird, akzeptiert wird,
Teil 3
´A = ({0, 1}, {z_(0,0), z_(0,1), z_(1,0), z_(1,1)}, z_(0,0), {z_(1,0), z_(1,1)}, delta)´
mit
´delta(z_(i_1,i_2), 0) = z_(i_2,0) " für " i_1, i_2 in {0, 1}´ ´delta(z_(i_1,i_2), 1) = z_(i_2,1) " für " i_1, i_2 in {0, 1}´
In den Zuständen ´z_(i,j)´ merkt sich der Automat die beiden zuletzt gelesenen Buchstaben. Dabei wird sich am Anfang der Berechnung eine ´0´ gemerkt, falls noch kein oder nur ein Zeichen gelesen wurde.
Teil 3
´delta´ ´z_00´ ´z_01´ ´z_10´ ´z_11´ ´0´ ´z_00´ ´z_10´ ´z_00´ ´z_10´ ´1´ ´z_01´ ´z_11´ ´z_01´ ´z_11´ Die Index-Nummer setzt sich aus den beiden zuletzt gelesenen Zeichen zusammen.
HPI, 2014-04-12, Theoretische Informatik 2, Blatt 2, Aufgabe 2
2014-07-21 16:29:42 UTC
2014-07-24 11:43:29 UTC