GTI Mitschrift

Grundlagen der Theoretischen Informatik

mitgeschrieben von Martin Lenders

Dieses Dokument vom 6. Juli 2009 steht unter einer Creative Commons BY-NC-ND 3.0 Deutschland Lizenzfur die Seite http://page.mi.fu-berlin.de/mlenders/mitschriften/gti/

http://creativecommons.org/licenses/by-nc-nd/3.0/de/

http://page.mi.fu-berlin.de/mlenders/mitschriften/gti/

Inhaltsverzeichnis

1 Turing-Maschine, Berechenbarkeit, Entscheidbarkeit 51.1 Definition der Turing-Maschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2 Church’sche These . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.3 Registermaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.4 Formale Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.1 Multiplikation von Wortern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4.2 Multiplikation von Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4.3 Potenz von Wortern und von Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5 Konfiguration (Momentaufnahme einer Turingmaschine) . . . . . . . . . . . . . . . . . . . . . . . 81.6 Turingmaschine mit mehreren Bandern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.7 Die universelle Turingmaschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.8 Unentscheidbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.8.1 Universelle Sprache und Diagonalsprache . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.8.2 Das Halteproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.8.3 Reduzierbarkeit von Problemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.8.4 Das Post’sche Korrespondenzproblem (PKP) . . . . . . . . . . . . . . . . . . . . . . . . . 131.8.5 Andere unentscheidbare Probleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.8.6 Satz von RICE (1953) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Regulare Sprachen und endliche Automaten 172.1 Deterministische endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Regulare Ausdrucke . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3 Nichtdeterministische endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.4 NEA mit ε-Ubergangen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.4.1 Elimination von ε-Ubergangen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.5 Minimierung deterministischer endlicher Automaten . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.5.1 Algorithmus zur Bestimmung des Minimalautomaten: . . . . . . . . . . . . . . . . . . . . 252.5.2 Satz von Nerode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.6 Das Pumping-Lemma fur regulare Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.7 Abschlusseigenschaften regularer Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.8 Zusammenfassung: regulare Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Grammatiken 313.1 Definition von Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Die Chomsky-Hierarchie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Typ-0-Sprachen (rekursiv aufzahlbare Sprachen) . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.4 Typ-3-Sprachen (regulare Sprachen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Typ-1-Sprachen (kontextsensitive Sprachen) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4 Kontextfreie Sprachen (Typ-2-Sprachen) 354.1 Tiefenstruktur von Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.2 Dyck-Sprache . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.3 Kontextfreie Grammtiken als Gleichungssysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.4 Eindeutigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374.5 Chomsky-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.6 Algorithus von

”CYK“ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4.7 (Erweiterte) Backus-Naur-Form (E)BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.8 Pumping-Lemma fur kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424.9 Abschlusseigenschaften kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.10 Entscheidungsprobleme kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.11 Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3

Inhaltsverzeichnis

4.12 Abschlusseigenschaften kontextfreier Sprachen gegenuber regularen Sprachen . . . . . . . . . . . 484.13 Deterministische kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.14 Deterministische Zweiwege-Kellerautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

4.14.1 Teilwortproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4

1 Turing-Maschine, Berechenbarkeit,Entscheidbarkeit

1.1 Definition der Turing-Maschine

Schreib−/Lesekopf

Steuerung

Zustand

(Programmzähler)

Programm

Zweiseitiges, unendliches Band

1 X0BBB B B B

(q, a)

(q′, a′, b)

Eine Turingmaschine wird beschrieben durch:

• Ein Eingabealphabet Σ

• ein Bandalphabet Γ ⊃ Σ

• ein Leerzeichen B ∈ Γ \ Σ

• eine endliche Menge Q von Zustanden

• eine Uberfuhrungsfunktion δ : Q× Γ→ Q× Γ× {−1, 0, 1}

• ein Anfangszustand q0 ∈ Q

• (eventuell) eine Menge von akzeptierenden Zustanden F ⊆ Q

δ ist das”Programm“ der TM

• δ(q, a) = (q′, a′, b) bedeutet: Wenn die Maschine im Zustand q ist und unter dem Kopf das Symbol a steht,dann wird a durch a′ auf dem Band ersetzt (a′ = a ist moglich), das Band wird um b verschoben und dieMaschine geht in den Zustand q′

• Die Eingabe ist eine Folge von Symbolen aus Σ (ein Wort uber Σ). Sie steht am Anfang auf dem Band;der Kopf steht uber dem ersten Symbol. Der Zustand ist q0.

Beispiel:Σ = {0, 1}, Γ = {0, 1, B, X}

Erkenne die Eingabe der Form: 0n1n, fur n ≥ 1

01, 0011, 000111, ... (richtig)001, 1100, 0100101, ... (falsch)

rechts und links von der Eingabe stehen unendlich viele B-Symbole

• Phase 1: laufe einmal von links nach rechts uber das Band und uberprufe, ob dort eine Folge von 0engefolgt von eine Folge von 1en steht.

• Phase 2: Fahre abwechselnd nach links und nach rechts und ersetze jeweils 0 und eine 1 durch X.Akzeptiere, wenn am Ende alles durch X erstzt ist und kene 0, 1 ubrig bleibt

5

KAPITEL 1. TURING-MASCHINE, BERECHENBARKEIT, ENTSCHEIDBARKEIT

δ 0 1 B X Kommentarq0 (q0, 0, 1) (q1, 1, 1) (q−, B, 0) egal fahre nach rechts uber Nullenq1 (q−, 0, 0) (q1, 1, 1) (q2, B,−1) egal fahre nach rechts uber Einsenq2 (q3, X, 1) (q2, 1,−1) (q4, B, 1) (q2, X,−1) fahre nach links und suche 0,

ersetze sie durch Xq3 (q3, 0, 1) (q2, X,−1) (q4, B, 1) (q3, X, 1) fahre nach rechts und suche 1,

ersetze sie durch Xq4 (q4, 0, 1) (q−, 1, 1) (q+, B, 0) (q4, X, 1) fahre nach rechts und suche 1;

akzeptiere wenn keine 1 mehrvorhanden ist.

q− (q−, 0, 0) (q−, 1, 0) (q−, B, 0) (q−, X, 0)q+ (q+, 0, 0) (q+, 1, 0) (q+, B, 0) (q+, X, 0)

• Die Maschine halt, wenn sie in einen Zustand q uber einen Symbol a mit δ(q, a) = (q, a, 0) steht.

Q = {q0, q1, q2, q3, q4, q+, q−}

q0 = q0

F = {q+}

• Die T. M. akzeptiert die Eingabe, wenn sie in einem Zustand aus F halt.

1.2 Church’sche These

Das was von einer Turing-Maschine berechnet werden kann, entspricht dem, was man intuitiv unter”algorith-

misch berechenbar“ versteht.

Beispiel: Addition zweier Binarzahlen

Eingabe: bin(x)#bin(y)$ (bin(x) := Binardarstellung einer positiven Zahl, fuhrende Nullen sind egal)Ausgabe: bin(x + y)#bin(y)$

Programmiertechniken:

• Verwenden mehrerer Spuren: Jedes Feld des Bandes wird als aus mehreren Unterfeldern beste-hend betrachtet.

X X X0 1 1 0 1

formal: Γ = Γ1 × Γ2 × Γ3 × . . .× Γk, Γi . . . Bandalphabet fur die i-te Spur.z. B.: {’ ’, x} × {0, 1, B, . . .}• Speichern von Variablen mit endlichen Wertebereich als Teil des Zustandes.

formal: Q = Q0 × V , V . . . Wertebereich der Variablen.1. Wandere nach rechts zur 1. unmarkierten Ziffer a.

s := a (merken)Markiere diese Ziffer auf dem Band.

2. Wandere nach links zur 1. unmarkierten Ziffer b von xErsetze b durch b + s + u, u := Ubertrag. (Markiere diese Ziffer)

3. Gehe zu 1 solange noch Ziffern ubrig sind.4. Losche alle Markierungen

qsu, Zustand (Programmzeile) q mit Werten s, u der Variablen, Haltezustand: h

s ∈ {0, 1}

u ∈ {0, 1}

Eingabealphabet: Σ = {0, 1, #, $}Bandalphabet: Γ = Σ ∪ {B, 0, 1}

6

1.3. REGISTERMASCHINEN

δ 0 1 0 1 # $ B Schrittq0u q0

u, 0, + q00 , 1, + q0

u, 0, + q0u, 1, + r0

u, #, +r0u r0

u, 0, + r0u, 1, + s0

u, 0,− s0u, 1,− s0

u, $,− 1s0

u t0u, 0,− t1u, 1,− u0u, #,−

tiu t0u, 0,− t1u, 1,− uiu, #,−

ui0 ui

0, 0,− ui0, 1,−

u00 q0

0 , 0, + q00 , 1, + v0

0 , 0, + 2u1

0, u01 q0

0 , 1, + q00 , 0, + v0

0 , 1.+u1

1 q01 , 0, + q0

1 , 1, + v10 , 0.+

v0u v0

u, 0, + v0u, 1, + v0

u, 0, + v0u, 1, + w0

u, #, +w0

u r0u, 0, + r0

u, 1, + x0u, 0,− x0

u, 1,−x0

u y0u, #,− 3

y00 y0

0 , 0,− y00 , 1,− z, B, +

y01 y0

1 , 0,− y01 , 1,− z, 1, +

z z, 0, + z, 1, + z, #, + p, $,− 4p p, 0,− p, 1,− p, #,− h, B, +

• Unterprogrammtechnik

1.3 Registermaschinen

Simulation eines RAM-Speichers auf einer TM:

##x1#y1##x2#y2##...###[Programmcode]

xi... Adresse, yi... Inhalt auf Adresse xi

1.4 Formale Sprachen

Σ . . . endliches Alphabet (Vorrat an Zeichen)Σ∗ . . . alle Worter endlicher Lange l, die man mit den Buchstaben aus Σ bilden kann.

w = a1a2a3 . . . al, ai ∈ Σl = |w| Lange des Wortes l ≥ 0ε ist das leere Wort |ε| = 0

Definition: Eine formale Sprache L ist eine Teilmenge von Σ∗

Beispiel:

L = {0n1n|n ≥ 1}

L = ∅

L = {ε}

7


1.4.1 Multiplikation von Wortern

u · v = uv (Buchstaben von u und v nebeneinander geschrieben)

Rechenregeln: 1. u · (v · w) = (u · v) · w

2. ∀u ∈ Σ∗ : u · ε = ε · u = u

Beispiel: u = abrav = kadabrau · v = abrakadabrav = kad ·u

1.4.2 Multiplikation von Sprachen

L1 · L2 = {uv|u ∈ L1, v ∈ L2}

Rechenregeln: 1. L1 · (L2 · L3) = (L1 · L2) · L3

2. L · ∅ = ε · u = u

3. L · {ε} = L

Beispiel: L1 = {a,ab} L2 = {a,ba}L1 · L2 = {aa,aba,abba}

1.4.3 Potenz von Wortern und von Sprachen

ui = u · u · u · . . . · u︸︷︷︸

i−mal

u1 = u

u0 = ε

Li = L · L · . . . · L︸︷︷︸

i−mal

= {u1 · u2 · . . . · ui|u1 ∈ L, u2 ∈ L, . . . , ui ∈ L}

L1 = L L0 = {ε}

L∗ := L0 ∪ L1 ∪ L2 ∪ . . .

= Menge der Worter, die man aus bel. vielen (≥ 0) Bestandteilen ∈ L zusammen multiplizieren kann.

1.5 Konfiguration (Momentaufnahme einer Turingmaschine)

Definition: Eine Konfiguration einer Turingmaschine ist ein Wort aus Γ∗QΓ∗, das nicht mit B anfangt oderaufhort (ein Wort ∈ Γ∗QΓ∗ \ (B(Γ ∪Q)∗ ∪ (Γ ∪Q)∗B)).Das Wort xqy mit x, y ∈ Γ∗ und q ∈ Q beschreibt den Zustand der Turingmaschine wo xy auf dem Bandsteht und der Kopf uber dem ersten Zeichen von y steht Fur zwei Konfigurationen k1 und k2 schreibt mank1 ⊢ k2 wenn die Turingmaschine in einem Schrittvon k1 nach k2 ubergeht. (Nachfolgerrelation zwischenKonfigurationen.)

k1

∗

⊢ k2 bedeutet, dass auf k1 nach beliebig vielen Schritten (≥ 0) die Konfiguration k2 folgt.

8

1.6. TURINGMASCHINE MIT MEHREREN BANDERN

1.6 Turingmaschine mit mehreren Bandern

• Eine Turingmaschine mit k Bandern hat k Schreib-/Lesekopfe.

• Das erste Band ist das Eingabeband.

• Die ubrigen Bander sind zu Beginn leer.

• Die Ubergangsfunktion δ : Q× Γk → Q× Γk × {−1, 0, +1}k

Beispiel: binare Addition von 2 n-Bit Zahlen geht mit 2 Bandern in O(n) Schritten (≤ konst. (n)) (mit einemBand in O(n2) Schritten).

Zuerst wird bin(y) auf das 2. Band kopiert, und dann bitweise von rechts nach links addiert.

Satz: Eine k-Band-Turingmaschine die nach T Schritten halt kann durch eine 1-Band-Turinmaschine simuliertwerden, die in hochstens const.T 2 Schritten halt.

Beweis: Simulation der k Bander auf k Spuren eines einzigen Bandes. Die Kopfposition der Bander ist af derjeweiligen Spur vermerkt.

Γ1 = Γ ∪ (Γ× {X, ’ ’})k ∪ {L}

• L markiert die Position links neben der linkesten Position die die simulierte Turingmaschine auf allenBandern besucht hat. In einer konstanten Anzahl von Fahrten uber das gesamte Band (ausgehendvon L) kann die Turingmaschine die Bandanderungen auf den k Bandern simulieren.

• Die simulierte Maschine kann in T Schritten hochstens T Schritte nach links und rechts gehen.

• Die Lange des uberstrichenen Bandinhalts in jedem Simulationsschritt ist ≤ 2T + 1

• Ein Simulationsschritt geht in ≤ const.T Schritten T -mal ⇒ T 2

• 2 n-Bit Binarzahlen konnen auf einem k-Band-TM in n · log n · const.log∗ n Schritten multipliziert

werden (Martin Fuhrer 2008, bestehender Rekord vorher const.n·log n log log n (Arnold Schon-

hage ≈ 1970))log∗ n := min{i| log2 log2 log2 . . . log2

︸︷︷︸

-mal

n ≤ 1}

Die Umkehrfunktion von log∗ ist 2

22

...

2 }

i-mal

= 2 ↑ i

Definition: Die von einer Turingmaschine M mit einer Teilmenge F ⊆ Q von akzeptierenden Zustanden akzep-tierte Sprache L(M) ist die Menge der Wortern bei deren Eingabe die Maschine einen akzeptierendenZustand erreicht (und dann anhalt).

L(M) =

{

x ∈ Σ∗

∣∣∣∣q0x

∗

⊢ yqz, mit y, z ∈ Γ∗ und q ∈ F

}

Eingabe x

M halt in q ∈ F → x ∈ L(M)

M halt in q /∈ F → x /∈ L(M)

M terminiert nicht → x /∈ L(M)

9


Definition: Eine Sprache L heißt rekursiv aufzahlbar (semi-entscheidbar, engl. recursiv enumerable) wenn eseine Turingmaschine M mit L = L(M) gibt.L heißt entscheidbar (rekursiv), wenn es eine Turingmaschine M gibt, die auf allen Eingaben halt undmit L = L(M)Unterscheide: abzahlbare (denumerable) Mengen: endlich oder gleichmachtig mit N

Turingmaschine die etwas berechnet: x ∈ Σ∗ steht auf dem Eingabeband.

• Wenn die Maschine halt, steht ein Wort y ∈ Σ∗ auf dem Ausgabeband (bzw. auf dem einzigen Band).

• Die von der Turingmaschine berechnete (partielle) Funktion fM ist definiert auf der Menge A = {x ∈Σ ∗ |M halt bei Eingabe um x}

fM : A→ Σ∗ mit A ⊆ Σ∗

• Eine partielle Funktion f : A → Σ∗ mit A ⊆ Σ∗ oder eine totale Funktion f : Σ∗ → Σ∗ heißtberechenbar, wenn es eine Turingmaschine M mit f = fM gibt.

1.7 Die universelle Turingmaschine

Eine universelle Turingmaschine liest als Eingabe:

1. Die Beschreibung einer beliebigen Turingmaschine M

2. Die Eingabe fur M .

Dann simuliert sie M mit dieser Eingabe und halt genau dann, wenn M halt.

• Die Beschreibung von M wird als 〈M〉 ∈ {0, 1}∗ bezeichnet.

• Man nennt 〈M〉 die Godelnummer von M .

Konventionen: a) M hat das Eingabealphabet {0, 1}

b) M hat Zustandsmenge Q = {q1, q2, ..., qk}q1 ist der Startzustandq2 ist der einzige akzeptierende Zustand

c) M hat Bandalphabet {0, 1, B, 3, 4, 5, . . . , |Γ| − 1} (keine wesentlichen Einschrankungen).

Jetzt mussen wir nur noch δ kodieren:als Liste von 5-Tupeln: δ(q, a) = (q′, b, m) wird als (q, a, q′, b, m) geschrieben.(qi1 , γj1 , qk1 , γl1 , m1), (qi1 , γj1 , ...), ...⇒ |111|0i110j110j110k110l110m1|11|0i210j210j210k210l210m2|11|...|111|

Beispiel:

δ(q1, 0) = (q2, B,−1), δ(q4, γ5) = (q2, γ5, +1), ...

⇒ 〈M〉 = 111010100100010110000100000100100000100011...111

1.8 Unentscheidbarkeit

1.8.1 Universelle Sprache und Diagonalsprache

Definition: Die universelle Sprache LU ist die Sprache

LU = {〈M〉x|M akzeptiert x} ⊆ {0, 1}∗

Satz: Es gibt eine universelle Turingmaschine MU mit L(MU ) = LU

Beweisskizze: MU muss zunachst den Anfang der Eingabe bis zum zweiten 111-Block lesen und entscheidenob es sich um eine gultige Godelnummer handelt.

MU kopiert die Beschreibung auf ein zweites Band, und kann anschließend die Maschine M Schritt furSchritt simulieren.

Wenn die simulierte Maschine M halt, dann halt auch MU (in einem akzeptierenden oder nicht akzep-tierenden Zustand, je nach M).

10

1.8. UNENTSCHEIDBARKEIT

Aufzahlung aller Worter aus {0, 1}∗ und aller Turingmaschinen:

w1 = ε

w2 = 0

w3 = 1

w4 = 00

w5 = 01

w6 = 10

w7 = 11

w8 = 000

...

M1, M2, ..., Mi, ...

Mi =

Turingmaschine M , falls wi = 〈M〉 ist

Turingmaschine, die einen Schritt

nach links macht, und dann in einem

akzeptierenzen Zustand anhalt. falls wi keine gultige Godelnummer ist

Definition: Die Diagonalsprache D ist

D = {wi| wi /∈ L(Mi)︸︷︷︸

Mi akzeptiert wi nicht.

, i = 1, 2, 3, ...}

w1 w2 w3 · · · wi · · · wk · · ·M1 +−

M2 + +−

M3 − + −+

M4 + − −...

Mi + + − +

D − − + +

Satz: D ist nicht rekursiv aufzahlbar und damit auch nicht entscheidbar.

Beweis durch Widerspruch: Angenommen, es gibt eine Turingmaschine Mk die D akzeptiert:

D = L(Mk) = {w|Mk akzeptiert w}

Betrachtet das Wort wk:

wk ∈ D

Definition von D⇐⇒ wk /∈ L(MK)

Annahme: Mk akzeptiert die Sprache D⇐⇒ wk /∈ D �

Satz: Das Komplement D der Diagonalsprache

D = {wi|wi ∈ L(Mi)}

ist rekursiv aufzahlbar, aber nicht entscheidbar

11


Beweis: 1. MD uberpruft, ob die Eingabe eine gultige Godelnummer 〈M〉 ist,wenn nein, dann akzeptiere.

2. Wenn ja, verdopple die Eingabe und starte die universelle Turingmaschine:

〈Mi〉︸︷︷︸

=wi

wi

akzeptiert genau dann, wenn wi /∈ L(Mi)

Nichtentscheidbarkeit folgt aus dem nachsten Satz.

Satz: 1. Eine Sprache L ⊆ Σ∗ ist genau dann entscheidbar, wenn die Komplementarsprache L = Σ∗ − Lentscheidbar ist.

2. L ist genau dann entscheidbar, wenn sowohl L als auch L rekursiv aufzahlbar sind.

Beweis: 1. Drehe die Angabe des Entscheidungsalgorithmus um.

2. L entscheidbar ⇒ L entscheidbar ⇒ L, L rekursiv aufzahlbar.

⇐M1 akzeptiert L, M2 akeptiert L

Lasse M1 und M2 ”parallel“ laufen (abwechselnd) auf derselben Eingabe x ∈ Σ∗

Wenn x ∈ L, dann terminiert M1.Wenn x ∈ L, dann terminiert M2.Sobald eine der simulierten Turingmaschinen M1 und M2 anhalt, ist die Antwort bekannt.

L Lentscheidbar entscheidbar

rekursiv aufzahlbar, nicht entscheidbar nicht rekursiv aufzahlbarnicht rekursiv aufzahlbar rekursiv aufzahlbar, nicht entscheidbarnicht rekursiv aufzahlbar nicht rekursiv aufzahlbar

Satz: Die universelle Sprache U ist unentscheidbar.

Beweis: Mit der Entscheidbarkeit von U konnte man auch die Diagonalsprache D = {wi|wi /∈ L(Mi)} entschei-den.

Wir wollen untersuchen, ob wi ∈ D ist.

Uberprufe ob wi die Godelnummer einer gultigen Turingmaschine M ist.

• Wenn nein: L(Mi) = Σ∗ wi ∈ Σ∗ → Antwort: JA

• Wenn ja: Mi = M

Uberprufe ob 〈Mi〉wi ∈ U ⇔ wi ∈ L(Mi)

– wenn ja → Antwort: NEIN.– wenn nein → Antwort: JA.

1.8.2 Das Halteproblem

Gegeben: Eine Turingmaschine M und eine Eingabe x ∈ Σ∗ (oder ein Programm in C, Java, ... mit einerEingabe).

Frage: Halt die Turingmaschine nach endlich vielen Schritten?

Formuliereung des Problems als formale Sprache:

H = {〈M〉|M halt bei Eingabe von x}

Satz: Das Halteproblem ist unentscheidbar

Beweis: indirekt.

Annahme: Es gibt einen Algorithmus, der das Halteprolem entscheidet.

Behauptung: Dann konnten wir auch die universelle Sprache U entscheiden.

U = {〈M〉x|x ∈ L(M), M halt bei Eingabe von x in einem akzeptierenden Zustand}

12


Teste zuerst, ob 〈M〉x ∈ H ist. Wenn nein, dann ist 〈M〉x /∈ U . Wenn ja, simuliere M auf der Eingabex, diese Simulation muss terminieren. Je nachdem, ob der Haltezustand von M ein akzeptierenderZustand ist oder nicht, gehort 〈M〉x zu U oder nicht.

Das spezielle HalteproblemHε = {〈M〉|M halt bei Eingabe ε}

Folgerung: Hε ist unentscheidbar.

Indirekter Beweis: Annahme wir hatten einen Algorithmus A, der Hε entscheidet.Behauptung: Dann konnten wir H entscheiden.

〈M〉x sei Eingabe fur H .

Konstruiere eine neue Turingmaschine M ′ die am Anfang das Wort x auf das Band schreibt, dannnach links zuruckkehrt und dann wie M weitermacht.Teste mit dem Algorithmus A, ob 〈M〉 ∈ Hε

〈M ′〉 ∈ Hε ⇔ 〈M〉x ∈ H

1.8.3 Reduzierbarkeit von Problemen

Definition: A, B ⊆ Σ∗

A ist auf B reduzierbarA ≤ B

wenn es eine berechenbare Funktion f : Σ∗ → Σ∗ gibt mit

x ∈ A⇔ f(x) ∈ B, ∀x ∈ Σ∗

Beispiel: H ≤ Hε

f(〈M〉x) = 〈M ′〉

f(y) = 〈M∞〉, falls y nicht mit der gultigen Codierung einer Turingmaschine beginnt

M∞ := eine Turingmaschine, die nie halt.

(”y ist keine korrekte Eingabe fur das Halteproblem“)

Beispiel: D ≤ U

Satz: 1. A ≤ B ∧B ≤ C ⇒ A ≤ C

2. A ≤ B und B entscheidbar ⇒ A entscheidbar

3. A ≤ B und A unentscheidbar ⇒ B unentscheidbar

Beweis: 1. Transitivitat

2. Wir wollen entscheiden, ob x ∈ A ist: Berechne f(x) und entscheide, ob f(x) ∈ B ist.

3. logisch aquivalent zu 2.

1.8.4 Das Post’sche Korrespondenzproblem (PKP)

Gegeben: Eine Folge von Paaren von Wortern (x1, x2), (y1, y2), ..., (xn, yn) xi, yi ∈ Σ∗

Frage: Gibt es eine Folge von Indizes i1, i2, ..., ik (k ≥ 1) mit xi1xi2xi3 ...xik= yi1yi2 ...yik

?

Beispiel (1, 111), (10111, 10), (10, 0)

((((((((((((

i1 = 1 i2 = 1⇒ i3 = 1((((x = 111

(((((((y = 111111111

i1 = 2 i2 = 1 i3 = 1 i4 = 3

x = 10111︸︷︷︸

1︸︷︷︸

1︸︷︷︸

10︸︷︷︸

y = 10︸︷︷︸

111︸︷︷︸

111︸︷︷︸

0︸︷︷︸

(10, 101), (011, 11), (101, 011)

(001, 0), (01, 011), (01, 101), (10, 001) kurzeste Losung k = 66

13


Satz: PKP ist unentscheidbar

Beweis: U ≤ PKP Zwischenschritt: Modifiziertes PKP

zusatzliche Bedingung: i1 = 1 MPKP ≤ PKPU ≤ PKP . Folge von Konfigurationen einer Turingmaschine

x1︸︷︷︸

x1

q0v#u1q1v1

xi

↓#u2q

2v2#u3q3v3#...

#q0v#︸︷︷︸

y1

u1q1v1#u2q

2v2#↑yi

u3q3v3#...

Beispiel

xi

↓#

xi + 1↓

︷︸︸︷

0︷︸︸︷

0︷︸︸︷

1︷︸︸︷

0

xj︷︸︸︷

q1 10#

#0010q110#↑yi

0︸︷︷︸

0︸︷︷︸

↑yi + 1

1︸︷︷︸

0︸︷︷︸

0q′︸︷︷︸

yi

10#

δ(a, 1) = (q′, 0, +1)

Gegeben: M, x ∈ Σ∗

Alphabet fur PKP = Γ ∪Q ∪ {#}

Anfangspaar: (x1, y1) = (#, #q0x#)

Kopierpaare: (xi, yi) = (a, a) fur a ∈ Γ ∪ {#}

Zustandsubergange:

(qa, q′b), falls δ(q, a) = (q′, b, 0)

(q#, q′b#), falls δ(q, B) = (q′b, 0)

(qa, bq′), falls δ(q, a) = (q′, b, 1)

(q#, bq′#), falls δ(q, B) = (q′, b, 1)

(cqa, q′cb), falls δ(q, a) = (q′, b,−1)

(cq#, q′cb#), falls δ(q, B) = (q′, b,−1)

(#qa, #q′Bb), falls δ(q, a) = (q′, b,−1)

(#q#, #q′Bb#), falls δ(q, B) = (q′, b,−1)

MPKP ≤ PKP

Gegeben: Eingabe fur MPKP

(x1, y1), (x2, y2), . . . (xn, ym)

Frage fur MPKP: Gibt es eine Folge

i1, i2, . . . , ik k ≥ 1 mit i1 = 1

Sodass xi1xi2 ...xik= yi1 ...yik

Reduktion: Wir konstruieren uns eine Eingabe (x′0, y

′0), (x

′1, y

′1), ..., (x

′n+1, y

′n+1),

Dieses PKP hat eine Losung ⇔ Das ursprungliche MPKP hat eine Losung.

14


Beispiel:

(0, 010), (11, 0), (101, 01) Eingabe fur MPKP

x′i = xi mit einem neuen Symbol # nach jedem Buchstaben

y′i = yi mit einem neuen Symbol # vor jedem Buchstaben

(x′1, y

′1) = (0#, #0#1#0) (x′

2, y′2) = (1#1#, #0) (x′

3, y′3) = (1#0#1#, #0#1)

x′0 = #x′

1 x′0 = #0#

y′0 = y′

1y′0 = #0#1#0

Dieses PKP kann nur min(x′0, y

′0) beginnen

x′0x

′3 = #0#1#0#1# x1x3 = 0101

y′0y

′3 = #0#1#0#0#1y1y3 = 01001

x′n+1 = $y′

n+1 = #$

....01 7→ 0#1#$

....01 7→ #0#1#$

Die Eingabe (x′0, y

′0), ..., (x

′n+1, y

′n+1) ist aus (x1, y1), ..., (xn, yn) berechenbar.

Lemma: U ≤MPKP

Beweis: Gegeben ist eine Eingabe 〈M〉x fur UWir konstruieren daraus eine Eingabe fur MPKP mit folgenden Eigenschaften

MPKP hat eine Losung ⇔ 〈M〉x ∈ U

(M akzeptiert x)

Idee: MPKP simuliert die Berechnung von M

Losungswort: #K0#K1#K2#... Ki aufeinanderfolgende Konfigurationen von M

K0 = q0xKi = uiq

ivi qi ∈ Q, ui, vi ∈ Γ∗

xi1xi2 ...xik= #|K1#|K2#K3#|

yi1yi2 ...yik= #K1#|K2#|K3#K4#|

Das y-Wort ist immer einen Schritt vorraus; dadurch konnen wir sicherstellen, dass Ki+1 aus Ki

durch einen Schritt vom M entsteht.(x1, y1) = (#, #q0x#) Anfangsregel(a, a) a ∈ Γ ∪ {#}... KopierregelZustandsregeln:

δ(q, a) =

(q′, b, +1) ⇒ (qa, bq′)

(q′, b, 0) ⇒ (qa, q′b)

(q′, b,−1) ⇒(cqa, q′cb)

(#qa, #q′Bb)

δ(q, B) =

(q′, b, +1) ⇒ (q#, bq′#)

(q′, b, 0) ⇒ (q#, q′b#)

(q′, b,−1) ⇒(cq#, q′cb#)

(#q#, #q′Bb#)

Loschregeln:Wenn M in einen akzeptierenden Zustand q ∈ F gerat, dann

”frisst“ dieser Zustand den Bandinhalt

(qa, q)(aq, q)

}

∀q ∈ F, a ∈ Γ

Abschlusspaar:(q##, #) ∀q ∈ F

Satz: Das Post’sche Korrespondenzproblem ist unentscheidbar.

15


1.8.5 Andere unentscheidbare Probleme

• Losbarkeit von Polynomgleichungen uber Z. (Matijasevic, 1970)

x = 3y − z2

z2 + u3y − x4 = 0...

S sei eine Eigenschaft von formalen Sprachen L, die von einigen aber nicht von allen rekursiv aufzahlbarenerfullt wird:

Beispiele: Ist S = ∅?Ist S = {ε}?ε ∈ S?Ist S endlich?Ist S = {0n1n|n ≥ 1}

1.8.6 Satz von RICE (1953)

Satz: Fur jede nichttriviale Eigenschaft S (im obigen Sinn) ist das folgende Problem unentscheidbar:

Gegeben: Turingmaschine M .

Frage: Hat L(M) die Eigenschaft S?

Annahme: ∅ hat nicht Eigenschaft SEs gibt eine Sprache L+, die Eigenschaft S hat und eine Turingmaschine M+ mit L(M+) = L+ Wirreduzieren das spezielle Halteproblem Hε auf das Entscheidungsproblem fur S:

Gegeben: Turingmaschine MFrage: Halt M bei Eingabe ε?Wir konstruieren daraus eine neue Turingmaschine M ′ mit der Eigenschaft

L(M ′) hat Eigenschaft S ⇔M halt bei Eingabe ε

• M ′ bekommt die Eingabe x ∈ Σ∗

• M ′ simuliert zunachst M mit leerer Eingabe.• Wenn M halt, dann simuliert M ′ die M+ mit der Eingabe x, und akzeptiert genau dann,

wenn M+ akzeptiert.M ′ ist aus M berechenbar.Fall 1: M halt nicht bei Eingabe ε⇒M ′ halt nie ⇒ L(M) = ∅ ⇒ L(M) hat Eigenschaft S nicht.

Fall 2: M halt bei Eingabe ε⇒M ′ verhalt sich wie M+ ⇒ L(M) = L(M+) = L+ ⇒ L(M) hat Eigenschaft S.

Wenn ∅ die Eigenschaft S hat, dann betrachte die komplementare Eigenschaft S (”nicht S“).

16

2 Regulare Sprachen und endliche Automaten

2.1 Deterministische endliche Automaten

A = (Q, Σ, δ, q0, F )Ein (deterministischen) endlicher Automat (DEA) (engl.: deterministic finite automaton, DFA) hat:

• eine endliche Zustandsmenge Q

• ein endliches Eingabealphabet Σ

• eine Zustandsuberfuhrungsfunktion δ : Q× Σ→ Q

• einen Startzustand q0 ∈ Q

• eine Menge von akzeptierenden Zustanden F ⊆ Q

Arbeitsweise: Der Automat beginnt in q0 und liest in jedem Schritt das nachste Eingabesymbol und andertdenm Zustand gemaß δ. Er akzeptiert das Eingabewort, wenn er sich nach dem Lesen des letzten Buch-stabens in einem Zustand ∈ F befindet.

Beispiel:

Q = {q0, q1, q2, q3} Σ = {0, 1}

q0 = q0 F = {q3}

δ 0 1q0 q1 q2

q1 q0 q3

q2 q3 q0

q3 q2 q1

Zustandsdiagramm:

Eingabe: x =↑q0

0↑q1

0↑q0

1↑q2

1↑q0

0↑q1

0↑q0

1↑q2 /∈ F

/∈ L(A)

L(A) = die von A akzeptierte Sprache

= {x ∈ {0, 1}∗|x enthalt eine gerade Anzahl an 0en und eine ungrade Anzahl an 1en}

Wir erweitern δ : Q× Σ→ Q auf δ : Q× Σ∗ → Q

δ(q, ε) = q, (∀q ∈ Q)

δ(q, a1a2...an) = δ(δ(q, a1a2...an−1, an)), (n ≥ 1)

17

KAPITEL 2. REGULARE SPRACHEN UND ENDLICHE AUTOMATEN

Beispiel: δ(q2, 010) = q0 = δ(δ(δ(δ(q2, ε), 0), 1), 0)

L(A) = die von A akzeptierte Sprache

= {x ∈ Σ∗|δ(q0, x) ∈ F}

Kann ein DEA die Sprache L = {0n1n|b ≥ 0} akzeptieren?Wir betrachten δ(q0, 0), δ(q0, 00), δ(q0, 000), ... Nach hochstens |Q| Schritten muss sich ein Zustand wiederholen

∃i ≤ j : δ(q0, 0i) = δ(q0, 0

j)

δ(δ(q0, 0i), 1i) = δ(q0, 0

i1i) ∈ F

weil A das Wort 0i1i akzeptieren soll.

δ(q0, 0j1i) = δ(δ(q0, 0

j)︸︷︷︸

=δ(q0,0i)

, 1i) = δ(q0, 0i1i) ∈ F ⇒ A akzeptiert 0j1i

Definition: Die von DEA akzeptierten Sprachen heißen regulare Sprachen.

Andere Charakteresierungen von regularen Sprachen:

• regulare Ausdrucke

• NEA: nichtdeterministische endliche Automaten

• Typ-3-Grammatiken

2.2 Regulare Ausdrucke

Beispiele fur regulare Ausdrucke:(0 + 1)∗ (0∗ + 01∗)10(1∗)

Definition: regulare Ausdrucke sind induktiv folgendermaßen definiert.

1. ∅, ε, a fur a ∈ Σ, sind regulare Ausdrucke

2. Wenn A und B regulare Ausdrucke sund, dann sind auch

• (A) · (B)• (A) + (B)• (A)∗

regulare Ausdrucke.

Beispiele: ((0) + (1))∗ = {0, 1}∗

(((((0)∗) + ((0) · ((1)∗))) · (1)) · (0)) · ((1)∗)

Man verwendet folgende Vereinfachungsregeln:

1.) ∗ hat hochste Prioritat, dann ·, dann +

2.) Uberflussige Klammern kann man weglassen.

3.) · kann man weglassen

4.) Endliche Mengen kann man auch als {..., ..., ...} schreiben

Jeder regulare Ausdruck beschreibt eine Sprache:

• L(∅) = ∅

• L(ε) = {ε}

• L(a) = {a} fur a ∈ Σ

• L((A) · (B)) = L(A) · L(B)

• L((A) + (B)) = L(A) ∪ L(B)

18

2.2. REGULARE AUSDRUCKE

• L((A)∗) = (L(A))∗

Beispiel: 1∗(01∗01∗) = {x ∈ {0, 1}∗|Anzahl der Nullen ist gerade}

Satz: Jede regulare Sprache wird durch einen regularen Ausdruck beschrieben:

Beweis mit Kleene-Algorithmus: (Kleene, 1953) L = L(A) A = ({q1, q2, ..., qn}, Σ, δ, q1, F )

Lkij = Menge der Worter, die von qi nach qj fuhren, und dabei als Zwischenzustande (außer dem ersten

und letzen Zustand) nur die Zustande q1, q2, ..., qk

Lkij = {x1x2...xn|δ(qi, x1....xn) = qj , δ(qi, x1...xl) ∈ {q1, ..., qk} fur 1 ≤ l < n}

k = n... keine Einschrankung der Zwischenzustande

L(A) =⋃

qj∈F

Ln1j

k = 0... keine Zwischenzustande, nur direkten Ubergang

L0ij = {a ∈ Σ|δ(qi, a) = qj} i 6= j

L0ii = {a ∈ Σ|δ(qi, a) = qi} ∪ {ε}

Die Lkij konnen induktiv fur k = 0, 1, 2, ..., n definiert werden.

Lemma: Lkij = Lk−1

ij ∪ Lk−1ik (Lk−1

kk )∗Lk−1kj

Beweis:”⊇“ Lk−1

ij ⊆ Lkij nach Definition. Lk−1

ik (Lk−1kk )∗Lk−1

kj ... ein Wort aus dieser Sprache wird, beginnendin qi nur Zustande q1, ..., qk−1, qk besuchen und in qj enden.

”⊆“ Betrachte ein Wort x ∈ Lk

ij und die Folge der Zustande die der Automat beim Lesen von x, ausgehendvon qi besucht.

Fall 1: qk tritt nicht als Zwischenzustand auf ⇒ x ∈ Lk−1i j

Fall 2: Zerlege x in Bestandteile an jeder Stelle, wo der Zustand qk erreicht wird.

qi

qkqk qkqkqj

∈ Lk−1ik

∈ Lk−1kk

∈ Lk−1kj

x besteht aus einem Anfangsstuck ∈ Lk−1ik , beliebig vielen (≥ 0) Zwischenstucken ∈ Lk−1

kk und einem

Endstuck ∈ Lk−1kj

Wenn i = k oder j = k ist, dann kann man die Formel vereinfachen:

Beispiel: Lkik = Lk−1

ik · (Lk−1kk )

Lkkk = (Lk−1

kk )∗ Lkkj = ((Lk−1

kk )∗Lk−1kj

19


Durch Induktion nach k ergibt sich: Alle Sprachen Lkij sind durch regulare Ausdrucke darstellbar, und

sonst auch L(A). Schranke fur die Lange des Ausdrucks:

(|Σ|+ 1) · 4|Q| · |Q|

(beim Ubergang von k auf k + 1 wird die Lange hochstens mit 4 multipliziert.)

Der Algorithmus von Floyd-Warshall fur kurzeste Wege in Graphen beruht auf dem gleichen Prinzip.

2.3 Nichtdeterministische endliche Automaten

DEA → regularer Ausdruck↑ ↓

NEA ←− (NEA + ε)

Definition: Ein nichtdeterministischer endlicher Automat (NEA) (engl.: nondeterministic finite automaton,NFA) A = (Q, Σ, δ, q0, F ) ist ahnlich wie ein DEA, außer dass:

δ : Q× Σ→ 2Q(Potenzmenge von Q)

Wenn ein Automat sich im Zustand q ∈ Q befindet und das Symbol a ∈ Σ liegt, kann er in irgendeinem derZustande aus der Menge δ(q, a) gehen.

Hochdruckwetter Kalte

Gewitter

Gesund

Kopfweh

Gesund

Gesund

Kopfweh,Gesund

• Eine Berechnung des Automaten bei Eingabe von x = a1a2...an ∈ Σ∗ ist eine Folge(q0, a1, q1, a2, q2, ..., qn−1, an, qn) mit qi ∈ Q mit q0 = Anfangszustand und qi+1 ∈ δ(qi, ai+1) fur i =0, ..., n− 1.

• Eine akzeptierende Berechnung ist eine Berechnung mit qn ∈ F .

• Ein Wort x ∈ Σ∗ wird von A akzeptiert, wenn es eine akzeptierende Berechnung fur x gibt.

L(A) = Menge der akzeptierten Worter

→ q0 q1 q2 q3 q4

0,10 1 0 1

0,1

L(A) = {Worter, die 0101 enthalten} = (0 + 1)∗0101(0 + 1)∗

δ 0 1q0 {q0, q1} {q0}q1 ∅ {q2}q2 {q3} ∅q3 ∅ {q4}q4 {q4} {q4}

Beispiel: 010 0101 0010000 wurde akzeptiert werden, 011110000111 /∈ L(A) jedoch nicht.Ein DEA entspricht dem Spezialfall wo |δ(q, a)| = 1 fur alle q und a.

Ursprunglicher Formalismus Alternativer Formalismusδ : Q× Σ→ 2Q δ ⊆ Q× Σ×Q (dreistellige Relation)

q′ ∈ δ(q, a) (q, a, q′) ∈ δ

20

2.3. NICHTDETERMINISTISCHE ENDLICHE AUTOMATEN

Konstruktion eines aquivalenten DEA A′ = (Q′, Σ, δ′, q′0, F′) zu einem gegebenen NEA A = (Q, Σ, δ, q0, F )

(Potenzmengenkonstruktion)

Q′ = 2Q q′0 == {q0}δ′ : Q′ × Σ→ Q′ F ′ = {q′ ∈ Q|q′ ∩ F 6= ∅}δ′(q′, a) =

⋃

q∈q′

δ(q, a)

Behauptung: L(A′) = L(A)

δ′({q1, q2}, 0) = δ(q1, 0) ∪ δ(q2, 0)

= ∅ ∪ {q3} = {q3}

δ′({q0, q1, q4}, 0) = δ(q0, 0) ∪ δ(q1, 0) ∪ δ(q4, 0)

= {q0, q1} ∪ ∅ ∪ {q4} = {q0, q1, q4}

F ′ = {q′ ∈ {q0, q1, q2, q3, q4}|q4 ∈ q′}

Beweis: δ′(q′0, a1a2...ak) = {q ∈ Q | es gibt eine Berechnung fur a1...ak die im Zustand q0 beginnt und in qendet.} =

”mogliche Zustande nach Lesen der ersten k Eingabezeichen.

Beweis durch Induktion nach k.

In der Praxis beginnt man mit q′0 = {q0} und erzeugt nur diejenigen Zustandsmengen, die von q0 erreichbarsind.

q′ 0 1q′0 {q0} {q0, q2} {q0}q′1 {q0, q1} {q0, qq} {q0, q2}q′2 {q0, q2} {q0, q1, q3} {q0}q′3 {q0, q1, q3} {q0, q1} {q0, q2, q4}q′4 {q0, q2, q4} {q0, q1, q3, q4} {q0, q4}q′5 {q0, q1, q3, q4} {q0, q1, q4} {q0, q2, q4}q′6 {q0, q4} {q0, q1, q4} {q0, q4}q′7 {q0, q1, q4} {q0, q1, q4} {q0, q2, q4}

q1 q2

→ q0 q3

q7 q4

q6 q5

1

0

0

1

1

0

0

1

10

1

10

0

00

L = {Worter, deren 4-letzter Buchstabe eine 1 ist}

→ q0 q1 q2 q3 q4

0,11 0,1 0,1 0,1

⇒ NEA hat k + 1 ZustandeJeder DEA benotigt mindestens 2k−1 Zustande

21


2.4 NEA mit ε-Ubergangen

Unterschied: δ : Q× (Σ ∪ {ε})→ 2Q

Der Automat kann auch, statt einen Buchstaben zu lesen, einen ε-Ubergang durchfuhren. Eine akzeptierendeBerechnung fur x ∈ Σ∗ ist eine Folge (q0, b1, q1, b2, q2, ..., qk) mit q0 = Startzustand,

bi ∈ Σ ∪ {ε}, qi ∈ δ(qi−1, bi), x = b1b2...bk, qk ∈ F

Satz: Zu jedem regularen Ausdruck S, gibt es einen NEA A mit ε-Ubergangen und einem einzigen akzep-tierenden Zustand mit L(A) = L(S)

Beweis: Induktion nach der Struktur von S

S = a ∈ Σ → a

S = ∅ →

S = ε →ε

S = S1 + S2 →A1

A2

εε

εε

L(A) = L(A1) ∪ L(A2)

S = S1 · S2 → A1 A2ε L(A) = L(A1) · L(A2)

S = (S1)∗ → A1

εL(A) = L(A1)

∗

DEA regulare Ausdrucke

NEA NEA mit ε-Ubergangen

Potenzmengenkonstruktion

Kleene-Algorithmus

Elimination von ε-Ubergangen

2.4.1 Elimination von ε-Ubergangen

Idee: Zusammenpacken einer Folge von ε-Ubergangen mit dem nachfolgenden Ubergang wo ein Buchstabegelesen wir, in einem einzigen Ubergang.

→ q1 q2

q5

q3 q4

ε, 1

1

0

0

ε, 0

ε, 0

0

ε

1

1

0

22

2.5. MINIMIERUNG DETERMINISTISCHER ENDLICHER AUTOMATEN

δ′(q1, 0) = {q3, q5, q1, q4}F′ = {q1, q2, q3, q5}

Gegeben: A = (Q, Σ, δ, q0, F )δ : Q× (Σ ∪ {ε})→ 2Q

neuer Automat: A′ = (Q, Σ, δ′, q0, F′) ohne ε-Ubergange

δ′(q, a) = {r ∈ Q | r kann im Automaten A von q aus durch eine Folge von k ≥ 0 ε-Ubergangen, undeinen Ubergang wo a gelesen wird, erreicht werden. }F ′ = {q ∈ Q | Von q aus kann der Automat A in k ≥ 0 ε-Ubergangen einen akzeptierenden Zustand r ∈ Ferreichen }

Der Automat A′ kann jede akzeptierende Berrechnung von A durch eine akzeptierende Berechnung ohne ε-Ubergangen

”simulieren“ und umgekehrt.

Berechnung der Menge Rε(q) = { Zustande, die von q aus durch ε-Ubergange erreichbar sind. }

R := {q}; ...Ergebnismenge

Q := {q}; ...Liste der zu bearbeitedenden Zustande

while !isEmpty(Q)entferne einen Zustand r aus Qforall s aus delta(r, epsilon):

if !(s aus R) thenR := R + {s}Q := Q + {s}

→ q0 q1

q4

q2 q3

ε

ε

ε

ε

δ′(q, a) =⋃

r∈Rε(q)

δ(r, a)

Beispiel: δ′(q1, 0) = δ(q1, 0) ∪ δ(q2, 0) ∪ δ(q3, 0) ∪ δ(q5, 0)F ′ = {q|Rε(q) ∩ F 6= ∅}

2.5 Minimierung deterministischer endlicher Automaten

→ a b c d

e f g h

0

1

0

1

01

0

1

0

1

0

1

01

0

1

23


1. Entfernen unerreichbarer Zustande: Zustande die nicht von q0 erreichbar sind

→ a b c

e f g h

0

1

0

1

01

0

1

0

1

01

0

1

2. Zusammenfassen von aquivalenten Zustanden. Zwei Zustande heißen aquivalent, wenn es keine Rolle spielt,in welchem der beiden Zustande man ist.

q ≡ rdef⇐⇒ ∀x ∈ Σ∗; δ(q, x) ∈ F ⇔ δ(r, x) ∈ F

q 6≡ r ⇐⇒ ∃x ∈ Σ∗; δ(q, x) ∈ F ⊕(XOR)

δ(r, x) ∈ F

︸︷︷︸

(∗)

Der Algorithmus beginnt mit einer ganz groben Klasseneinteilung in zwei Klassen Q = F ∪ (Q−F ). DieseKlasseneinteilung wird nach und nach verfeinert, wenn sich herrausstellt, dass Zustande in der gleichenKlasse nicht aquivalent sind.

Invariante: Wenn q und r nicht in derselben Klasse sind, dann gilt (∗):

∃x ∈ Σ∗ : (δ(q, x) ∈ F ∧ δ(r, y) /∈ F ) ∨ (δ(q, x) /∈ F ∧ δ(r, x) ∈ F )

Beispiel: Q = {a} ∪ {b, c, e, f, g, h} = K1 ∪K2

δ(b, 0) = g ∈ K2

δ(c, 0) = a ∈ K1

δ(e, 0) = h ∈ K2

δ(f, 0) = c ∈ K2

δ(g, 0) = g ∈ K2

δ(h, 0) = g ∈ K2

⇒ c unterscheidet sich vom Rest, da δ(c, 0) ∈ K1 ∧ δ({b, e, f, g, h}, 0)Zerlege K2 = A ∪B, je nachdem in welche (bisherige) Klasse δ(q, 0) istK2 = {c} ∪ {b, e, f, g, h}

neue Klasseneinteilung: Q = {a}K1

∪ {c}K2

∪ {b, e, f, g, h}K3

δ(b, 0) ∈ K3

δ(e, 0) ∈ K3

δ(f, 0) ∈ K2

δ(g, 0) ∈ K3

δ(h, 0) ∈ K3

Zerlege K3 = {f} ∪ {b, e, g, h}

Neue Zerlegung: Q = {a}K1

∪ {c}K2

∪ {f}K3

∪ {b, e, g, h}K4

δ(b, 0) ∈ K4

δ(e, 0) ∈ K4

δ(g, 0) ∈ K4

δ(h, 0) ∈ K4

24

2.5. MINIMIERUNG DETERMINISTISCHER ENDLICHER AUTOMATEN

δ(b, 1) = c ∈ K2

δ(e, 1) = f ∈ K3

δ(g, 1) = e ∈ K4

δ(h, 1) = c ∈ K2

Zerlege K4 = {e} ∪ {g} ∪ {b, h}

Neue Zerlegung: Q = {a}K1

∪ {c}K2

∪ {e}K3

∪ {f}K4

∪ {g}K5

∪ {b, h}K6

δ(b, 0) ∈ K6

δ(h, 0) ∈ K6

δ(b, 1) ∈ K3

δ(h, 1) ∈ K3

Es ergibt sich keine weitere Verfeinerung

→ a {b, h} c

e f g

0

1 0

1

0

1

0

1

0

1

0

1

a 6≡ c wenn x = ε

h 6≡ g weil δ(h, 1) = c, δ(g, 1) = e und c 6≡ e

c 6≡ e weil δ(c, 0) = a, δ(e, 0) = h und h 6≡ a

h 6≡ a weil h /∈ F, a ∈ F

h 6≡ g weil δ(h, 10) ∈ F, δ(g, 10) /∈ F

2.5.1 Algorithmus zur Bestimmung des Minimalautomaten:

• Beginne mit der Terlegung Q = K1 ∪K2 in zwei Klassen

K1 = F

K2 = Q− F

Q = K1 ∪K2 ∪ ... ∪Kj

Solange es zwei Zustande q, r in derselben Klasse Ki gibt und einen Buckstaben a ∈ Σ mit:

Klasse δ(q, a) gehort (q ∈ Ki)

Abbruchbedingung: ∀Ki∀q, r ∈ Ki, ∀a ∈ Σ: δ(q, a) und δ(r, a) gehoren zur gleichen Klasse.

Zustande des neuen Automaten: {K1, ..., Kj}δ′(Ki, a) = KLasse, zu der δ(q, a) gehort, fur irgendein q ∈ Ki (unabhangig von der Wahl von q).

Satz: Zu jedem DEA (zu jeder regularen Sprache) gibt es einen eindeutig bestimmten (eindeutig bis aufBennenung der Zustande) Minimalautomaten, der die gleiche Sprache akzeptiert.

• Dieser hat unter allen aquivalenten DEA’s die kleinste Anzahl von Zustanden.

• Der Minimalautomat kann in O(|Q|2 · |Σ|) Schritten berechnet werden.

25


[l]Q = {q1, q2, q3} ∪ {q4, q7} ∪ {q5} ∪{q6}

δ(q1, 0)δ(q2, 0)δ(q3, 0)

in der selben Klasse?

δ(q1, 1)δ(q2, 1)δ(q3, 1)

?

ein Verfeinerungsschritt O(|Q| · |Σ|)

Man kann hochstens (|Q| − 1)-mal verfeinernZusatzlich: Verwalten der Kalssen Einteilung

q1 1

q2 1

q3 1

q4 2

q5 3

q6 4

q7 2

Entfernen der unerreichbaren Zustande O(|Q| · |Σ|)Es geht auch in O(|Q| · log |Q| · |Σ|) Zeit, Hopcroft:Die Nerode-Relation bezuglich einer Sprache L.

Definition: Zwei Worter u und v heißen Nerode-aquivalent, wenn

u ≡L vdef⇐⇒ ∀x ∈ Σ∗: ux ∈ L⇔ vx ∈ L

Diese Relation ist eine Aquivalenzrelation. Daher konnen wir die Aquivalenzklassen [u]L = {v ∈ Σ∗ | v ≡L u}bilden.

2.5.2 Satz von Nerode

Satz: Eine Sprache L ist genau dann regular, wenn die Nerode-Relation endlich viele Aquivalenzklassen hat.Die Anzahl der Aquivalenzklassen ist in diesem Fall die Anzahl der Zustande des Minimalautomaten.

Beweis:”⇒“

L = L(A) fur DEA A = (Q, Σ, δ, q0, F )Wenn δ(q0, u) = δ(q0, v) dann u ≡L v

∀x ∈ Σ∗: ux ∈ L ⇔ δ(q0, ux) ∈ F

⇔ δ(δ(q0, u), x) ∈ F

⇔ δ(δ(q0, v), x) ∈ F

⇔ δ(δ(q0, vx) ∈ F ⇔ vx ∈ L

Folgerung: ≡L hat hochstens |Q| Aquivalnzklassen. Jeder DEA hat mindestens so viele Zustande, wie ≡L

Aquivalenzklassen hat.

Beispiel:

L = {x ∈ {0, 1}∗ | k-letzter Buchstabe ist eine 1, |x| ≥ k}

= Σ∗ · 1 · Σk−1

Behauptung: u, v ∈ Σk, u 6= v u 6≡L v⇒ ≡L hat mindestens 2k Aquivalenzklassen.

xu = 1000100100000 /∈ Lv = 1000110100000 ∈ L

Beweis der Behauptung: u 6= v unterscheiden sich in der i-ten Position, o. B. d. A. u hat dort eine 0, vhat dort eine 1.Fur x = 0i−1ux /∈ L, vx ∈ L

26

2.6. DAS PUMPING-LEMMA FUR REGULARE SPRACHEN

Beweis:”⇐“

[u1]L [u2]L , ..., [uk]L seine Aquivalenzklassen von ≡L

Q = {[u1]L [u2]L , ..., [uk]L}

Σ

δ([ui]L , a) = [uia]Lq0 = [ε]LF = {[ui]L | ui ∈ L}

zu zeigen:

1) Dieser Automat ist wohldefiniert :Das Ergebnis von δ, die Menge F hangt nicht davon ab, welcher Representant ui aus der Aquivalenz-klasse [ui]L gewahlt wird.δ : v ≡ ui([v]L = [ui]L)⇒ [va]L = [uia]L ⇔ va ≡L uiav ≡L ui, a ∈ Σ⇒ va ≡L uia

∀x ∈ Σ∗: vax ∈ L⇔ uiax ∈ L

∀y ∈ Σ∗: vy ∈ L⇔ uiy ∈ L ↑ y = a · x

def

F : z.z. [[ui]L] ≡ [v]L︸︷︷︸

⇔ui≡Lv

⇒ (ui ∈ L⇔ v ∈ L)

⇔ ∀x ∈ Σ∗: (uix ∈ L⇔ vx ∈ L)⇒ Fur x = ε: ui ∈ L⇔ v ∈ L

2) Der Automat akzeptiert L.

Behauptung: δ(q0, x) = [x]LBeweis durch Induktion nach |x|IA: |x| = 0 x = ε

δ(q0, ε) = q0!=X

[ε]L

IS: x = y · a a ∈ Σ, fur y ist die Aussage bewiesen. δ(q0, x) = δ(q0, ya) = δ(δ(q0, y), a) =δ([y], a) = [ya] = [x]Weil Definition von δ unabhangig von der Wahl des Representanten y in der Klasse [y] ist.

2.6 Das Pumping-Lemma fur regulare Sprachen

Fur jede Regulare Sprache L gibt es eine n0 ∈ N (∀L ⊆ Σ∗: L regular ⇒ ∃n0 ∈ N).

∀x ∈ L: |x| ≥ n0∃u, v, w ∈ Σ∗: x = u · v · w, v 6= ε, ∀i ≥ 0: u · vi · w ∈ L, |uv| ≤ n0︸︷︷︸

Sogar diese starkere Aussage gilt

In Worten: In einer rgularen Sprache hat jedes genugend lange Wort eine Stelle, an der man”pumpen“ kann.

Das Lemma wird in der Regel dazu verwendet, um zu zeigen, dass eine Sprache nicht regular ist.

Beispiel: L = {0n1n | n ≥ 1} nicht regular.

Annahme: L ware regular ⇒ Pumping-Lemma ist anwendbar∃n0: Wahle x = 0n01n0

∃x = uvw, v 6= ε, sodass ∀i: uviw ∈ L

Fall 1: v enthalt nur Einsen uv0w enthalt weniger Einsen als Nullen.⇒/∈ L Widerspruch

00001︸︷︷︸

u

11︸︷︷︸

v

1︸︷︷︸

w

00001|1 i = 0

00001111 i = 1

00001 1111︸︷︷︸

v2

1 i = 2

... ∈ L

27


Fall 2: v enthalt nur Nullen ...Fall 3: v enthalt Nullen und Einsen

uv2w = u v︸︷︷︸

001

v︸︷︷︸

001

w enthalt Einsen, die vor Nullen stehen. ⇒/∈ L

L = {0n1n | n ≥ 1} ist nicht regular

n0 0n20 = uvw uviw

︸︷︷︸

0n0+(i−1)·|v|

∈ L

Die Langen der Worter uviw bilden eine arithmetische Folge mit Abstand |v| ≤ n20

Abstand zwischen zwei Quadratzahlen:

(n20 + 1)2 − (n2

0)2 =

��(n20)

2 + 2(n20) + 1− (n2

0)2 = 2n2

0 + 1 > n20

++ + + ++++ + + +

> n20

Es gibt ein Wort uviw, dessen Lange (n20)

2 < |uviw| < (n20 + 1)2 ist. ⇒ Widerspruch

Beweis: L sei regular (L ∈ L3), A... DEA mit L(A) = Ln0 := |Q||x| ≥ 0x = x1x2....xn

q0

Betrachte die Zustande:

δ(q0, ε) = q0

δ(q0, x1)δ(q0, x1x2)

...δ(q0, x1x2...xn0)

Ein Zustand q′ muss mehrfach vorkommen

q0 q′u

v

∃0 ≤ i < j ≤ n0 : δ(q0, x1...xi) = δ(q0, x1...xj)︸︷︷︸

δ(δ(q0, x1...xi)︸︷︷︸

q′

,xi+1...xJ)=q′=q′

δ(q′, xi+1...xj) = q′

28

2.7. ABSCHLUSSEIGENSCHAFTEN REGULARER SPRACHEN

u = x1...xi

v = xi+1...xj 6= ε

w = xj+1...xn

∀i ≥ 0: δ(q0, uviw) = δ(q0, uvw︸︷︷︸

x

) ∈ F

L = {01} n0 = 3 L = {0i1j2

| i ≥ 0, j ≥ 0}

⊲ q0 ·0 1

2.7 Abschlusseigenschaften regularer Sprachen

Satz: Die regularen Sprachen sind abgeschlossen gegenuber Vereinigung, Durchschnitt, Produkt, *-Operation,Umkehrung, Komplement, Substitution mit regularen Sprachen, Homomorphismen und inverse Homo-morphismen.D. h. z. B.: L1, L2 ∈ L3 ⇒ L1 ∪ L2 ∈ L3

Beweise: • Vereinigung, Produkt, *-Operation: regulare Ausdrucke X

• Komplement:Wenn L regular ist, dann ist auch L = Σ∗ − L regular.

Beweis: DEA A = (Q, Σ, δ, q0, F ) akzeptiert LA′ = (Q, Σδ, q0, Q− F ) akzeptiert L �

• Umkehrung (alle Worter von hinten nach vorne gelesen)regulare Ausdrucke Bsp.: (a + b)(ab)∗a∗b∗ → b∗a∗(ba)∗(a + b)

Beispiel: k-te Buchstabe von rechts = 1 DEA benotigt 2k Zustandek-te Buchstabe von links = 1 DEA kommt mit k + 2 Zustande aus.

• Durchschnitt: L1 ∩ L2 = L1 ∪ L2

• Durchschnitt, Vereinigung mit DEA

”Produkt zweier Automaten“ (Ubung)

Anwendungsbeispiel L = {x ∈ {0, 1}∗ | x enthalt gleich viele Einsen und Nullen}L′

nicht regular= L ∩ 0∗1∗ = {0n1n |n ≥ 0}

nicht regular

• Homomorphismus

Definition: Ein Homomorphismus h zwischen Σ∗ und Γ∗ ist eine Abbildung h : Σ∗ → Γ∗ mit derEigenschaft

h(x, y) = h(x) · h(y) (∀x, y ∈ Σ∗)

Ein Homomorphismus ist durch eine beliebige Abbildung h : Σ∗ → Γ∗ eindeutig gegeben (Σ∗ =Γ∗) ist nicht ausgeschlossen.

Beispiel:

h(a) = 01 h(abaabaab) = 0101010101

h(b) = ε

h(c) = 01

h(x1...xn) = h(x2) · h(x2) · ... · h(xn) xi ∈ Σ

• Substitution

Definition: Bei einer Substitution σ wird ein Buchstabe a ∈ Σ durch die Sprache σ(a) ersetzt.Substution ist gegeben durch die Abbildung σ : Σ→ 2Γ∗

σ(L) = {y | y ∈ σ(x1) · σ(x2)σ(x3)...σ(xn), x1x2x3...xn ∈ L}

29


Beispiel: L = (01)∗

σ(0) = {a}σ(1) = {b, c}σ(L) = {ababab, ababac, ac, abacacab, ε, ...}= (a(b + c))∗

——σ(0) = aσ(1) = ab∗bσ(L) = {aabbbbbaabaabbbb, ...}= σ(a(ab∗b))∗ = (aab∗b)∗

Satz: L ⊆ Σ∗ regularσ(a), a ∈ Σ seien regular ⇒ σ(L) regularSpezialfall: |σ(a)| = 1... Homomorphismus.

Beweis: requlare AusdruckeR: regularer Ausdruck fur L, Ra regularer Ausdruck fur σ(a), a ∈ ΣErsetze in R jedes Vorkommen eines Buchstaben a ∈ Σ durch Ra

• inverse Homomorphismenh : Σ∗ → Γ∗ Homomorphismus

Satz:(L ⊆ Γ∗) ∈ L3 ⇒ h−1 := {x ∈ Σ∗ | h(x) ∈ L} ∈ L3

Beispiel: h(a) = 0h(b) = 10abaab

Beweis: DEA A = (Q, Γ, δ, q0, F )

⊲

1a, b0b

1 0a0, 1 a b b

0

a b

neuer DEA A′ = (Q, Σ, δ′, q0, F )δ′(q, x) = δ(q, h(x)), x ∈ Σ

2.8 Zusammenfassung: regulare Sprachen

• DEA, NEA: Uberprufen ob x ∈ L

• NEA, regulare Ausdrucke: Erzeugen der Worter aus L

30

3 Grammatiken

3.1 Definition von Grammatiken

Beispiel: in Programmiersprachen; arithmetische Ausducke:

• Zahlen und Variablen sind arithmetische Ausdrucke

• wenn A und B arithmetische Ausdrucke, dann sind auch A+B, A−B, A∗B, A/B, (A) arithmetischeAusdrucke

S → V, S → Z, S → (S) S,→ S + S,

S → S − S, S → S ∗ S, S → S/S,

Z → U, Z → U,

U → 0, U → 1, ..., U → 9

⇒U → 0|1|...|9

B → B, V ′ → V ′B, V ′ → V ′U

B → a, B → b, B → c, ...

⇒B → a|b|c|...

Σ = {(, ), +,−, ∗, /, 0, 1, ..., 9, a, b, c, ...}

V = {S, V ′, Z, U, B}

Beispiel: 5 + (13 ∗ 2) ∈ L(G) 3 ∗ (−4) /∈ L(G)S → S + S → Z + S → U + S → 5 + S → 5 + (S) → 5 + (S ∗ S) → 5(S ∗ Z) → 5 + (Z ∗ Z) →5 + (UZ ∗ Z)→ 5 + (UU ∗ Z)→ 5 + (1U ∗ U)→ 5 + (13 ∗ U)→ 5 + (13 ∗ 2)

Definition: Eine Grammatik G besteht aus:

• einer Menge V aus Variablensymbolen

• einer Menge Σ aus Terminalsymbolen (Σ ∩ V = ∅)

• einer Menge P von Ersetzungsregeln (Produktionen), P ∈ V + × (V ∪ Σ)∗ V + = V ∗ − {ε}

• einem Startsymbol S ∈ V

Worter aus (V ∪ Σ)∗ nennt man auch Satzformen.

u ∈ (V ∪Σ)∗, wenn v aus u dadurch entsteht, dass man ein Vorkommen einer linken Seite (Pramisse) x einerRegel (x, y) ∈ P durch die rechte Seite (Konklusion) ersetzt, dann schreibt man u→ {ε}

v ist aus u in einem Schritt ableitbar.

u→ v ⇔ ∃(x, y) ∈ P, ∃u1, u2 ∈ (Σ ∪ V )∗ : u = u1xu2 ∧ v = u1yu2

Wenn v aus u in k ≥ 0 Schritten abgeleitet werden kann, dann schreibt man u∗→ v:

∃v0, v1, ..., vk : u = v0 → v1 → v2 → ...→ vk = v︸︷︷︸

eine Ableitung

Definition: Die von einer Grammatik G = (V, Σ, P, S) beschriebene Spache L(G) ist

L(G) = {x ∈ Σ∗ | S∗→ x}

31

KAPITEL 3. GRAMMATIKEN

3.2 Die Chomsky-Hierarchie

Nach Noam Chomsky (zeitgenossischer Linguist)

• Typ-0-Grammatiken: beliebige Grammtiken

• Typ-1-Grammatiken: monotone bzw. kontext-sensitive Grammtiken

P ⊆ {(x, y) | x ∈ V +, y ∈ (Σ ∪ V \ {S})∗, |x| ≤ |y|} ∪ {(S, ε)}

D. h. die Konklusionen der Regeln sind mindestest so lang wie die Pramissen.

• Typ-2-Grammatiken: kontextfreie Grammatiken

P ⊆ V × (Σ ∪ V )∗

• Typ-3-Grammatiken: rechtslineare Grammatiken

P ⊆ V × (ΣV ∪ {ε})

Beispiel:

S → aT |bS

T → +V

T → ε

Die beschriebenen Sprachen dieser Grammatiken entsprechen den regularen Sprachen (es gibt auch linkslin-eare Grammatiken)

Entsprechend gibt es Typ-0-Sprachen, Typ-1-Sprachen, ...L0,L1,L2,L3 seien die Typ-0-Sprachen, Typ-1-Sprachen, ...

trivial

L3regular

⊂6=

L2kontextfrei

⊂6=

L1kontextsensitiv

⊂6=

L0rekursiv aufzahlbar

L= {0n1n} L= {0n1n0n} Die Sprachen aus L1 sind entscheidbar

3.3 Typ-0-Sprachen (rekursiv aufzahlbare Sprachen)

Satz: Typ-0-Sprachen sind genau die rekursiv aufzahlbaren Sprachen.

Beweis:”⇒“ G = (V, Σ, S, P ) sei gegeben, x ∈ Σ∗. Ist x ∈ L(G)?Algorithmus: Probiere alle Ableitungen der Lange k systematisch durch und prufe, ob dabei x her-auskommt, fur k = 0, 1, 2, 3, ....Dieser Algorithmus akzeptiert gdw. x ∈ L(G) (andernfalls kann er nicht terminieren). �

”⇐“ Gegeben TM M = (Q, Σ, δ, Γ, q0, B, F )

Idee: q0x ⊢ k1 ⊢ k2 ⊢ ... ⊢ k2

Simulation durch G: x← $q0x#← ......← $kn−1#← $kn#← ......← S

V = Q ∪ {$, #} ∪ {Va | a ∈ Γ}︸︷︷︸

neue Variablen, die dem Bandalphabet entsprechen

∪{S}

Produktionen P :

δ(q, a) = (q′, b, 0) ⇒ q′Vb → qVa

δ(q, a) = (q′, b, +1) ⇒ Vbq′ → qVa

δ(q, a) = (q′, b,−1) ⇒ q′VcVb → VcqVa, ∀c ∈ Γ

32

3.4. TYP-3-SPRACHEN (REGULARE SPRACHEN)

Anfangsregeln: Erzeuge eine beliebige Konfiguration mit einem akzeptierenden Zustand und genugendvielen B-Symbolen rechts und links.

S → $T#

T → TVa|VaT, ∀a ∈ Γ

T → q, ∀q ∈ F

Endregeln: B-Symbole an den Randern loschen, $, # loschen, Symbole Vx in Terminalsymbole xuberfuhren, q0 loschen

VB#→ #, #→ ε

$VB → $, $q0 → ε

Vx → x, x ∈ Σ

Jede akzeptierende Berechnung fur w ∈ Σ∗ kann in eine Ableitung von w transformiert werden.

Jede Ableitung eines Wortes x entspricht einer akzeptierenden Berechnung. �

3.4 Typ-3-Sprachen (regulare Sprachen)

Satz: Typ-3-Sprachen sind genau die regularen Sprachen

Beispiel:

S → aT |bS V = {S, T }

T → bT |bS|aS|ε Σ = {a, b}

S → aT → abS → abbS → abbaT → abbabT → abbab︸︷︷︸

∈L(G)

Beweis:”⇐“ Gegeben: DEA (bzw. NEA) A = (Q, Σ, δ, q0, F )Gesucht: Typ-3-Grammatik fur L(A)

G : V = QΣ = Σ

q q′ q → aq′a

P = {q → aq′ | q ∈ Q, a ∈ Σ, q′ = δ(q, a)q′∈δ(q,a)

} ∪ {q → ε | q ∈ F}

S = q0

”⇒“ Gegeben: G = (V, Σ, P, S)

Gesucht: NEA A mit L(A) = L(G)

A : Q = VΣ = Σδ(q, a) = {q′ | (q → aq′) ∈ P}F = {q ∈ V | (q → ε) ∈ P}q0 = S Zustande des Automaten entsprechen den Variablen der Grammatik.Berechnungen des Automaten werden durch Ableitungen der Grammatik dargestellt und umgekehrt.

L = {0n1n|n ≥ 0} ist keine Typ-3-Sprache, aber sie ist eine Typ-2-Sprache

G: S → 0S1|ε

S → 0S1→ 00S11→ 000S111→ 000111

33

KAPITEL 3. GRAMMATIKEN

3.5 Typ-1-Sprachen (kontextsensitive Sprachen)

Bei alle Regeln ist die Konklusion mindestens so lang wie die Pramisse.Ausnahme: S → ε ist erlaubt, S darf jedoch in keiner Konklusion vorkommen.

Folgerung: in einer Ableitung konnen die Satzformen nicht schrumpfen, außer bei der Ableitung S → ε, aberdiese Ableitung ist in einem Schritt zu Ende.

Beispiel: V = {S, T, U, W, V0, V1}Σ = {0, 1}S → ε|V0TV1V0|010

T → V0V1U UV1 → V1U UV0 →WV0V0|00 V1W →WV1 V0W → V0T

V0 → 0 V1 → 1 V1W →WV1 U1→ 1U UV1 → V1U

S∗→ 0T 10→ 001U10∗→ 0011U0→ 0011W00∗→ 00W1100→ 00T 1100∗→ 000W111000

∗→ 00001111U000

→ 000011110000

L(G) = {0n1n0n | n ≥ 0}

Bemerkung: Man kann die Regeln einer kontextsensitiven Grammatik in die Form bringen, dass immer nureine einzelne Variable durch etwas Neues ersetzt wird.

z. B. ABA︸︷︷︸

Kontext

C A︸︷︷︸

Kontext

→ ABAA01DA

Beispiel: Regel ABC → BAD neue Variablen X1, X2, X3, ...wird ersetzt durch:

ABC → X1BC X1X2X3 → BX2X3

X1BC → X1X2C BX2X3 → BAX3

X1X2C → X1X2X3 BAX3 → BAD

Satz: Typ-1Sprachen sind entscheidbar.

Beweis: G... Gramatik, x ∈ Σ∗

Frage: x ∈ L(G) (auch bekannt als das Wortproblem)Wenn x = ε x ∈ L(G)⇔ (S → ε) ∈ PAndernfalls konnen in der Ableitung von x nur Satzformen auftreten, die hochstend so lang wie x.

M = {y ∈ (V ∪Σ)∗ | |y| ≤ |x|, S∗→ y, y 6= ε}

M kann folgendermaßen induktiv konstruiert werden:

Beginne mit M := {S}S c h l e i f e :∀y ∈M : ∀z ∈ (V ∪ Σ∗): y → z, |z| ≤ |x| .

M := M ∪ {z}wiederho le , s o l ange neue Elemente zu M dazugekommen s ind .

|M | ≤|x|∑

i=1

(|Σ|+ |V |)i endlich. Daher muss die Schleife irgendwann terminieren

x ∈ L(G)⇔ x ∈M �

34

4 Kontextfreie Sprachen (Typ-2-Sprachen)

4.1 Tiefenstruktur von Sprachen

Das Wetter war gestern regnerisch.

Satz

Subjektgruppe

Nominalgruppe

Artikel

”das“

Hauptwort

”Wetter“

Pradikatgruppe

Verb

”war“

Adverb

”gestern“

Pradikat

Adjektiv

”regnerisch“

Bei einer kontextfreien Grammatik wird bei der Syntaxanalyse ein solcher”Syntax-Baum“ aufgebaut.

Gestern hat | es︸︷︷︸

Subjekt

| geregnet.

(Im Deutschen kann das Pradikat zerlegt werden ⇒ Analyse kann sehr schwer sein!)

4.2 Dyck-Sprache

D1 S → SS | (S) | ε

S → SS → (S)S → (SS)S → ((S)S)S → (()S)S → (()(S))S → (()())S∗→ (()())((S))→ (()())(()) ∈ D1

())(() /∈ D1

Klammertiefe:

Dyck-Weg

b

b

b

b

b

b

b

b

b

b

( ( ) ( ) ) ( ( ) )

Definition: Der Weg mit n Schritten nach oben ր und n Schritten nach unten ց, der oberhalb der x-Achsebleibt wird Dyck-Weg genannt.

35

KAPITEL 4. KONTEXTFREIE SPRACHEN (TYP-2-SPRACHEN)

D2 S → SS | (S) | [S] | ε

⇒ ([()()])[] ∈ D2

Dk... k verschiedene Klammerpaare.

L = {x ∈ {a, b}∗ | x enthalt gleich viele as wie bs}

ba

ba

bb

bb

ba

bb

bb

bb

ba

bb

ba

ba

ba

bb

S → SS|ε|aPb|bNa

P → PP |aPb|ε

N → NN |bNa|ε

P...”positive“ Dyck-Worter (= a, ) = b

N...”negative“ Dyck-Worter ) = a, (= b

4.3 Kontextfreie Grammtiken als Gleichungssysteme

Man kann eine kontextfreie Grammatik auch als Gleichungssystem, dessen Losungen unbekannte Sprachen sindinterpretieren

VS = VS · VS ∪ {ε} ∪ a · Vp · b ∪ b · Vn · a

VP = VP · VP ∪ a · VP · b ∪ {ε}

VN = VN · VN ∪ b · VN · a ∪ {ε}

VS , VP , VN sind”unbekannte“ Sprachen.

VS = {x ∈ Σ∗ | S∗→ x} = L

VP = {x ∈ Σ∗ | P∗→ x}

VN = {x ∈ Σ∗ | N∗→ x}

sind eine Losung des Gleichungssystems (nicht unbedingt eindeutig).

S

S

( S

S

( S

ε

)

S

( S

ε

)

)

S

( S

( S

ε

)

)

36

4.4. EINDEUTIGKEIT

Rechtsableitung: S → SS → S(S) → S((S)) → S (()) → (S)(()) → (SS)(())∗→ (()())(()) entspricht der

bottom-up-Syntaxanalyse

Linksableitung: S → SS → (S)S → (SS)S → ((S)S)S → (()S)S → (()(S))S → (()())S∗→ (()())((S)) →

(()())(()) entspricht der top-down-Syntaxanalyse

Die Beliebigkeit bei der Auswahl, welche Variable be einer Ableitung als nachstes ersetzt wird, kann auf dreiArten aus der Welt geschafft werden:

1. Linksableitung: Es wird immer die linkeste Variable ersetzt

2. Rechtsableitung: Es wird immer die rechteste Variable ersetzt

3. Syntaxbaum: Wurzel = S, Kinder einses Variablenknotens sind die Symbole auf der rechten Seite einerRegel in der passenden Reihenfolge, Blatter sind Terminalsymbole, dargestelltes Wort wird durch die Folgeder Blatter gegeben.

()()() kann durch 2 verschiedene Syntaxbaume / Linksableitungen / Rechtsableitungen dargestellt werden.

S

S

( S

ε

)

S

S

( S

ε

)

S

( S

ε

)

S

S

S

( S

ε

)

S

( S

ε

)

S

( S

ε

)

anders arithmetische Ausdrucke (am Beispiel 3− 5 + 5):

S

S

3 - 4

+ 5

��

��

��

��

��

��S

3 - S

4 + 5

4.4 Eindeutigkeit

Definition: Eine kontextfreie Sprache ist eindeutig, wenn jedes Wort eine eindeutige Linksableitung / eineeideutige Rechtsableitung / einen eindeutigen Syntaxbaum hat.

Beispiel: S → if B then S | if B then S else S | while ... | ...

if B1 then (if B2 then )S1 else S2

if B1 then (if B2 then S1 else S2)

Grammatik nicht eindeutig!

37


A... bedingte Anweisung, die noch auf”else“ wartet.

T... bbeliebige Anweisung, inklusive einer bedingten Anweisung mit else-Klausel, die abgeschlossen ist

S → A|T

A→ if B then S | if B then T else A

T → if B then T else T | while ... | andere Anweisungen...

aquivalente Grammatik, die eindeutig ist.

S → S + S|S − S|Z (mehrdeutig)

S → Z|S + Z|S − Z (eindeutig)

Es gibt Sprachen, fur die es keine eindeutige Grammatik gibt:

{0i1j01k | i = j ∨ j = k} = {0n1n}0∗ ∪ 0∗{1n0n}

0n1n0n sind in beiden”Teilsprachen“ enthalten.

Solche Sprachen heißen inharent mehrdeutig.

4.5 Chomsky-Normalform

Definition: Eine kontextfreie Grammatik ist in Chomsky-Normalform (CNF), wenn jede Regel lediglich folgendeGestalt haben:

1. A→ BC, A, B, C ∈ V

2. A→ b, A ∈ V, b ∈ Σ

Ausnahme: Die Regel S → ε ist erlaubt, aber S darf nie auf der rechten Seite einer Regel vorkommen.

Satz: Zu jeder kontextfreien Grammatik G gibt es eine Grammatik G′ in CNF mit

L(G′) = L(G)− {ε}

1. Elimination von Terminalsymbolen auf der rechten Seite:

• Fuhre fur jedes a ∈ Σ eine neue Variable Va ein.• Ersetze a durch Va auf allen rechten Seiten• Fuge Regeln Va → a hinzu.

Beispiel:

S → (S)... S → V(SV)

V( → (

V) →)

2. Zerlegung von Regeln mit mehr als 2 Variablen auf der rechten Seite

• Einfuhren von zusatzlichen Zwischenvariablen in mehreren Schritten

Beispiel:

A→ BAAS... A→ BSV1

V1 → AV2

V2 → AS

3. Elimination von ε-Regeln

Konstruiere die Menge M aller Variablen A ∈ V , fur die A∗→ ε. Fur jede Regel, die eine Variable

aus M auf der rechten Seite enthalt, erstelle eine neue Regel, in der ein Vorkommen dieser Variablengestrichen wird.

38

4.5. CHOMSKY-NORMALFORM

Beispiel: M := {V, U, A} fur

U → V W | V | W | ε

V →W | V V | ε | V

A→ U | V V | ε | V

(B → AU↓ε

BV↓ε

| ABV | AUB | AB | BV | UB | B)

U → V W U →W

• M wird initialisiert mit den Variablen A fur die es eine Regel A∗→ ε gibt.

• Durch das Aufstellen neuer verkurzter Regeln konnen neue Regeln der Form A∗→ ε entstehen.

• Die entsprechende Variablen werden dann zu M hinzugefugt.• Erstelle fur jede Variable A aus M eine neue Variable A′.• Auf der rechten Seite aller Regeln wird wird jede diese Variablen A durch A′ ersetzt.• Die Regeln fur A’ sind dieselben wie fur A, nur die ε-Regel wird gestrichen.

Am Beispiel:

U → V ′W ′ | V ′ | W ′ | ε

U ′ → V ′W ′ | V ′ | W ′

V →W ′ | V ′V ′ | V ′ | ε

V ′ →W ′ | V ′V ′ | V ′

...

Behauptung: Fur alle A ∈M gilt

LA′ = LA − {ε} (LX = {s ∈ Σ∗ | X∗→ s})

Begrundung: X∗→ S, S 6= ε Betrachte die rechte Seite der ersten Regel dieser Ableitung.

X → Y Z: Eventuell wird Y oder Z in der Ableitung zu ε gemacht; In diesem Fall enthalt dieneue Grammatik eine Regel X ′ → Y ′ oder X ′ → Z ′, wo das bereits berucksichtigt ist.Fur die nachsten Ableitungsschritte geht man genauso vor.

Lasse die Regeln fur die ursprunglichen Variablen A ∈ M weg, außer fur S. Falls S ∈ M ist, fugedafur die Regeln S → ε, S → S′ein

4. Elimination von K → L

• Fur jede Regel der Form A→ BC, A→ x ∈ Σ berechne die Variablenmenge

VA = {X ∈ V | X∗→ A}.

• Erstelle neue Regeln X → BC bzw. X → x fur alle X ∈ VA.• Anschließend entferne alle Regeln der Form A→ B.

Beispiel: Angenommen fur alle Regeln K → L ergeben folgenden Zusammenhang:

A B D

C E

In einer Ableitung kann eine Kette von Anwendungen derartiger REgeln vorkommen.

A→ B → C → A→ B → B → C → A→ B → C → DABa

(U V AB→V A

UU → UV BUU → ........→ UV DUU)

39


D → AB VD = {A, B, C, D, E}A→ AB, B → AB, C → AB, (D → AB), E → ABDie Menge VA konnen durch umgekehrte Graphensuche bestimmt werden: Suche alle VariablenX , von denen aus A erreichbar ist.

Folgerung: Typ-2-Sprachen sind Typ-1-Sprachen.

Grund: CNF-Grammatik erfullt die Forderungen von Typ-1-Grammatiken

4.6 Algorithus von”CYK“

Der CYK-Algorithmus (Cocke, Kasami, Younger) wird zur Losung des Wortproblems fur kontextfreieSprachen in CNF angewandt. (basiert auf dem Prinzip dynamischer Programmierung)

Eingabe: s = s1s2...sn ∈ Σ∗. Ist s ∈ L(G)

Vij := {X ∈ V | X∗→ sisi+1...sj} (1 ≤ i ≤ j ≤ n)... Teilprobleme s1s2... si...sj ...sn

s ∈ L(G)⇔ s ∈ V1n

Berechne Mengen Vij induktiv, nach Lange j − i + 1 der Teilkette si...sj .

A→ BC...→ sisi+1...sk|sk+1...sj

Vii = {X | (X → si) ∈ P}

Vij = {X | ∃(X → BC) ∈ P, ∃k: i ≤ k ≤ j: B ∈ Vik ∧C ∈ Vk+1,j}

vorher berechnet

Beispiele: Gegeben sei folgende Grammatik in CNF:

Σ = {0, 1, +}

S → 0 | SP

P →MS | +

M → 0 | 1 | PP

Ist das Wort s = 0 + 1 + 0 = s1s2s3s4s5 in der Sprache L(G)?

i, j 1 2 3 4 5

1 M, S S − − −

2 P − − −3 M − −4 P −5 M, S

⇒ 0 + 1 + 0 ist nicht in der Sprache L(G).

V12 = {S} oder k = 2 oder V11 = {M, S} V22 = {P}

V13 = ∅k = 1

oder k = 2V11 = {M, S}

oder V12 = {S}V23 = ∅

V33 = {M}

40

4.7. (ERWEITERTE) BACKUS-NAUR-FORM (E)BNF

S

S

S

0

P

+

P

M

P

+

P

+

S

0

s = 0 + + + 0

i, j 1 2 3 4 5

1 M, S S S S S

20

P M − M

3+

P M P

4+

P −

5+

M, S

0

i < j: Vij =⋃

k=i,i+1,...,j−1

{X | ∃(X → BC) ∈ P : B ∈ Vik ∧C ∈ Vk+1,j}

Laufzeit: Es mussen hochstens n2 Mengen Vij berechnet werden. Jede Berechnung ist eine Schleife uberhochstens n Werte k. ⇒ O(n3)

4.7 (Erweiterte) Backus-Naur-Form (E)BNF

Beispiel: (hypothetische) Grammatik eines Ausschnitts einer Programmiersprache

〈arithmetischer Ausdruck︸︷︷︸

Variable der Grammatik

〉 ::=↑→

〈Term〉 {〈Additionsoperator〉〈Term〉}

〈Additonsoperator〉 ::= +Terminalsymbol

|

”oder“

−Terminalsymbol

〈Term〉 ::= 〈Faktor〉 {〈Multiplikationsoperator〉〈Faktor〉}

〈Multiplikationsoperator〉 ::= ∗ | /

〈Faktor〉 ::= 〈Zahl〉 | 〈Variable〉 | (〈Arithmetischer Ausdruck〉 | 〈Funltionsaufruf〉)

〈Funktionsaufruf〉 ::= 〈Name〉() | 〈Name〉 (〈Argumentliste〉)

〈Argumentliste〉 ::= 〈Argument〉 {, 〈Argument〉}

::= | { } [ ] 〈〉︸︷︷︸

Metasymbole

{...} beliebig viele Wiederholungen (auch 0) des Inhalts[...] Optional. Der Inhalt kann auch weggelassen werden.

41


{ } [ ] mussen bei der Ubersetzung in eine kontextfreie Grammatik aufgelost werden, durch Einfuhren vonneuen Variablen und zusatzlichen Regeln.

{abc} ↔ (abc)∗

[abc]↔ (abc + ε)︸︷︷︸

als regularer Ausdruck

| ↔ +

4.8 Pumping-Lemma fur kontextfreie Sprachen

Fur jede kontextfreie Sprache L gibt es eine Schranke n0 ∈ N.

∀x ∈ L: |x| ≥ n0 ∃y, z, u, v, w ∈ Σ∗:[x = yzuvw ∈ L ∧ (∀i ≥ 0)yziuviw ∈ L ∧ z, v 6= ε

]

z v

Beispiel: L = {0n1n | n ∈ N}

Annahme: L sein kontextfrei ⇒ n0

x = 0n01n00n0 = yzuvw

Fall 1: z enthalt sowohl 0 als auch 1.

z2, z3, ...enthalt mehr Ubergange zwischen 0 und 1 als z

⇒yz2uv2w enthalt mehr als 2 Ubergange

⇒yz2uv2w /∈ L

Fall 2: v enthalt 0 und 1 analog.Also ist z und v jeweils in einem der drei Blocke 0n0 , 1n0 , 0n0 enthalten.

yziuviw...mindestens ein Block andert seine Lange, mindestens ein Block andert seine Lange nicht.

⇒yziuviw /∈ L fur i 6= 1

⇒ L ist nicht kontextfrei

Beweis: Sei L(G), G in CNFEin Ableitungsbaum fur x mit |x| = n hat n− 1 innere Knoten A mit je zwei Kindern.

Der Ableitungsbaum ist ein binarer Baum

Wenn jeder Weg von der Wurzel zu einem Knoten, aus dem ein Terminalsymbol entsteht, ≤ h Vari-ablenknoten enthalt, dann |x| ≤ 2h−1

S

X

X

a

X

X

0

X

1

X

X

b

X

c

1

2

3

4

42

4.9. ABSCHLUSSEIGENSCHAFTEN KONTEXTFREIER SPRACHEN

Wenn |x| > 2h−2, dann gibt es einen Weg von der Wurzel, der h Variablenknoten enthalt

h := |V |+ 1

→ Dieser Weg muss eine Variable A mehrfach enthalten.

n := 2|V |−1 + 1 funktioniertS

AT1

AT2

y z u v w

Die beiden Teilbaume, die unter diesen beidenKnoten hangen heißen T1 und T2

T2 ⊂ T1

S∗→ yAw

T1 : A∗→ zAv (zv 6= ε)

T2 : A∗→ u

S∗→ yAw

∗→yzAvw

∗→ yzuvw

beliebig oft wiederholen

S∗→ yAw

∗→ yuw

(i=0)

(= yz0uv0w)

S∗→ yAw

∗→ yzAvw

∗→ yzzAvvw

∗→ yziAviw

∗→ yziuviw

(i≥1)�

Folgerung: Die Chomsky-Hierarchie ist echt: L0,L1,L2,L3 seien die Typ-0-Sprachen, Typ-1-Sprachen, ...

L3regular

⊂6=

L2kontextfrei

⊂6=

L1kontextsensitiv

⊂6=

L0rekursiv aufzahlbar

L= {0n1n} L= {0n1n0n} ⊂ entscheidbare Sprachen Halteproblem

4.9 Abschlusseigenschaften kontextfreier Sprachen

Satz: Kontextfreie Sprachen sind abgeschlossen bezuglich ∪, ·, ∗Kontextfreie Sprachen sind nicht abgeschlossen bezuglich ∩ und Komplement

Beweis: L1 = {0n1n0m | m, n ∈ N}, L1 = {0n1m0m | m, n ∈ N}L1 ∩ L2 = {0n1n0n | b ∈ N} nicht kontextfrei.

L1 ∩ L2 = L1 ∪ L2 (de-Morgan)Wenn kontextfreie Sprachen abgeschlossen bezuglich Komplement waren, dann ware sie auch abgeschlossenbezuglich ∩Das Komplement von {0n1n0n} ist kontextsensitiv.

43


4.10 Entscheidungsprobleme kontextfreier Sprachen

Seien G1, G2 kontextfreie Grammatiken

• L(G1) = 0? entscheidbar• L(G1) = 0? entscheidbar• Ist L(G1) regular? unentscheidbar• L(G1) = Σ∗? unentscheidbar (ohne Beweis)• L(G1) = L(G2)? unentscheidbar (ohne Beweis)• L(G1) ⊆ L(G2)? unentscheidbar (ohne Beweis)• L(G1) ∩ L(G2) = ∅? unentscheidbar (s. Ubung 11)• L(G1) 6= ∅?

Wir nehmen an, dass G1 in CNF vorliegt.

Definition: Eine Variable heißt uberflussig, wenn sie in keiner Ableitung eines Wortes ∈ Σ∗ vorkommt.

2 Grunde: 1. S → AB → ABA→ ... von S nicht ereichbar.

2. Aus der Variable lasst sich kein Terminalwert erzeugen.

Beispiel: A→ AB (einzige Regel fur A)

• Menge M : Initialisiere M := {A ∈ V | (A→ x) ∈ P}

• Wenn ses eine Regel A→ BC mit B, C ∈M gibt, dann setzte M := M ∪ {A}.

• Wiederhole, bis keine neuen Varaiblen mehr in M aufgenommen werden. Variablen in M = V −Msind uberflussig aus dem zweiten Grund.

• Entferne die Variablen in M und alle Reglen, die M enthalten aus der Grammatik.

S →��AC (A ∈M)

M2 := Menge der Variablen, die von S aus erreichbar sind.

• Initialisiere M2 := {S}

• Wenn es eine Regel A→ BC mit A ∈M2 gibt, dann setze M2 = M2 ∪ {B, C}.

• Wiederhole, bis M3 sich stabilisiert.

• Streiche Variablen in V −M2. Das Ergebnis ist eine Grammatik ohne Uberflussige Variablen.

4.11 Kellerautomaten

Typ-0-Sprachen ⇐⇒ Turingmaschinen(Typ-1-Sprachen ∼ Turingmaschinen mit linearem Platzbedarf)Typ-2-Sprachen ⇐⇒ Kellerautomaten

Typ-3-Sprachen ⇐⇒ endliche Automaten

Linksableitung:

S → ABC → bAABC → bbAAABC → bbAABC → bb B BSBC︸︷︷︸

Terminalsymbole des endgultigen Wortes aktuelle Variable”zukunftige Variablen“

D. h. Anderung nur am Anfang, den nur das erste Variablensymbol wird durch etwas anderes ersetzt.

44

4.11. KELLERAUTOMATEN

Definition: Ein (nichtdeterministischer) Kellerautomat (Push-down automaton, PDA) hat

• ein Eingabealphabet Σ

• eine Zustandsmenge Q

• ein Kelleralphabet Γ

• ein Bodensymbol Z0 ∈ Γ

• einen Anfangszustand q0 ∈ Q

• eine Ubergangsrelation δ: Q× (Σ ∪ {ε})× Γ→ 2Q×Γ∗

(q′, z) ∈ δ(q, a, γ) bedeutet: Wenn der PDA im Zustand q ist, as obere Kellersymbol γ ist, und er den Buchstabena liest (bzw. nichts liest, falls a = ε ist), dann kann er in den Zustand q′ wechseln und die Spitze des Kellersdurch z ersetzen (z = ε: Das oberste Symbol γ wird geloscht).

Es gibt zwei Arten von Kellerautomaten:

a) solche, die mit leerem Keller akzeptieren.

b) solche, die durch eine Menge F ⊆ Q von akzeptierenden Zustanden akzeptieren

Beispiel: L = {w#wR | w ∈ {0, 1}}Σ = {0, 1, #}Γ = {0, 1, Z0}a) Q = {q0, q1}b) Q = {q0, q1, q2} mit F = {q2}

δ(q0, 0, Z0) = {(q0, 0Z0)} δ(q1, 0, 0) = {q1, ε}

δ(q0, 1, Z0) = {(q0, 1Z0)} δ(q1, 1, 1) = {q1, ε}

δ(q0, 0, 0) = {(q0, 00)} a)δ(q1, ε, Z0){q1, ε}

δ(q0, 0, 1) = {(q0, 01)} a)δ(q1, ε, Z0){q2, Z0}

δ(q0, 1, 0) = {(q0, 10)} δ(q1, 0, 1) = ∅

δ(q0, 1, 1) = {(q0, 11)}...

δ(q0, #, 1) = {(q1, 1)} usw.

δ(q0, #, 0) = {(q1, 0)}

δ(q0, #, Z0) = {(q1, Z0)}

Definition: Eine Konfiguration eines Kellerautomaten ist ein Tripel (q, w1...wm, z) mit

• q ∈ Q... augenblicklicher Zustand,

• w1...wn ∈ Σ∗... noch nicht gelesener Teil des Eingabewortes und

• z ∈ Γ∗... Inhalt des Stapels (Spitze ist links.)

Beispiel:

(q0, 01#10, Z0) ⊢ (q0, 1#10, 0Z0) ⊢ (q0, #10, 10Z0) ⊢ (q1, 10, 10Z0) ⊢ (q1, 0, 0Z0) ⊢ (q1, ε, Z0)(a) ⊢ (q1, ε, ε)

(b) ⊢ (q2, ε, Z0)

Nachfolgerelation ⊢ fur Konfiguration

(q, w1w2...wn, z1...zk) ⊢ (q′, w2...wn, zz2...zk) falls (q′, z) ∈ δ(q, w1, z1), w1 ∈ Σ

(q, w1w2...wn, z1...zk) ⊢ (q′, w1...wn, zz2...zk) falls (q′, z) ∈ δ(q, ε, z1)

∗

⊢ ... transitive reflexive Hulle von ⊢

45


Die vom PDA M akzeptierte Sprache ist:

a) L(M) = {x ∈ Σ∗: (q0, x, Z0)∗

⊢ (q′, ε, ε), q′ ∈ Q}

b) L(M) = {x ∈ Σ∗: (q0, x, Z0)∗

⊢ (q′, ε, z), q′ ∈ F, z ∈ Γ∗}

Definition: Ein PDA ist ein deterministischer Kellerautomat (DPDA) wenn:

∀q ∈ Q, γ ∈ Γ, a ∈ Σ: |δ(q, a, γ)|+ |δ(q, ε, γ)| ≤ 1

(Dann gibt es zu jeder Konfiguration hochstens eine Nachfolgekonfiguration.)

D. h. unser obiges Beispiel ist eigentlich ein DPDA

Beispiel: L2 = {wwR | w ∈ {0, 1}∗}Σ = {0, 1} Γ = {0, 1, Z0}δ(q0, w, γ) wie oben (w ∈ {0, 1})δ(q0, ε, γ) = {(q1, γ)} fur γ ∈ {0, 1, Z0}δ(q1, ...) wie oben.

(q0, 0110, Z0) ⊢ (q0, 110, 0Z0) ⊢ (q0, 10, 10Z0) ⊢ (q1, 10, 10Z0) ⊢ ...weiter wie bisher ⊢ (q0, 0110, Z0)

⊢ (q0, 110, 0Z0) ⊢ (q1, 110, 0Z0) STOP.

Satz: Die PDAs, die nach (a) und nach (b) akzeptieren, akzeptieren dieselbe Klasse von Sprachen.

Beweis:”⇒“ Seien M = (Q, Σ, Γ, q0, Z0, δ) ein PDA, der mit leerm Keller akzeptiert, undM ′ = (Q ∪ {qF , q′0}, Σ, Γ ∪ {Z ′

0}, q′0, Z

′0, δ

′, F = {qF }) ein PDA, der nach b) akzeptiert

δ′(q′0, ε, Z′0) = {(q0, Z0Z

′0)} δ′(q, ε, Z ′

0) = {(qF , ε)}

• Alle Ubergange von δ werden ubernommen.• M ′ fugt ein zusatzliches Kellersymbol Z ′

0 als unterstes ein.

”⇐“ M = (Q, Σ, Γ, q0, Z0, δ, F ) sei ein Automat, der nach b) akzeptiert

neuer Automat M ′:

• fugt ein zusatzliches unterestes Kellersymbol ein. Wenn M in einem akzeptierenden Zustandubergehen, wo der Keller geleert wird, ohne die Eingabe gelesen wird.• Das zusatzliche Kellersymbol stellt sicher, dass M ′ nicht nur deshalb akzeptiert, weil M den

Keller leert.

Satz: Die kontextfreien Sprachen sind genau die Sprachen, die von Kellerautomaten akzeptiert werden.

Beweis:”⇒“ Wir nehmen an, die Grammatik ist in CNF.

• Σ, Γ = V, Z0 = S, {q0}, Automat akzeptiert mit leerem Keller.• Fur jede Regel A→ B1B2...Bk fuge (q0, B1...Bk) ∈ δ(q0, ǫ, A) ein.• Fur jede Regel A→ u ∈ Σ fuge (q0, ε) ∈ δ(q0, u, A) ein.

δ(q0, ε, A) := {(q0, B1...Bk) | (A→ B1...Bk ∈ V ∗) ∈ P}

δ(q0, u, A) := {(q0, ε) | (A→ u) ∈ P}, u ∈ Σ

Der Kellerautomat kann nun genau die Linksableitung der Grammatik nachbilden.

S → ABC → uBC → uAAC → uAC → uvC → uvBC → uvuC → uvuv

m

(q0, uvuv, S) ⊢ (q0, uvuv, ABC) ⊢ (q0, vuv, BC) ⊢ (q0, vuv, AAC) ⊢ ...

”⇐“ Gegeben: Kellerautomat, akzeptiert durch F ⊆ Q von akzeptierenden Zustanden.

Gesucht: Grammatik G.

V = Q× Γ×Q ∪ {S} Variablen haben die Form (q, Z, q′)

”Tripelkonstruktion“

46

4.11. KELLERAUTOMATEN

Idee: S∗→ w1w2...wk

︸︷︷︸(q1, Z1, q2)(q2, Z2, q3)(q3, Z3, q4)...(ql, Zl, ql+1)

das soll folgende Rechnung widerspiegeln

(q0, w1...wn, Z0)∗

⊢ (q1, wk+1...wn, Z1Z2...Zl) (die ersten k Symbole sind gelesen.)

• qi>1 ist der Zustand, der in der weiteren Rechnung angenommen wird, sobald Zi als oberstesStartsymbol erscheint.• q2, q3, ... werden geraten.

Regeln: Fur alle (q′, z′) ∈ δ(q, a, z) mit |z′| ≥ 1, Z ′ = z1z2...zl

(q, z, q)→ a(q′, z1, q1)(q1, z2, q2)...(ql−1, zl, q), ∀q1, q2, ..., ql−1, q (a ∈ Σ ∪ {ε})

Fur alle (q′, ε) ∈ δ(q, a, z)

(q, z, q′)→ a

Behauptung: (q, Z, q′)∗→ w ∈ Σ∗ ⇔ (q, w, Z)

∗

⊢ (q′, ε, ε)Der Automat hat w gelesen und sieht das erste Mal, was unter Z auf dem Stapel ist.

Beweis durch Induktion nach der Lange der Ableitung bzw. nach der Lange der Rechnung.Beispiel: L = {wwT | w ∈ {0, 1}∗} Q = {q0, q1}

δ(q0, x, z) = {(q0, xz)}, x ∈ {0, 1}, z ∈ {0, 1, z0} (1)

δ(q0, ε, z) = {(q1, z)} (2)

δ(q1, x, x) = {(q1, ε)}, x ∈ {x ∈ {0, 1}} (3)

δ(q1, ε, z0) = {(q1, ε)}

Also werden die folgenden Produktionen gebildet(1) am Beispiel δ(q0, 0, Z0) = {(q0, 0Z0)}

(q0, Z0, q0)→ 0(q0, 0, q0)(q0, Z0, q0)

(q0, Z0, q0)→ 0(q0, 0, q1)(q1, Z0, q0)

−→ (q0, Z0, q1)→ 0(q0, 0, q0)(q0, Z0, q1)

−→ (q0, Z0, q1)→ 0(q0, 0, q1)(q1, Z0, q1)

(2) am Beispiel δ(q0, ε, 0) = {(q1, 0)}

(q0, 0, q0)→ (q1, 0, q0)

(q0, 0, q1)→ (q1, 0, q1)

(3) am Beispiel δ(q0, ε, 0) = {(q1, 0)}

(q1, 1, q1)→ 1

(q0, 0110, Z0) ⊢ (q0, 110, 0Z0) ⊢ (q0, 10, 10Z0) ⊢ (q1, 10, 10Z0) ⊢ (q1, 0, 0Z0) ⊢ (q1, ε, Z0)

⊢ (q1, ε, ε)

S → (q0, Z0, q1)→ 0(q0, 0, q1)(q1, Z0, q1)→ 01(q0, 1, q1)(q1, 0, q1)(q1, Z0, q1)

→ 01(q1, 1, q1)(q1, 0, q1)(q1, Z0, q1)→ 011(q1, 0, q1)(q1, Z0, q1)

→ 0110(q1, Z0, q1)→ 0110

Annahme: Automat akzeptiert durch leeren KellerStartregeln: S → (q0, Z0, q) fur alle q ∈ Q

Aus der Behauptung folgt: L(G) = L(M)

w ∈ L(G)⇔ S∗w⇔ ∃q: (q0, Z0, q)

∗→ w

Beh.⇐⇒ ∃q: (q0, w, Z0)

∗

⊢ (q, ε, ε)⇔ w ∈ L(M)

47


4.12 Abschlusseigenschaften kontextfreier Sprachen gegenuber regularenSprachen

Satz: Die kontextfreien Sprachen sind abgeschlossen gegenuber dem Durchschnitt mit regularen Sprachen.

Bew.: M1 sei ein PDA fur die kontextfreie Sprache L1, der durch akzeptierende Zustande akzeptiert. A2 sei einDEA fur L2.

• PDA: M mit Q = Q1 ×Q2

δ((q1, q2), ε, Z) := {((q′, q2), z′) : (q′, z′) ∈ δ1(q1, ε, Z)}

δ((q1, q2), a, Z) := {((q′, δ2(q2, a)), z′ : (q′, z′) ∈ δ1(q1, a, Z))} a ∈ Σ

q0 = (q10 , q

20)

F = F1 × F2

”Produkt der Automaten: Der neue Kellerautomat M simuliert M1 und A2 gleichzeitig:

L(M)) = L(M1) ∩ L(A2)

4.13 Deterministische kontextfreie Sprachen

Definition: Eine deterministische kontextfreie Sprache ist eine Sprache, die von einem deterministischen Keller-automaten mit einer akzeptierenden Zustandsmenge akzeptriert werden.

Beispiele: • {0n#1n | n ∈ N} ist deterministisch kontextfrei

• {w#wR | w ∈ Σ∗} ist deterministisch kontextfrei

• {wwR | w ∈ {0, 1}∗} ist kontextfrei, aber nicht deterministisch kontextfrei

Bemerkung: Deterministisch kontextfreie Sprachen sind abgeschlossen unter Komplement, aber nicht unterUmkehrung.

4.14 Deterministische Zweiwege-Kellerautomaten

K1 K2

⇐⇒ K1 K2

Kellerautomaten mit zwei Kellern, sind genauso machtig wie Turingmaschinen.

Deterministische Zweiwege-Kellerautomaten konnen auf dem Eingabeband beliebig nach links uder nach rechtsfahren.

δ(q, a, z) = (q′, Z1Z2...Zk, b), a ∈ Σ ∪ {%, $}, b ∈ {0, +1,−1}: Bewegung des Kopfes

Die Eingabe ist durch % und $ auf dem Eingabeband begrenzt.

%w1w2...wn$ Ausgangskonfiguration

Lesekopf

48

4.14. DETERMINISTISCHE ZWEIWEGE-KELLERAUTOMATEN

4.14.1 Teilwortproblem

Eingabe: x#y

Frage: Kommt das Muster x im Text y vor?

L = {x#uxv | x, u, v ∈ (Σ0)∗}

% x # $

.. .

• Kopiere y auf den Stapel, von rechts nach links

• Fahre zur ersten Position von x

• (A) Vergleiche die Symbole von x mit dem Sybol auf dem Stapel, die Symbole werden vom Stapel geloscht.

• Wenn # gelesen wird → Teilwort vorhanden → akzeptiere

• Bei einem Konflikt fahre zuruck zum Anfang und fulle den Stapel mit den Symbolen von x auf. Loscheerstes Symbol des Stapels und gehe zu (A).

Satz: Jede Sprache, die von enem deterministischen Zweiwege-Kellerautomaten akzeptiert wird, kann in linearerZeit von einer Registermaschine (RAM) entschieden werden.

Folgerung: Teilwortproblem ist in linearer Zeit losbar.

Beweis: EntladefunktionEingabe: %

↑

0

w1↑

1

...wn...

$↑

n+1

ent(q, Z, i) = (q′, j) q, q′ ∈ Q, Z ∈ Γ, 0 ≤ i, j ≤ n + 1

Wenn der Automat im Zustand q an Position i ist, und das oberste Stapelsymbol Z ist, dann ist er zudem Zeitpunkt, wo das darunterliegende Stapelsymbol sichtbar wird, in Zustand q′ und an Position j

ent (q, Z, i)i f i nArbe i t [ q, Z, i ] then STOP; // Wort wird n i cht a k z ep t i e r ti f ENT[ q, Z, i ] 6= 0 then

return ENT[ q, Z, i ]i nArbe i t [ q, Z, i ] := true...(q′, Z1...Zk, b) := δ(q, wi, Z)j := i + bfor l := 1, 2, ..., k

(q′, j) := ent (q′, Zl, j )ENT[ q, Z, i ] := (q, j)inArbe i t [ q, Z, i ] := fa l se

return (q ’ , j )

Idee: Speichere die Werte der Entladefunktion in einem Feld ENT[q, Z, i] der Große O(n) sobald sie berechnetwurden (Initialisiere zu 0).

Die Technik heißt Tabellieren (engl. memorization)

Laufzeit: O(n) Jeder Eintrag von ENT wird hochstens einmal berechnet.

Problem: Bei rekursiven Aufrufen kann die Laufzeit∞ sein. Wahrend ent(q, z, i) aufgerufen ist, kann ein rekur-siver Aufruf mit denselben Parametern (q, z, i) gestartet werden.⇒ Algorithmus terminiert nicht.⇒ Kellerautomat terminiert nicht, weil sich die Konfiguration (q, z, i) unendlich oft wiederholt. Der Stapelwird dabei immer weiter wachsen oder konstant bleiben.

49


Durch ein Boolsches Feld inArbeit[q, z, i] (am Anfang false) wird endlose Rekursion vermieden.

Wir konnen annehmen, dass der Kellerautomat, wenn er ein Wort akzeptieren will, in einen akzeptierendenZustand geht und dann der Keller leert.

Wort wird akzeptiert ⇐⇒ ent(q0, z0, 1) = (q′, j) mit q′ ∈ F

50

Documents

GTI Mitschrift