Matroids Matheplanet Forum Index
Moderiert von Bilbo
Informatik » Theoretische Informatik » Entscheidbarkeit von EVEN-CFL (Satz von Rice?)
Autor
Universität/Hochschule Entscheidbarkeit von EVEN-CFL (Satz von Rice?)
rapiz
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 26.11.2019
Mitteilungen: 108
  Themenstart: 2020-03-18

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 sauber aufschreiben? Wäre es so bereits genug? Danke bei jeglicher Hilfe.


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]