a) Zeigen Sie, dass das folgende Problem unentscheidbar ist.
Problem: PDACont
Gegeben: Kellerautomaten A1, A2
Frage: Gilt L(A1) ⊆ L(A2)?
Hinweis :Reduzieren Sie von einem Grammatikproblem
b) Zeigen Sie, dass das folgende Problem semientscheidbar ist.
Problem: CFGPalindrom
Gegeben: Kontextfreie Grammatik G
Frage: Enthält L(G) ein Palindrom, also gibt es ein Wort w ∈ L(G), so dass w = w^R?
