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 eine Satzform einer Grammatik?

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

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

Fenster schliessen

Was ist ein Ableitungsschritt?

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

Fenster schliessen

Was ist ein Ableitungsstück?

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

Fenster schliessen

Was ist eine Ableitung?

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.

Fenster schliessen

Warum ist das Ableiten kein deterministischer Prozess?

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.

Fenster schliessen

Wie werden Typ 3-Grammatiken definiert?

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

Fenster schliessen

Erklären Sie linkslinear und rechtslinear in Bezug auf Typ-3-Grammatiken.

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.

Fenster schliessen

Welche 3 Typen von Regeln sind bei Typ 3-Grammatiken zugelassen?

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