Dein Fortschritt:
0 / 0 Aufgaben
1
Durch 3 teilbar
13 BEAFB I–IIEin Prüfbaustein liest Binärzahlen von links nach rechts und akzeptiert genau die, deren Wert durch 3 teilbar ist; führende Nullen sind erlaubt, das leere Wort gilt als 0. Der Zustand ri bedeutet „der bisher gelesene Wert hat bei Division durch 3 den Rest i“.
DEA „durch 3 teilbar“ über Σ = {0, 1}
- Geben Sie die Zustandsfolgen für
110und111an und entscheiden Sie jeweils, ob das Wort akzeptiert wird. (3 BE) - Stellen Sie die zugehörige reguläre Grammatik in der Notation N, T, Startsymbol, Produktionsregeln auf. (4 BE)
- Stellen Sie die Ableitung von
1001dar und ordnen Sie jedem Schritt den Zustand des DEA zu. (3 BE) - Das leere Wort soll nicht mehr erzeugt werden, alle anderen Wörter der Sprache schon. Erläutern Sie, wie die Grammatik dafür geändert werden kann. (3 BE)
Hinweise
Hinweis zu Aufgabe a)
Folgen Sie ab r0 den Pfeilen; die Zustandsfolge hat ein Element mehr als das Wort Zeichen.
Hinweis zu Aufgabe b)
Ordnen Sie r0, r1, r2 die Nichtterminale S, A, B zu. Jeder Pfeil wird eine Regel, der Endzustand eine ε-Regel.
Hinweis zu Aufgabe c)
Das Nichtterminal am Ende jeder Satzform ist der aktuelle Zustand.
Hinweis zu Aufgabe d)
Einfach S → ε zu streichen, reicht nicht — dann fehlen auch
11 oder 0. Ein neues Startsymbol hilft.