Formale Sprachen #23 - Erkennbar folgt kontextfrei

Jede erkennbare Sprache ist kontextfrei. Hierfür geben wir eine Beweisskizze, indem wir aus einem endlichen Automaten eine kontextfreie Grammatik konstruieren, welche die selbe Sprache erzeugt.

[@Neos4398]

„Falls das bisschen doof erklärt war“ - ne man das war besser erklärt als alles, was ich dieses Semester an der Uni zu hören bekommen habe!!

[@drstoned8523]

genau so muss man erkären, danke

[@Christian-rq5xf]

Genial

[@francescogruen2385]

Richtig gut erklärt, danke dafür. Könnten sich meine Profs mal ne Scheine von abschneiden.

[@edi9840]

Danke!

[@DDEVIL1193]

Kann man auch von dem Zustand U einfach machen U -> a würde ja dann auch erkannt werden, und man hätte kein Epsilon Übergang in der Grammatik. Oder ist das dann nicht mehr kontextfrei?

[@NLogSpace]

Das könnte man machen, aber um sämtliche Epsilonregeln loszuwerden müsste man dann solche Regeln für jede Kante einführen, die auf einen Endzustand zeigt, also auch noch T --> b und S --> a. Wenn allerdings S auch ein Endzustand wäre, würde man um Epsilon-Regeln nicht herumkommen, dann müsste man die Regel S->epsilon einführen. Die resultierende Grammatik wäre also etwas komplizierter, aber es würde auch funktionieren.

[@jhoana3570]

Hallo Leif,
wir haben bei uns in Formale Sprachen gelernt, dass ab den Kontextsensitiven Sprachen gilt, dass mit jeder Produktion das Wort wächst, d.h. rechts darf nicht das leere Wort stehen. Also formal: Für alpha -> beta gilt | alpha |

[@NLogSpace]

Hi Jhoana,
also das ist so: Bei kontextsensitiven Grammatiken sind diese verkürzenden Produktionen nicht erlaubt, bei kontextfreien und rechtslinearen Grammatiken hingegen schon.
Wichtig ist aber: Man kann jede kontextfreie Grammatik in eine neue Grammatik umwandeln, die immer noch die gleiche Sprache erzeugt, aber keine verkürzenden Regeln mehr hat. Das macht man, indem man die Chomsky-Normalform bildet.
Bedeutet unterm Strich: Nicht jede kontextfreie Grammatik ist auch eine kontextsensitive Grammatik, aber jede kontextfreie Sprache ist eine kontextsensitive Sprache.
Viele Grüße
Leif

[@JeyWiTV]

Aber ist die letztendliche Grammatik denn nicht eigentlich vom Typ-3, also rechtslinear?

[@NLogSpace]

+Ching Wu Richtig, die Grammatik rechtslinear, also vom Typ 3. Aber jede Typ-3-Grammatik ist auch von Typ 2, und die definieren genau die kontextfreien Sprachen. Und das wollten wir letztendlich zeigen: Jede erkennbare Sprache ist kontextfrei.

[@FrogEnjoyer17]

Also NEA bzw DEA erkennbar, weil turing-erkennbare Sprachen können ja auch Kontextsensitiv sein, oder hab ich das falsch verstanden?

[@NLogSpace]

Ich verstehe die Frage nicht, kannst Du die nochmal ausführlicher formulieren?

[@FrogEnjoyer17]

@@NLogSpacesorry,
also die Aussage des Videos ist: Erkennbar => Kontextfrei
und wir wissen Erkennbar Es existiert eine Turing Maschine welche alle Wörter aus der Sprache akzeptiert rekursiv aufzählbare Sprache
Aufgrund der Transitivität würde das bedeuten: rekursiv aufzählbare Sprache => Kontextfrei
Jetzt ist aber beispielsweise eine kontextsensitive Sprache ja auch erkennbar aber nicht kontextfrei.
Deshalb frage ich mich ob hier die DEA/NEA-Erkennbarkeit gemeint ist und nicht die allgemeine bzw Turing Erkennbarkeit

[@Wabadabadubdup]

Also jede erkennbare Grammatik ist Teilmenge einer kontextfreien Grammatik?

[@NLogSpace]

Ich denke Du meinst das richtige, aber Du verwendest die Begriffe falsch: Mit "erkennbare Grammatik" meinst Du wahrscheinlich "rechtslineare Grammatik", denn erkennbare Grammatiken haben wir nicht definiert. Und eine rechtslineare Grammatik ist nicht "Teilmenge" einer kontextfreien Grammatik, denn eine kontextfreie Grammatik ist keine Menge. Jede rechtslineare Grammatik ist einfach eine kontextfreie Grammatik.

[@Wabadabadubdup]

@@NLogSpace Danke für die Antwort