Automatentheorie - 4. Semester

Ein Wort v lässt sich aus u erzeugen, falls eine Substitution \(x \to y\) existiert, wobei x Teil des Wortes u ist und y Teil des Wortes v.

Genutzt werden Produktionen aus P, die angeben, welche Substitutionen möglich sind.

\(\forall (x,y) \in P \ \exists(y,x) \in P\), d.h. die Ableitung ist symmetrisch.

Eine Satzform x einer Grammatik ist eine Folge von Symbolen aus N oder \(\Sigma\).

\(x \in (N\cup \Sigma)^*\)

Ein Ableitungsschritt ist Teil einer Ableitung, der mithilfe der Anwendung einer Produktion aus P x nach x' überführt.

Ein Ableitungsstück ist eine endliche Folge (x₀...x_n) von Satzformen, wobei jede Satzform stets aus der vorhergehenden Satzform durch einen Ableitungsschritt \(x_{i-1} \to x_i\) hervorgeht.

Eine Ableitung ist ein Ableitungsstück, das mit dem Startsymbol \(S \in N\) beginnt und dessen letzte Satzform ein Wort \(w \in \Sigma^*\) ist bzw. kein Nonterminal \(A \in N\) mehr enthält.

Zu einem Zeitpunkt kann es mehrere Ableitungsmöglichkeiten geben.

- verschiedene Regeln sind anwendbar

- Regeln sind an verschiedenen Stellen anwendbar.

- Ableitungen können beliebig lang werden.

\(G = (\Sigma, N, P, S)\) mit (Terminalalphabet, Nonterminalalphabet, Menge der Produktionen, Startsymbol aus dem Nonterminalalphabet)

linkslineare Typ 3-Grammatik: Nonterminalsymbol steht in der Ableitung links vom Terminalsymbol, sofern es vorhanden ist. Wörter werden von rechts nach links erzeugt.

rechtslineare Typ 3-Grammatik: Nonterminalsymbol steht in der Ableitung rechts vom Terminalsymbol, sofern es vorhanden ist. Wörter werden von links nach rechts erzeugt.

1.) \(A \to aB \in \Sigma^*N\) Regel zum Erzeugen neuer Buchstaben am rechten Ende des abzuleitenden Wortes

2.) \(A \to a \in \Sigma\) terminierende Regel zum Erzeugen des letzten Buchstabens

3.) \(A \to \varepsilon\) terminierende Regel ohne Erzeugen eines Buchstabens

Sei L eine reguläre Sprache, so existiert ein \(n \in \mathbb N \), sodass sich alle Wörter x aus L mit einer Wortlänge größer oder gleich n in x = uvw zerlegen lassen. Dabei gilt:

1.) \(|v| \geq 1\)

2.) \(|uv| \leq n\)

3.) \(\forall i \in \mathbb N_0: uv^iw \in L\) (Infix des Wortes kann beliebig aufgepumpt werden)

- wenn die Sprache L regulär ist

- erfülltes Pumping Lemma heißt jedoch nicht, dass die Sprache regulär ist

- DEA, NEA, Epsilon-Automaten

- verallgemeinerte endliche Automaten

- reguläre Ausdrücke

- Rechtskongruenzen (siehe Satz von Myhill Nerode)

- rechtslineare und linkslineare Grammatiken

- deterministische Kellerautomaten DPDA

- kontextfreie Grammatiken

- Kellerautomaten

- kontextsensitive Grammatiken

- linear beschränkte Automaten

- Typ 0 Grammatiken

- Turingautomaten

Typ 3: alle

DPDA: Differenz

Typ 2: Vereinigung, Konkatenation, Kleene-Stern

Typ 1: alle

Typ 0: Schnitt, Vereinigung, Konkatenation, Kleene-Stern

Typ 3: alle

DPDA: alle

Typ 2: Wortproblem, Leerheitsproblem, Endlichkeitsproblem

Typ 1: Wortproblem

Typ 0: keins

Eine Grammatik heißt kontextfrei, falls die Menge der Ableitungsregeln |P| mit \(P \subseteq N \times (\Sigma \cup N)^*\) endlich ist. Das heißt, dass die Restriktion bezüglich der Position des Nonterminals aufgehoben ist und ein Nonterminal in min. ein Nonterminal und beliebig viele Terminale abgeleitet werden darf.

Chomsky-Normalform und Greibachnormalform

Jedes Nonterminal wird in zwei Nonterminale oder in ein Terminalsymbol abgeleitet.

1.) Eliminierung der Epsilon-Regeln, indem die Ersetzung eines Nonterminals durch Epsilon in den anderen Regeln vorweggenommen wird. Bsp.: \(A \to aA, A\to aB, B \to \varepsilon \ wird \ zu \ A\to aA, A\to a\)

2.) Eliminierung von Kettenregeln \(A \to B\), die nichts zur Worterzeugung beitragen

3.) Separation von Terminalsymbolen (Einsatz eines "Zwischen-Nonterminals", um kein Nonterminal in einer Terminal- und ein Nonterminalsymbol abzuleiten)

4.) Eliminierung von mehrelementigen Nonterminalketten

Die Produktionen müssen in der Form \(P \subseteq N \times (\Sigma \circ N^*)\) darstellbar sein. Das heißt, dass ein Nonterminal in maximal ein Terminal- und beliebig viele Nonterminalsymbole abgeleitet wird.

Falls es für min. ein Wort zwei oder mehr Ableitungsbäume gibt.

Wenn sie in eine eindeutige Grammatik überführt werden kann, so heißt sie inhärent mehrdeutig.

Es gibt eine natürliche Zahl n, sodass für alle Wörter z aus L mit \(|z| \geq n\) gilt:

z = uvwxy

\(|vx| \geq 1\)

\(|vwx| \leq n\)

\(\forall i \geq 0: uv^i wx^iy \in L\)

Ist die Sprache kontextfrei, ist das Pumping-Lemma erfüllt. Ein erfülltes Pumping-Lemma bedeutet jedoch nicht, dass die Sprache kontextfrei ist.

- "Gedächtnisfunktion" durch unendlich großen Kellerspeicher mit Stack-Funktionalität

- Zeichenablage nach dem LIFO-Prinzip, es wird jeweils nur das oberste Zeichen im Keller gelesen

\(K = (\Sigma, S, \Gamma, \delta, s_0, \perp, F)\) mit \(\Gamma\) als Stack und \(\perp\)als bottom-Symbol.

\(d: S \times (\Sigma \cup \{\varepsilon\}) \times \Gamma \to P(S\times\Gamma^*)\)

Man ist in einem Zustand, liest ein Zeichen aus dem Eingabeband oder ein Epsilon sowie anschließend das oberste Zeichen aus dem Stack. Daraus folgt ein Zustand und eine Eingabe in den Stack.

Sobald der Kellerautomat einen Endzustand erreicht hat und im Keller nur noch das Bottom-Symbol enthalten ist bzw. der Keller vollständig leer ist.

\(P \subseteq ((\Sigma \cup N)^*\setminus \Sigma^*)\times(\Sigma\cup N)^*\)

Das heißt, dass ein Nonterminal oder eine Verbindung aus Nonterminalen und Terminalen in eine Verbindung aus Nonterminal- und Terminalsymbolen abgeleitet werden kann, wobei auf der linken Seite der Ableitung nicht mehr Zeichen als auf der rechten Seite stehen dürfen. Damit ist es möglich, Verkettungen von Terminal- und Nonterminalsymbolen direkt abzuleiten.

Monotonie-Eigenschaft: Satzform a darf nicht länger sein als die abgeleitete Satzform b.

Das leere Wort verletzt diese Monotonie-Eigenschaft. Als einzige Regel, die diese Eigenschaft verletzt, wird daher die Ableitung des Startsymbols in Epsilon zugelassen (nur das Startsymbol!).

Typ 1-Grammatik ohne Monotonie-Beschränkung

Reduktionsregel: \(A \to \varepsilon\), Nonterminale werden gelöscht

Terminierungsregel: \(A \to a\)

Expansionsregel: \(A \to AB\), Nonterminal wird in 2 Nonterminale umgewandelt

Doppelsubstitutionsregel: \(AB \to CD\), 2 Nonterminale werden durch 2 andere Nonterminale ersetzt