Hallo,
ich glaube das Wortproblem für Chomsky-0 Sprachen ist
semi-entscheidbar, oder ?
Ja.
D.h. doch, dass ich eine Funktion angeben kann, die bei
Eingabe einer Typ-0 Grammatik und eines Wortes über dem
gegebenen Alphabet „ja“ ausgibt, wenn sich das Wort in der
Sprache befindet, die durch die Grammatik aufgebaut wird. Wenn
längere Zeit nichts ausgegeben wird, weiss man nicht, ob das
Wort in der Sprache enthalten ist oder nicht.
Exakt. Mathematischer ausgedrückt, wird hier nur von dem Teil der charakteristischen Funktion der Sprache Berechenbarkeit gefordert, der 1 zurückliefert.
- Frage: Wie lange soll man warten, bis man sagen kann, dass
da nichts mehr rauskommt ?
- Frage: Kann es nicht auch umgekehrt sein, dass „nein“
rauskommt, wenn das Wort nicht in der Sprache enthalten ist
und bei „ja“ die Funktion nicht terminiert ?
Wäre das der Fall, wäre die Sprache einfach nicht semi-entscheidbar. Man hat höchstens abzählbar (unendlich) viele Wörter und für jedes Wort der Sprache eine endliche Anzahl an Schritten, die benötigt werden, um es zu erkennen. Jetzt muß man es unter einen Hut bekommen, daß zu keiner Zeit das Semi-Entscheidungsverfahren resp. Aufzählungsverfahren sich in „unendlichen“ Ästen verliert. Und das geschieht durch:
- Begrenzung der zulässigen Schrittlänge zum Erkennen eines Wortes.
- Für jede Schrittlänge werden nur endlich viele Wörter betrachtet.
- Insgesamt (bei unendlicher Laufzeit) werden alle Schrittlängen und alle Wörter berücksichtigt.
Das geht z.B. indem man eine Schrittlänge n vorgibt und dafür nur Wörter die
