Wird von einer nicht deterministischen Zustandsmaschine benötigt M = (Q, T, D, q 0 , F) einen deterministischen endlichen Automaten bauen M = (Q", T, D", q" 0 , F"). Der Anfangszustand für den zu konstruierenden Automaten ist der ε-Abschluss des Anfangszustands des Anfangsautomaten. ε-Abschluss - eine Menge von Zuständen, die von einem gegebenen durch Übergänge entlang ε erreichbar sind. Während es Zustände gibt, für die keine Übergänge konstruiert wurden (Übergänge werden durch Symbole gemacht, Übergänge durch die im ursprünglichen Automaten), ist für jedes Symbol der ε-Abschluss der Menge von Zuständen, die vom betrachteten Zustand aus erreichbar sind durch Übergang durch das betrachtete Symbol berechnet. Wenn der Zustand, der der gefundenen Menge entspricht, bereits existiert, wird dort eine Transition hinzugefügt. Wenn nicht, wird der neue empfangene Zustand hinzugefügt.

Beispiel

Initialisierung

Die Zustände, die dem ε-Abschluss des Anfangszustands entsprechen, sind markiert. Diese Zustände entsprechen dem Zustand EIN zukünftigen DKA.

Erste Iteration

Es gibt Übergänge vom ε-Abschluss zu den NCA-Zuständen 3 und 10 (gem a und c, beziehungsweise). Für Zustand 3 ist der ε-Abschluss die Menge der Zustände (3, 4, 6), für Zustand 10 – (10). Lassen Sie uns die neuen DFA-Zustände, die diesen Mengen entsprechen, als bezeichnen B und C.

DKA-Staat	Satz von NFA-Zuständen
		a	b	c
EIN	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	-	-
C	{10}	-	-	-

Zweite Iteration

Aus der Menge der Zustände des NFA (3, 4, 6) entsprechend dem Zustand des DFA B es gibt zwei Übergänge - zu Zustand 5 (durch b) und 7 (von c). Ihre ε-Abschlüsse schneiden sich, aber die Mengen selbst sind unterschiedlich, daher werden ihnen zwei neue DFA-Zustände zugewiesen - D und E. Aus den Staaten der NFA, die dem Staat der EDA entsprechen C, es gibt keine Übergänge.

DKA-Staat	Satz von NFA-Zuständen	Springbare Charaktere
		a	b	c
EIN	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	-	-	-
E	{2, 7, 8, 9}	-	-	-

Dritte Iteration

Aus den Zuständen des NFA, die den Zuständen des DFA entsprechen D und E es werden Übergänge zu den Mengen von Zuständen vorgenommen, die den vorhandenen Zuständen entsprechen (von der Menge (2, 5, 8, 9), die dem Zustand entspricht D, an aÜbergang zu Zustand 3, der zu der Menge (3, 4, 6) gehört, die dem Zustand des DFA entspricht B, an c- Übergang zum Zustand 10 entsprechend dem Zustand C; ähnlich für den Satz, der dem Zustand des DFA entspricht E). Der Prozess des Aufbaus der Tabelle von Zuständen und Übergängen des DFA ist abgeschlossen.

DKA-Staat	Satz von NFA-Zuständen	Springbare Charaktere
		a	b	c
EIN	{1, 2, 9}	B	-	C
B	{3, 4, 6}	-	D	E
C	{10}	-	-	-
D	{2, 5, 8, 9}	B	-	C
E	{2, 7, 8, 9}	B	-	C

Ergebnis:

Aufbau einer rechtslinearen Grammatik aus einem endlichen Automaten

Jedem Zustand ist ein Nichtterminal zugeordnet. Wenn es einen Zustandsübergang gibt X in einen Staat Y an a, fügen Sie die Regel hinzu X → ja. Fügen Sie für Endzustände Regeln hinzu X→ z. Für ε-Übergänge - X → Y.

Beispiel 1 (deterministische Zustandsmaschine)

• A → a b | c C
• B → b D | c E
• C → z
• D → a b | c C
• E → a b | c C

Beispiel 2 (nicht deterministische Zustandsmaschine)

• 1 → 2 | 9
• 2 → a 3
• 3 → 4 | 6
• 4 → b 5
• 5 → 8
• 6 → c 7
• 7 → 8
• 8 → 2 | 9
• 9 → c 10
• 10 → ε

Bau von DFA durch RV

Lassen Sie uns einen regulären Ausdruck haben r. Basierend auf diesem regulären Ausdruck ist es notwendig, einen deterministischen endlichen Automaten zu bauen D so dass L(D) = L(r).

Modifikation regulärer Ausdrücke

Lassen Sie uns ein Symbol hinzufügen, das das Ende des RV bedeutet - "#". Als Ergebnis erhalten wir einen regulären Ausdruck ( r)#.

Einen Baum bauen

Stellen wir uns einen regulären Ausdruck als Baum vor, dessen Blätter die Endzeichen sind und dessen innere Knoten die Operationen der Verkettung ".", der Vereinigung "∪" und der Iteration "*" sind. Wir weisen jedem Blatt des Baumes (außer ε-Blättern) eine eindeutige Nummer zu und bezeichnen sie einerseits als Position im Baum und andererseits als Position des entsprechenden Symbols Blatt.

Berechnung von Funktionen nullable, firstpos, lastpos

Wenn wir nun den Baum T von unten nach oben von links nach rechts durchlaufen, berechnen wir drei Funktionen: nullable, erstepos, und letzte Pos. Funktionen nullable, erstepos und letzte Pos an den Knoten des Baums definiert. Der Wert aller Funktionen außer nullable, ist die Menge der Positionen. Funktion erstepos(n) für jeden Knoten n des Regex-Syntaxbaums gibt den Satz von Positionen an, die mit den ersten Zeichen in den Teilzeichenfolgen übereinstimmen, die durch den Teilausdruck erzeugt werden, der auf endet n. Ebenfalls, letzte Pos(n) gibt den Satz von Positionen an, die den letzten Zeichen in den Teilzeichenfolgen entsprechen, die von Teilausdrücken mit top erzeugt werden n. Für Knoten n, deren Unterbäume (d. h. ein Baum, dessen node n ist eine Wurzel) kann ein leeres Wort erzeugen, definieren wir nullable(n) = Stimmt, und für andere Knoten FALSCH. Tabelle zu berechnen nullable, erstepos, letzte Pos:

Knoten n	nullable(n)	erstepos(n)	letzte Pos(n)
ε	Stimmt	∅	∅
ich ≠ ε	FALSCH	{ich}	{ich}
u ∪ v	nullable(u) oder nullable(v)	erstepos(u) ∪ erstepos(v)	letzte Pos(u) ∪ letzte Pos(v)
du . v	nullable(u) und nullable(v)	wenn nullable(u) dann erstepos(u) ∪ erstepos(v) anders erstepos(u)	wenn nullable(v) dann letzte Pos(u) ∪ letzte Pos(v) anders letzte Pos(v)
v*	Stimmt	erstepos(v)	letzte Pos(v)

Followpos bauen

Funktion Folgepos berechnet über nullable, erstepos und letzte Pos. Funktion Folgepos auf mehreren Positionen definiert. Bedeutung Folgepos ist eine Reihe von Positionen. Wenn ein ich- Stellung also Folgepos(ich) gibt es viele Positionen j so dass es eine Schnur gibt ... CD... in der von RW beschriebenen Sprache enthalten, so dass ich passt zu diesem Eintrag c, a j- Eintrag d. Funktion Folgepos kann auch in einem Durchlauf des Baums gemäß den folgenden zwei Regeln berechnet werden

1. Lassen n- interner Knoten mit "." (Verkettung); a, b- seine Nachkommen. Dann für jede Position ich darin enthalten letzte Pos(a Folgepos(ich) viele erstepos(b).
2. Lassen n- interner Knoten mit "*"-Operation (Iteration), a- sein Nachkomme. Dann für jede Position ich darin enthalten letzte Pos(a), fügen Sie dem Satz von Werten hinzu Folgepos(ich) viele erstepos(a).

Beispiel

Funktionswert berechnen Folgepos für reguläre Ausdrücke ( a(b|c))*c.

Position	Bedeutung Folgepos
1: (a (b|c))*c	{2, 3}
2: (a(b |c))*c	{1, 4}
3: (a(b|c ))*c	{1, 4}
4: (a(b|c))*c	{5}

Erstellen eines DFA

Ein DFA ist eine Menge von Zuständen und eine Menge von Übergängen zwischen ihnen. Der DFA-Zustand ist eine Reihe von Positionen. Die Konstruktion eines DFA besteht in der allmählichen Hinzufügung der notwendigen Zustände und der Konstruktion von Übergängen für sie. Zunächst gibt es einen Zustand erstepos(Wurzel) (Wurzel- die Wurzel des Baumes), die keine Übergänge hat. Der Übergang erfolgt durch Zeichen aus dem regulären Ausdruck. Jedes Zeichen entspricht einer Reihe von Positionen ( p ich). Alle vereinen Folgepos(x) ist der Zustand, zu dem man gehen muss, wobei x eine Position ist, die sowohl unter den Positionen des Zustands als auch unter den Positionen des Symbols aus dem RE vorhanden ist, an dem der Übergang erfolgt. Wenn es keinen solchen Zustand gibt, muss er hinzugefügt werden. Der Vorgang muss wiederholt werden, bis alle Übergänge für alle Zustände aufgebaut sind. Alle Zustände, die die Position des am Ende des RE hinzugefügten #-Symbols enthalten, werden für endgültig erklärt.

DFA erhalten von RV ( a(b|c))*c

Beispiel

Erstellen Sie DFA anhand eines regulären Ausdrucks ( a(b|c))*c.

DKA-Staat	Symbol
	ein(1)	b(2)	c(3, 4)
A(1, 4)	B(2, 3)	-	C(5)
B(2, 3)	-	A(1, 4)	A(1, 4)
C(5)	-	-	-

Erstellen eines DFA mit einer minimalen Anzahl von Zuständen

Für einen überall definierten DEA wird ein DEA mit einer minimalen Anzahl von Zuständen konstruiert, d.h. so dass . Für jeden DFA gibt es ein überall definiertes DFA-Äquivalent dazu.

Konstruktion eines überall definierten DEA

Führen Sie einen neuen Zustand ein und definieren Sie eine neue Reihe von Zuständen .

Lassen Sie uns eine neue Übergangsfunktion wie folgt definieren:

Erstellen einer Partition (formal)

Lassen Sie uns die anfängliche Partition erstellen P Sätze von Zuständen in zwei Gruppen: Endzustände F und andere S/F, d.h. P = {F, Q\F}.

Bewerben Sie sich für jede Gruppe G ∈ P folgendes Verfahren. zerschlagen G in Untergruppen, so dass die Staaten s und t aus G genau dann in derselben Gruppe landeten, wenn für jedes Eingabesymbol a Zustände s und tÜbergänge haben a zu Staaten aus derselben Gruppe in P.

Die resultierenden Untergruppen werden der neuen Partition hinzugefügt P Neu.

Annehmen P = P neu und wiederholen Sie den Aufbau der Partition bis zur Stabilisierung, d.h. bis sich die Partition nicht mehr verändert.

Erstellen einer Partition (Algorithmus)

Um eine Partition zu konstruieren, gibt es den folgenden Algorithmus. Wir erstellen eine Übergangstabelle für den ursprünglichen Automaten, erstellen eine anfängliche Partition.

Wir weisen jeder Gruppe aus der Partition eine Kennung zu (für die anfängliche Partition beispielsweise 0 und 1).

Jedem Zustand (jeder Zeile der Tabelle) wird eine Zeichenfolge der Form „a.bcd…xyz“ zugewiesen, wobei die Kennung der Gruppe ist, zu der der Zustand gehört [die erste Spalte (woher wir gehen), die zweite Spalte (wo wir nach dem ersten Zeichen gehen), …, die letzte Spalte (wo wir nach dem letzten Zeichen gehen)].

Wir bilden neue Gruppen entsprechend der Koinzidenz von Strings, d. h. so, dass Zustände mit denselben zugewiesenen Strings in eine Gruppe fallen.

Dann eine neue Iteration. Den resultierenden Gruppen weisen wir neue Bezeichner zu, zum Beispiel (0, 1, ..., n). Und wir wiederholen den Bau der Trennwand bis zur Stabilisierung.

Beachten Sie, dass Sie, wenn nur noch ein Zustand in der Gruppe übrig ist, in späteren Phasen der Erstellung der Partition die Zeichenfolge der Identifikatoren für diesen Zustand nicht mehr ausschreiben können, da diese Zeichenfolge aufgrund des ersten Zeichens von in jedem Fall eindeutig ist die Saite. Mit anderen Worten, beim Aufteilen passiert einer Gruppe aus einem Zustand nichts – sie wird unverändert in einen neuen Split übertragen.

Konstruktion des reduzierten Automaten

Jede der resultierenden Gruppen wird zum Zustand eines neuen DFA. Wenn die Gruppe den Anfangs- (End-) Zustand des ursprünglichen Automaten enthält, wird diese Gruppe zum Anfangs- (bzw. End-) Zustand des neuen DFA. Übergänge werden auf offensichtliche Weise konstruiert: Ein Übergang von einer Gruppe zu einem Zustand wird als Übergang zu einer Gruppe betrachtet.

Wir bringen die Maschine. Wir entfernen zuerst das Nichterzeugende (steril, "tot"), dann unerreichbare Zustände (Definitionen werden für Symbole gegeben, aber in naheliegender Weise auf Zustände des Automaten übertragen).

Im Allgemeinen macht das Entfernen toter Zustände einen DFA zu einem NFA, da in einem DFA alle Übergänge definiert werden müssen. Im Drachenbuch wird eine solche Abweichung von der formalen Definition jedoch immer noch als akzeptabel angesehen.

Beispiel

Um einen DFA mit einer minimalen Anzahl von Zuständen für einen DFA der folgenden Form zu konstruieren:

• Anfängliche Teilung: (C) ( Endzustand), (A, B, D, E) ( alle anderen Staaten).
• (C)( ohne Veränderung), (A, D, E), (B), ( da wir von A, D, E entlang a, c nach B bzw. C gehen).
• Wir können keine Splits mehr machen.

Gruppe (C) korrespondiere mit Zustand C, Gruppe (A, D, E) mit Zustand A und Gruppe (B) mit Zustand B. Dann erhalten wir einen DFA mit einer minimalen Anzahl von Zuständen:

Beispiel (Algorithmus zum Erstellen einer Partition)

Eine Übergangstabelle für einen überall definierten (Zustand Z hinzugefügt) DFA entsprechend RV (ab|ε)a*|abb|b*a. Aus den Prüfungsfragen 2012.

	a	b	ich 0	ich 1
→A*	B	C	0.01	0.12
B*	D	E	0.00	1.01
C	F	C	1.01
D*	D	Z	0.01	0.04
E*	D	Z	0.00	1.03
F*	Z	Z	0.11
Z	Z	Z	1.11

Iterationen:

• I 0: ABCDEF(0), CZ(1).
• I 1: AD(0), BE(1), C(2), F(3), Z(4).
• I 2: A, B, C, D, E, F, Z.

Ergebnis: Die Maschine hatte bereits die Mindestanzahl an Zuständen :-)

DFA, das die Sprachvervollständigung ermöglicht

Der Algorithmus zum Erstellen eines DFA, der das Komplement der Sprache L (L̅) akzeptiert, besteht aus zwei Schritten:

• Erstellen eines vollständigen DFA
• Bau des gewünschten Automaten daraus

Tatsächlich gibt es so etwas wie einen vollständigen DFA nicht. Unter voller DKA etwas Lehrer verstehen den Automaten, in dessen Übergangstabelle es keine leeren Zellen gibt. Allerdings darf es laut DFA-Definition - δ: Q × Σ → Q - auf keinen Fall leere Zellen geben. Der Automat "mit leeren Zellen" erfüllt jedoch die Definition der NFA. Nicht selten erhält man im Zuge des Lösens einen solchen NFA, dem nur Übergänge vor dem DEA fehlen.

Um es wieder aufzufüllen, reicht es aus, einen neuen Zustand hinzuzufügen X, und "anstelle von" nicht existierenden Übergängen fügen diesem neuen Zustand Übergänge hinzu. Vergessen Sie nicht, Übergänge von hinzuzufügen X in X. Es ist leicht zu erkennen, dass dort, wo der ursprüngliche Automat aufgrund des Fehlens eines Übergangs eine Kette nicht akzeptiert hat, der neue Automat in den Zustand übergeht X und hänge daran fest. Da der neue Zustand kein akzeptierender (endgültiger) Zustand ist, wird der neue Automat diese Kette auch nicht akzeptieren.

Um nun den gewünschten Automaten zu bauen, ist es nur noch notwendig, die Rollen von akzeptierenden und nicht akzeptierenden Zuständen zu ändern. Mit anderen Worten, F" = Q \ F.

Aufbau eines LL(k)-Analysators

Transformation der Grammatik

Nicht jede Grammatik ist LL(k)-parsbar. Eine kontextfreie Grammatik gehört zur LL(1)-Klasse, wenn sie keine FIRST-FIRST-Konflikte (Linksrekursion ist ein Sonderfall eines solchen Konflikts) und FIRST-FOLLOW hat.

Manchmal ist es möglich, Nicht-LL(1)-Grammatiken so umzuwandeln, dass sie zu LL(1) werden. Einige (genauer gesagt diejenigen, die im Kurs betrachtet wurden) Transformationen sind unten angegeben.

Linke Rekursion entfernen

Angenommen, wir haben eine Formregel (im Folgenden in diesem Abschnitt Großbuchstaben - nichtterminale Symbole, Kleinbuchstaben - Ketten beliebiger Zeichen):

• A→A a| EIN b| … | EIN k | m | n | … | z

Es ist keiner eindeutigen Analyse zugänglich und sollte daher konvertiert werden.

Es ist leicht zu zeigen, dass diese Regel mit dem folgenden Regelpaar äquivalent ist:

• A → m b | n b | … | z B
• B → a b | b b | … | k b | ε

Linke Faktorisierung

Das Wesentliche dieses Verfahrens ist die Eliminierung von Mehrdeutigkeiten bei der Auswahl von Regeln für das linke Zeichen. Dazu wird ein gemeinsames linkes Präfix gefunden und was darauf folgen kann, wird in einer neuen Regel herausgenommen (Kleinbuchstaben - Ketten beliebiger Zeichen)

Beispiel

• A → a c | a df | a dg | b

Konvertiert zu

• A → a b | b
• B → c | d f | d g

was wiederum wird

• A → a b | b
• B → c | d AUS
• C → f | g

Beispiel für die Grammatikkonvertierung

G= ((S, A, B), (a, b, c), P, S)

• S→SAbB | a
• A→ab | aa | ε
• B → c | ε

Linke Rekursion für S entfernen:

• S → wieS 1
• S 1 → AbBS 1 | ε

Linke Faktorisierung für A:

• A → aA 1 | ε
• A 1 → b | a

Abschließende Grammatik:

• S → wieS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Bauen Sie ERST und FOLGEN

FIRST(α), wobei α ∈ (N ∪ T)* die Menge der Terminals ist, von denen α beginnen kann. Wenn α ⇒ ε, dann ε ∈ FIRST(α). Dementsprechend ist der Wert von FOLLOW( EIN) für Nichtterminal EIN- Viele Terminals, die unmittelbar danach erscheinen können EIN in irgendeiner sentimentalen Form. Wenn ein EIN kann das Zeichen ganz rechts in irgendeiner Satzform sein, dann gehört das abschließende $-Token auch zu FOLLOW( EIN)

ERSTE Berechnung

Für Endgeräte

• Für jedes Endgerät x, x ∈ T, ERSTE( x) = {x}

Für Nicht-Terminals

• Wenn ein X ein Nichtterminal ist, dann setzen wir FIRST( X) = {∅}
• Wenn Grammatik eine Regel hat X→ ε, dann addiere ε zu FIRST( X)
• Für jedes Nicht-Terminal X und für jede Inferenzregel X → Y 1 …Y k zu ERST hinzufügen ( X) die ERSTE Menge aller Symbole auf der rechten Seite der Regel bis auf das erste, von dem ε nicht abgeleitet ist, einschließlich seiner

Für Ketten

• Für Zeichenkette X 1 …X k FIRST ist die Vereinigung von FIRST-Zeichen, die in der Zeichenfolge enthalten sind, bis zum ersten, das ε ∉ FIRST hat, einschließlich.

Beispiel

• S → wieS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

ERSTE Nicht-Terminals in der Reihenfolge der Abhängigkeitsauflösung:

• ERSTE(S) = (a)
• ZUERST(A) = (a, ε)
• ZUERST(A 1) = (b, a)
• ZUERST(B) = (c, ε)
• ZUERST(S 1) = (a, b, ε)

FIRST für Inferenzregeln:

• ZUERST(aS 1) = (a)
• ERSTER(ABBS 1) = (a, b)
• ZUERST(ε) = (ε)
• ZUERST(aA 1) = (a)
• ZUERST(a) = (a)
• ZUERST(b) = (b)
• ZUERST(c) = (c)

Berechnung FOLGEN

Berechnung der FOLLOW-Funktion für Zeichen X:

• Sei FOLLOW(X) = (∅)
• Wenn X ein Grammatikaxiom ist, dann füge die Markierung $ zu FOLLOW hinzu
• Für alle Regeln der Form A → αXβ füge FIRST(β)\(ε) zu FOLLOW(X) hinzu (auf X können die Zeichen folgen, die mit β beginnen)
• Für alle Regeln der Form A → αX und A → αXβ, ε ∈ FIRST(β), füge FOLLOW(A) zu FOLLOW(X) hinzu (d. h. auf X können alle Zeichen folgen, die A folgen können, falls in in die Inferenzregel, das X kann ganz rechts sein)
• Wiederholen Sie die beiden vorherigen Absätze so lange, wie es möglich ist, dem Satz Zeichen hinzuzufügen

Beispiel

• S → wieS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Ergebnis:

• FOLGE(N) = ($)
• FOLLOW(S 1) = ($) (S 1 ist das Zeichen ganz rechts in der Regel S → aS 1)
• FOLLOW(A) = (b) (Auf A in Regel S 1 → AbBS 1 folgt b)
• FOLLOW(A 1) = (b) (A 1 ist das Zeichen ganz rechts in der Regel A → aA 1 , daher wird FOLLOW(A) zu FOLLOW(A 1) hinzugefügt)
• FOLLOW(B) = (a, b, $) (add FIRST(S 1)\(ε) (folgt aus Regel S 1 → AbBS 1), FOLLOW(S 1) (weil es S 1 → ε gibt))

Zusammenstellung einer Tabelle

Tisch M für ein Nicht-Terminal-Terminal-Paar (in der Zelle M[EIN, a]) gibt die Regel an, nach der das Eingabewort reduziert werden muss. Die Tabelle wird wie folgt ausgefüllt: Für jede Inferenzregel einer gegebenen Grammatik A → α (wobei α als Kette auf der rechten Seite der Regel verstanden wird) werden die folgenden Aktionen ausgeführt:

1. Für jedes Endgerät a∈ FIRST(α) füge eine Regel hinzu EIN → α zu M[EIN, a]
2. Wenn ε ∈ FIRST(α), dann für jeden b∈ FOLGEN( EIN) hinzufügen EIN → α zu M[EIN, b]
3. ε ∈ ZUERST(α) und $ ∈ FOLLOW( EIN), hinzufügen EIN → α zu M[EIN, $]
4. Alle leeren Zellen sind ein Fehler im Eingangswort

Beispiel

Erstellen Sie eine Grammatiktabelle

• S → wieS 1
• S 1 → AbBS 1 | ε
• A → aA 1 | ε
• A 1 → b | a
• B → c | ε

Ergebnis:

	a	b	c	$
S	S → wieS 1 (Erste Regel, Schluss S → aS 1 , a ∈ FIRST(aS 1))	Error (Vierte Regel)	Error (Vierte Regel)	Error (Vierte Regel)
S1	S 1 → AbBS 1 (Erste Regel, Ausgang S 1 → AbBS 1 , a ∈ FIRST(AbBS 1))	S 1 → AbBS 1 (Erste Regel, Ausgang S 1 → AbBS 1 , b ∈ FIRST(AbBS 1))	Error (Vierte Regel)	S1 → ε (Dritte Regel, Schluss S 1 → ε, ε ∈ FIRST(ε), $ ∈ FOLLOW(S 1))
EIN	A → aA 1 (Erste Regel, Ausgang A → aA 1 , a ∈ FIRST(aA 1))	A→ε (Zweite Regel, Ausgabe A 1 → ε, b ∈ FOLLOW(A 1))	Error (Vierte Regel)	Error (Vierte Regel)
Ein 1	A1 → ein (Erste Regel, Ausgang A 1 → a, a ∈ FIRST(a))	A1 → b (Erste Regel, Ausgabe A 1 → b, b ∈ FIRST(b))	Error (Vierte Regel)	Error (Vierte Regel)
B	B→e	B→e (Zweite Regel, Schluss B → ε, a ∈ FOLLOW(B))	B → c (Erste Regel, Ausgabe B → c, c ∈ FIRST(c))	B→e (Dritte Regel, Schluss B → ε, $ ∈ FOLLOW(B))

String-Parsing

Das Analysieren einer Zeichenfolge ist recht einfach. Seine Essenz ist wie folgt: Bei jedem Schritt wird das obere Symbol gelesen v c Eingangskette.

• Wenn ein v- Terminalsymbol
  • Wenn ein v fällt zusammen mit Mit, dann werden sie beide zerstört, es gibt eine Verschiebung
  • Wenn ein v stimmt nicht mit überein Mit, dann wird ein Analysefehler signalisiert
• Wenn ein v- Nicht-Terminal-Symbol, c springt stattdessen zum Anfang der Zeile zurück v die rechte Seite der Regel, die aus der Tabellenzelle genommen wird, wird an den Stack zurückgegeben M[v, c]

Der Vorgang endet, wenn sowohl die Zeichenfolge als auch der Stapel die Endmarkierung (#) erreicht haben.

Beispiel

Analysieren wir den String "aabbaabcb":

Stapel	Linie	Aktion
S#	a abbaabcb$	S → wieS 1
a S1#	a abbaabcb$	Wechsel
S1#	a bbaabcb$	S 1 → AbBS 1
EIN bbs 1 #	a bbaabcb$	A → aA 1
a A 1 bBS 1 #	a bbaabcb$	Wechsel
Ein 1 bbs 1 #	b baabcb$	A1 → b
b bbs 1 #	b baabcb$	Wechsel
b BS 1#	b aabcb$	Wechsel
B S1#	a abc$	B→e
S1#	a abc$	S 1 → AbBS 1
EIN bbs 1 #	a abc$	A → aA 1
EIN bbs 1 #	a abc$	A → aA 1
a A 1 bBS 1 #	a abc$	Wechsel
Ein 1 bbs 1 #	a bcb$	A1 → ein
a bbs 1 #	a bcb$	Wechsel
b BS 1#	b cb$	Wechsel
B S1#	c b$	B → c
c S1#	c b$	Wechsel
S1#	b$	S 1 → AbBS 1
EIN bbs 1 #	b$	A→ε
b BS 1#	b$	Wechsel
B S1#	$	B→e
S1#	$	S1 → ε
#	$	bereit

Aufbau eines LR(k)-Analysators

Berechnung von k in LR(k)

Es gibt keinen Algorithmus, der es im allgemeinen Fall erlauben würde, k für eine beliebige Grammatik zu berechnen. Es lohnt sich normalerweise, einen LR(1)-Parser zu bauen. Wenn es höchstens eine Operation pro Satz hat (Shift, Reduce oder Accept), dann ist die Grammatik LR(0). Wenn jedoch beim Erstellen eines LR(1)-Parsers ein Konflikt und eine Kollision auftritt, dann ist diese Grammatik nicht LR(1) und es lohnt sich, zu versuchen, LR(2) zu erstellen. Wenn es fehlschlägt, es zu bauen, dann LR(3) und so weiter.

Abschluss der Grammatik

Lassen Sie uns eine neue Regel S" → S hinzufügen und S" zu einem Axiom der Grammatik machen. Diese zusätzliche Regel ist erforderlich, um zu bestimmen, wann der Analysator beendet wird und die Eingabekette zulässig ist. Die Zulassung erfolgt genau dann, wenn eine Faltung nach der Regel S → S" möglich ist.

Konstruktion eines kanonischen Systems von Mengen zulässiger LR(1)-Situationen

Am Anfang steht eine Menge I 0 mit der Konfiguration des Analysators S" → .S, $. Dann wird die Schließoperation auf diese Konfiguration angewendet, bis aufgrund ihrer Anwendung keine neuen Konfigurationen hinzugefügt werden. Als nächstes , Übergänge zu neuen Mengen werden konstruiert, indem der Punkt um ein Zeichen nach rechts verschoben wird (Sprünge werden von dem Zeichen ausgeführt, das vor dem Sprung hinter dem Punkt und nach dem Sprung davor war), und diejenigen Konfigurationen, die aus den vorhandenen erhalten wurden werden auf diese Weise zu diesen Mengen hinzugefügt, die Schließoperation wird auch auf sie angewendet, und der gesamte Vorgang wird wiederholt, bis keine neuen Mengen mehr erscheinen.

Beispiel

Konstruieren Sie ein kanonisches System von Mengen zulässiger LR(1)-Situationen für die angegebene Grammatik:

• S" → S
• S → AB
• A → Aa | ε
• B → cBc | d

Lösung:

• Wir bauen einen Abschluss für die Konfiguration S" → .S, $:
  • S → .ABA,$
• Für die resultierenden Konfigurationen (S → .ABA, $) bauen wir auch einen Abschluss:
  • A → .Aa, c
  • A → .Aa, d
  • A → .,c
  • A → ., d
• Für die resultierenden Konfigurationen (A → .Aa, c; A → .Aa, d) konstruieren wir auch einen Abschluss:
  • A → .Aa, a
  • A → ., ein
• Es können keine Konfigurationen mehr im I 0 -Zustand gebaut werden - der Abschluss ist gebaut

• Von I 0 aus können Sie Übergänge entlang S und A vornehmen und erhalten eine Reihe von Konfigurationen I 1 und I 2, die aus den folgenden Elementen bestehen:
  • I 1 = (S" → S., $)
  • I 2 = (S → A.BA, $; A → A.a, c; A → A.a, d; A → A.a, a)
• I 1 erfordert kein Schließen
• Konstruieren wir den Abschluss I 2:
  • B → .cBc, a
  • B → .cBc, $
  • B → .d, a
  • B → .d, $
• Alle anderen Sets sind ähnlich aufgebaut.

Erstellen der Parser-Tabelle

Der letzte Schritt beim Erstellen eines LR(1)-Parsers ist das Erstellen von Tabellen Aktion und gehe zu. Tisch Aktion gebaut für Eingabe-String-Zeichen, d.h. für Terminals und Zeilenende-Marker $, table gehe zu ist für Grammatiksymbole gebaut, d. h. für Terminals und Nicht-Terminals.

Erstellen einer Goto-Tabelle

Die Goto-Tabelle zeigt, in welchen Zustand zu gehen ist, wenn das nächste Grammatiksymbol angetroffen wird. Wenn es also im kanonischen Mengensystem einen Übergang von gibt ich ich in ich j durch Symbol A, dann in Goto( ich ich, A) wir setzen den Zustand ich j. Nachdem wir die Tabelle gefüllt haben, nehmen wir an, dass in allen leeren Zellen Goto( ich ich, A) = Fehler

Erstellen der Aktionstabelle

• Wenn es am Terminal a einen Übergang vom Zustand I i zum Zustand I j gibt, dann Action(I i , a) = Shift(I j)
• Wenn A ≠ S" und es eine Konfiguration A → α., a gibt, dann Action(I i , a) = Reduce(A → α)
• Für einen Zustand I i mit Konfiguration S" → S., $, Action(I i , $) = Akzeptieren
• Für alle leeren Zellen Action(I i , a) = Error

Beispiel

Erstellen Sie Aktions- und Goto-Tabellen für die Grammatik

• S" → S
• S → AB
• A → Aa | ε
• B → cBc | d

Lösung:

	Aktion				gehe zu
	a	c	d	$	S	S"	EIN	B	a	c	d
ich 0	Reduzieren (A → ε)	Reduzieren (A → ε)	Reduzieren (A → ε)		ich 1		ich 2
ich 1				annehmen
ich 2	Verschiebung (I 6)	Verschiebung (I 4)	Verschiebung (I 5)					ich 3	ich 6	ich 4	ich 5
ich 3	Reduzieren (A → ε)			Reduzieren (A → ε)			ich 13
ich 4		Verschiebung (I 8)	Verschiebung (I 9)					ich 7		ich 8	ich 9
ich 5	Reduzieren (B → d)			Reduzieren (B → d)
ich 6	Reduzieren (A → Aa)	Reduzieren (A → Aa)	Reduzieren (A → Aa)
ich 7		Verschiebung (I 10)								ich 10
ich 8		Verschiebung (I 8)	Verschiebung (I 9)					ich 11		ich 8	ich 9
ich 9		Reduzieren (B → d)
ich 10	Reduzieren (B → cBc)			Reduzieren (B → cBc)
ich 11		Verschiebung (I 12)								ich 12
ich 12		Reduzieren (B → cBc)
ich 13	Verschiebung (I 14)			Reduzieren (S → ABA)					ich 14
ich 14	Reduzieren (A → Aa)			Reduzieren (A → Aa)

Kettenanalyse

Bei jedem Schritt wird das oberste Zeichen gelesen v aus dem Analysatorstapel und nehmen Sie das letzte Zeichen c Eingangskette.

Wenn in der Tabelle der Aktionen an der Kreuzung v und c gelegen:

• Wechsel( ich k), dann auf den Stapel legen Mit und dann ich k. Dabei c aus der Schnur entfernt.
• Reduzieren( EIN → u), dann werden alle Terminal- und Nicht-Terminal-Symbole, aus denen die Kette besteht, von der Spitze des Stapels entfernt u, nach denen der Staat sucht Ich bin ganz oben bleiben. Laut Übergangstabelle an der Kreuzung Ich bin und EIN Finde den nächsten Zustand Ist. Danach wird A auf den Stapel geschoben, und dann Ist. Die Linie bleibt unverändert.
• Akzeptieren, dann ist das Parsen abgeschlossen
• Leere ist ein Fehler

Beispiel

Lassen Sie uns die Analyse der Zeichenfolge aaaccdcc erstellen:

Stapel	Linie	Aktion
ich 0	a aaccdcc$	Reduziere (A → ε), gehe zu I 2
Ich 0 A ich 2	a aaccdcc$	Verschiebung (I 6)
Ich 0 EIN Ich 2 ein ich 6	a accdc$	Reduziere (A → Aa), gehe zu I 2
Ich 0 A ich 2	a accdc$	Verschiebung (I 6)
Ich 0 EIN Ich 2 ein ich 6	a ccdcc$	Reduziere (A → Aa), gehe zu I 2
Ich 0 A ich 2	a ccdcc$	Verschiebung (I 6)
Ich 0 EIN Ich 2 ein ich 6	c cdcc$	Reduziere (A → Aa), gehe zu I 2
Ich 0 A ich 2	c cdcc$	Verschiebung (I 4)
I 0 EIN I 2 s ich 4	c dcc$	Verschiebung (I 8)
Ich 0 EIN Ich 2 c Ich 4 c ich 8	d cc$	Verschiebung (I 9)
Ich 0 EIN Ich 2 c Ich 4 c Ich 8 d ich 9	c c$	Reduziere (B → d), gehe zu I 11
Ich 0 A Ich 2 c Ich 4 c Ich 8 B ich 11	c c$	Verschiebung (I 12)
Ich 0 EIN Ich 2 c Ich 4 c Ich 8 B Ich 11 c ich 12	c$	Reduziere (B → cBc), gehe zu I 7
Ich 0 A Ich 2 c Ich 4 B ich 7	c$	Verschiebung (I 10)
Ich 0 EIN Ich 2 c Ich 4 B Ich 7 c ich 10	$	Reduziere (B → cBc), gehe zu I 3
Ich 0 A Ich 2 B ich 3	$	Reduziere (A → ε), gehe zu I 13
Ich 0 EIN Ich 2 B Ich 3 A ich 13	$	Reduziere (S → ABA), gehe zu I 1
Ich 0 S ich 1	$	annehmen

Übersetzung arithmetischer Ausdrücke (Seti-Ullman-Algorithmus)

Notiz. Der Code wird im Doggy-Style Motorola-like generiert, d.h.

Op Arg1, Arg2

steht für

Arg2 = Arg1 Op Arg2

Einen Baum bauen

Der Baum wird wie für einen arithmetischen Ausdruck üblich aufgebaut: An der Wurzel die Operation mit der niedrigsten Priorität, gefolgt von Operationen mit etwas höherer Priorität und so weiter. Klammern haben den höchsten Vorrang. Wenn es mehrere Operationen mit derselben Priorität gibt – a op b op c – dann wird der Baum wie für den Ausdruck (a op b) op c aufgebaut.

Beispiel

Erstellen Sie einen Baum für den Ausdruck a + b / (d + a − b × c / d − e) + c × d

Lösung: Wir schreiben den Ausdruck in das Formular

((a) + ((b) / ((((d) + (a)) − ((b) × (c)) / (d)) − (e)))) + ((c) × ( d))

Dann befindet sich an der Wurzel jedes Unterbaums eine Operation, und die Ausdrücke in Klammern links und rechts davon sind seine Unterbäume. Für den Teilausdruck ((b) × (c)) / (d) befindet sich beispielsweise die Operation „/“ an der Wurzel des entsprechenden Teilbaums, und die Teilausdrücke ((b) × (c)) und (d ) werden seine Unterbäume sein.

Baumstruktur (Berechnung der Registeranzahl)

• Wenn der Scheitelpunkt das linke Blatt ist (also eine Variable), dann markieren wir ihn mit Null.
• Wenn der Scheitelpunkt das rechte Blatt ist, markieren wir ihn mit einem
• Wenn wir beide seiner Teilbäume für einen Scheitelpunkt markieren, dann markieren wir ihn wie folgt:
  • Wenn die linken und rechten Teilbäume mit unterschiedlichen Nummern gekennzeichnet sind, wählen Sie die größte davon
  • Wenn der linke und der rechte Teilbaum mit denselben Nummern beschriftet sind, dann wird diesem Teilbaum eine Nummer zugeordnet, die um eins größer ist als diejenige, die die Teilbäume beschriftet

Blattmarkierungen	Baumstruktur mit identischen Teilbäumen	Der linke Teilbaum ist mit einer großen Zahl gekennzeichnet	Der rechte Teilbaum ist mit einer großen Zahl gekennzeichnet

Rechts - gleich wie ein Vorfahre.

Wenn das Etikett links Nachfahre mehr Etiketten Rechts, dann Rechts Kind wird Register zugeordnet einer noch als der Vorfahr, und links - gleich wie ein Vorfahre.

Der Code wird gebildet, indem der Baum wie folgt von unten nach oben durchlaufen wird:

1. Für den Scheitelpunkt mit dem Label 0 wird kein Code generiert

2. Oben Blatt X mit Etikett 1 und Register R ich, dann der Code

BEWEGE X, Ri

3. Wenn die Spitze intern ist mit Register R ich und sein linkes Kind ist Blatt X mit dem Label 0, dann entspricht es dem Code

<Код правого поддерева>OpX, Ri

4. Wenn Teilbäume eines Knotens mit Register R ich- nicht verlässt und das Label des rechten Eckpunkts größer oder gleich dem Label des linken Eckpunkts ist (der das Register Rj, j = i + 1 hat), dann entspricht der Code dem Eckpunkt

<Код Rechts Teilbaum><Код links Teilbäume > Op Rj, Ri

5. Wenn die Teilbäume des Knotens mit Register R ich- keine Blätter und das Label des rechten Scheitels (für das das Register Rj, j = i + 1) kleiner ist als das Label des linken, dann entspricht der Code dem Scheitel

Die Registerverteilung ist in der Grafik rechts dargestellt. Generierter Code:

MOVE d, R0 ;R0 = d MOVE c, R1 ;R1 = c MUL b, R1 ;R1 = (b × c) DIV R1, R0 ;R0 = (b × c) / d MOVE a, R1 ;R1 = a ADD d, R1 ;R1 = a + d SUB R1, R0 ;R0 = (a + d) − ((b × c) / d) MOVE e, R1 ;R1 = e SUB R0, R1 ;R1 = ((a + d) − ((b × c) / d)) − e MOVE R1, R0;R0 = ((a + d) − ((b × c) / d)) − e DIV b, R0 ;R0 = b / (((a + d) − ((b × c) / d)) − e) ADDiere a, R0 ;R0 = a + (b / (((a + d) − ((b × c) / d )) − e)) MOVE d, R1 ;R1 = d MUL c, R1 ;R1 = c × d ADD R0, R1 ;R1 = (a + (b / (((a + d) − ((b × c ) / d)) − e))) + (c × d) MOVE R1, R0;R0 = (a + (b / (((a + d) − ((b × c) / d)) − e) )) + (c × d)

Übersetzung logischer Ausdrücke

Dieser Abschnitt zeigt, wie Sie Code für die verzögerte Auswertung von booleschen Ausdrücken generieren. Als Ergebnis des Algorithmus wird ein Codestück erhalten, das unter Verwendung der Operationen TST, BNE, BEQ einen logischen Ausdruck berechnet, indem es zu einem der Labels wechselt: TRUELAB oder FALSELAB.

Einen Baum bauen

Der Baum eines logischen Ausdrucks spiegelt die Reihenfolge wider, in der er entsprechend der Priorität der Operationen ausgewertet wird, d. h. um den Wert eines Baumknotens auszuwerten (was eine Operation an zwei Operanden ist, die Teilbäume des Knotens sind), müssen wir Berechnen Sie zuerst die Werte seiner Teilbäume.

Betriebspriorität: Der NOT-Operator hat die höchste Priorität, gefolgt von AND und dann OR. Wenn andere logische Operationen im Ausdruck verwendet werden, müssen sie durch diese drei auf eine bestimmte Weise ausgedrückt werden (normalerweise gibt es keine anderen Operationen und eine Ausdrucksumwandlung ist nicht erforderlich). Die Assoziativität für Operationen gleicher Priorität erfolgt von links nach rechts, d. h. A und B und C werden als (A und B) und C behandelt

Beispiel

Konstruieren Sie einen Baum für den logischen Ausdruck nicht A oder B und C und (B oder nicht C).

Lösung: siehe Diagramm rechts.

Für jeden Knoten des Baums werden 4 Attribute berechnet:

• Knotennummer
• Das Label, zu dem gesprungen werden soll, wenn der Ausdruck im Knoten falsch ist (false label, fl)
• Das Label, zu dem gesprungen werden soll, wenn der Ausdruck im Knoten wahr ist (true label, tl)
• Label-Sign (Schild) (für weitere Details siehe unten)

Knoten werden in zufälliger Reihenfolge nummeriert, die einzige Bedingung ist die Eindeutigkeit der Knotennummern.

Das Baumlayout erfolgt wie folgt:

• fl gibt die Nummer des Knotens an, zu dem der Übergang erfolgt, oder falselab, wenn dieser Knoten falsch ist
• tl gibt die Nummer des Knotens an, zu dem der Übergang erfolgt, oder truelab, wenn dieser Knoten wahr ist

Vorzeichen gibt an, in welchem ​​Fall die Auswertung des aktuellen Teilbaums abgebrochen werden kann.

Für die Baumwurzel gilt: fl=falselab, tl=truelab, sign=false.

Auf diese Weise:

Beispiel

Markieren Sie den Baum, der für den logischen Ausdruck nicht A oder B und C und (B oder nicht C) erstellt wurde.

Codegenerierung

Im generierten Code verwendete Maschinenbefehle:

• TST - Überprüfen des Arguments auf Wahrheit und Setzen eines Flags, wenn das Argument falsch ist
• BNE - Auf das Label springen, wenn das Flag nicht gesetzt ist, also die Bedingung mit TST geprüft wird Stimmt
• BEQ - Auf das Label springen, wenn das Flag gesetzt ist, also die Bedingung mit TST geprüft wird FALSCH

Der Code ist wie folgt aufgebaut:

• der Baum wird von der Wurzel aus durchlaufen, bei UND und ODER wird zuerst der linke Teilbaum durchlaufen, dann der rechte
• für jeden passierten Scheitelpunkt wird seine Nummer (Etikett) gedruckt
• für Blatt A (Nummer, tl, fl, Zeichen) wird TST A gedruckt
  • wenn sign == true, wird BNE tl ausgegeben
  • wenn sign == false, wird BEQ fl ausgegeben

Beispiel

Für den obigen Ausdruck wird der folgende Code generiert:

1:2:4: TST A BEQ TRUELAB 3:5:7: TST B BEQ FALSELAB 8: TST C BEQ FALSELAB 6:9: TST B BNE TRUELAB 10:11: TST C BNE FALSELAB TRUELAB: FALSELAB:

Beispiel-Matching-Methode

Die Idee der Methode ist, dass für denselben Programmabschnitt der Code auf unterschiedliche Weise generiert werden kann und dadurch eine Optimierung für den einen oder anderen Parameter erreicht werden kann.

Formulierung des Problems

Es gibt viele Beispiele, von denen jedes durch einen Teil der Zwischendarstellung, für die es anwendbar ist, das Gewicht und den generierten Code definiert ist. Es gibt einen Zwischendarstellungsbaum, der ein Fragment des Programms ist, für das Code generiert werden muss. Ziel ist es, eine solche Bedeckung des Zwischenrepräsentationsbaums mit Samples so aufzubauen, dass das Gesamtgewicht der Samples minimal ist.

Muster sind Bauanleitungen und die ihnen entsprechenden Parse-Bäume. Für jeden Abtastwert ist seine Ausführungszeit (in Zyklen) bekannt. Mit ihrer Hilfe generieren wir den optimalen (in Bezug auf die Ausführungszeit) Code.

Musterbeispiele

Aufbau einer Zwischendarstellung

Zuerst erstellen wir einen Analysebaum für den gesamten Ausdruck.

Aufbau einer Abdeckung

Nun generieren wir für jeden Scheitelpunkt (wir gehen sie in der Reihenfolge von den Blättern bis zur Wurzel durch) den optimalen Code für seinen Teilbaum. Dazu gehen wir einfach alle Proben durch, die an einem bestimmten Scheitelpunkt anwendbar sind. Die Ausführungszeit bei Verwendung eines bestimmten Musters ist die Summe aus der Zeit, die benötigt wird, um seine Argumente auszuwerten (und wir kennen bereits den optimalen Code für ihre Berechnung dank der Baumtraversierungsreihenfolge) und der Ausführungszeit des Musters selbst. Von allen erhaltenen Optionen wählen wir die beste aus – es wird der optimale Code für den Unterbaum dieses Knotens sein. An der Wurzel des Baums erhalten wir den optimalen Code für den gesamten Ausdruck.

Codegenerierung

Es ist nicht erforderlich, den Code für alle Scheitelpunkte aufzuschreiben – es reicht aus, die erforderliche Mindestzeit und das zu verwendende Beispiel aufzuschreiben. Alles andere davon lässt sich leicht wiederherstellen.

Wir haben unendlich viele Register in diesen Problemen, sodass Sie jedes Mal ein neues verwenden können.

Bau von Wohnmobilen nach EDA

Aufbau des NFA nach der rechtslinearen Grammatik

Grammatik-Casting

Um eine beliebige COP-Grammatik in die reduzierte Form umzuwandeln, müssen Sie die folgenden Schritte ausführen:

• entferne alle unfruchtbaren Zeichen;
• alle unerreichbaren Zeichen entfernen;

Unnütze Zeichen entfernen

Eingang: COP-Grammatik G = (T, N, P, S).

Ausgang: Eine COP-Grammatik G' = (T, N', P', S), die keine unfruchtbaren Symbole enthält, für die L(G) = L(G').

Methode:

Baue rekursiv Mengen N 0 , N 1 , ...

1. N0 = ∅, ich = 1.
2. N. ich = (A | (A → α) ∈ P und α ∈ (N. ich - 1 ∪ T)*) ∪ N. ich-1 .
3. Wenn N i ≠ N i – 1, dann i = i + 1 und gehe zu Schritt 2, andernfalls N’ = N i ; P' besteht aus Regeln der Menge P, die nur Symbole aus N' ∪ T enthält; G' = (T, N', P', S).

Definition: ein Symbol x ∈ (T ∪ N) heißt unerreichbar in einer Grammatik G = (T, N, P, S), wenn es in keiner Satzform dieser Grammatik vorkommt.

Beispiel

Unnötige Zeichen aus der Grammatik entfernen G((A, B, C, D, E, F, S), (a, b, c, d, e, f, g), P, S)

• S → AcDe | CaDbCe | Saca | aCb | dFg
• A → SeAd | cSA
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb | aAc | cfF
• D→fCE | ac | dEdAS | ε
• E→ESacD | aec | eFF

Lösung

• N0 = ∅
• N 1 = (B (B → bfg) , D (D → ac) , E (E → aec) )
• N2 = (B, D, E, C (C → Ebd))
• N 3 = (B, D, E, C, S (S → aCb) )
• N 4 \u003d (B, D, E, C, S) \u003d N 3

G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | aec

Nicht erreichbare Zeichen entfernen

Eingang: COP-Grammatik G = (T, N, P, S)

Ausgang: Eine COP-Grammatik G' = (T', N', P', S), die keine unerreichbaren Symbole enthält, für die L(G) = L(G').

Methode:

1. V0 = (S); ich = 1.
2. V ich = (x | x ∈ (T ∪ N), (A → αxβ) ∈ P und A ∈ V ich - 1 ) ∪ V ich-1 .
3. Wenn V i ≠ V i - 1 , dann i = i + 1 und gehe zu Schritt 2, andernfalls N’ = V i ∩ N; T' = V ich ∩ T; P' besteht aus den Regeln der Menge P, die nur Symbole von V i enthält; G' = (T', N', P', S).

Definition: Eine COP-Grammatik G heißt reduziert, wenn sie keine unerreichbaren und sterilen Symbole enthält.

Beispiel

Nicht erreichbare Zeichen aus Grammatik entfernen G"((B, C, D, E, S), (a, b, c, d, e, f, g), P", S)

• S → CaDbCe | Saca | aCb
• B → CaBd | aDBc | BSC | bfg
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | aec

Lösung

• V0 = (S)
• V 1 = (S, C (S → CaDbCe) , D (S → CaDbCe) , a (S → CaDbCe) , b (S → CaDbCe) , e (S → CaDbCe) )
• V 2 = (S, C, D, a, b, e, E (C → Ebd) , d (C → Ebd) , f (D → fCE) )
• V 3 = (S, C, D, E, a, b, d, e, f, c (E → ESacD) )
• V 4 \u003d (S, C, D, E, a, b, d, e, f, c) \u003d V 3

G""((C, D, E, S), (a, b, c, d, e, f), P"", S)

• S → CaDbCe | Saca | aCb
• C→Ebd | Seb
• D→fCE | ac | ε
• E→ESacD | aec

Bequemer ist es, den Wortschatz einer Sprache in Form von regulären Ausdrücken zu beschreiben und eine Sprache mit Hilfe von KA zu erkennen. Daher ist es wichtig, Sprachdefinitionen in Form von regulären Ausdrücken in eine Definition in Form eines FA umwandeln zu können. Eine solche Transformation wurde von Kennet Thompson vorgeschlagen.

Die Zustandsmaschine ist eine Fünf (S, S, d, S 0 , F)

S ist eine endliche Menge von Zuständen.

S ist eine endliche Menge gültiger Eingangssignale.

d - Übergangsfunktion. Sie spiegelt die Menge Sx(SÈ(e)) in die Menge der Zustände eines nichtdeterministischen endlichen Automaten. Für einen deterministischen Automaten spiegelt die Übergangsfunktion die Menge SxS in die Menge der Zustände des Automaten wider. Mit anderen Worten bestimmt d abhängig vom Zustand und dem Eingabesymbol den neuen Zustand des Automaten.

S 0 - Anfangszustand des endlichen Automaten, S 0 О S.

F ist die Menge der Endzustände des Automaten, F О S.

Der Betrieb einer Zustandsmaschine ist eine Abfolge von Schritten. Der Schritt wird durch den Zustand des Automaten und das Eingabesymbol bestimmt. Der Schritt selbst besteht darin, den Zustand des Automaten zu ändern und das nächste Symbol der Eingabesequenz zu lesen.

Es gibt die folgenden Regeln zum Konvertieren von regulären Ausdrücken in einen Zustandsautomaten.

1 Der reguläre Ausdruck „e“ wird in einen Automaten aus zwei Zuständen und einem e-Übergang zwischen ihnen transformiert (Abbildung 1).

Abbildung 1. - Automat für den elektronischen Übergang

2 Ein regulärer Ausdruck aus einem Zeichen „a“ wird in eine endliche Zustandsmaschine aus zwei Zuständen und einem Übergang zwischen ihnen gemäß dem Eingangssignal a umgewandelt (Abbildung 2).

Abbildung 2. - Automat zum Springen nach Symbol a

3 Es gebe einen regulären Ausdruck rs und endliche Automaten für den Ausdruck r und den Ausdruck s wurden bereits gebaut. Dann werden die beiden Automaten in Reihe geschaltet. Abbildung 3 zeigt die anfänglichen Automaten für die Sprachen r und s. Die Abbildung zeigt einen Automaten zum Erkennen der Verkettung dieser Sprachen.

Automatisch für r Automatisch für s

Abbildung 3. - Anfängliche Automaten

Abbildung 4. - Maschine zum Verketten von Sprachen

4 Es gebe einen regulären Ausdruck r | s und endliche Automaten wurden bereits für den Ausdruck r und den Ausdruck s gebaut (Abbildung 3). Dann muss es in dem resultierenden Automaten eine Alternative geben, einen der beiden Automaten auszuführen. Das heißt, der Automat für den Ausdruck r | s für Automaten für r und s aus Abbildung 3 hat die in Abbildung 5 gezeigte Form.

Abbildung 5. - Maschine zum Kombinieren von Sprachen

5 Es gebe einen regulären Ausdruck r* mit dem konstruierten endlichen Automaten r. Dabei werden zwei neue Zustände für die Möglichkeit der Umgehung des Automaten des Ausdrucks r eingeführt, und es wird auch ein e-Übergang zwischen End- und Anfangszustand für die Möglichkeit der wiederholten Wiederholung des Automaten r eingeführt. Baut man für den regulären Ausdruck r einen Automaten ähnlich wie in Abbildung 3, so entspricht der in Abbildung 6 gezeigte endliche Automat dem regulären Ausdruck r*.

Einstellungen

Gemäß dem Satz von Kleene kann jeder reguläre Ausdruck einem endlichen Automaten zugeordnet werden, der ein formales Modell des Algorithmus zum Erkennen von Lexemen ist, die durch diesen regulären Ausdruck bezeichnet werden. Allgemein ausgedrückt ist ein endlicher Automatenerkenner durch einen endlichen Satz von Eingabestromzuständen definiert, die für ihn und Übergänge zwischen ihnen charakteristisch sind. Ein Zustandswechsel tritt auf, wenn die Zeichen des Eingabestroms aus dem gegebenen Alphabet gemäß der Übergangsfunktion empfangen werden, die die möglichen nachfolgenden Zustände aus dem Eingabezeichen und dem aktuellen Zustand bestimmt. Unter den möglichen Zuständen werden der Anfangszustand (Anfangszustand) und der Endzustand (Zulassungszustand) unterschieden, in denen sich der endliche Automaten-Erkenner jeweils zu Beginn und am Ende der Verarbeitung von Tokens des Eingangsstroms befinden kann. Wenn die eingegebene Folge von Zeichen eine Folge von Übergängen erzeugen kann, die den endlichen Automaten vom Anfangszustand in einen der Endzustände überführen kann, wird er als zulassend betrachtet und gehört zu der regulären Menge, die er erkennt.

(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*

Tabelle 1

	0	1
Q1	Q4	Q2
Q2	Q3	Q1
Q3	Q2	Q4
Q4	Q1	Q3

Die Spalten der Übergangstabelle stellen die Zeichen des Eingabealphabets dar, und die Zeilen entsprechen den aktuellen Zuständen des DFA. Die Elemente jeder Zeile geben die Zustände des DFA an, in die er vom aktuellen Zustand übergehen sollte, wenn er die entsprechenden Zeichen des Eingabealphabets empfängt. Insbesondere folgt aus der ersten Zeile dieser Übergangstabelle, dass das Empfangen der Symbole 0 und 1 im Anfangszustand Q1 den DFA in die Zustände Q4 bzw. Q2 überträgt.

Beim Erkennen der Eingabesequenz aus der Übergangstabelle ist es einfach, die Änderungen im Zustand des DFA zu verfolgen, um festzustellen, ob einer der akzeptierenden Zustände erreicht ist oder nicht. Insbesondere für einen binären Vektor 01001000 mit einer geraden Anzahl von Nullen und Einsen erzeugt der betrachtete DFA die folgende Folge von Übergängen, wobei jeder Übergang mit dem Zeichen des Eingabealphabets gekennzeichnet ist, das ihn aufruft:

Q1 0 Q4 1 Q3 0 Q2 0 Q3 1 Q4 1 Q1 0 Q4 0 Q1

Diese Folge von Übergängen endet mit dem akzeptierenden Zustand Q1, daher gehört der binäre Vektor 01001000 zu der regulären Menge, die von dem betrachteten DFA erkannt wird, und erfüllt den obigen regulären Ausdruck.

Abschließend ist festzuhalten, dass die betrachtete informelle Bauweise

Reguläre Ausdrücke (REs) sind eine sehr bequeme Form, sogenannte reguläre oder automatische Sprachen zu schreiben. Daher wird RT in vielen Systemen, die Ketten verarbeiten, als Eingabesprache verwendet. Betrachten Sie Beispiele für solche Systeme:

• Der Unix-Befehl grep oder ähnliche Befehle zum Suchen nach Zeichenfolgen, wie sie in Webbrowsern oder Textformatierungssystemen zu finden sind. In solchen Systemen werden REs verwendet, um Muster zu beschreiben, nach denen der Benutzer in einer Datei sucht. Verschiedene Suchmaschinen wandeln die RT entweder in eine deterministische endliche Zustandsmaschine (DFA) oder eine nicht-deterministische endliche Zustandsmaschine (NFA) um und wenden diese Zustandsmaschine auf die zu durchsuchende Datei an.
• Lexikalische Analysegeneratoren. Lexikalische Analysatoren sind Bestandteil des Compilers, sie zerlegen das Quellprogramm in logische Einheiten (Token), die aus einem oder mehreren Zeichen bestehen und eine bestimmte Bedeutung haben können. Der lexikalische Analysegenerator nimmt die formalen Beschreibungen der Token, die im Wesentlichen RTs sind, und erstellt einen DFA, der erkennt, welcher Token in seiner Eingabe erscheint.
• RT in Programmiersprachen.

In diesem Artikel werden wir uns zuerst mit endlichen Automaten und ihren Typen (DFA und NFA) vertraut machen und dann ein Beispiel für den Aufbau eines minimalen DFA unter Verwendung eines regulären Ausdrucks betrachten.

Zustandsmaschinen

Ein endlicher Automat (FA) ist ein Konverter, der es Ihnen ermöglicht, eine Eingabe mit einer entsprechenden Ausgabe zu verknüpfen, und diese Ausgabe kann nicht nur von der aktuellen Eingabe abhängen, sondern auch von dem, was vorher passiert ist, von der Vorgeschichte des endlichen Automaten. Auch menschliches Verhalten und nicht nur künstliche Systeme lassen sich mit CA beschreiben. Mit KA kann man nicht nur das Verhalten künstlicher Systeme beschreiben, sondern sogar menschliches Verhalten. Ihre Reaktion zum Beispiel darauf, dass Ihr Nachbar nachts laute Musik hört, wird nach dem ersten solchen Vorfall eins sein und nach mehreren solchen Vorfällen ganz anders sein. Es kann unendlich viele solcher Hintergrundgeschichten geben, stellt sich die Frage; Welche Art von Gedächtnis sollte ein Raumschiff haben, um sich für jede Vorbereitung anders zu verhalten? Es ist klar, dass es nicht möglich ist, unendlich viele Vorgeschichten zu speichern. Daher teilt der Automat sozusagen alle mögliche Vorgeschichte in Äquivalenzklassen ein. Zwei Historien sind äquivalent, wenn sie das Verhalten des Automaten in der Zukunft gleichermaßen beeinflussen. Die Äquivalenzklasse, der der Automat seine aktuelle Geschichte zuschreibt, wird auch als interner Zustand des Automaten bezeichnet.

Sehen wir uns nun an, wie CA angegeben werden kann. Sie können in Form von Grafiken oder in Form von Steuertabellen angegeben werden. In Form einer Grafik wird der KA wie folgt angegeben:

• die Eckpunkte des Graphen entsprechen den Zuständen der CA.
• gerichtete Kanten entsprechen Übergangsfunktionen (in der Nähe jeder solchen Kante ist das Symbol angegeben, entlang dem der Übergang durchgeführt wird).
• Ein Knoten mit einer eintretenden Kante, die nicht mehr als einen Zustand hinterlässt, entspricht dem Anfangszustand.
• die Endzustände der CA sind mit einer fetten Umrandung gekennzeichnet.

In Form einer Steuertabelle wie folgt:

• KA-Zustände befinden sich in den Zeilen der Tabelle.
• Zeichen der erkannten Sprache - in Spalten.
• an der kreuzung ist der zustand angegeben, der von dem angegebenen zustand durch das angegebene symbol erreicht werden kann.

Ein Beispiel für KA in Form eines Diagramms und in Form einer Kontrolltabelle wird unten präsentiert.

DKA und NKA

Der Hauptunterschied zwischen einem DFA und einem NFA besteht darin, dass sich der DFA während des Betriebs nur in einem Zustand befinden kann, während sich der NFA gleichzeitig in mehreren Zuständen befinden kann. Als Beispiel für die Arbeit der NCA kann man die Idee des amerikanischen Physikers Hugh Everett anführen, dass jedes Ereignis die Welt in mehrere Welten zerlegt, in denen dieses Ereignis jeweils auf seine eigene Weise endete. Zum Beispiel hat Hitler in einer Welt die 2. Welt gewonnen. Krieg, in einem anderen - Newton ging ins Geschäft statt in die Physik und die Entdeckung der Gesetze der klassischen Mechanik musste um 50 Jahre verschoben werden.Um irgendwelche Schlüsse aus der Funktionsweise der Maschine zu ziehen, sollte man alle "Welten" studieren. Nachdem die gesamte Eingabekette gelesen wurde, gehen wir davon aus, dass die NFA diese Kette akzeptiert, wenn sie in mindestens einer der vielen "Welten" die Arbeit in einem akzeptierenden Zustand abgeschlossen hat. Dementsprechend weist der Automat die Sprosse zurück, wenn sie in jeder "Welt" in einem nicht akzeptablen Zustand endet. Der DFA hingegen akzeptiert einen String, dies ist offensichtlich, wenn er sich nach dem Lesen des gesamten Eingabestrings in einem akzeptierenden Zustand befindet.

In den meisten Fällen ist das Erstellen eines NFA viel einfacher als das Erstellen eines DFA. Trotzdem ist die Verwendung von NFA zur Modellierung keine gute Idee. Glücklicherweise ist es möglich, für jeden NFA einen DFA zu erstellen, der dieselbe Eingabesprache akzeptiert. In diesem Artikel stellen wir keinen Algorithmus zum Konstruieren eines DFA aus einem NFA vor, sondern betrachten diesen Algorithmus anhand eines nachstehenden visuellen Beispiels.

Erstellen eines minimalen DFA aus einem regulären Ausdruck

Hier ist zunächst die in diesem Artikel verwendete RW-Syntax:

• Verkettung wird mit einem Leerzeichen oder einer leeren Zeichenfolge angegeben (z. B.: ab)
• Union, mit dem Symbol "|"
• Iteration (Kleene-Abschluss), mit "*"-Symbol

Betrachten Sie ein Beispiel mit einem regulären Ausdruck:

xy* (x | y*) | ab (x | y*) | (x | a*) (x | y*)

Es ist notwendig, einen minimalen DFA aus einem regulären Ausdruck zu erstellen und die Erkennung einer korrekten und einer falschen Zeichenfolge zu demonstrieren.

Zunächst vereinfachen wir diese RT, indem wir das rechtsseitige Distributivgesetz der Verkettung in Bezug auf die Vereinigung verwenden, und erhalten die folgende RT:

(xy* | ab | (x | a*)) (x | y*)

Jetzt bauen wir einen Automaten für dieses Wohnmobil:

Gemäß der Verkettungstransformationsregel (wir werden die Regeln für die Transformation von RV in KA nicht angeben, da sie ziemlich offensichtlich sind) erhalten wir den folgenden Automaten:

Nach der Unions-Transformationsregel:

Gemäß der Verkettungstransformationsregel:

Und am Ende wenden wir die Schließungstransformationsregel an und erhalten εNCA:

Wir beseitigen ε-Übergänge („Sternchen“ bezeichnet Endzustände):

In diesem NFA sind die Zustände s3 und s5 äquivalent, da δ(s3, x) = δ(s5, x) = s1 und δ(s3, y) = δ(s5, y) = s5, s7. Zustände umbenennen s6 -> s5 und s7 -> s6:

Wir bauen DFA nach NFA:

In diesem DEA sind die Zustände p1 und p5 äquivalent, da
δ(p1, x) = δ(p5, x) = p4 und δ(p1, y) = δ(p5, y) = p5. Benennen Sie die Zustände p6 -> p5 und p7 -> p6 um:

Dieser Automat ist der minimale DFA.

Sei δ die Übergangsfunktion, dann wird die aus δ konstruierte erweiterte Übergangsfunktion mit δ' bezeichnet, und ω ist die Eingabezeichenfolge.

Sei die Kette ω = aaax eingegeben, wir erwarten, dass sich der Automat in einem der akzeptierenden Zustände befindet.

δ'(p0, ε) = p0
δ'(p0, a) = δ(δ'(p0, ε), a) = δ(p0, a) = p3
δ'(p0, aa) = δ(δ'(p0, a), a) = δ(p3, a) = p5
δ'(p0, aaa) = δ(δ'(p0, aa), a) = δ(p5, a) = p5
δ'(p0, aaax) = δ(δ'(p0, aaa), a) = δ(p5, a) = p4

p4 ist ein gültiger Endzustand, also ist die Zeichenkette aaax für diesen Automaten gültig.

Nehmen wir nun an, dass ω = xyyb:

δ'(p0, ε) = p0
δ'(p0, x) = δ(δ'(p0, ε), x) = δ(p0, x) = p1
δ'(p0, xy) = δ(δ'(p0, x), y) = δ(p1, y) = p1
δ'(p0, xyy) = δ(δ'(p0, xy), y) = δ(p1, y) = p1
δ'(p0, xyyb) = δ(δ'(p0, xyy), b) = δ(p1, b) = ∅

Hier sehen wir, dass wenn das Symbol b in den Automaten eingegeben wird, wenn er sich im Zustand p1 befindet, dieser Automat sterben wird, daher ist die Kette xyyb falsch.

P. S. In diesem Artikel wurde der Algorithmus zum Erstellen eines DFA durch RT betrachtet, aber es gibt bequemere Algorithmen, insbesondere für die Programmierung, aber dies ist ein Thema für einen anderen Artikel ...

Für das weitere Studium der Eigenschaften endlicher Automaten und insbesondere für die Lösung des Syntheseproblems ist der folgende Satz wichtig.

Satz 7.7 (Determinationssatz). Für jeden endlichen Automaten kann ein äquivalenter deterministischer endlicher Automat konstruiert werden.

Um den Satz zu beweisen, ist es zunächst notwendig, den Algorithmus zur Konstruktion eines deterministischen endlichen Automaten aus dem ursprünglichen zu beschreiben; Zweitens rechtfertigen Sie diesen Algorithmus, indem Sie rigoros beweisen, dass er tatsächlich einen endlichen Automaten liefert, der deterministisch und dem ursprünglichen äquivalent ist. Hier stellen wir nur den Algorithmus zur Konstruktion eines deterministischen Automaten vor.

Die Transformation eines beliebigen endlichen Automaten in einen äquivalenten deterministischen erfolgt in zwei Schritten: Zuerst werden die Bögen mit der Bezeichnung λ entfernt, dann erfolgt die eigentliche Bestimmung.

1. Entfernung von λ-Übergängen (mit \lambda bezeichnete Bögen).

Um sich von der ursprünglichen Zustandsmaschine zu entfernen M=(V,Q,q_0,F,\delta) zum äquivalenten endlichen Automaten M"=(V,Q",q_0,F",\delta") ohne λ-Übergänge genügt es, die folgenden Transformationen im ursprünglichen Graphen M durchzuführen.

a. Alle Zustände außer dem Anfangszustand, in die nur die mit λ bezeichneten Bögen eintreten, werden entfernt; dies definiert die Menge Q" des endlichen Automaten M" . Es ist klar, dass Q"\subseteq Q . In diesem Fall nehmen wir an, dass der Anfangszustand gleich bleibt.

b. Die Menge der Bögen des endlichen Automaten M" und ihrer Labels (also der Übergangsfunktion M" ) ist wie folgt definiert: für zwei beliebige Zustände p,r\in Q",~ p\to_(a)r gilt genau dann, wenn a\in V , und im Graphen M gilt: Entweder existiert ein Bogen von p nach r, dessen Label das Symbol a enthält, oder es existiert ein Zustand q, so dass p\Rightarrow_(\lambda)^(+)q und q\to_(a)r . In diesem Fall darf die Ecke q allgemein gesprochen nicht zur Menge Q " gehören, d.h. beim Übergang zum Automaten M verschwinden" (Abb. 7.11). Wenn aber q\in Q" ist, dann bleibt natürlich der Bogen (q,r) in M" erhalten und das Symbol a wird eines der Symbole sein, die zum Label dieses Bogens gehören (Abb. 7.12).

In M" sind also alle Bögen M gespeichert, deren Label von λ verschieden sind und die ein Paar (Knoten) von Zuständen aus der Menge Q" (nicht entfernt nach Punkt a) verbinden. Außerdem gibt es für jedes Tripel von Zuständen p,q,r (nicht notwendigerweise verschieden!), so dass p,r\in Q" und einen von Null verschiedenen Weg von p nach q gibt, dessen Label gleich λ ist (also der Weg durch λ-Übergänge), und von q nach r führt ein Bogen, dessen Label das Zeichen a des Eingabealphabets enthält, in M" wird ein Bogen von p nach r konstruiert, dessen Label enthält das Symbol a (siehe Abb. 7.11).

in. Die Menge der Endzustände F" des endlichen Automaten M" enthält alle Zustände q\in Q" , also die Zustände des endlichen Automaten M, die nicht nach Punkt a gelöscht werden, für die q\Rightarrow_(\lambda)^(\ast)q_f für ein q_f\in F (d. h. entweder ist der Zustand q selbst der Endzustand des endlichen Automaten M, oder von ihm führt ein Pfad ungleich Null entlang der mit λ bezeichneten Bögen zu einem der Endzustände des endlichen Automaten M ) (Abb. 7.13).

2. Eigentlich Bestimmung.

Lassen M=(Q,V,q_0,F,\delta) ist ein endlicher Automat ohne λ-Übergänge. Konstruieren wir einen äquivalenten deterministischen endlichen Automaten M_1 .

Dieser endliche Automat ist so definiert, dass seine Zustandsmenge die Menge aller Teilmengen der Zustandsmenge des endlichen Automaten M ist. Das bedeutet, dass jeder einzelne Zustand des endlichen Automaten M_1 als eine Teilmenge der Menge von Zuständen des endlichen Automaten M definiert ist. In diesem Fall ist der Anfangszustand des neuen endlichen Automaten (d. h. M_1 ) eine Singleton-Teilmenge, die den Anfangszustand des alten endlichen Automaten (d. h. M ) enthält, und die Endzustände des neuen endlichen Automaten sind alle solche Teilmengen Q, die enthalten mindestens ein letztes die Spitze des ursprünglichen endlichen Automaten M .

Von nun an werden wir mit einiger Redefreiheit manchmal die Zustände des endlichen Automaten M_1 Zustandsmengen nennen. Es ist jedoch wichtig, klar zu verstehen, dass jede solche Zustandsmenge ein separater Zustand des neuen endlichen Automaten ist, aber keine Menge seiner Zustände. Gleichzeitig ist dies für den ursprünglichen ("alten") endlichen Automaten M genau die Menge seiner Zustände. Bildlich gesprochen wird jede Teilmenge von Zuständen des alten endlichen Automaten in einen Zustand des neuen endlichen Automaten "kollabiert"*.

* Formal sollte die Menge Q_1 als eine Menge definiert werden, die in einer Eins-zu-Eins-Korrespondenz mit der Menge 2^Q steht, aber es ist immer noch bequemer zu berücksichtigen, dass Q_1 mit 2^Q zusammenfällt, weil die Menge von Zuständen eines endlichen Automaten kann jede nicht leere endliche Menge sein.

Die Übergangsfunktion des neuen endlichen Automaten ist so definiert, dass von der Zustandsmenge S durch das Eingabesymbol a der endliche Automat M_1 in die Zustandsmenge, die die Vereinigung aller Zustandsmengen des alten endlichen Automaten ist, übergeht die dieser alte endliche Automat am Symbol a von jeder Zustandsmenge S vorbeiführt. Somit ist der endliche Automat M_1 per Konstruktion deterministisch.

Die obige verbale Beschreibung lässt sich wie folgt in Formeln übersetzen: Wir bauen den Zustandsautomaten M_1 so auf

M_1=(Q_1,V,\(q_0\),F_1,\delta_1), wo

\begin(cases)Q_1=2^Q,\quad F_1=\(T\colon\, T\cap F\ne\varnothing,~T\in2^Q\),\\ (\forall S\subseteq Q) (\forall a\in V)\Bigl(\delta_1(S,a)= \bigcup\limits_(q\in S)\delta(q,a)\Bigr). \end(Fälle)

Beachten wir, dass es unter den Zuständen des neuen endlichen Automaten einen Zustand \varnothing gibt, und nach (7.8) \delta_1(\varnothing,a)=\varnothing für jedes Eingabezeichen a . Dies bedeutet, dass die Zustandsmaschine M_1, wenn sie einmal in einem solchen Zustand ist, diesen nicht verlässt. Allgemein wird jeder Zustand q eines endlichen Automaten, so dass für jedes Eingabesymbol a \delta(q,a)=q gilt, ein absorbierender Zustand des endlichen Automaten genannt. Somit ist der Zustand \varnothing der deterministischen Zustandsmaschine M_1 absorbierend. Es ist auch nützlich, dies zu beachten \delta_1(S,a)=\varnothing genau dann, wenn für jedes q\in S (Zustände des alten endlichen Automaten aus der Menge der Zustände S ) \delta(q,a)=\varnothing, d.h. im Graphen M hinterlässt jeder solche Zustand q keinen Bogen, der mit dem Symbol a markiert ist.

Es kann bewiesen werden, dass der durch einen solchen Algorithmus erhaltene endliche Automat dem ursprünglichen äquivalent ist.

Beispiel 7.9. Wir bestimmen den in Abb. 7.14.

Ein äquivalenter endlicher Automat ohne λ-Übergänge ist in Abb. 2 dargestellt. 7.15. Beachten Sie, dass der Scheitelpunkt q_2 verschwindet, da nur "leere" Bögen hineinkommen.

Um den resultierenden Automaten zu bestimmen, ist es absolut nicht notwendig, alle seine 2^3=8 Zustände aufzuschreiben, von denen viele möglicherweise nicht vom Anfangszustand \(q_0\) aus erreichbar sind. Um von \(q_0\) erreichbare Zustände zu erhalten, und nur von ihnen, verwenden wir die sogenannte Ziehmethode.

Dieses Verfahren kann im allgemeinen Fall wie folgt beschrieben werden.

Im ursprünglichen endlichen Automaten (ohne leere Bögen) definieren wir alle Mengen von Zuständen, die vom Anfangszustand aus erreichbar sind, d.h. für jedes Eingabezeichen a finden wir die Menge \delta(q_0,a) . Jede solche Menge im neuen Automaten ist ein Zustand, auf den direkt vom Anfangszustand aus zugegriffen werden kann.

Für jede der definierten Zustandsmengen S und jedes Eingabesymbol a finden wir die Menge \textstyle(\mathop(\bigcup\limits_(q\in S) \delta(q,a))\limits^(\phantom(A)^(.))). Alle in diesem Schritt erhaltenen Zustände sind die Zustände eines neuen (deterministischen) Automaten, der vom Anfangsknoten entlang eines Pfades der Länge 2 erreichbar ist. Wir wiederholen das beschriebene Verfahren, bis keine neuen Zustandsmengen (einschließlich der leeren) erscheinen. Man kann zeigen, dass in diesem Fall alle solchen Zustände des endlichen Automaten M_1 erhalten werden, die vom Anfangszustand \(q_0\) aus erreichbar sind.

Für den endlichen Zustandsautomaten in Abb. 7.15 haben wir:

\begin(aligned)& \delta_1(\(q_0\),a)=\(q_1\);\qquad \delta_1(\(q_0\),b)=\(q_1,q_3\);\\ & \ delta_1(\(q_1\),a)=\(q_1\);\qquad \delta_1(\(q_1\),b)=\(q_1\);\\ & \delta_1(\(q_1,q_3\) ,a)= \delta(q_1,a)\cup \delta(q_3,a)= \(q_1\)\cup\(q_1\)=\(q_1\);\\ & \delta_1(\(q_1, q_3\),b)= \delta(q_1,b)\cup \delta(q_3,b)= \(q_1\)\cup\(q_1\)=\(q_1\). \end(ausgerichtet)

Da es keine neuen Zustandsmengen mehr gibt, endet die "Zieh"-Prozedur hier, und wir erhalten den in Abb. 7.16.

Reguläre Sprachergänzung

Eine der wichtigen theoretischen Konsequenzen des Determinationssatzes ist der folgende Satz.

Satz 7.8. Das Komplement einer regulären Sprache ist eine reguläre Sprache.

Sei L eine reguläre Sprache im Alphabet V . Dann ist das Komplement der Sprache L (als Menge von Wörtern) die Sprache \overline(L)=V^(\ast)\setminus L.

Nach Satz 7.7 kann für eine reguläre Sprache L ein deterministischer endlicher Automat M konstruiert werden, der L zulässt. Da in einem deterministischen Automaten von jeder Ecke für jedes Eingabesymbol ein Übergang zu genau einer Ecke definiert ist, gibt es unabhängig von der Zeichenfolge x im Alphabet V einen eindeutigen Pfad dafür in M ​​, beginnend bei der Initiale Zustand, in dem die Zeichenfolge x gelesen wird. Es ist klar, dass der String x vom Automaten M erlaubt ist, also x\in L(M) , wenn und nur wenn der letzte Zustand des angegebenen Pfades final ist. Dies impliziert, dass die Kette x\notin L(M) genau dann ist, wenn der letzte Zustand des angegebenen Pfads nicht endgültig ist. Aber wir brauchen nur einen endlichen Automaten M", der die Kette x genau dann zulässt, wenn der ursprüngliche endliche Automat M dies nicht zulässt. .

Der bewiesene Satz erlaubt uns, einen endlichen Automaten zu konstruieren, der einen bestimmten Satz von Ketten nicht zulässt, indem wir die folgende Methode anwenden: Zuerst bauen wir einen Automaten, der einen bestimmten Satz von Ketten zulässt, dann bestimmen wir ihn und übergeben ihn an den Automaten für das Komplement wie im Beweis von Satz 7.8 angegeben.

Beispiel 7.10. a. Lassen Sie uns einen endlichen Automaten bauen, der alle Zeichenfolgen im Alphabet \(0;1\) außer Zeichenfolge 101 zulässt.

Zuerst konstruieren wir einen endlichen Automaten, der eine einzelne Kette 101 erlaubt. Dieser Automat ist in Fig. 2 gezeigt. 7.17.

Dieser Automat ist quasi-deterministisch, aber nicht deterministisch, da er nicht vollständig definiert ist. Lassen Sie uns ihn bestimmen und erhalten Sie einen deterministischen äquivalenten endlichen Automaten, der in Abb. 7.18.

Und wenn wir schließlich zur Addition übergehen (und die Zustände umbenennen), erhalten wir den in Abb. 7.19.

Beachten Sie, dass im resultierenden Automaten alle Scheitelpunkte mit Ausnahme des Scheitelpunkts s_3 endgültig sind.

Beachten Sie auch, dass der Übergang zum Komplement, der im Beweis von Satz 7.8 diskutiert wird, nur in einem deterministischen Automaten durchgeführt werden kann. Wenn wir die Rollen von finalen und nicht-finalen Ecken in dem in Abb. 7.17 würden wir einen Automaten bekommen, der die Sprache \(\lambda,1,10\) zulässt, was nicht – wie leicht zu sehen ist – die Menge aller Zeichenketten außer der Zeichenkette 101 ist.

Beachten Sie auch, dass der endliche Zustandsautomat in Abb. 7.19 lässt alle Zeichenfolgen zu, die ein Vorkommen der Zeichenfolge 101 enthalten, aber nicht mit der Zeichenfolge selbst übereinstimmen. Hier ist zum Beispiel der Pfad, der die 1011-Kette trägt: s_0,s_1,s_2,s_3,t.

b. Lassen Sie uns einen endlichen Automaten konstruieren, der alle Zeichenfolgen im Alphabet \(0;1\) zulässt, außer denen, die ein Vorkommen der Zeichenfolge 101 enthalten. Betrachten Sie eine Sprache L , in der jede Zeichenfolge ein Vorkommen der Zeichenfolge 101 enthält. Es kann wie folgt definiert werden:

L=(0+1)^(\ast)101(0+1)^(\ast).

Wir müssen einen Automaten bauen, um die Sprache L zu ergänzen.

Direkt aus dem regulären Ausdruck lässt sich in diesem Fall leicht ein endlicher Automat konstruieren, der die Sprache L zulässt (Abb. 7.20).

Dann führen wir die Bestimmung durch die "Ziehmethode" durch. Das Ergebnis der Bestimmung ist in Fig. 2 gezeigt. 7.21.

Für eine vollständige Lösung des Problems wird nur Abb. 7.21 Vertauschen Sie die Rollen der finalen und nicht-finalen Ecken (Abb. 7.22).

in. Lassen Sie uns die Idee diskutieren, einen endlichen Automaten zu konstruieren, der diejenigen und nur die Zeichenfolgen im Alphabet \(0;1\) zulässt, die nicht mit der Zeichenfolge 01 beginnen und nicht mit der Zeichenfolge 11 enden (d.h. Zeichenfolgen der Form 01x und Strings der Form y11 sind nicht erlaubt, egal welche Ketten x,y\in\(0;1\) ).

In diesem Fall ist das Komplement der Sprache, für das es notwendig ist, einen endlichen Automaten zu bauen, die Menge aller solcher Folgen von Nullen und Einsen, die mit der Zeichenfolge 01 beginnen oder mit der Zeichenfolge 11 enden. Ein Automat, der diese Menge von zulässt strings ist als Automat zum Kombinieren konstruiert 01(0+1)^(\ast)+(0+1)^(\ast)11 genauso wie im Beweis des Satzes von Kleene (siehe Satz 7.6).

Die Eigenschaft der Klasse der regulären Sprachen, unter Komplement abgeschlossen zu sein (siehe Satz 7.8), impliziert sofort, dass diese Klasse unter Schnittmenge, mengentheoretischen und symmetrischen Differenzen abgeschlossen ist.

Folgerung 7.3. Für zwei beliebige reguläre Sprachen L_1 und L_2 gelten die folgenden Aussagen:

1) der Schnittpunkt L_1\cap L_2 ist regulär;
2) die Differenz L_1\setminus L_2 ist regulär;
3) symmetrischer Unterschied L_1\vartriangle L_2 regulär.

Die Gültigkeit der Aussagen ergibt sich aus den Identitäten:

\begin(aligned) &(\scriptstyle(\mathsf(1))))\quad L_1\cap L_2= \overline(\overline(L_1) \cup\overline(L_2))\,;\\ &(\scriptstyle (\mathsf(2))))\quad L_1\setminus L_2= L_1\cap \overline(L_2)\,;\\ &(\scriptstyle(\mathsf(3))))\quad L_1\,\triangle\ ,L_2 = (L_1\cup L_2)\setminus (L_1\cap L_2).\end(aligned)

Erstens erlauben uns die erhaltenen Ergebnisse zu behaupten, dass die Klasse der regulären Sprachen in Bezug auf die Operationen der Vereinigung, des Schnitts und der Addition eine Boolesche Algebra ist, in der die Einheit die universelle Sprache und die Null die leere Sprache ist . Zweitens ermöglichen uns diese algebraischen Eigenschaften der Familie regulärer Sprachen, das wichtige Problem der Anerkennung der Äquivalenz zweier beliebiger endlicher Automaten zu lösen.

Nach Definition 7.10 sind endliche Automaten äquivalent, wenn die von ihnen zugelassenen Sprachen gleich sind. Um die Äquivalenz der Automaten M_1 und M_2 zu verifizieren, genügt es daher zu beweisen, dass die symmetrische Differenz der Sprachen L(M_1) und L(M_2) leer ist. Dazu wiederum genügt es, einen Automaten zu konstruieren, der diesen Unterschied zulässt, und zu verifizieren, dass die Sprache, die er zulässt, leer ist. Im Allgemeinen wird das Problem des Erkennens, dass eine Zustandsmaschinensprache leer ist, das Zustandsmaschinen-Leerheitsproblem genannt. Um dieses Problem zu lösen, genügt es, die Menge der Endzustände des Automaten zu finden, die vom Anfangszustand aus erreichbar sind. Da es sich bei der endlichen Zustandsmaschine um einen gerichteten Graphen handelt, kann dieses Problem beispielsweise mit der Breitensuche gelöst werden. Die vom endlichen Automaten zugelassene Sprache ist genau dann leer, wenn die Menge der vom Anfangszustand erreichbaren Endzustände leer ist. In der Praxis ist es vorzuziehen, die Äquivalenz endlicher Automaten durch einen Minimierungsalgorithmus zu erkennen, aber nun ist es uns wichtig zu betonen, dass die grundsätzliche Möglichkeit zur Lösung des Äquivalenzproblems aus Satz 7.7 und seinen algebraischen Konsequenzen folgt.