Aufgabe:
Text erkannt:
Aufgabe \( 9.1 \) [Semientscheidbarkeit und Unentscheidbarkeit]
5 Punkte
a) Zeigen Sie, dass das folgende Problem unentscheidbar ist.
Problem: PDACONT
Gegeben: Kellerautomaten \( \mathcal{A}_{1}, \mathcal{A}_{2} \)
Frage: Gilt \( L\left(\mathcal{A}_{1}\right) \subseteq L\left(\mathcal{A}_{2}\right) \) ?
Hinweis
Reduzieren Sie von einem Grammatikproblem
(2,5 Punkte)
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 \in L(G) \), so dass \( w=w^{R} \) ?
(2,5 Punkte)
Ich stehe leider komplett auf dem Schlauch bei dieser Aufgabe. Kann mir irgendjemand weiterhelfen? Ich bin über jede Hilfe dankbar
