Beispiel 1:
Entwerfen Sie einen FA mit ∑ = {0, 1}, der die Zeichenfolge akzeptiert, die mit 1 beginnt und mit 0 endet.
Lösung:
Der FA hat einen Startzustand q0, von dem aus nur die Kante mit Eingang 1 in den nächsten Zustand übergeht.
Wenn wir im Zustand q1 den Wert 1 lesen, befinden wir uns im Zustand q1, wenn wir jedoch im Zustand q1 den Wert 0 lesen, gelangen wir zum Zustand q2, dem Endzustand. Wenn wir im Zustand q2 entweder 0 oder 1 lesen, wechseln wir zum Zustand q2 bzw. zum Zustand q1. Beachten Sie, dass sich die Eingabe im Endzustand befindet, wenn sie mit 0 endet.
Beispiel 2:
Entwerfen Sie einen FA mit ∑ = {0, 1}, der die einzige Eingabe 101 akzeptiert.
Lösung:
In der gegebenen Lösung können wir sehen, dass nur die Eingabe 101 akzeptiert wird. Daher wird für Eingabe 101 kein anderer Pfad für andere Eingaben angezeigt.
Beispiel 3:
Design FA mit ∑ = {0, 1} akzeptiert eine gerade Anzahl von Nullen und eine gerade Anzahl von Einsen.
Lösung:
Dieser FA berücksichtigt vier verschiedene Stufen für Eingang 0 und Eingang 1. Die Stufen könnten sein:
Dabei ist q0 sowohl ein Startzustand als auch der Endzustand. Beachten Sie sorgfältig, dass eine Symmetrie von Nullen und Einsen gewahrt bleibt. Wir können jedem Zustand folgende Bedeutungen zuordnen:
q0: Zustand einer geraden Anzahl von Nullen und einer geraden Anzahl von Einsen.
q1: Zustand einer ungeraden Anzahl von Nullen und einer geraden Anzahl von Einsen.
q2: Zustand einer ungeraden Anzahl von Nullen und einer ungeraden Anzahl von Einsen.
q3: Zustand der geraden Anzahl von Nullen und der ungeraden Anzahl von Einsen.
Beispiel 4:
Design FA mit ∑ = {0, 1} akzeptiert die Menge aller Strings mit drei aufeinanderfolgenden Nullen.
Lösung:
Die Zeichenfolgen, die für diese bestimmte Sprache generiert werden, sind 000, 0001, 1000, 10001, ..., wobei 0 immer in einer Gruppe von 3 erscheint. Das Übergangsdiagramm sieht wie folgt aus:
Beachten Sie, dass die Reihenfolge der dreifachen Nullen beibehalten wird, um den Endzustand zu erreichen.
Beispiel 5:
Entwerfen Sie einen DFA L(M) = {w | w ε {0, 1}*} und W ist eine Zeichenfolge, die keine aufeinanderfolgenden Einsen enthält.
Lösung:
Wenn drei aufeinanderfolgende Einsen auftreten, lautet der DFA:
Hier sind daher zwei aufeinanderfolgende Einsen oder eine einzelne Eins akzeptabel
Die Stufen q0, q1, q2 sind die Endzustände. Der DFA generiert die Zeichenfolgen, die keine aufeinanderfolgenden Einsen wie 10, 110, 101 usw. enthalten.
Beispiel 6:
Entwerfen Sie einen FA mit ∑ = {0, 1}, der die Zeichenfolgen mit einer geraden Anzahl von Nullen gefolgt von einer einzelnen 1 akzeptiert.
Lösung:
mamta kulkarni
Der DFA kann durch ein Übergangsdiagramm wie folgt dargestellt werden:
