Unterabschnitte
Zu jeder Grammatik

gibt es eine NTM

mit

.
Zu jeder DTM

gibt es eine Grammatik

mit

.
47
Eingabe: |
P (Regeln von ) |
|
S (Startsymbol von ) |
|
w (zu überprüfendes Wort
, wobei Terminalalphabet) |
- Solange
- Wähle nichtdeterministisch eine Regel
aus
- Wenn
ein Teilwort von
ist, ersetze es durch
48
- Wir geben ,,JA'' aus, wenn die Schleife fertig ist.
Typ 0 Sprachen sind unter
- Vereinigung
- Konkatenation
- Kleenabschluß
- sowie dem Durchschnitt (
)49
abgeschlossen.
Unter dem Komplement ist Typ 0 nicht abgeschlossen. Z.B. sind

und

nicht beide semientscheidbar.
Fußnoten
- ....47
- Der zweite Teil ohne Beweis.
- ...
48
- 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ß
. Wenn dies nicht gilt, so ,,hängen'' wir in der Schleife.
- ...)49
- Wir können die Semientscheidungsverfahren der beiden Sprachen parallel oder hintereinander laufen lassen. Wenn beide akzeptieren, dann akzeptiert auch die Durchschnittssprache.