Der Entwurf des EA aus Abb. 3.10 bereitet viel Arbeit, aber die könnte sich lohnen, wenn man auf eine übersichtliche Weise einen EA für eine Sprache wie

L = {x {0, 1} | x enthält mindestens eines der Wörter 000, 011 oder 110 als Teilwörter}.

entwerfen möchte. Dann wäre es ausreichend, den EA aus Abbildung 3.10 zu benutzen, die von p000 und p011 ausgehenden Kanten durch

δ (p000, 0) = δ (p000, 1) = p000 und δ (p011, 0) = δ (p011, 1) = p011

zu ersetzen und

F = {p000, p011, p110}

Aufgabe 3.23 Modifiziere den Automaten aus Abbildung 3.10, damit er folgende Sprachen akzeptiert:

a){xyz {0, 1} | y {001, 010, 100}, x, z {0, 1} },

b) {xyz {0, 1} | y {01, 100, 111}, x, z {0, 1} },

c){x011 | x {0, 1} },

d){xz {0, 1} | x {0, 1} , z {001, 010, 100}}.

Zusammenfassung

Eine systematische Methode zum Entwurf von endlichen Automaten basiert auf der Idee zu überlegen, welche Informationen man über das bisher gelesene Präfix der Eingabe speichern muss, um die gegebene Sprache zu akzeptieren (die gesuchte Eigenschaft zu überprüfen). Jeder möglichen Kombination dieser Informationsinhalte wird ein Zustand zugeordnet. Die Übergänge zwischen zwei Zuständen sind dann durch die entsprechenden Änderungen der Worteigenschaften beim Lesen eines Buchstabens gegeben. Manchmal lohnt es sich beim Automatenentwurf, nicht minimalistisch zu sein, sondern mehr Information abzuspeichern als notwendig. Der resultierende endliche Automat wird zwar grösser, dafür aber viel übersichtlicher und für andere auch verständlicher.

449

Kontrollfragen

1.Jeder endliche Automat, der über einem Alphabet Σ arbeitet, verteilt Σ in disjunkte Klassen. Wie sind die Klassen bestimmt?

2.Welche Bedeutung hat es, wenn ein EA durch das Lesen von zwei unterschiedlichen Wörtern x und y den gleichen Zustand erreicht?

3.Wie kann man für eine gegebene Sprache zeigen, dass man zwei Wörter immer unterscheiden muss, damit kein endlicher Automat für L diese zwei Wörter in derselben Zustandsklasse hat?

4.Kann es sich für den Entwurf lohnen, einen nicht kleinstmöglichen Automaten zu entwerfen?

Kontrollaufgaben

1.Entwirf endliche Automaten für folgende Sprachen:

a){0.1} −{λ , 00, 11},

b){00, 001, 101},

c){0, 00, 101, 1011}.

2.Sei L = {x {a, b, c} | |x|a ≥ 3}. Erkläre, warum jeder EA M mit L(M) = L zwischen den vier Wörtern λ , bbab, aacc und abcabcac unterscheiden muss!

3.Sei L = {w {0, 1} | 2 ·|w|0 −|w| und 4 = 2}. Entwirf einen EA für L. Finde drei Wörter, von denen keine zwei in dieselbe Zustandsklasse eines endlichen Automaten für L gehören können und begründe warum!

4.Zeichne einen Obstautomaten, der im Unterschied zu unserem Obstautomaten auch 20- Cent-Münzen M0.20 annimmt.

5.Entwirf EA für folgende Sprachen:

a){x1111y | x, y {0, 1, 2} },

b){x110110y | x, y {0, 1, 2} },

c){x010101y | x, y {0, 1} },

d){x0y | x, y {0, 1} },

e){x0y1z | x, y, z {0, 1} },

f){x {0, 1} | |x|0 ≥ 3},

g){x {0, 1} | 3 ≤ |x|1 ≤ 5},

h) {x001y101z | x, y, z {0, 1} },

e){x0011 | x {0, 1} },

f){x10011 | x {0, 1} },

g){1x11001 | x {0, 1} },

h){x11001y0 | x, y {0, 1} }.

6.Wende die Entwurfstrategie aus Abbildung 3.10 an, um einen EA für folgende Sprachen zu entwerfen:

a){x {0, 1} | x enthält 11 als Teilwort oder endet mit dem Suffix 10},

b){λ , 0, 11, x000 | x {0, 1} },

c){x {0, 1} | x enthält 00 oder 11 als Teilwörter}.

Bestimme die entsprechenden Zustandsklassen für alle entworfenen Automaten.

7.Entwirf endliche Automaten für die folgenden Sprachen und bestimme dabei die Bedeutung aller Zustandsklassen:

a){xy | x {0, 1} und y {00, 10}},

b){xy | x {0, 1} und y {101, 010, 111, 011, 110}},

c){xyz | x, z {0, 1} und y {00, 111, 101}},

d){1xy | x {0, 1} und y {11, 010}}.

451

Lösungen zu ausgesuchten Aufgaben

Aufgabe 3.4

Der endliche Automat für die Sprache L = {0, 1} − {λ } ist in Abb. 3.11 gezeichnet. Der Anfangszustand q0 darf nicht ein akzeptierender Zustand sein, sonst würde λ akzeptiert. Bei jedem Symbol übergeht der Automat in den akzeptierenden Zustand q1 und bleibt in diesem Zustand, egal welche Symbole noch gelesen werden. Damit werden alle nicht leeren Wörter akzeptiert.

Abbildung 3.11

Aufgabe 3.8

Es reicht, alle Zustände ausser q5 in akzeptierende Zustände umzuwandeln.

Aufgabe 3.13

Um zu zeigen, dass kein EA für L = {0110} nach dem Lesen von Wörtern λ und 0 in den gleichen Zustand gelangen darf, wählen wir z = 110. Damit ist λ z = 110 / L und 0z = 0110 L. Somit ist klar, dass jeder Automat zwischen λ und 0 unterscheiden muss. Wenn beide 0 und λ zu einer gleichen Klasse Klasse[q] gehören würden, müssten λ z und 0z entweder beide akzeptiert oder beide verworfen werden. Für λ und 01 kann man z = 10 wählen und erhält nun λ 01 = 01 / L und 01z = 0110 L. Welches andere z kann man auch wählen, um zu zeigen, dass man zwischen λ und 01 unterscheiden muss? Für die Wörter 01 und 0110 kann man z = λ wählen. Damit erhalten wir 01z = 01 / L und 0110z = 0110 L. Die Wahl z = 10 ist auch günstig, weil 01z = 0110 L und 0110z = 011010 / L. Die Wahl z = 1 für 01 und 0110 wird uns nicht helfen, weil in diesem Fall beide 01z und 0110z nicht in der Sprache liegen. Für das Wortpaar (01, 011) ist z = 0 oder z = 10 eine gute Wahl, um zu zeigen, dass 01 und 011 nicht zu der gleichen Zustandsklasse gehören dürfen. Schaffst du es selbst, für die restlichen Wortpaare das passende z zu finden?

Aufgabe 3.15

Wir wählen λ Klasse[q0], 0 Klasse[q1] und 00 Klasse[q2]. Für (λ , 0) wählen wir z = 0. Somit gilt λ z = 0 / L und 0z = 00 L. Für (λ , 00) wählen wir z = λ . Somit erhalten wir λ z = λ / L und 00z = 00 L. Für das Paar (0, 00) wählen wir λ = 0 und erhalten 0z = 00 L und 00z = 000 / L.

Aufgabe 3.16 (e)

Ein EA für die Sprache

{w {a, b, 1} | w = 1x und |x|a mod 2 = 0}

verwirft alle Wörter, die mit a oder b (unterschiedlich von 1) anfangen. In diesem Fall geht der

EA in den Abfallkorb (Abb. 3.12). Wenn das erste Symbol 1 ist, wird überprüft, ob der restliche Teil des Eingabewortes eine gerade Anzahl von Symbolen a beinhaltet. Wo und wieviele Symbole 1 und b in diesem Suffix vorkommen, spielt keine Rolle.

a

a, b

r 1, a, b

Abbildung 3.12

Die Bedeutung der Zustände q0, p0, p1 und r kann wie folgt beschrieben werden.

Aufgabe 3.16 (g)

Jeder endliche Automat für diese Sprache muss für das bisher gelesene Wort w den Rest der Zahl |w|0 −2 ·|w|1 nach der Teilung durch 5 abspeichern. Weil es 5 unterschiedliche Reste 0, 1, 2, 3 und 4 gibt, reichen uns 5 Zustände q0, q1, q2, q3 und q4 mit der Bedeutung

Klasse[qi] = {w {0, 1} | |w|0 −2 ·|w|1 mod 5 = i}

für i = 0, 1, 2, 3, 4. Wenn man eine 0 liest, erhöht sich die Zahl |w|0 −2 ·|w|1 um 1. Damit wächst der Rest für Reste 0, 1, 2 und 3 um 1. Wenn der Rest 4 war, ist der neue Rest 0. Damit kann man in einer Schleife aus 0-Kanten alle Zustände verbinden (Abb. 3.13). Wenn man eine 1 liest, wird die Zahl |w|0 −2 ·|w|1 um zwei vermindert. Das bedeutet, dass die 1-Kanten in der Schleife zwei Stellen zurück springen müssen. Bemerke, dass es das Gleiche ist, wie drei Schritte nach vorne zu springen.

453

Abbildung 3.13

muss. In der ersten Phase sollte man noch nicht intensiv über den Automatenentwurf nachdenken, sondern die Aufgabenstellung präzisieren und mehrere Lösungsstrategien vorschlagen. Typischerweise gibt es keine „optimale“ Strategie, jede hat gewisse Vorund Nachteile. Hinzu kommt noch die Tatsache, dass man keinen so komplexen Automaten, wie etwa das Deutsche Steuergesetz mit 40 000 Seiten, entwerfen will. Zu komplexe Automaten sind unübersichtlich und somit schwer auf Korrektheit zu überprüfen. Ihre Herstellungskosten sind höher. Wenn sie versagen, ist die Fehlersuche viel aufwendiger und damit teurer. Die Wahrscheinlichkeit von Produktionsfehlern ist größer und damit steigen wiederum die Kosten für die Qualitätskontrolle. Die Mitglieder der Projektgruppe sind also auf der Suche nach transparenten, guten Lösungsstrategien. Am Ende der ersten Phase müssen sie sich für eine Strategie entscheiden und ihre Wahl plausibel begründen.

2. Phase Nachdem eine Lösungsstrategie festgelegt wurde, geht man zum Automatenentwurf über. Die Zustände werden verwendet, um alle denkbaren Situationen darzustellen. Das Alphabet wählt man so, dass man mit seinen Buchstaben alle möglichen vorhandenen Signale darstellen kann. Dabei wird nicht unbedingt von Anfang an eindeutig vermittelt, welche Information durch den Zustand gespeichert und welche durch die Signale übertragen werden. Ein Beispiel: Die Information, dass ein Fußgänger den Signalknopf der Ampel gedrückt hat, kann in den Steuerungszustand des ganzen Systems übernommen werden. Es könnte jedoch auch sein, dass diese Information auf der Signalebene bleibt und das Signal erst dann erlischt, wenn die Fußgängerampel auf Grün geschaltet wird.

Für die Projektarbeit in einer Klasse wird dieses Vorgehen empfohlen: Die Klasse wird in Arbeitsgruppen mit vier bis fünf Schülern aufgeteilt. Jede Gruppe erhält eine andere Aufgabenstellung und wählt jemanden, der die Kommunikation innerhalb des Teams leitet. Für die Umsetzung der ersten Phase hat die Klasse circa zwei bis sechs Unterrichtsstunden Zeit. Wenn die erste Phase als Hausaufgabe bearbeitet wird, gibt es einen festen Abgabetermin. In der ersten Phase erstellt jede Gruppe ein Dokument, in dem sie schriftlich alle wichtigen Überlegungen sowie die ausgewählte Strategie mit ihrer Herleitung darlegt. Diese schriftliche Dokumentation der eigenen Vorgehensweise wird an alle anderen Gruppen verteilt. Danach trägt jede Gruppe der kompletten Klasse ihre Vorgehensweise vor. Nach jedem Referat wird im Plenum über die Vorschläge der Gruppe eine ausführliche Diskussion geführt. Es ist wünschenswert, dass sich daraus noch Korrekturund Änderungsvorschläge entwickeln, die anschließend in eine überarbeitete Dokumentation eingearbeitet werden. Diese wird erneut in der Klasse diskutiert.

457

Nach den beiden Diskussionsrunden arbeitet jede Gruppe am Automatenentwurf separat weiter. Wieder wird die Vorgehensweise ausführlich schriftlich dokumentiert und begründet. Die so hergestellten Aufzeichnungen werden erneut an alle verteilt. In einem Abschlussvortrag präsentiert jede Gruppe die Ergebnisse ihrer Arbeit.

Hinweis für die Lehrperson Die Qualität der Abschlusspräsentation kann in die Bewertung einbezogen werden. Für die Bewertung ist jedoch der Inhalt der schriftlichen Dokumentation und damit auch die verständliche Darstellung des Lösungsweges maßgeblich.

Der Rest dieses Abschnittes ist folgendermaßen gegliedert: Zuerst wird eine Beispielaufgabe mit einem Link zu einer ausführlichen Musterlösung präsentiert. Danach werden mittels Aufgaben weitere Fragestellungen vorgeschlagen, die sich zur Projektbearbeitung eignen.

Beispiel 4.1 Projektaufgabe zur Steuerung einer T-Kreuzung

Siedlung C

Siedlung A

Siedlung B

Abbildung 4.1

Allgemeine Situation Es gibt eine T-Kreuzung mit den drei Siedlungen A, B und C wie in Abb. 4.1 dargestellt. Die Straße zwischen den Siedlungen A und B ist eine Einbahnstraße in Fahrtrichtung zur Kreuzung. Die Wagen dürfen von dieser Straße links und rechts abbiegen. Diese Straße ist nicht so intensiv befahren wie die andere, die eine stark frequentierte Hauptstraße ist und auf der Autos in beide Richtungen fahren. Es