427

Aufgabe 2.12 Könntest du, ohne die Berechnung aufzuschreiben, feststellen, ob C1 −|M−C2 für M aus Abb. 2.12 für folgende C1 und C2 gilt?

a)C1 = (q0, 110110),C2 = (q3, 1101)

b)C1 = (q2, 0110),C2 = (q3, 0011)

Begründe deine Antwort!

Aufgabe 2.13 Für welche Paare der folgenden Konfigurationen (C1,C2) ist C2 aus C1 durch eine Berechnung der EA M (Abb. 2.12) erreichbar?

a)C1 = (q2, 0101001),C2 = (q2, 1)

b)C1 = (q1, 110110),C2 = (q3, 10)

c)C1 = (q0, 010100100),C2 = (q3, 100)

Zusammenfassung

Endliche Automaten sind Programme mit nummerierten Zeilen, die keine Variablen, sondern nur die Verzweigungsbefehle select und if ... then ... else verwenden. Die Zeile, in der das Programm seine Arbeit beendet, bestimmt das Resultat. Endliche Automaten lösen Entscheidungsprobleme. Die Zeilen sind auf zwei Gruppen verteilt. Ein Gruppe bedeutet Akzeptanz, die andere Nichtakzeptanz.

Bei der Visualisierung von endlichen Automaten ziehen wir eine graphische Darstellung vor. Die Zeilen bezeichnen wir als Knoten eines gerichteten Graphen. Einzelne gotoAnweisungen sind durch Kanten (Pfeile) dargestellt.

Ein Berechnungsschritt eines endlichen Automaten entspricht der Ausführung des Befehls einer Zeile. Wir verstehen darunter einen Übergang aus einer Konfiguration in eine andere. Mit dem Begriff der Konfiguration bezeichnen wir eine vollständige Beschreibung der Situation (der Gesamtzustände) eines Rechnermodells. Eine Berechnung kann man dann als eine Folge von Berechnungsschritten ansehen oder als eine Folge von Konfigurationen darstellen, wobei man aus jeder Konfiguration der Folge die nachfolgende Konfiguration in einem Schritt erreichen kann.

Zur mathematischen Darstellung eines endlichen Automaten verwenden wir den Begriff Zustand anstelle von Programmzeile.

Kontrollfragen

1.Was sind die Grundkomponenten eines Rechners? Welche fehlen bei endlichen Automaten?

2.Wie kann ein endlicher Automat rechnen, wenn er keine Variablen benutzen darf?

3.Welche sind die einzigen Befehle eines endlichen Automaten?

4.Wie löst ein endlicher Automat ein Entscheidungsproblem?

5.Welche drei Modelle von endlichen Automaten wurden vorgestellt? Wie wechseln die Namen der Grundbegriffe bei dem Übergang von Modell zu Modell?

6.Was ist eine Konfiguration eines endlichen Automaten?

7.Was ist ein Berechnungsschritt eines endlichen Automaten? Was ist eine Berechnung eines endlichen Automaten?

8.Wann betrachten wir eine Berechnung als eine Berechnung auf einem Wort? Wie viele Berechnungen gibt es auf einem Wort?

9.Wann akzeptiert ein endlicher Automat ein Wort? Wie stellen wir fest, dass ein EA ein gegebenes Wort verwirft (nicht akzeptiert)?

Kontrollaufgaben

1.Schreibe einen endlichen Automaten als ein zweizeiliges Programm, das

a)über dem Alphabet {a, b, c, d} arbeitet,

b)mit der nullten Zeile akzeptiert und

c)in einer beliebigen Zeile nach dem Lesen jedes Buchstabens die Zeile wechselt.

2.Stelle den EA aus der Kontrollaufgabe 1 in den anderen Formen dar.

429

3.Bestimme die drei kürzesten Wörter über {0, 1}, die der EA in Abb. 2.3 akzeptiert. Bestimme die vier kürzesten Wörter über {0, 1}, die der Automat nicht akzeptiert.

4.Betrachte den endlichen Automaten in Abb. 2.4. Schreibe die Berechnungen des Automaten auf den Wörtern 06, 09, 05, 0101010, 0011001.

5.Betrachte den EA aus Abb. 2.12. Finde zwei Konfigurationen C und D so, dass D aus C nicht erreichbar ist. Ist die Konfiguration (q0, 111) aus der Konfiguration (q1, 00010111) erreichbar?

6.Entwerfe graphisch einen endlichen Automaten zum Verkauf von Briefmarken vom Wert 50c und 80c. Zum Kauf darf man nur Münzen 10c, 20c und 50c verwenden. Der Verkaufsautomat gibt kein Geld zurück, also muss die Einkaufssumme genau einbezahlt werden.

Lösungen zu ausgesuchten Aufgaben

Aufgabe 2.1

Wenn man in der 0-ten Zeile des Programms das Symbol c liest, wird der Befehl goto 0 ausgeführt. Somit bleibt man in der 0-ten Zeile.

Wenn man in der ersten Zeile das Symbol b liest, setzt die Ausführung des Programms wegen „input = b goto 0“ die Arbeit in der 0-ten Zeile fort.

Aufgabe 2.4 Das Programm zu dem endlichen Automaten in Abb. 2.4 sieht wie folgt aus:

Die Zeile 1 ist die einzige akzeptierende Zeile. Das leere Wort λ wird damit nicht akzeptiert, weil man mindestens ein Symbol braucht um aus der Zeile 0 die Zeile 1 zu erreichen. Damit ist das kürzeste akzeptierte Wort das Wort 0. Es wird kein anderes Wort der Länge 1 akzeptiert. Von der Länge 2 werden die Wörter 10 und 00 akzeptiert. Von der Länge 3 sind es die Wörter 011, 101 und 110.

Aufgabe 2.9

Die graphische Darstellung des Übergangs zwischen zwei Konfigurationen in Abb. 2.11 entspricht dem Berechnungsschritt:

(r, 0011) −|M− (s, 011).

Aufgabe 2.12 a)

Die Konfiguration C2 = (q3, 1101) kann nicht aus der Konfiguration C1 = (q0, 110110) erreicht werden, weil das Wort 1101 aus C2 kein Suffix des Wortes 110110 aus C1 ist.

geht der Automat immer dann, wenn ohne Rücksicht auf den noch nicht gelesenen Rest (Suffix) des Eingabewortes schon sicher ist, dass das Wort nicht in der Sprache liegt. Der Automat darf den Abfallkorb nicht mehr verlassen, was man dadurch gewährleistet, dass keine Transition aus dem Abfallkorb führt. Der resultierende Automat ist in Abb. 3.2 dargestellt.

Abbildung 3.2

Wir sehen,

δ (q5, 0) = δ (q5, 1) = q5

gewährleistet das Nicht-Verlassen des Abfallkorbs. Die Transitionen

δ (q4, 0) = δ (q4, 1) = q5

verursachen, dass jedes Wort, welches mit dem Präfix 0110 anfängt und dann weiter fortgesetzt wird, nicht akzeptiert wird.

Aufgabe 3.1 Zeichne einen endlichen Automaten, der die Sprache {abbaa} über dem Alphabet {a, b} akzeptiert.

Beispiel 3.2 Wir betrachten jetzt die Sprache L = {00111, 111, 000}, die drei Wörter enthält. Um einen EA A mit L(A) = L zu entwerfen, wählen wir eine ähnliche Strategie wie im Beispiel 3.1. Wir testen die korrekten Symbolfolgen. Die Wörter 000 und 00111 haben das gemeinsame Präfix 00. Deshalb überprüfen wir die ersten zwei Symbole für diese beiden Wörter gemeinsam und erst dann die restlichen Suffixe 0 und 111. Diese Strategie ist in Abb. 3.3 durch einen Teilautomaten dargestellt.

433

Abbildung 3.3

Aufgabe 3.2 Vervollständige den Teilautomaten aus Abb. 3.3 zu einem Automaten A mit L(A) = {00111, 111, 000}. Wie würdest du diesen EA modifizieren, um einen EA für die folgenden Sprachen zu entwerfen?

a)L = {00111, 101}

b)L = {111, 0000, 0011}

c)L = {00111, 000, 0111}

Aufgabe 3.3 Entwirf endliche Automaten für die folgenden endlichen Sprachen:

a)L = {11111} über {0, 1},

b)L = {0101, 11, 0100} über {0, 1},

c)L = {0, 00, 001, 0010} über {0, 1, 2},

d)L = {0, 1, 2, 00, 10, 211} über {0, 1, 2}.

435

Anfangszustand q0 über einem Alphabet Σ arbeitet, dann setzt A eine Funktion aus Σ nach Q um, die jedem Wort x aus Σ den Zustand zuordnet, in dem A nach dem Lesen von x endet. Mit anderen Worten, wenn

gilt, hat A dem Wort x den Zustand p zugeordnet.

für jedes p Q. Die Klasse [p] beinhaltet alle Wörter, deren Bearbeitung aus der entsprechenden Startkonfiguration im Zustand p endet. Somit sieht die Situation wie in Abb. 3.5 aus.

Abbildung 3.5 Σ

Offensichtlich ist

Klasse[p] ∩Klasse[q] = 0/

437

Später werden wir für diese Zuordnung der Klassen zu den Zuständen auch die Korrektheit beweisen. Weil q4 der einzige akzeptierende Zustand ist, gilt

L(A) = Klasse[q4] = {0110}.

Aufgabe 3.7 Begründe mit eigenen Worten, warum die Klassen der fünf Zustände des EA in Beispiel 3.4 korrekt bestimmt sind.

Aufgabe 3.8 Wie würdest du den EA in Abb. 3.2 modifizieren, damit er die folgende Sprache L = {x {0, 1} | x ist ein Präfix von 0110} akzeptiert?

Aufgabe 3.9 Entwirf einen EA, der die Sprache L = {x {0, 1, 2} | x ist ein Präfix von 1101102} akzeptiert. Bestimme dabei die Klassen, die zu den Zuständen gehören.

Aufgabe 3.10 Bestimme die Wortklassen der Zustände von den endlichen Automaten, die du bei der Bearbeitung von Aufgabe 3.3 entworfen hast.

Aufgabe 3.11 Bestimme die Wortklassen der Zustände von den endlichen Automaten, die du bei der Bearbeitung der Aufgabe 3.6 entworfen hast.

Aufgabe 3.12 Welche Bedeutung haben die Klassen für den Obstautomaten in Abb. 2.5?

Warum ist dieses Konzept der Zerlegung von Σ in Zustandsklassen für den Automatenentwurf nützlich?

Die zu erkennende Sprache L ist durch konkrete Eigenschaften ihrer Wörter gegeben. Ein EA A mit L(A) = L soll diese Eigenschaften erkennen, indem er sich nach der Bearbeitung eines Präfixes etwas merkt. Der Inhalt des Merkens wird durch den Zustand bestimmt, in dem er sich gerade befindet. Jeder Zustand entspricht konkreten Worteigenschaften. Wenn man im Vorfeld richtig abschätzt, was man sich zum Erkennen der Worteigenschaften merken muss, dann kann man die Zustände und ihre Bedeutungen bestimmen. Erst danach bestimmt man fast automatisch die Transitionen (Kanten) zwischen den Zuständen.

Hinweis für die Lehrperson Die nachfolgenden Überlegungen empfehlen wir nicht für das Selbststudium. Eine intensive Mitwirkung der Lehrperson ist erwünscht. Es ist auch an der Lehrperson zu entscheiden, wie weit sie den exakten Weg des mathematischen Formalismus verfolgt. Statt des hier präsentierten allgemeinen Zugangs kann man die Idee auch nur anhand von Beispielen erklären.

Um es noch besser zu begreifen, stellen wir folgende Überlegung an: Seien x und y zwei unterschiedliche Wörter, die zur gleichen Klasse Klasse[p] eines EA A gehören. Dies bedeutet

In Abb. 3.6 ist diese Tatsache veranschaulicht.

Abbildung 3.6

Nach dem Lesen von x und y gelangt der EA A in den gleichen Zustand p. In diesem Augenblick

kann A zwischen x und y nicht mehr unterscheiden.

Der Automat weiß nur, dass er sich im Zustand p befindet, jedoch nicht, durch welches Wort er p erreicht hat (weil er keinen Speicher hat). Welche Konsequenzen hat das? Wenn noch ein beliebiges Wort z (Suffix z) zu lesen ist, dann endet der endliche Automat A in einem Zustand q. Der Zustand q ist dabei jener, zu dem man gelangt, wenn man im

yz in der Klasse[q]. Somit gehören entweder xz und yz in L(A) (wenn q F ) oder beide nicht (wenn q / F ). Formal lautet diese wichtige Beobachtung:

Satz 3.1 Sei A = (Σ, Q, δ , q0, F ) ein endlicher Automat. Seien x und y zwei beliebige Wörter aus Σ . Wenn

für einen Zustand p Q ist, dann gilt für alle Wörter z Σ : xz und yz gehören zur selben Klasse[q] für ein q Q

439

und folglich

xz L yz L.

Was lernen wir aus dieser Behauptung? Wir haben eine Strategie (Methode) entwickelt, mit der wir für eine gegebene Sprache die Merkmale der Wörter bestimmen können, die in jedem EA, der L akzeptiert, durch Zustände unterschieden werden müssen.

Sehen wir uns die Sprache L = {0110} und den entsprechenden Automaten in Abb. 3.2 an. Wenn wir es intuitiv betrachten, muss sich jeder EA, der L akzeptiert, das bisher gelesene Präfix von 0110 merken.

Lass uns diese Intuition formal bestätigen! Wenn ein EA nach dem Lesen von

x = 0 und y = 01

in beiden Fällen in den gleichen Zustand gelangen würde (d.h. er könnte nicht mehr unterscheiden, ob er bisher 0 oder 01 gelesen hat), dann würden wir

z = 10

auswählen. Es gilt:

xz = 010 / L und yz = 0110 L

Also muss xz = 010 verworfen und yz = 0110 akzeptiert werden. Wenn aber 0 und 01 in dieselbe Zustandsklasse gehören würden, dann wäre es laut Satz 3.1 nicht möglich. Deswegen muss jeder EA für L zwischen 0 und 01 unterscheiden können, indem er jeweils nach dem Lesen von 0 und von 01 in unterschiedliche Zustände gelangt.

Aufgabe 3.13 Zeige, dass jeder EA für L = {0110} zwischen den Wörtern λ , 0, 01, 011 und 0110 unterscheiden können muss. Finde dazu für jedes Paar (x,y) dieser fünf Wörter ein z, so dass xz L und yz / L (oder xz / L und yz L). Beispielsweise kann man für das Paar (0,0110) z als 110 oder als λ wählen.

Aufgabe 3.14 Entwirf einen EA für L = {aaab} über {a, b}. Erkläre die Bedeutung der Zustände des entworfenen Automaten und begründe, warum du sie brauchst.

441

Weil λ keine 0 enthält, muss q0 der Anfangszustand sein. Wenn man eine 1 liest, bleibt man im aktuellen Zustand, weil es keinen Einfluss auf die Akzeptanzbedingung hat. Also:

δ (q0, 1) = q0, δ (q1, 1) = q1 und δ (q2, 1) = q2.

Beim Lesen einer 0 ändert sich die Anzahl der Nullen um 1 und entsprechend dieser Änderung müssen die Transitionen (Kanten mit Beschriftung 0) gelegt werden. Für die Zustände q0 und q1 bedeutet es, dass der Rest um 1 größer geworden ist und somit gilt

δ (q0, 0) = q1 und δ (q1, 0) = q2.

Wenn der Rest 2 war, dann bedeutet eine zusätzliche 0, dass der Rest 0 wird. Daher bestimmen wir

δ (q2, 0) = q0.

Der Zustand q2 ist der akzeptierende Zustand, (d.h. F = {q2}), weil

L = Klasse(q2).

Wenn uns jetzt jemand die Aufgabe stellen würde, einen EA für die Sprache

L0,2 = {w {0, 1} | |w|0 mod 3 = 0 oder |w|0 mod 3 = 2}

zu erzeugen, würden wir einfach den EA aus Abb. 3.7 benutzen und dabei nur F = {q0, q2} festsetzen. Weil

L0,2 = Klasse(q0) Klasse(q2),

Aufgabe 3.15 Wende Satz 3.1 an, um zu zeigen, dass das Merken der Anzahl Nullen modulo 3 im Beispiel 3.4 unvermeidbar war. Hinweis: Du musst drei Wörter w0, w1 und w2 finden, so dass gilt: w0 Klasse(q0), w1 Klasse(q1) und w2 Klasse(q2). Für jedes Paar (wi, w j ) mit i =j muss man ein z finden, so dass eins der Wörter wiz und w j z in L ist und das andere nicht.

a){w {0, 1} | |w|1 mod 5 {1, 3}},

b){w {0, 1} | |w|1 mod 5 {0, 2, 4}},

c){w {0, 1} | |w|0 mod 6 ist gerade},

d){w {a, b} | |w|a = 2} = {biab j abk | i, j, k N},

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

f){w {0, 1} | 2 ·|w|0 mod 5 = 1},

g){w {0, 1} | |w|0 −2 ·|w|1 mod 5 = 0},

Bestimme für die entworfenen Automaten alle Zustandsklassen.

Beispiel 3.6 Unsere nächste Aufgabe ist es, einen EA für die Sprache

L(0010) = {x0010y | x, y {0, 1} }

zu entwerfen.

Hier ist der Entwurf etwas schwieriger als bei einer Sprache, bei der alle Wörter mit 0010 anfangen sollen. Wir müssen feststellen, ob 0010 an beliebiger Stelle im Eingabewort vorkommt. Zuerst muss sich der EA merken, welchen Teil des Präfixes von 0010 er schon in den zuletzt gelesenen Buchstaben gefunden hat. Ein Beispiel: Wenn das bisher gelesene Wort 011001 war, dann muss er sich merken, dass er schon 001 als Kandidaten gefunden hat. Wenn jetzt das nächste Symbol 0 ist, dann muss er akzeptieren. Falls der EA das Präfix 1100 einer Eingabe gelesen hat, muss er merken, dass die letzten zwei Symbole 00 passend waren1. Damit ergeben sich fünf mögliche Zustände entsprechend den fünf

1Im Prinzip reicht es aus, die Zahl 2 zu speichern, weil das Wort 0010 bekannt ist und 00 das Präfix der Länge 2 ist.

443

Präfixen von 0010. Ihre Bedeutung wird nachfolgend halbformal beschrieben.

Klasse[p0] kein Präfix von 0010 ist ein nicht leeres Suffix von dem bisher gelesenen Wort x (z.B. x = λ oder x endet mit 11) und das Wort enthält das Teilwort 0010 nicht.

Klasse[p1] die Wörter enden mit 0 und enthalten kein längeres Präfix von 0010 als Suffix (z.B. sie enden mit 110) und das Wort enthält das Teilwort 0010 nicht.

Klasse[p2] die Wörter enden mit 00 und enthalten kein längeres Präfix von 0010 als ihr Suffix und das Wort enthält das Teilwort 0010 nicht.

Klasse[p3] die Wörter enden mit 001 und das Wort enthält das Teilwort 0010 nicht.

Klasse[p4] die Wörter enden mit 0010 oder beinhalten 0010 als Teilwort.

Diese Vorlage ergibt direkt die folgende Teilstruktur (Abb. 3.8) des zu konstruierenden EA.

Abbildung 3.8

Dass die Folge 0010 gelesen werden muss, um den einzigen akzeptierenden Zustand p4 zu erreichen, ist offensichtlich. Erreicht man p4 , hat der EA schon 0010 in der Eingabe gefunden und somit verbleibt man im akzeptierenden Zustand (δ (q4, 0) = δ (q4, 1) = q4), unabhängig davon, was noch kommt. Das Lesen einer 1 in q0 ändert nichts. Es gab noch kein Präfix von 0010 in den letzten Buchstaben, weil 0010 mit 0 anfängt.

Um den EA zu vervollständigen, fehlen uns drei Pfeile aus den Zuständen p1, p2 und p3 zum Lesen von 1 aus p1 und p3 und von 0 aus p2. Es gibt nur eine eindeutige Möglichkeit, dies korrekt umzusetzen (um L(0010) zu erkennen). Sie ist in Abb. 3.9 dargestellt. Wird eine 1 in p1 gelesen, beginnt die Suche nach 0010 neu, weil 0 das längste

Abbildung 3.9

Suffix des gelesenen Wortes ist, das einem Präfix von 0010 entspricht. Somit bedeutet eine hinzugekommene 1 am Schluss, dass wir aktuell kein Präfix von 0010 vorliegen haben. Mit anderen Worten: Wenn 0 das Suffix von x mit x Klasse[p1] war, dann ist 01 das Suffix von x1. Somit hat x1 kein passendes Suffix. Damit ist

δ (p1, 1) = p0.

Wenn man aber in p2 eine 0 liest, bleibt es dabei, dass 00 das Suffix des eben gelesenen Wortes ist. (Wenn 00 ein Suffix von x ist, ist 000 ein Suffix von x0.) Somit bleiben wir in p2, also

δ (p2, 0) = p2.

Wenn man in p3 zu einer 1 kommt, endet das gelesene Wort auf 11. (Wenn x mit 001 endet, dann endet x1 mit 0011.) Somit kann das Wort am Ende kein nichtleeres Suffix von 0010 enthalten. Die einzige, mögliche Schlussfolgerung ist

δ (p3, 1) = p0.

Aufgabe 3.17 Beschreibe die Klassen der Zustände des EA in Abb. 3.9 formal genau. Nimm für jede Klasse einen Repräsentanten (ein Wort aus der Klasse) und wende Satz 3.1 an. Zeige daran, dass man diese Klassen wirklich unterscheiden muss.

Aufgabe 3.18 Entwirf einen EA, der die folgende Sprache akzeptiert:

a){0010x | x {0, 1} },

b){xabbaabay | x, y {a, b} },

c){x00110 | x {0, 1} }.

445

Im Beispiel 3.6 haben wir einen EA in Abb. 3.9 entworfen, der genau die Wörter akzeptiert, die das Wort 0010 als Teilwort enthalten. Der anstrengendste Teil des Entwurfs bestand in der Bestimmung der Kanten (Transitionen), wenn die Suche nach 0010 wegen einer Unstimmigkeit unterbrochen wurde. Dann musste man entscheiden, ob die Suche neu beginnen soll oder ob das zuletzt gelesene Suffix doch noch ein kürzeres Präfix von 0010 enthält. In diesem Fall musste die weitere Suche an der entsprechenden Stelle fortgesetzt werden. Dass man an dieser Stelle wirklich aufpassen muss, zeigt die Schwierigkeit der Klassenbeschreibung in Aufgabe 3.17. Man kann das Risiko in diesem Entwurfprozess vermeiden, indem man mehr Informationen über das gelesene Wort speichert. Eine Idee wäre, mit Hilfe der Zustandsnamen alle Suffixe der Länge 4 zu speichern. Ein Beispiel: Ein Zustand q0110 soll alle Wörter enthalten, die mit 0110 enden. Dadurch ist alles übersichtlich und die Beschreibung der Zustandsklassen einfach. Diese Transparenz geht jedoch auf Kosten der Automatengröße. Wir haben 24 = 16 Zustände, um alle Suffixe der Länge 4 über {0, 1} zu speichern. Das ist jedoch nicht alles. Es gibt auch kürzere Wörter, die natürlich kein Präfix der Länge 4 enthalten. Alle Wörter kürzer als 4 benötigen daher eigene Zustände, woraus sich

23 + 22 + 21 + 1 = 15

weitere Zustände ergeben. Weil das Zeichnen eines EA mit 16 + 15 = 31 Zuständen einen hohen Aufwand produziert, stellen wir eine Anwendung dieser Idee für die Suche nach einem kürzeren Teilwort vor.

Beispiel 3.7 Betrachten wir die Sprache

L = {x110y | x, y {0, 1} }.

Wie oben angedeutet, führen wir die Zustände pabc ein, wobei in pabc die Wörter ankommen, die mit dem Suffix abc für a, b, c {0, 1} enden. Dies ist noch nicht ganz genau, weil wir für abc =110 ein Wort mit dem Suffix abc nur dann in die Klasse[pabc] aufnehmen können, wenn das Wort das Teilwort 110 nicht enthält (in diesem Fall müsste die Akzeptanz eines solchen Wortes längst entschieden worden sein). Wir beschreiben jetzt die Bedeutung aller Zustände:

Klasse[p110] = L = {x {0, 1} | x enthält das Teilwort 110}, Klasse[p000] = {x000 | x {0, 1} und x000 enthält

das Teilwort 110 nicht},

Klasse[p001] = {x001 | x {0, 1} und x001 enthält das Teilwort 110 nicht},

Klasse[p010] = {x010 | x {0, 1} und x010 enthält das Teilwort 110 nicht},

Klasse[p011] = {x011 | x {0, 1} und x011 enthält das Teilwort 110 nicht},

Klasse[p100] = {x100 | x {0, 1} und x100 enthält das Teilwort 110 nicht},

Klasse[p101] = {x101 | x {0, 1} und x101 enthält das Teilwort 110 nicht},

Klasse[p111] = {x111 | x {0, 1} und x111 enthält das Teilwort 110 nicht}.

Dann brauchen wir die Zustände

pλ , p0, p1, p00, p01, p10 und p11

für kürzere Wörter, daher gilt:

Klasse[pλ ] = {λ }, Klasse[p0] = {0}, Klasse[p1] = {1}, Klasse[p00] = {00}, Klasse[p01] = {01},

Klasse[p10] = {10} und Klasse[p11] = {11}.

Der Startzustand ist offensichtlich der Zustand pλ , und p110 ist der einzige akzeptierende Zustand.

Der daraus resultierende EA ist in Abb. 3.10 dargestellt. Die Verzweigungsstruktur (Baumstruktur in der Informatik genannt) oben weist jedem Wort der Länge kürzer gleich 3 einen anderen Zustand zu. Alle anderen Kanten (Transitionen) führen zu den untersten Zuständen pabc. Wenn zum Beispiel ein Wort x001 durch eine Null zu x0010 verlängert wird, dann muss man aus p001 in p010 übergehen (d.h. δ (p001, 0) = p010).

Deswegen sind die Kanten so gelegt, dass durch das Lesen eines weiteren Symbols immer der Zustand erreicht wird, der dem neuen Suffix der Länge 3 entspricht. Die einzige Ausnahme ist der Zustand p110. Von dort aus wird nicht in einen anderen Zustand

447

01

Abbildung 3.10

gewechselt, egal welche Symbole noch gelesen werden, denn das Teilwort 110 wurde bereits in der Eingabe erkannt und das gesamte Wort musste akzeptiert werden.

Aufgabe 3.19 In Abb. 3.10 fehlen die Pfeile aus dem Zustand p011 für beide Symbole 0 und 1. Kannst du sie korrekt einzeichnen?

Aufgabe 3.20 Verändere den EA in Abb. 3.10 so, dass er die Sprache {x100y | x, y {0, 1} } akzeptiert.

Aufgabe 3.21 Modifiziere den EA in Abb. 3.10 so, dass er die Sprache {w100 | w {0, 1} } akzeptiert.

Aufgabe 3.22 Modifiziere den EA in Abb. 3.10 so, dass er die Sprache {00} {x111 | x {0, 1} } akzeptiert.