PDAs

Welche Aussage ist korrekt?

• Jede kontextfreie Sprache kann von einem DFA erkannt werden

• Jeder PDA erkennt genau die regulären Sprachen

• Für jede kontextfreie Sprache existiert ein PDA

• Reguläre Sprachen sind Typ-2 im Chomsky-Hierarchie

Ordne die Grammatiken den Chomsky-Typen korrekt zu:

• regulär, kontextfrei, kontextsensitiv, rekursiv aufzählbar

• kontextfrei, regulär, kontextsensitiv, rekursiv

• regulär, kontextsensitiv, kontextfrei, rekursiv

• regulär, regulär, regulär, regulär

Was beschreibt die Transitionsrelation Δ eines Kellerautomaten?

• Eine Relation, die nur Eingabe und Folgezustände betrachtet

• Δ⊆Q×(Σ∪{ε})×Γ×Q×Γ^∗

• Eine Relation über Zustände, Eingabesymbole, Kellersymbole und Folgezustände

• Eine Relation über Zustände, Eingabesymbole, Kellersymbole und Folgezustände und Kellersymbole

Was ist eine kontextfreie Grammatik?

• Eine Grammatik mit Produktionen der Form A→α, wobei A∈V, α∈(V∪Σ)∗

• Eine Grammatik mit Produktionen, bei denen auf der linken Seite genau ein Nichtterminal steht

• Eine Grammatik mit Produktionen der Form A→α, wobei A∈V/S, α∈(V∪Σ)+ .

• Eine Grammatik mit beliebigen Produktionen α→β, wobei ∣α∣≤∣β∣

Was beschreibt eine Typ-3 Grammatik (regulär)?

• Produktionen der Form A→aB oder A→a mit A,B∈V,a∈Σ

• Produktionen der Form A→aB oder A→a mit A,B∈V,a∈Σ^*

• Beliebige Produktionen mit Variablen auf beiden Seiten

• Produktionen der Form A→BC

Was ist eine Typ-1 Grammatik (kontextsensitive)?

• Produktionen der Form A→a

• Alle Produktionen l→r mit ∣l∣≤∣r∣

• Nur Produktionen mit rechten Seiten aus Terminals

• Produktionen wie A→ε ohne Einschränkungen

Welche algorithmischen Probleme sind bei Typ-3 Grammatiken lösbar?

• Wortproblem

• Leerheitsproblem

• Äquivalenzproblem

• Keine der genannten

Welche algorithmischen Probleme sind bei Typ-2 Grammatiken lösbar?

• Wortproblem

• Leerheitsproblem

• Äquivalenzproblem

• Keine der genannten

Welche algorithmischen Probleme sind bei Typ-1 Grammatiken lösbar?

• Wortproblem

• Leerheitsproblem

• Äquivalenzproblem

• Keine der genannten

Welche algorithmischen Probleme sind bei Typ-0 Grammatiken lösbar?

• Wortproblem

• Leerheitsproblem

• Äquivalenzproblem

• Keine der genannten