Kellerautomaten Flashcards
1
Q
Wie ist ein nichtdeterministischer Kellerautomat definiert?
A
2
Q
Wie stehen PDAs und CFLs in Beziehung?
A
Eine Sprache ist kontextfrei genau dann, wenn es einen PDA gibt, der sie akzeptiert
3
Q
Erkläre den Übergangsausdruck
A
a: Input der gelesen wird
b: oberstes Stackelement, das gelesen wird
c: Element, welches auf den Stack gepusht wird
4
Q
Können PDAs erkennen, ob der Input-String das Ende erreicht hat?
A
Nein, aber es lässt sich implementieren
5
Q
Kann ein PDA erkennen, ob dessen Keller leer ist?
A
Nein, aber es lässt sich implementieren anhand eines Symbols, das signalisiert, dass der Keller leer ist
6
Q
Was bedeutet dies?
A
w andersherum geschrieben
7
Q
Wie ist ein deterministischer Kellerautomat definiert?
A
