Sprachen vom Typ 0 ::: Theoretische Informatik

Zu jeder Grammatik

gibt es eine NTM $\tau$ mit $L(G)=L(\tau)$ .
Zu jeder DTM $\tau$ gibt es eine Grammatik

mit $L(\tau)=L(G)$ .⁴⁷

Eingabe:	P (Regeln von )
	S (Startsymbol von )
	w (zu überprüfendes Wort $w\in\Sigma^{*}$ , wobei $\Sigma$ Terminalalphabet)

Solange
- Wähle nichtdeterministisch eine Regel $u\rightarrow v$ aus
- Wenn ein Teilwort von ist, ersetze es durch ⁴⁸
Wir geben ,,JA'' aus, wenn die Schleife fertig ist.

Typ 0 Sprachen sind unter

abgeschlossen.

Unter dem Komplement ist Typ 0 nicht abgeschlossen. Z.B. sind

und $\overline{H}$ nicht beide semientscheidbar.

....⁴⁷: Der zweite Teil ohne Beweis.
...⁴⁸: Der Baum zur Erzeugung von wird rückwärts verfolgt, bis wir das Wort auf das Startsymbol reduziert haben, so daß wir sagen können, daß $w\in L(G)$ . Wenn dies nicht gilt, so ,,hängen'' wir in der Schleife.
...)⁴⁹: Wir können die Semientscheidungsverfahren der beiden Sprachen parallel oder hintereinander laufen lassen. Wenn beide akzeptieren, dann akzeptiert auch die Durchschnittssprache.

Ψ Die Informatikseite