Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Wortproblem für Typ 0 Aufwärts: Grammatiken Vorherige Seite: Sprachen vom Typ 0   Inhalt

Unterabschnitte

Kontextsensitive Sprachen - Typ 1

LBAs - Linear beschränkte Automaten

Linear beschränkte Automaten sind NTMs, die mit linear beschränktem Platz auskommen. Sie sind durch zwei Begrenzungssymbole $\$ $ und $\char93 $ links und rechts beschränkt.
Zu jeder kontextsensitiven Grammatik $G$ gibt es einen LBA $\tau$ mit

\begin{displaymath}L_{LBA}(\tau)=L(G)\end{displaymath}

Zu jedem LBA $\tau$ gibt es eine Grammatik $G$ mit

\begin{displaymath}L(G)=L_{LBA}(\tau)\end{displaymath}

Determinismus $\leftrightarrow$ Nichtdeterminismus

Die Frage, ob deterministsche LBAs und nichtdeterministische LBAs die selben Sprachen akzeptieren können, ist noch nicht gelöst.

Wortproblem

Der Algorithmus kann als nichtdeterministisches Zusammenschieben bezeichnet werden.
  • 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$.
    • Schiebe den LBA um $\vert v\vert-\vert u\vert$ Stellen zusammen. Das sind genau die Stellen, die nun nicht mehr benötigt werden.
  • Wenn die Schleife erfolgreich abgelaufen ist, geben wir ,,JA'' aus.

Abgeschlossenheit

Typ 1 Sprachen sind zusätzlich zu der Abgeschlossenheit von Typ 0 Sprachen auch unter dem Komplement abgeschlossen.
next up previous contents
Nächste Seite: Wortproblem für Typ 0 Aufwärts: Grammatiken Vorherige Seite: Sprachen vom Typ 0   Inhalt