Automatentheorie - 4. Semester

- 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

endliche, abgeschlossene Menge vereinbarter, eindeutiger, unterscheidbarer, unzerlegbarer Einzelzeichen / Symbole

Reihe aus Elementen eines Alphabets

Menge von Zeichenreihen aus Eingabezeichen

- Menge der Zeichenreihen einer natürlichen Sprache

- Menge aller von einem endlichen Automaten akzeptierten Zeichenreihen

Wenn zwei Alphabete durch eine Operation (z.B. Differenz, Vereinigung, Schnittmenge) verbunden werden, ist das Ergebnis ebenfalls ein Alphabet.

Bsp.: Wenn A und B reguläre Sprachen sind, dann ist auch A vereinigt B eine reguläre Sprache.

Diese Rechnung kann genutzt werden, wenn die Schnittmenge der beiden Alphabete die leere Menge ist, sie also keine gemeinsamen Elemente haben. Andernfalls würden diese doppelt gezählt werden.

| Potenzmenge des Alphabetes | = 2 ^|Alphabet|

\(\Sigma \times \Sigma \to \Sigma ^*\)

Das leere Wort ^{\(\varepsilon\)} ist das Neutralelement. Jedes Wort lässt sich als Verkettung beliebiger Zeichen aus \(\Sigma\) mit dem leeren Wort in beliebiger Häufigkeit darstellen. Z.B. w = ab = \(a\varepsilon\varepsilon b \varepsilon\)

Definition eines Alphabetes mithilfe einer Eigenschaft ^\(\xi\)(a_i)

Sinnvoll, falls Elemente von \(\Sigma\) eine Teilmenge einer Obermenge A darstellen.

wiederholte Konkatenation des Zeichens mit sich selbst

0-te Potenz entspricht dem leeren Wort

rekursive Definition:

a¹= a⁰ • a¹ = a, a² = a⁰ • a¹ • a¹

Die Potenzbildung eines Zeichens lässt sich auch auf Zeichenmengen übertragen. Die Vereinigung aller Potenzen über \(\Sigma\) bildet den Kleene-Abschluss \(\Sigma\)*.
\(\Sigma^* \setminus \{\varepsilon\} = \Sigma^+\)

Sortierung gemäß der Länge der Wörter

Wörter gleicher Länge werden stellenwertig hinsichtlich der enthaltenen Alphabetzeichen sortiert.

x ist Präfix von w und x ist ungleich w und ungleich dem leeren Wort

Eine Sprache ist präfixfrei, wenn eine Wort x aus Präfix, Infix und Suffix besteht und der Präfix nicht Teil der Sprache ist.

Die deutsche Sprache ist z.B. nicht präfixfrei: "ausmachen" ist ein Wort mit dem Präfix "aus", was ebenfalls ein Wort der deutschen Sprache ist.

als formale Sprache L über \(\Sigma\)

über die Konkatenation der Elemente (jedes Element einer Sprache mit alle Elementen der anderen Sprache)

akzeptierende Konzepte --> endliche Automaten

beschreibende Konzepte --> reguläre Ausdrücke

erzeugende Konzepte --> Grammatiken

Transduktoren: Moore Maschine, Mealy Maschine

Akzeptoren: nichtdeterministischer endlicher Automat NEA, deterministischer endlicher Automat DEA, ^{\(\varepsilon\)} - endlicher Automat

Quintupel: (\(\Sigma\), S, \(\delta\), s₀, F) --> (Eingabealphabet, Zustandsmenge, Zustandsübergangsfunktion, Anfangszustand, Endzustandsmenge)

\(\delta\) : S x \(\Sigma\) --> S