Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Kontextsensitive Sprachen - Typ Aufwärts: Grammatiken Vorherige Seite: Abschlußeigenschaften   Inhalt

Unterabschnitte

Sprachen vom Typ 0

Allgemein

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

Nichtdeterministisches Semientscheidungsverfahren für das Wortproblem

Eingabe: P (Regeln von $G$)
  S (Startsymbol von $G$)
  w (zu überprüfendes Wort $w\in\Sigma^{*}$, wobei $\Sigma$ Terminalalphabet)
  • Solange $w\not= S$
    • Wähle nichtdeterministisch eine Regel $u\rightarrow v$ aus $P$
    • Wenn $v$ ein Teilwort von $w$ ist, ersetze es durch $u$48
  • Wir geben ,,JA'' aus, wenn die Schleife fertig ist.

Abgeschlossenheit

Typ 0 Sprachen sind unter
  • Vereinigung
  • Konkatenation
  • Kleenabschluß
  • sowie dem Durchschnitt ( $L_{1}\cap L_{2}$)49
abgeschlossen.

Unter dem Komplement ist Typ 0 nicht abgeschlossen. Z.B. sind $H$ und $\overline{H}$ nicht beide semientscheidbar.

Fußnoten

....47
Der zweite Teil ohne Beweis.
...$u$48
Der Baum zur Erzeugung von $w$ 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.
...)49
Wir können die Semientscheidungsverfahren der beiden Sprachen parallel oder hintereinander laufen lassen. Wenn beide akzeptieren, dann akzeptiert auch die Durchschnittssprache.
next up previous contents
Nächste Seite: Kontextsensitive Sprachen - Typ Aufwärts: Grammatiken Vorherige Seite: Abschlußeigenschaften   Inhalt