Fo SAP Schritt-für-Schritt PDF

Preview

Summary

Download Fo SAP Schritt-für-Schritt PDF

Description

Formale Systeme Schritt für Schritt

Theoretische Informatik (Fachhochschule Aachen)

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

1 Automatenkonstruktion 1.1 Eine immer wieder gern gestellte Frage ist die nach einem Automaten, der auf Teilbarkeit in einem bestimmten Zahlensystem pr¨uft. Der Grundgedanke zur L¨osung dieser Aufgaben ist immer der Gleiche: Wir lesen eine Zahl in der Reihenfolge ein, in der wir sie auch vorlesen w¨urden (also wir 2315 in der Reihenfolge 2-3-1-5 eingelesen). Wann immer ich also eine Zahl einlese steigt die Wertigkeit der bisher eingelesenen Zahl um den Faktor y. Dazu wird immer noch die neueingelesene Ziffer addiert. Rechnen wir nun in Z/xZ (betrachten wir also nur den Rest bei Division durch x) ¨andert sich daran eigentlich nichts. Es gilt dann also wenn a die bisher eingelesenen Ziffern bezeichnet und b die neue Ziffer: (ab) (mod x) ⌘ a ⇤ y + b (mod x) Mit dieser Wissen in der Hinterhand ist ein Automat dann schnell konstruiert. Wir legen f¨ ur jeden M¨oglichen Restwert einen Zustand an. Rest 0 ist der Startzustand. F¨ur jede Zahl lesen wir nun eine Transition an. Um das Ziel zu bestimmen rechnen wir den aktuellen Restwert mal y und addieren die neueingelesene Ziffer. Das Ergebnis rechnen wir noch modulo x und erhalten den Zielzustand der Transition.

1.2.1 In a Nutshell Schritt 1: Zun¨achst f¨uhren wir f¨ur jedes Paar von Zust¨ anden der beiden Automaten, deren Produktautomaten wir bilden einen Zustand sein. Der Einfachheit halber benennen wir die Zust¨ande nach dem Zustandspaaren, die sie repr¨asentieren. Schritt 2: Beginnend beim Startzustand sehen wir uns an, welche Zust¨ande im Paar des aktuellen Zustands enthalten sind. Wir pr¨ufen nun f¨ur jeden der beiden Automaten, welcher Zustand erreicht worden w¨are wenn ein bestimmtes Zeichen eingelesen worden w¨ are. Die beiden Zust¨ ande, die erreicht worden w¨aren sind das Ziel einer Transition ¨uber dieses Zeichen. Das machen wir f¨ur alle Zeichen. Schritt 3: Wiederhole Schritt 2 f¨ur jeden Zustand des Automaten Schritt 4: Markiere Anfangs- und Enzustand/-zust¨ ande. Das Paar das sowohl den Anfangszustand vom ersten als auch den vom zweiten enth¨alt, wird der neue Anfangszustand. Je nach dem ob wir nach dem Schnitt oder der Vereinigung von zwei Sprachen suchen werden Endzust¨ande entweder die Paare, deren Komponenten ausschließlich aus Endzust¨anden bestehen oder Paare die mindestens einen Endzustand enthalten.

4

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

1.2.2 Beispiel Aufgabe: Geben Sie einen DFA anm der die Sprache L(A) \ L(B) akzeptiert. A:

B: b

a

a

q1

p0

a q0

a, b b

p1

b Schritt 1: F¨ur jedes Paar von Zust¨ anden einen Zustand erzeugen: (q0 , p0 )

(q1 , p0 )

(q0 , p1 )

(q1 , p1 )

Schritt 2: Pr¨ufen: Welcher Zustand wird in A erreicht, wenn ein best. Zeichen gelesen wird. z.B. erreicht man aus q0 mit a q1 und aus p0 a p0 . Also f¨uhrt eine a-Transition von (q0 , p0 ) nach (q1 , p 0 ) a

(q0 , p0 )

(q0 , p1 )

(q1 , p0 )

(q1 , p1 )

Schritt 3: Wiederhole Schritt 2 bis f¨ur jeden Zustand genau eine Transition f¨ur jedes Zeichen den Zustand verl¨asst. a (q1 , p0 ) a (q0 , p0 ) b

b

a (q0 , p1 )

(q1 , p1 )

a

b b

5

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

Schritt 4: Anfangs- und Endzustand/-zust¨ ande markieren. Anfangszustand ist das alt. Endzustand Paar, das sowohl den Anfangszustand von A, als auch den von B enth¨ ist jedes Zustandspaar, dessen Komponenten in A und B ein Endzustand sind (also hier (q1 , p0 ), da q1 Endzustand von A und p0 ein Endzustand von B ist. a

(q0 , p0 )

(q1 , p 0 )

a

(q1 , p 1 )

a

b

b

a (q0 , p1 ) b b

Bevor wir uns den Potenzmengenautomat an einem konkreten Beispiel ansehen, kurz das allgemeine Vorgehen: 1.3.1 In a Nutshell : Betrachte den Anfangszustand. F¨ ur ihn f¨uhrt man den Anfangszustand des Potenzmengenautomates ein: {q0 } : F¨ur jedes Zeichen stellt man sich nun die Frage: Welche Zust¨ande kann ich ” beim Einlesen dieses Zeichens erreichen?“. Diese Zust¨ande findet man in dem man f¨ ur die Zust¨ande, die in der Menge des aktuellen Zustands sind alls M¨oglichkeiten austestet. F¨ur jedes Zeichen fasst man diese Zust¨ ande in einer Menge zusammen. Existiert diese Menge schon als Zustand? Gut dann f¨uhren wir jetzt eine Transition vom aktuellen Zustand mit dem jeweiligen Zeichen dorthin. Nein? Dann f¨uhren wir ihn ein und verfahren, als h¨ atte es ihn schon gegeben. Falls die Menge des neuen Zustands einen Endzustand des Automaten enth¨alt, wird der neue Zustand ein Endzustand. : Nun gehen wir u¨ber zu einem Zustand im Potenzmengenautomaten, den wir bisher noch nicht betrachtet haben und verfahren wie in Schritt 2. Haben wir alle Zust¨ ande betrachtet? Gut! Wir sind fertig.

6

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

1.3.2 Beispiel Aufgabe: Betrachte folgenden NFA: b q0

a, b

a a, b

q1

b

q2

Konstruieren sie mit der Potenzmengenkonstruktion einen DFA, der die gleiche Sprache erkennt. Wir f¨uhren den Anfangszustand ein mit der Menge, die nur den Anfangszustand enth¨alt {q0 } : Jetzt schauen wir uns an, wo wir mit den Zeichen a und b aus q0 hinkommen k¨onnen. Lesen wir ein a ein k¨ onnen wir nur nach q1 kommen. Mit einem b hingegen k¨ onnen wir sowohl in q0 bleiben wie auch nach q1 wechseln: {q0 }

a

{q1 }

b {q0 , q1 } Als n¨ achstes m¨ussen wir nun den Zustand {q1 } betrachten. a {q0 }

a

{q1 }

b

{q2 }

b {q0 , q1 } Da q2 ein akzeptierender Zustand des NFA war, ist jeder Zustand, der q2 enth¨alt hier auch ein akzeptierender Zustand. F¨ uhren wir Schritt 2 weiter durch, erhalten wir schließlich folgenden DFA:

7

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

b

a a

{q0 }

{q1 }

b

{q2 }

a

b {q0 , q1 }

b {q0 , q 1 , q2 }

b

AUTOMATENKONSTRUKTION

a

{q1 , q 2 } a

b

1.4.1 In a Nutshell Schritt 1: Wir wollen einen NFA erhalten. Dieser darf keine ε-Transitionen enthalten. Deswegen entfernen wir zun¨ achst alle ε-Transitionen. Wir haben nun einen NFA. Nun gilt es diesen noch so zu erweitern, dass er ¨aquivalent zum urspr¨ unglichen ε-NFA ist. Schritt 2: Als n¨ achstes sehen wir uns alle m¨oglichen Paare von Zust¨ anden an. Dabei kann so ein Paar auch aus dem zweimal dem gleichen Zustand bestehen und es macht einen Unterschied, ob wir (p, q) oder (q, p) betrachten. F¨ur jedes dieser Paare (p, q) testen wir nun ob q von p aus erreicht werden kann, indem zuerst beliebig viele ε-Transitionen im urspr¨ unglichen Automaten durchgef¨uhrt werden, dann eine nicht-ε-Transition gemacht wird und daraufhin wieder beliebig viele ε-Transitionen im urspr¨unglichen Automaten gemacht werden (Keine Sorge, gleich kommt noch ein konkretes Beispiel). Ist das der Fall verbinden wir p und q mittels der nicht-ε-Transition die zwischen den ε-Transitionen stand.

1.4.2 Beispiel Aufgabe: Erstelle zu folgendem ε-NFA einen ¨aquivalenten NFA. a q0

q1

b

q2

ε a

ε

ε

b

q3

q4

8

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

Schritt 1: Zun¨achst entfernen wir mal alle ε-Transitionen. Damit erhalten wir folgenden NFA: q0

a

q1

b

a

q2 b

q3

q4

Schritt 2: Als n¨ achstes m¨ ussen wir uns alle Zustandspaare ansehen. Exemplarisch machen wir das hier mal f¨ur zwei dieser Paare. Am Ende muss es nat¨urlich f¨ur alle Paare gemacht werden. Zun¨ achst sehen wir uns das Paar (q1 , q 2 ) an. Zun¨ achst d¨ urfen wir beliebig viele ε-Transitionen machen. Da uns die einzige ε-Transition, die von q1 ausgeht, q2 nicht n¨aher bringt, verzichten wir. Danach lesen wir ein beliebiges Zeichen ein. In diesem Fall sind nur a und b m¨oglich. Haben wir a eingelesen befinden wir uns in q3 und k¨onnen q2 unter ausschließlicher Benutzung von ε-Transitionen erreichen. Deswegen f¨ ugen wir eine a-Transition von q1 nach q2 hinzu. Haben wir b eingelesen, dann befinden wir uns in q2 . Nun m¨ussten wir eine b-Transition von q1 nach q2 einf¨ugen. Da die bereits existiert, brauchen wir das nicht zu tun. Nun haben wir also folgenden NFA: a q0

q1 a

a, b

q2 b

q3

q4

Jetzt sind wir mit diesem Paar fertig und betrachten ein anderes Paar: (q1 , q 1 ). Wir kommen mit einer ε-Transition von q1 nach q0 oder wir k¨onnen in q1 bleiben. Betrachten wir zun¨achst q0 . Von dort aus k¨ onnen wir mit einer a-Transition wieder nach q1 kommen, wobei auf die nachfolgenden ε-Transitionen wieder verzichtet wird. Daher m¨ussen wir eine a-Transition von q1 nach q1 hinzuf¨ ugen. Betrachten wir nun den Fall, dass wir eben in q1 geblieben w¨aren. Nach der Regel m¨ ussen wir nun ein Zeichen einlesen. Die einzigen Zeichen, die wir einlesen k¨onnen sind a und b, womit wir nach q3 bzw. q2 kommen. Da uns von dort allerdings keine ε-Transitionen zur¨uck zu q1 f¨uhren sind wir mit diesem Paar fertig:

9

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

a a q0

q1

a, b

q2

a

b q3

q4

Wenden wir diese Schritte auch auf die anderen Zustandspaare an, ergibt sich folgender NFA: b a a q0

a

q1

a, b a, b

q2 b

a

b q3

b

q4

b

Hinweis: Der blaue und der gr¨une Pfeil sind nur deswegen farbig markiert, um Verwechslungen bei der Zuordnung der Beschriftungen auszuschließen.

Zu Beginn wissen wir noch nichts weiter ¨uber den regul¨aren Ausdruck, als das er uns vom Anfangszustand zum Endzustand f¨ uhren soll. Gibt es mehrere Endzust¨ande f¨ uhren wir einfach einen neuen (alleinigen) Endzustand ein, der per Epsilontransition von allen (ehemaligen) Endzust¨ anden aus erreicht werden kann. Wir wollen also rQ (q0 , q f ) berechnen, wobei q0 der Anfangszustand und qf der Endzustand ist. Schritt 1: Angeben, was noch berechnet werden muss. z.B. rQ (q0 , qf ), im Fall, das noch nichts berechnet wurde. Schritt 2: Angeben, was als n¨ achstes berechnet werden soll. Dabei entfernen wir je einen Zustand aus Q und berechnen rQ (s, t) folgendermaßen: rQ (s, t) = rQ\x (s, t) + rQ\x (s, x)rQ\x (x, x)∗ rQ\x (x, t) Anschaulich bedeutet das, dass wir in unserem Automaten entweder direkt von s zu t gehen oder aber erst zu einem Zustand dazwischen (x) gehen, dort dann beliebig viele Zeichen einlesen und schließlich zu t weitergehen. Alle diese Teilausdr¨ucke (z.B. rQ\x (x, x)) werden dann in die Liste der noch zu berechnenden Ausdr¨ucke eingetragen. K¨onnen keine weiteren Zust¨ande aus der Menge die unten an r dransteht entfernen - steht also an r die leere Menge dran - d¨urfen wir r durch

10

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

ein konkretes Zeichen ersetzen. Dieses lesen wir am Automaten ab. r∅ (q0 , q 1 ) erg¨abe mit unten abgebildetem Automaten also ein a, da eine a-Transition direkt von q0 nach q1 f¨ uhrt. Gibt es keine solche Transition, w¨ahlen wir ;. Sind die Zust ¨ande in den Klammern gleich nehmen wir ein ε. a b a q0

q1 b

Schritt 3: Solange die Liste der noch zu berechnenden Ausdr¨ucke noch nicht leer ist geht’s weiter mit Schritt 1. Ansonsten lassen sich die Ausdr¨ucke nun wieder nach und nach zusammensetzen, da die jeweiligen Teilausdr¨ucke ja inzwischen berechnet sind. F¨ur obigen Automaten erhalten wir dann beispielsweise als Ergebnis: rQ (q0 , q1 ) ⌘ b∗ a(a∗ bb∗ a)∗

1.6 1.6.1 In a Nutshell Um aus einem regul¨aren Ausdruck einen Automaten zu konstruieren m¨ussen wir uns zun¨achst ansehen, wie sich bestimmte Operationen in einem Automaten umsetzen lassen: Beginnen wir mit dem Kleene Sternchen: ε

q0

A

qA0

qAn

ε Wir f¨ uhren daf¨ ur einen neuen Zustand ein der per ε-Transition zum Startzustand uhrt, der den Ausdruck erkennt, an dem das Kleene-Sternchen eines Automaten A f¨ steht. Der oder die Endzust¨ande f¨uhrt dann per ε-Transition zur¨uck zu unserem neuen Startzustand. Als n¨ achstes sehen wir uns die Konkatenation an: q0

ε

qA0

A

qAn

ε

q01

ε

qB0

B

qBn

Es wird also nur ein Zustand vor dem ersten Automaten eingef¨ugt, der per ε-Transition zum Automaten f¨ uhrt, der die erste Sprache erkennt. Dann wird ein zweiter Zustand zwischen dem ersten und dem zweiten Automaten eingef¨ugt. Zu diesem f¨ uhrt eine εTransition vom Endzustand des ersten Automaten. Außerdem f¨uhrt eine ε-Transition von ihm zum zweiten Automaten. Damit haben wir die beiden Sprachen konkateniert.

11

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

¨ hnlich basteln wir uns ein oder“: A ” A qA0 qAn ε ε q0

q01 ε qB0

ε

B

qBn

M¨ ochten wir nun einen Automaten erstellen, der den regul¨aren Ausdruck erkennt, splitten benutzen wir immer wieder obige Konstrukte. Haben wir eins der Konstrukte verwendet, k¨ onnen wir den zugeh¨origen Operator aus dem regul¨aren Ausdruck streichen und mit dem vereinfachten Teilausdruck weitermachen. Dabei arbeiten wir uns von außen nach innen vor. 1.6.2 Beispiel Aufgabe: Geben Sie einen Automaten an, der den folgenden regul¨aren Ausdruck erkennt: (ab)∗ + c Zun¨ achst k¨ummern wir uns um das oder“: ” A q q A0

An

ε

ε

q0

q01 ε qB0

ε

c

qBn

Als n¨ achstes k¨ ummern wir uns um das Kleene-Sternchen: a b qA0 qA1 qAn ε ε ε

q0

q01

ε qB0

c

ε qBn

Damit sind wir fertig und haben unseren Automaten, der (ab)∗ + c erkennt.

12

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

1.7 Myhill-Nerode-DFA (Verfeinerungsalgorithmus) 1.7.1 In a Nutshell Schritt 1: Zuna¨chst betrachten wir die Menge aller Zust¨ande. Diese Unterteilen wir dann in die Menge der Endzust¨ande und Nicht-Endzust¨ande. Schritt 2: Nun pr¨ ufen wir in jeder der Mengen, ob sich die Zust¨ande in der Menge bzgl. ihrer Transitionen gleich verhalten. Im Klartext: Wenn man eine Transition ¨uber ein bestimmtes Zeichen ausf¨uhrt, wird dann jeweils die gleiche (der hier konstruierten) Menge erreicht? Diesen Vorgang wiederholen wir solange, bis sich alle Zust¨ande innerhalb einer Menge gleich verhalten. Schritt 3: Alle Zust¨ ande, die sich jetzt noch zusammen in einer Menge befinden legen wir zu einem einzigen Zustand zusammen. Die Transitionen k¨onnen wir am urspr¨ unglichen DFA ablesen, indem wirf¨ur einen beliebigen Zustand aus jeder Menge f¨ur jede Transition schauen aus welcher Menge der Zustand ist, der durch die Transition erreicht wird. 1.7.2 Beispiel a

b q0

a

q1 a

b

b

q2

q3

a

b

Schritt 1: Zun¨achst unterteilen wir in Endzust¨ ande und nicht Endzust¨ande. Wir erhalten also folgendes: {q0 , q1 , q2 , q 3 } (Endzustand?) P1 = {q0 , q3 }

P2 = {q1 , q 2 }

Schritt 2: Wir testen nun durch, wie sich die Elemente der Mengen bzgl. Transitionen verhalten. F¨ ur die Endzust¨ande stellen fest, dass das mit einer a-Transition immer P2 und mit einer b-Transition immer P1 erreicht wird.

13

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

F¨ ur P1 stellen wir fest, dass q3 , wenn ein a gelesen wird immer ein Element aus P2 erreicht wird und mit einem b ein Element aus P1 . Schritt 3: Da wir nun mit dem Aufspalten fertig sind, k¨onnen wir den Myhll-NerodeDFA konstruieren, indem wir f¨ur jede der verbleibenden Mengen einen Zustand anlegen und die entsprechenden Transitionen anlegen. F¨ur die Transitionen reicht es sich im urspr¨ unglichen DFA einen Zustand aus der Menge anzusehen und f¨ur jedes Zeichen zu schauen, aus welcher Menge der Zustand ist, der durch die Transition erreicht wird. a b a P1

P2 b

1.8 Rechtslineare Grammatik ! Automat 1.8.1 In a Nutshell Eine Grammatik ist genau dann Rechtslinear, wenn gilt, dass alle Produktionen die Form A ! aB A!a A!ε haben. Rechtslineare Grammatiken haben den Vorteil, dass sie sich relativ einfach Automaten uberf¨ uhren lassen: ¨ Schritt 1: Wir f¨uhren f¨ur jedes Nichtterminal einen nicht akzeptierenden Zustand ein. Weiterhin erzeugen wir einen Zustand qaccept , der der einzige akzeptierende Zustand des Automaten wird. Schritt 2: Nun behandeln wir die Produktionsregeln wie folgt: Fall 1: A ! aB In diesem Fall f¨uhren wir eine Transition ein, die von A nach B f¨ uhrt und a einliest. Fall 2: A ! a _ A ! ε Hier f¨ uhren wir eine Transition von A nach qaccept ein, mit der a eingelesen wird.

14

Distributing prohibited | Downloaded by DataSec l ([email protected])

FoSAP Schritt f¨ur Schritt

1

AUTOMATENKONSTRUKTION

1.8.2 Beispiel Wir wollen folgende Grammatik in einen Automaten ¨uberf¨uhren: S ! aA A ! aB|a B!b Schritt 1: Wir haben drei Nichtterminale: A, B und S. F u ¨ r jeden erstellen wir einen Zustand und zus¨ atzlich den akzeptierenden Zustand qaccept : S

A

B

qaccept Schritt 2: Nun f¨ uhren wir S ! aA eine Transition von S nach A u ¨ ber a ein. Analog behandeln wir die anderen Produktionen. S

a

a

A

B

a

b qaccept

1.9 Grammatik ! Kellerautomaten 1.9.1 In a Nutshell F¨ur jede kontextfreie Sprache l¨ asst sich ein PDA ( pushdown automata“) angeben. Am ” einfachsten ist dies, wenn wir die Grammatik, die der PDA erkennen soll, in ChomskyNormalform vorliegen haben. Schritt 1: Bringe die zu erkennende Grammatik in Chomsky-Normalform. Wie das geht, ist in Abschnitt 3.6 beschrieben. Schritt 2: Unser Automat besteht nur aus dem Startzustand. Diesen erstellen wir nun. Schritt 3: Nun m¨ ussen wir die Transitionen erstellen. Diese f¨uhren alle vom Startzustand aus wieder i...