Unterabschnitte
Zu jeder Grammatik
![$G$](img402.png)
gibt es eine NTM
![$\tau$](img64.png)
mit
![$L(G)=L(\tau)$](img436.png)
.
Zu jeder DTM
![$\tau$](img64.png)
gibt es eine Grammatik
![$G$](img402.png)
mit
![$L(\tau)=L(G)$](img437.png)
.
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
![$H$](img143.png)
und
![$\overline{H}$](img167.png)
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.