Lernkarten

Karten 80 Karten
Lernende 4 Lernende
Sprache Deutsch
Stufe Universität
Erstellt / Aktualisiert 29.03.2016 / 02.10.2018
Lizenzierung Keine Angabe
Weblink
Einbinden
0 Exakte Antworten 80 Text Antworten 0 Multiple Choice Antworten
Fenster schliessen

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

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

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.

Fenster schliessen

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!).

Fenster schliessen

Was sind Typ 0 Grammatiken?

Typ 1-Grammatik ohne Monotonie-Beschränkung

 

Fenster schliessen

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