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.