Rekursive Aufzählung < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:05 Fr 18.01.2013 | | Autor: | starki |
| Aufgabe | Es sei G eine beliebige Typ-0-Grammatik.
(a) Geben Sie eine rekursive Aufzählung der von G erzeugten Sprache [mm] L_G [/mm] an.
(b) Geben Sie ein Semi-Entscheidungsverfahren für das Wortproblem von [mm] L_G [/mm] an.
Beweisen Sie die Korrektheit der Aufzählungsfunktion (a) bzw. des Verfahrens (b). |
Also folgende Dinge habe ich mittlerweile herausgefunden, die wichtig wären für die Aufgabe:
* Da G eine Typ-0-Grammatik, gibt es für sie eine Turingmaschine.
* Eine rekursive Aufzählung ist eine totale und berechenbare Funktion. Nun bin ich am überlegen, was das für eine Funktion ist. Ich hege den Verdacht, dass es sich um f: [mm] \IN \rightarrow [/mm] L geht.
Meine derzeitige Idee ist es, die Funktion f: [mm] \IN \rightarrow [/mm] L zu kreieren, indem ich sage: Es gibt ja eine Turingmaschine, die alle Wörter der Grammatik G auf ein Band aufschreibt. Diese zähle ich und sage: f(n) = das Wort an der n-ten Stelle. Doch kann ich diesen Ansatz wählen oder brauche ich dafür was anderes? Und falls ja, könntet ihr mir ein paar Hinweise dafür geben?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 So 20.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
