Lernkarten
Was ist ein Kellerautomat?
- "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
Wie werden nicht-deterministische Kellerautomaten formal beschrieben?
\(K = (\Sigma, S, \Gamma, \delta, s_0, \perp, F)\) mit \(\Gamma\) als Stack und \(\perp\)als bottom-Symbol.
Wie ist die Zustandsübergangsfunktion eines nicht-deterministischen Kellerautomaten formal beschrieben?
\(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.
Wann gilt ein Wort durch einen Kellerautomaten als akzeptiert?
Sobald der Kellerautomat einen Endzustand erreicht hat und im Keller nur noch das Bottom-Symbol enthalten ist bzw. der Keller vollständig leer ist.
Wann heißt eine Grammatik kontextsensitiv?
\(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.
Welches Problem stellt das leere Wort Epsilon für Typ 1 Grammatiken dar?
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!).
Was sind Typ 0 Grammatiken?
Typ 1-Grammatik ohne Monotonie-Beschränkung
Welche 4 Grundtypen ergeben sich für die Produktionen von Typ 0-Grammatiken?
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
