0 Daumen
74 Aufrufe

Es sei EVEN-CFL $$=\left\{w | M_{w} \text { ist eine } \mathrm{TM}, \text { sodass } L\left(M_{w} \right) \text{ ausschließlich Worte gerader Länge enthält und kontextfrei ist.}\right .\}$$

Frage : Ist EVEN-CFL entscheidbar?

Versuche an dieser Aufgabe den Beweis von Entscheidbarkeit zu lernen.

Nun sagt der Satz von Rice ja aus, dass semantische Eigenschaften die nicht-trivial sind unentscheidbar sind.


Dies greift doch hier, da es nicht um eine syntaktische Eigenschaft der TM, sondern um die Eigenschaft der Sprache geht, die nicht-trivial ist, da Sprachen existieren, die kontextfrei sind und Andere die nicht kontextfrei sind, wie die rekursive Sprache.

Ebenfalls existieren in beiden Sprache Fälle in denen gerade / ungerade Worte akzeptiert werden je nachdem.


Wie würde man dies nun in einer Prüfung aufschreiben?


Danke bei jeglicher Hilfe.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community