Dies ist eine alte Version des Dokuments!
Abba-Automat
Gegeben ist der erkennende Automat M durch M = {Z, E, δ, Q, {P}}, wobei E = {a,b} und Z = {P,Q,R} ist.1)
Die Übergangsfunktion δ: Z × E 6 Z ist durch die folgende Tabelle festgelegt:
δ(Q,a)=Q, δ(Q,b)=R, δ(P,a)=Q, δ(P,b)=P, δ(R,a)=Q und δ(R,b)=P. a) Zeichne den Automatengraph b) Prüfe folgende Wörter und notiere, in welchem Zustand sie enden und ob sie vom Automaten akzeptiert werden oder nicht: (1) aba, (2) bbaa, (3) aabb und (4) ababba. c) Gib selbst noch je zwei eigene Beispiel-Wörter an, die akzeptiert werden, sowie zwei Bei- spielwörter, die nicht akzeptiert werden. Beschreibe außerdem kurz in Deutsch, welche Eigen- schaft akzeptierte Wörter haben müssen.
1)
Z: ZUstandsmenge, E: Eingabemenge, δ: Übergangsfunktion, Q: Startzustand, {P}: Endzustandsmenge