AFE-Zusammenfassung 2019-20 PDF

Preview

Summary

Download AFE-Zusammenfassung 2019-20 PDF

Description

Automaten, formale Sprachen und Endscheidbarkeit Gedächtnisstütze Ruben Deisenroth 27. Mai 2020

Inhaltsverzeichnis 1

endliche- und nichtendliche Automaten 3 1.1 Satz von Myhill-Nerode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Pumping-Lemma für reguläre Sprachen (Typ 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Konkatenation von zwei Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Grammatiken 4 2.1 Ableitbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Pumping Lemma für kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 Chomsky-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Berechnungsmodelle 6 3.1 Kellerautomat (PDA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Turingmaschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Chomsky-Hierarchie

8

2

6 7

1 endliche- und nichtendliche Automaten 1.1 Satz von Myhill-Nerode Die Äquivalenzrelation ∼L ist definiert durch: w ∼L w′ gdw. für alle x ∈ Σ∗ ist wx ∈ L ⇔ w′ x ∈ L das heißt: egal welches Wort man anhängt, so kommt bei w und w′ die gleiche Akzeptanz raus. Die Äquivalenzrelation ∼A ist definiert durch: w ∼A w′ gdw. ˜ δ (q0 , w) = δ˜(q0 , w′ ) das heißt: der DFA der die Sprache beschreibt endet bei w und w′ auf dem gleichen Zustand. Die Äquivalenzrelation ≈L ist definiert durch: w ≈L w′ gdw. für alle x, y ∈ Σ∗ ist xwy ∈ L ⇔ xw′ y ∈ L das heißt: egal welches Wort man vorsetzt und anhängt, so kommt beiw und w′ die gleiche Akzeptanz raus.≈L ist verträglich mit Konkatenation: (u ≈ u′ ∧ v ≈ v ′ ) ⇒ uv ≈L u′ v ′ Der Index index(R) ist: index(R) = |Σ∗ /R | ={Menge aller Äquivalenzklassen von R} Nach Myhill-Nerode sind äquivalent: • ∼L hat endlichen Index • ∼A hat endlichen Index (Korollar 2.4.5) • ≈L hat endlichen Index (Übung 2.4.11) • L ist regulär.

1.2 Pumping-Lemma für reguläre Sprachen (Typ 3) Wenn L erkennbar, Dann gilt: ∃n ∈ N, sodass ∀x ∈ L mit |x| ≥ n: ∃ Zerlegung x = u · v · w mit v = ε und |u · v| ≤ n, sodass ∀m ∈ N : uv m w ∈ L Analog dazu das Beweisschema zum wiederlegen: Wenn ∀n ∈ N gilt: ∃x ∈ L mit |x| ≥ n, sodass ∀ Zerlegungen x = u · v · w mit v = ε und |u · v| ≤ n gilt, dass ∃m ∈ N : uv m w ∈ /L Dann ist L nicht erkennbar (regulär).

Sei n ∈ N gegeben. Setze w = an bn . Sei Zerlegung x = u · v · w mit x = ε und |v · w| ≤ n gegeben. Setze i = 0. Dann hat uv m w = uw weniger a als b. Und somit uvm w ∈ /L

(a) Pumping Lemma umgestellt (b) Beispiel für Sprache L = {an bn |n ≥ 0}

Abbildung 1: Links: Beweisschema sprache nicht regulär, rechts Beispiel L = {an bn |n ≥ 0}

⇒ kann beweisen, dass L nicht regulär ist, aber nicht dass es Regulär ist.

3

1.3 Konkatenation von zwei Sprachen Seien A und B zwei ε-DFAs wie folgt: a,b q2

start

q0

a

b

b

a,b

b

a q0

start

q1

q1 a

(b) B

(a) A

a,b q2 a,b

b

b

b a

q0

start

a

ε

q1

q3

q4 a

ε-Übergang (c) A · B

Abbildung 2: Konkatenation der Automaten A und B

2 Grammatiken Definition: G = (Σ, V, P, X0 ), wobei: • Σ:Alphabet, Σ = 0 • V :Variablenmenge, nicht in Σ enthalten • P Menge der Produktionen/Regeln • X0 ∈ V die Startvariable

2.1 Ableitbarkeit 1-Schritt-Ableitbarkeit (direkte Ableitbarkeit) →G : x →G x′ :⇔ x = uvw, x′ = uv ′ w für eine Produktion c → v ′ von G. Ableitbarkeit{ →G : es existiert ein →G -Pfad von x nach x′ : ∗ x′ :⇔ x →G x = x1 →G x2 →G . . . →G xn = x′ .

4

2.2 Pumping Lemma für kontextfreie Sprachen Wenn L kontextfrei, Dann gilt: ∃n ∈ N, sodass ∀x ∈ L mit |x| ≥ n: ∃ Zerlegung x = y · u · v · w · z mit u =  ε oder w = ε und |uvw| ≤ n, sodass ∀m ∈ N : y · um · v · wm · z ∈ L Analog dazu das Beweisschema zum wiederlegen: Wenn ∀n ∈ N gilt: ∃x ∈ L mit |x| ≥ n, sodass ∀ Zerlegungen x = y · u · v · w · z mit u =  ε oder w = ε und |uvw| ≤ n gilt, dass ∃m ∈ N : y · um · v · wm · z ∈ /L Dann ist L nicht kontextfrei.

2.3 Chomsky-Normalform Ziel: nur Produktionen der Form X → Y Z und X→a (und ggf. X0 → ε) Umformung:

1. S → ε (ε-Regeln) eliminieren: • Zustände, bei denen ε-Bildung (Auch durch mehrfaches ableiten) möglich ist in Menge M = {. . .} aufschreiben. • ε-Produktion streichen • für alle Ableitungen, die Nicht-Terminale ausM enthalten, jede mögliche Regel durch weglassen dieser Nicht-Terminale hinzufügen.(Außer es führt zu ε) • Falls ε ursprünglich akzeptiert wurde: X0 → X|ε hinzufügen (harmlos) 2. S → T (Kettenregeln) eliminieren: • Verkettungen in M = {(X, Y ), (Y, Z ), (X, Z )} aufschreiben (Auch durch mehrfaches ableiten) • Reine Verkettungsregeln (= Alleinstehende Variablen auf der rechten Seite) entfernen • unerreichbare Regeln entfernen 3. Ordnen (Terminale Auslagern): S → aXb zu S → X1 X2 X1 → X3 S X3 → a X2 → b 4. Verkürzen von Nichtterminal-Regeln (auf Länge 2): S → AST BB|b zu S → AX1 |b X1 → SX2 X2 → T X3 X3 → BB

5

3 Berechnungsmodelle 3.1 Kellerautomat (PDA) Formelle Definition: ein (nichtdeterministisccher) Kellerautomat P ist definiert als: P = (Σ, Q, q0 , ∆, A, Γ, #) mit • Σ (Sigma): Das endliche Eingabealphabet • Q: Die endliche Zustandsmenge • q0 : Der Anfangszustand, q0 ⊆ Q • ∆ (Delta): Die endliche Übergangsrelation • A: Die Menge der Akzeptierenden Zustände, A ⊆ Q • Γ (Gamma): Das Kelleralphabet • #: das Anfangs-Kellersymbol, # ∈ Γ Sodass gilt: Startkonfiguration C0 [w] = (q0 , w, #) Akzeptanz: P C0 [w] −→ Cf bedeutet, dass der PDA P eine Berechnung auf w hat, die auf Cf endet. Eine Berechnung auf w ist akzeptierend, wenn • sie das gesamte Eingabewort abarbeitet (leeres Rest wort), • mit leerem Keller endet (leeres Kellerwort) • und in einem Akzeptierenden Zustand q ∈ A endet P

Folglich ist L(P) = {w ∈ Σ∗ : C0 [w] −→ (q, ε, ε) für ein q ∈ A} ε; A → A start

q0

ε; C0 → C0

a; c 0 → AC0

q1

b; A → ε

ε; C0 → C0

A

oberstes Kellersymbol

B αrest #

a; A → AA q2

Kellerspeicher

Abbildung 3: Darstellung eines PDAs

6

3.2 Turingmaschine Formelle Definition: eine Turingmaschine M ist definiert als: M = (Σ, Q, q0 , δ, q+ , q− ) mit • Σ: Das endliche Eingabealphabet • Q: Die endliche Zustandsmenge • q0 : Der Anfangszustand • q+ : Der akzeptierende Endzustand • q− : Der verwerfende Endzustand • δ: die Übergangsfunktion Der Lesekopf kann verschoben werden mit: • : Eine Zelle nach rechts • ◦: In der aktuellen Zelle bleiben Akzeptanz: M • w −→ ∞: Die Berechnung von M auf w divergiert M • w −→ STOP: Die Berechnung von M auf w terminiert M + • w −→ q : M akzeptiert w M

• w −→ q− : M verwirft w

···

□

□

a

b

a

b

□

□

···

q0 b|b| >

start

q0

b|#| >

a|a| < q−

q1

b|b| >

#|a| < q+

q2 a|b| < q3

b|a| <

□|a| < Abbildung 4: Darstellung einer Turingmaschine

7

4 Chomsky-Hierarchie

Typ endscheidbar semi-endscheidbar

3 2 1 0 bel. Σ-Sprachen

abgeschlossen unter ∪ ∩ − · ∗ + + + + +

+ − + + +

+ − + − +

+ + + + +

+ + + + +

Tabelle 1: Übersicht der Abschlusseigenschaften

8...