/
-
- 1 / 80
-
Cartes-fiches
Geben Sie für jede Sprachklasse an, welche Entscheidungsprobleme (Wortproblem, Leerheitsproblem, Endlichkeitsproblem, Äquivalenzproblem) sie betreffen.
Typ 3: alle
DPDA: alle
Typ 2: Wortproblem, Leerheitsproblem, Endlichkeitsproblem
Typ 1: Wortproblem
Typ 0: keins
Wann heißt eine Grammatik kontextfrei (Typ 2)?
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.
Welche beiden Normalformen gibt es für Typ 2-Grammatiken?
Chomsky-Normalform und Greibachnormalform
Wie wird die Chomsky-Normalform gebildet?
Jedes Nonterminal wird in zwei Nonterminale oder in ein Terminalsymbol abgeleitet.
Welche Transformationsregeln gibt es zur Vereinfachung von Typ 2-Grammatiken?
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
Wie wird die Greibach-Normalform gebildet?
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.
Wann heißt eine kontextfreie Grammatik mehrdeutig und wie nennt sie sich, wenn sie in eine eindeutige Grammatik überführt werden kann?
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.
Wie funktioniert das Pumping-Lemma für kontextfreie Sprachen?
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.
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
