0 Daumen
404 Aufrufe

(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?

Avatar von

kann jemand mir bitte die Lösung geben?

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community