0 Daumen
123 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?

von

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community