Zusammenfassung Grundlagen der Theoretischen Informatik B: komplett PDF

Preview

Summary

Download Zusammenfassung Grundlagen der Theoretischen Informatik B: komplett PDF

Description

Grundkurs Theoretische Informatik Zusammenfassung

Inhaltsverzeichnis 1 Endliche Automaten 1.1 Alphabete, Wörter, Sprachen . . . . . . . . . . . . . . . . . . . . . 1.2 Formale Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Verhalten von Automaten . . . . . . . . . . . . . . . . . . . . . . . 1.4 Reguläre Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Vollständige Automaten . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Nichtdeterministische endliche Automaten . . . . . . . . . . . . . . 1.7 Äquivalenz von deterministischen und nichtdeterministische endlichen Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 Endliche Automaten mit ε-Übergängen . . . . . . . . . . . . . . . . 1.9 Verallgemeinerte endliche Automaten . . . . . . . . . . . . . . . . . 1.10 Äquivalenz von Automaten . . . . . . . . . . . . . . . . . . . . . . . 1.11 Minimierung endlicher Automaten . . . . . . . . . . . . . . . . . . .

5 5 5 6 6 6 7 7 7 7 8 8

2 Reguläre Sprachen REGΣ 2.1 Regulärer Ausdruck . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Äquivalenz von endlichen Automaten und regulären Ausdrücken . . 2.3 Typ-3-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Rechtslineare Typ-3-Grammatiken . . . . . . . . . . . . . . . . . . . 2.5 Linkslineare Typ-3-Grammatiken . . . . . . . . . . . . . . . . . . . 2.6 Äquivalenz rechtslinearer und linkslinearer Grammatiken . . . . . . 2.7 Verallgemeinerte Typ-3-Grammatiken . . . . . . . . . . . . . . . . . 2.8 Äquivalenz von endlich Automaten und Typ-3-Grammatiken . . . . 2.9 Abschlusseigenschaften von REGΣ . . . . . . . . . . . . . . . . . . 2.10 Entscheidbarkeitsprobleme . . . . . . . . . . . . . . . . . . . . . . .

9 9 9 9 10 10 10 11 11 11 12

3 Endliche Maschinen 3.1 Mealy-Maschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Moore-Maschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Äquivalenz von Mealy- und Moore-Bereichenbarkeit . . . . . . . . .

13 13 14 14

4 Kontextfreie Sprachen 15 4.1 Typ-2-Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.2 Chomsky-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . 15

4.3 Greibach-Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.4 Mehrdeutigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.5 Abschlusseigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . 16 5 Kellerautomaten 5.1 Nichtdeterministische Kellerautomaten . . . . . . . . . . . . . . . . 5.2 Akzeptieren mit leerem Keller . . . . . . . . . . . . . . . . . . . . . 5.3 Äquivalenz von kontextfreien Grammatiken und Kellerautomaten . 5.4 Deterministische Kellerautomaten . . . . . . . . . . . . . . . . . . . 5.5 Abschlusseigenschaften von DP DAΣ . . . . . . . . . . . . . . . . . 5.6 Entscheidbarkeitsprobleme . . . . . . . . . . . . . . . . . . . . . . . 5.7 Präfixeigenschaft . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17 17 17 18 18 19 19 20

6 Typ-1- und Typ-0-Sprachen 6.1 Typ-1 Sprachen (kontextsensitive Sprachen) . . . . . . . . . . . . . 6.2 Typ-0-Sprachen (rekursiv-aufzählbare Sprachen) . . . . . . . . . . . 6.3 Abzählbare und nicht abzählbare Mengen . . . . . . . . . . . . . . . 6.4 Wortproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.5 Turingautomaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.6 Linear beschränkte Automaten . . . . . . . . . . . . . . . . . . . . 6.7 Äquivalenz zwischen Typ-1-Grammatiken und linear beschränkten Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.8 Äquivalenz zwischen Typ-0-Grammatiken und Turingautomaten . .

22 22 22 23 23 24 25

7 Berechenbarkeit 7.1 Turingmaschine und Turingberechenbarkeit . . . . . . . . . . . . . . 7.2 Programmiersprache TURING . . . . . . . . . . . . . . . . . . . . . 7.2.1 Elementare Anweisungen . . . . . . . . . . . . . . . . . . . . 7.2.2 Zusammengesetzte Anweisungen und TURING-Programme . 7.3 Programmiersprache LOOP . . . . . . . . . . . . . . . . . . . . . . 7.4 Programmiersprache WHILE . . . . . . . . . . . . . . . . . . . . . 7.5 Programmiersprache GOTO . . . . . . . . . . . . . . . . . . . . . . 7.6 Primitiv-rekursive Funktionen . . . . . . . . . . . . . . . . . . . . . 7.7 µ-rekursive Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . 7.8 Die Churchsche These . . . . . . . . . . . . . . . . . . . . . . . . .

27 27 27 28 28 29 30 31 31 33 33

25 26

7.9 Universelle Turingmaschine . . . . . . . . 7.9.1 Codierung von Turingmaschinen . . 7.10 Eine Standardnummerierung für P . . . . 7.11 Das utm-Theorem . . . . . . . . . . . . . . 7.12 Das smn-Theorem . . . . . . . . . . . . . . 7.13 Anwendungen von utm- und smn-Theorem 7.14 Bedeutung von utm- und smn-Theorem . .

. . . . . . .

. . . . . . .

8 Entscheidbarkeit 8.1 Existenz unentscheidbarer Probleme . . . . . . 8.2 Entscheidbare und semi-entscheidbare Mengen 8.3 Reduzierbarkeit von Mengen . . . . . . . . . . 8.4 Unentscheidbare Probleme . . . . . . . . . . . 8.4.1 Das Halteproblem . . . . . . . . . . . . 8.4.2 Das Korrekheitsproblem . . . . . . . . 8.4.3 Das Äquivalenzproblem . . . . . . . . . 8.4.4 Satz von Rice . . . . . . . . . . . . . . 9 Komplexität 9.1 Die Klasse P . . . . . . 9.2 Die Klasse N P . . . . . 9.3 Die Klassen EXP T IME 9.4 NP-Vollständigkeit . . . 9.5 Die Klasse P SP ACE . .

. . . . . . . . . . . . . . . . . . . . . . . . und N EXP T IME . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

. . . . . . . .

. . . . .

. . . . . . .

34 34 36 37 37 38 38

. . . . . . . .

40 40 40 41 41 41 42 42 43

. . . . .

44 44 44 45 45 46

1 ENDLICHE AUTOMATEN

1 Endliche Automaten 1.1 Alphabete, Wörter, Sprachen Symbole/Buchstaben bilden ein Alphabet Σ. Beispiel: Σ = {a, b} Die endlich langen Zeichenfolgen, die über ein Alphabet Σ gebildet werden können, heißen Wörter aus Σ. In einem Alphabet kommen keine Wörter vor, die über diesem Alphabet gebildet werden. Beispiel: abba, aa, b, bbbb. Das leere Wort ε ist Wort über jeden Alphabet Σ. Es ist in jeder Wortmenge enthalten und kann deshalb kein Teil des Alphabetes sein. Es gilt εω = ωε = ω . Σ∗ die Menge aller Wörter, die über dem Alphabet Σ gebildet werden können. Beispiel: Σ∗ = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, ...}. Die Menge Σ∗ ohne das leere Wort ist Σ+ Sei w ∈ Σ∗ ein Wort der Form w = xyz mit x, y, z ∈ Σ∗ , dann heißt x Präfix, y Infix und z Suffix, Postfix oder Rest.

1.2 Formale Sprachen Sei Σ ein Alphabet, dann heißt jede Menge L ⊆ Σ∗ eine formale Sprache über Σ. Die Konkatenation sei definiert durch L1 ◦ L2 = {vw|v ∈ L1 , w ∈ L2 } Beispiel: Sei L1 = {ε, ab, abb} und L2 = {b, ba}, dann ist L1 ◦L2 = {b, ba, abb, abba, abbb, abbba} und L2 ◦ L1 = {b, bab, babb, ba, baab, baabb} Die n-te Potenz einer Sprache L ∈ Σ∗ ist festgelegt durch: L0 = {ε} L1 = L0 ◦ L = {ε} ◦ {a, ab} = {a, ab} = L L2 = L1 ◦ L = {a, ab} ◦ {a, ab} = {a2 , a2 b, aba, (ab)2 } ...

Seite 5

1 ENDLICHE AUTOMATEN Das Kleene-Stern-Produkt: L∗ =

∪

Ln = L0 ∪ L1 ∪ L2 ∪ L3 ∪ ...

n≥0

Eine Sprache L ⊆ Σ∗ heißt präfixfrei genau dann, wenn für alle Wörter w ∈ L gilt: Ist x ein echter Präfix von w, dann ist x ∈ / L.

1.3 Verhalten von Automaten Man unterscheidet Akzeptor (endlicher Automat ohne Ausgabe) und Transduktor (endlich Automat mit Ausgabe). Die Zustandsüberführungsfunktion ist definiert durch δ ∗ (s, aw) = δ ∗ (δ(s, a), w) für alle a ∈ Σ und w ∈ Σ∗ . δ muss nicht rechtstotal/surjektiv sein. Des Weiteren gilt δ ∗ (s, ε) = s für alle s ∈ S, dabei sei S die Zustandsmenge des Automaten. Ein Konfigurationsübergang von k = (s, w) zu k ′ = (s′ , w ′ ) wird durch (s, w) ⊢ (s′ , w′ ) notiert. Dabei sei ⊢∗ der Konfigurationsübergang in endlich vielen Schritten. Es gilt: δ ∗ (start, aabbba) = stop und (start, aabbba) ⊢∗ (stop, ε).

1.4 Reguläre Sprachen Die Menge aller Eingabewörter w, die einen Automaten von der Startkonfiguration in endlich vielen Schritten in eine Endkonfiguration überführen, heißt die vom Automaten akzeptierte Sprache L(A). Eine Sprache L ⊆ Σ∗ heißt regulär, falls es einen endlichen Automaten gibt, der L akzeptiert, d.h. für den L = L(A) gilt. Sei DF AΣdie Klasse der von endlichen Automaten akzeptierte Sprachen über Σ. Sei REGΣdie Klasse der regulären Sprachen über Σ. Wegen Zeile darüber gilt: DF AΣ= REGΣ

1.5 Vollständige Automaten Jeder Automat kann zu einem vollständigen Automaten erweitert werden. Dazu wird ein neuer Zustand tot eingeführt. Die Zustandsüberführungsfunktion wird dadurch rechtstotal/surjektiv: { δ(s, a), falls δ auf (s, a) definiert ist δ(s, a) = tot, sonst

Seite 6

1 ENDLICHE AUTOMATEN Befindet sich der Automaten einmal auf tot, kann er diesen Zustand nicht mehr verlassen

1.6 Nichtdeterministische endliche Automaten . N F AΣist die Klasse der von nichtdeterministische endliche Automaten akzeptierten Sprachen über dem Alphabet Σ. Ein nicht deterministischer endlicher Automat ist ein Automat in dem es zu einem Zustand und einem Eingabewort mehrere Folgezustände geben kann.

1.7 Äquivalenz von deterministischen und nichtdeterministische endlichen Automaten Sei Σ ein Alphabet. Dann gilt DF AΣ= N F AΣ. Einen nichtdeterministische endlichen Automaten kann man per Potenzmengenkonstruktion in einen deterministischen endlichen Automaten umwandeln.

1.8 Endliche Automaten mit ε-Übergängen εF AΣist die Klasse der von ε-Automaten akzeptierten Sprachen über dem Alphabet Σ. Ein ε-Übergang ist ein Zustandswechsel, ohne dass ein Buchstabe gelesen wird. Sei Σ ein Alphabet. Dann gilt εF AΣ= N F AΣ. Jeder nichtdeterministische Automat ist auch ein (spezieller) ε-Automat nur ohne ε-Übergänge. Durch eine Modifikation des Automaten kann jeder ε-Automat zu einem nichtdeterministische Automaten umgewandelt werden.

1.9 Verallgemeinerte endliche Automaten GF AΣist die Klasse der von verallgemeinert endlichen Automaten akzeptierten Sprachen über dem Alphabet Σ. Für einen verallgemeinert endlicher Automat können Zustandsübergänge für Symbole und Wörter definiert werden.

Seite 7

1 ENDLICHE AUTOMATEN

1.10 Äquivalenz von Automaten Es gilt: REGΣ= DF AΣ= N F AΣ= εF AΣ= GF AΣ

1.11 Minimierung endlicher Automaten Zu jedem deterministischen endlichen Automaten A existiert ein äquivalenter minimaler Automat Amin . Es gibt keinen Automaten, welcher weniger Zustände als Amin besitzt. Amin ist eindeutig, wenn man von der Bezeichnung seiner Zustände absieht, da alle minimalen Automaten zueinander isomorph sind. Bei nichtdeterministischen endlichen Automaten gilt diese Eigenschaft nicht.

Seite 8

2 REGULÄRE SPRACHEN REGΣ

2 Reguläre Sprachen REGΣ Ein regulärer Ausdruck ist ein Muster für die Wörter einer regulären Sprache. Eine Typ-3-Grammatik gibt Regeln an, mit denen die Wörter einer regulären Sprache erzeugt werden können. Reguläre Ausdrücke stellen ein beschreibendes Konzept, Typ-3-Grammatiken ein erzeugendes Konzept für reguläre Sprachen dar.

2.1 Regulärer Ausdruck Sei Σ ein Alphabet. Die Menge der regulären Ausdrücke REXPΣüber Σ ist genau die Menge der Wörter über Σ ∪ {∅, ε, ∗, |, ◦, (, )}. L(∅) = ∅ definiert die leere Sprache und L(ε) = {ε} legt die Sprache fest, welche nur das leere Wort enthält. Es gilt L(∅∗ ) = (L(∅))∗ = ∅∗ = {ε} = L(ε). Die Bedeutung (Semantik) eines regulären Ausdrucks ist durch die Funktion L : REXPΣ→ ℘(Σ∗ ) definiert, welche jedem regulären Ausdruck über Σ eine Sprache über Σ zuordnet.

2.2 Äquivalenz von endlichen Automaten und regulären Ausdrücken Zu jedem endlichen Automaten A über Σ existiert ein regulärer Ausdruck α über Σ, so dass L(A) = L(α) gilt. Zu jedem regulären Ausdruck α über Σ existiert ein endlicher Automat A über Σ, so dass L(α) = L(A) gilt.

2.3 Typ-3-Grammatiken Sei Σ ein Alphabet. Eine (links- oder rechtslineare) Grammatik G = (Σ, N, P, S ) über Σ besteht aus dem Terminalalphabet Σ, dem davon disjunkten Nonterminalalphabet N , einer Produktionsmenge P sowie dem Startsymbol S ∈ N . Die Elemente p = (l, r) ∈ P heißen Produktionen oder Regeln. P ist die Produktions- bzw. Regelmenge von G. l heißt die linke, r die rechte Seite der

Seite 9

2 REGULÄRE SPRACHEN REGΣ Regel p. Die von G erzeugte Sprache L(G) ist definiert durch L(G) = {w ∈ Σ∗ | S ⇒∗ w}. L(G) ist die Menge der Terminalwörter, die aus dem Startsymbol in endlich vielen Schritten abgeleitet werden können. Zwei Grammatiken G1 und G2 heißen äquivalent falls L(G1 ) = L(G2 ) gilt.

2.4 Rechtslineare Typ-3-Grammatiken Bei rechtslinearen Grammatiken darf die rechte Seite w2 einer Produktion w1 → w2 nur das leere Wort (A → ε), ein Terminalsymbol (A → a) oder ein Terminal gefolgt von einem einzigen Nichtterminal sein (A → aB). Sei daher P ⊆ N × (ΣN ∪ Σ ∪ {ε}). Eine Sprache L ⊆ Σ∗ heißt rechtslinear, falls eine rechtslineare Grammatik G über Σ existiert mit L = L(G). Sei ReLΣdie Klasse der rechtslinearen Sprachen über Σ bezeichnen.

2.5 Linkslineare Typ-3-Grammatiken Bei linkslinearen Grammatiken darf umgekehrt die rechte Seite w2 einer Produktion nur das leere Wort, ein Terminalsymbol oder ein Nichtterminal gefolgt von einem Terminal sein (A → Ba). Sei daher P ⊆ N × (N Σ ∪ Σ ∪ {ε}). Eine Sprache L ⊆ Σ∗ heißt linkslinear, falls eine linkslineare Grammatik G über Σ existiert mit L = L(G). Sei LiLΣdie Klasse der linkslinearen Sprachen über Σ bezeichnen.

2.6 Äquivalenz rechtslinearer und linkslinearer Grammatiken Es gilt: ReLΣ = LiLΣ, da zu jeder rechtslinearen Grammatik eine äquivalente linkslineare existiert (und umgekehrt). Rechts- und Linkslineare Grammatiken

Seite 10

2 REGULÄRE SPRACHEN REGΣ erzeugen dieselbe Sprachklasse. Die Elemente dieser Sprachklasse seien die Typ-3Sprachen. Sei T Y P 3Σdie Klasse aller Typ-3-Sprachen über Σ.

2.7 Verallgemeinerte Typ-3-Grammatiken Verallgemeinerte Typ-3-Grammatiken erzeugen bei einer Produktion nicht nur einen Terminalbuchstabel sondern ein Terminalwort. Somit gilt bei der Projektion A → uB (oder A → Bu): u ∈ Σ+ . Sei GT Y P 3Σdie Klasse der mit verallgemeinerten Typ-3-Grammatiken erzeugbaren Sprachen über dem Alphabet Σ. Sei T Y P 3Σ= GT Y P 3Σ, da sich eine Produktion einer verallgemeinerten Typ-3-Grammatik als Hintereinanderausführung von Produktionen mit Terminalsymbolen darstellen lässt.

2.8 Äquivalenz von endlich Automaten und Typ-3-Grammatiken Zu jeder Typ-3-Grammatik G über dem Alphabet Σ existiert ein endlicher Automat A über Σ mit L(G) = L(A). Zu jedem endlichen Automaten A über dem Alphabet Σ existiert eine rechtslineare Grammatik G über Σ mit L(A) = L(G). Somit gilt: REGΣ= T Y P 3Σ.

2.9 Abschlusseigenschaften von REGΣ Sei Σ ein Alphabet, dann gilt: 1. ∅ ∈ REGΣ, d.h. die leere Sprache ist regulär 2. Σ ∈ REGΣ, d.h. das Alphabet ist selbst eine reguläre Sprache 3. Σ∗ ∈ REGΣ, d.h. die Menge aller Wörter ist eine reguläre Sprache

Seite 11

2 REGULÄRE SPRACHEN REGΣ 4. {w} ∈ REGΣfür alle w ∈ Σ∗ , d.h. jede aus einem Wort bestehende Sprache ist regulär 5. L ∈ REGΣfür jede endliche Sprache L ⊆ Σ∗ , d.h. jede endliche Sprache ist regulär Sei Σ ein Alphabet und seien L, L1 , L2 ∈ REGΣ, dann gilt: 1. L1 ∪ L2 ∈ REGΣ, d.h. die Vereinigung regulärer Sprachen ist regulär 2. L1 − L2 ∈ REGΣ, d.h. die Differenz regulärer Sprachen ist regulär 3. Σ∗ − L ∈ REGΣ, d.h. das Komplement einer regulärer Sprachen ist regulär 4. L1 ∩ L2 ∈ REGΣ, d.h. der Durchschnitt regulärer Sprachen ist regulär 5. L1 ◦ L2 ∈ REGΣ, d.h. die Konkatenation regulärer Sprachen ist regulär 6. L∗ ∈ REGΣ, d.h. das Kleene-Stern-Produkt einer regulärer Sprachen ist regulär 7. SP (L) ∈ REGΣ, d.h. die Spiegelung regulärer Sprachen ist regulär

2.10 Entscheidbarkeitsprobleme Seien L, L1 und L2 reguläre Sprachen über Σ. Die folgenden Probleme sind entscheidbar, d.h. es gibt Algorithmen zur Lösung der Probleme: ?

1. das Wortproblem: w ∈ L ? 2. das Leerheitsproblem: L = ∅ ?

3. das Endlichkeitsproblem: |L| < ∞ ?

4. das Durchschnittsproblem: L1 ∩ L2 = ∅ ?

5. das Äquivalenzproblem: L1 = L2

Seite 12

3 ENDLICHE MASCHINEN

3 Endliche Maschinen WICHTIG! In anderen Quellen wird nicht zwischen Automaten und Maschinen unterschieden. Endliche Maschinen erzeugen, im Gegensatz zu endlichen Automaten, eine Ausgabe (Akzeptor (Acceptor) und Transduktor (Transducer)). Primär unterscheidet man zwischen der Mealy- und Moore-Maschine (Mealy machine und Moore maschine). Eine endliche Maschine ist der Endzustand nicht von Interesse, da es nicht um das Akzeptieren von Sprachen sondern um das Transformieren von Wörtern geht.

3.1 Mealy-Maschine Sei M = (Σ, ∆, S, δ, λ, s0 ) eine (nichtdeterministische) Mealy-Maschine. Dann ist Σ das Eingabealphabet, ∆ das Ausgabealphabet, S die endliche Zustandsmenge, δ : S × Σ → S die Zustandsüberführungsfunktion, λ : S × Σ → ∆ die Ausgabefunktion und s0 ∈ S der Startzustand. Eine Konfiguration von M sei kM = (s, v, w) ∈ S × Σ∗ × ∆∗ . Die Konfigurationsübergänge von M sind definiert durch die Relation ⊢M ⊆ (S × Σ∗ × ∆∗ ) × ( S × Σ ∗ × ∆∗ ) . Die Funktion fM : Σ∗ → ∆∗ definiert durch fM (x) = λ∗ (s0 , x) heißt die von M berechnete (Wort-)Funktion. Es gilt fM (x) = y genau dann wenn (s0 , x, ε) ⊢∗ (s, ε, y) gilt, wobei s irgendein Zustand ist. Eine Mealy-Maschine erzeugt die Ausgabe in Abhängigkeit vom aktuellen Zustand und der aktuellen Eingabe. Sei π = (F, A, p) ein Problem. π wird von einer Mealy-Maschine Mπ = (Σ, ∆, S, δ, λ, s0 ) gelöst, falls es eine Eingabecodierung α : F → Σ∗ und eine Ausgabecodierung

Seite 13

3 ENDLICHE MASCHINEN β : ∆∗ → A gibt, so dass p(x) = β(fMπ (α(x))) gilt. Ein Problem heißt Mealyberechenbar, falls es eine Mealy-Maschine gibt, die das Problem löst.

3.2 Moore-Maschine Eine Moore-Maschine gleicht in der Definition einer Mealy-Maschine. Einzig die Ausgabefunktion unterscheidet sich, da die Ausgabe eine Moore-Maschine einzig vom aktuellen Zustand abhängig ist: λ : S → ∆. Sei M = (Σ, ∆, S, δ, λ, s0 ) eine Moore-Maschine. Dann heißt die Funktion fM : Σ∗ → ∆∗ definiert durch fM (x) = y genau dann, wenn (s0 , x, ε) ⊢∗ (s, ε, y) ist, die von M berechnete Funktion. Moore-berechenbar definiert sich synchron zur Mealy-Berechenbarkeit.

3.3 Äquivalenz von Mealy- und Moore-Bereichenbarkeit Eine Mealy-Maschine ME = (ΣM E , SM E , ∆M E , δM E , λME , sM E ) und eine MooreMaschine MO = (ΣM O , SM O , ∆MO , δMO , λMO , sM O ) heißen äquivalent genau dann, wenn fM E (x) = fM O (x) für alle x ∈ Σ∗ gilt. Zu jeder Moore-Maschine MO existiert eine äquivalente Mealy-Maschine MEM O und zu jeder Mealy-Maschine ME existiert eine äquivalente Moore-Maschine MOM E .

Seite 14

4 KONTEXTFREIE SPRACHEN

4 Kontextfreie Sprachen 4.1 Typ-2-Grammatiken Bei einer Typ-3-Grammatik kann höchstens ein Terminalsymbol erzeugt werden. Typ-2-Grammatiken besitzen diese Beschränkung nicht. Sei G eine Grammatik (Σ, N, P, S) mit dem Terminalalphabet Σ, dem davon disjunktem N...