Home       Servicebereich  Projekte  Kontakt  

Logo von LWsystems LWsystems bietet Ihnen systemübergreifende IT-Beratung und umfassenden Service in allen Fragen Ihrer IT-Infrastruktur.
Rufen Sie uns einfach an!

05455- 932 132 oder 05403- 55 56

Anhang


Unterabschnitte

Zusammenfassung

Die Sprachen bzw. die sie erzeugenden Grammatiken lassen sich hierarchisch ordnen. Diese Aufstellung wird als Chomsky-Hierarchie bezeichnet.


Die Chomsky-Hierarchie

Klassifizierung der Grammatiken

Die Grammatiken lassen sich in kontextfreie und kontextsensitive Grammaktiken, sowie in Grammtiken vom Typ-0, Typ-1, Typ-2 und Typ-3 einordnen. Dieses Arten von Grammatiken bilden eine Hierarchie, bei der die Typ-0-Grammatiken die größte Menge darstellen. Die weiteren Typen sind jeweils Untermengen der verhergehenden Typen. Dieses liegt darin begründet, daß der Aufbau der Regelmenge ausgehend von den Typ-0 Grammatiken zu den Typ-3 Grammatiken immer weiter eingeschränkt wird, so daß die mit Ihnen erzeugbarenen Mengen an Sprachen auch immer kleiner werden.

Typ-3-Grammatiken

Eine Regel einer Typ-3-Grammatik kann pro Ableitungsschritt höchstens ein Terminalsymbol mit einer links- oder rechtsseitigen Ableigung erzeugen. Aus diesem Grunde ist die Ableitung einer Sprache der Form $L = \{a^nb^n\vert n \ge0\}$ nicht möglich, da die Anzahl der as und bs bei der Ableitung der beiden Grammatiken gleich sein muß. Dieses läßt sich nur erreichen, indem pro Ableitungsschritt zwei Terminalsymbole erzeugt werden.

Typ-2-Grammatiken (kontextfreie Grammatiken)

Eine Ableitung bei der pro Schritt zwei Terminalsymbole erzeugt werden ist mit der Typ-2-Grammatik möglich. Aus diese

Typ-2-Grammatiken sind kontextfreie Grammatiken. Die Anwendung der einzelnen Regeln erfolgt vollkommen unabhängig vom Kontext des schon erzeugten Wortes. Die linke Seite einer Regel einer kontextfreien Grammatik besteht nur aus einem Nichtterminal, daß dann abgeleitet wird. Die Ableitungsregeln dürfen allerdings

Typ-1-Grammatiken (kontextsensitive Grammatiken)

Die Typ-1-Grammatiken werden auch konstextsensitive Grammatiken genannt. Hier ist der Einsatz der einzelnen Regeln vom Kontext abhängig.

Die linken Seiten der Regeln können aus Wörtern aus nichtterminalen und terminalen Symbolen bestehen, wobei allerdings mindestens 1 Nichtterminal enthalten sein muß. Die Länge der rechten Regelseiten darf nicht kleiner sein als die Linke Seite. Ein Ableitungsschritt erzeugt ein Wort, dessen Länge größer oder gleich der Länge des abzuleitenden Wortes ist. Aus diesem Grunde heißen kontextsensitive Grammatiken monoton.

Die Sprache $L = \{a^nb^nc^n\} \vert n \ge 1$ läßt sich mit einer kontextfreien Grammatik nicht erzeugen, da mit den kontextfreien Regeln zum einen die Anzahl und Reihenfolge der Buchstaben nicht kontrolliert werden kann. Zudem ist der Einsatz der Terminierungsregeln vom Kontext abhängig, da diese nur abhängig vom Kontext eingesetzt werden dürfen. Eine solche Grammatik heißt auch kontextsensitiv.

Typ-0-Grammatiken

Die Typ-0-Grammatiken entstehen aus den Typ-1-Grammatiken wenn die Monotonieeigenschaft aufgehoben wird. Bei Ableitung einer entsprechenden Typ-0-Regel kann die Länge des abgeleitenden Wortes in einem Ableitungsschritt kleiner sein als die des abzuleitenden Wortes.

Mit den Typ-0-Grammatiken wird die Klasse der sogenannten rekursiv-aufzählbaren Sprachen erzeugt. Mit Hilfe einer Typ-0-Grammatik lassen sich fast alle denkbaren Sprachen erzeugen. Nur Sprachen, die überabzählbar sind, also keine einfache bijektive Abbildung (Wörter lassen sich 1 zu 1 auf der Menge der Natürlichen Zahlen abbilden und können somit eindeutig durchnummeriert werden) zulassen lassen sich hiermit nicht erzeugen.

Die Klasse der überabzählbaren Sprachen lassen sich mit keiner Grammatik erzeugen und werden auch von keinem Automaten akzeptiert. Diese Sprachen werden als $2^{\Sigma^*}$ Sprachen bezeichnet.

Hierarchie der Grammatiken

Aus den einzelnen Grammatiken läßt sich die folgende Hierarchie mit den aufgeführten Eigenschaften aufstellen:

Typ Kontext- monotonie links rechts
Typ-0 kontextsensitiv nicht monoton T + nT t
Typ-1 kontextsensitiv monoton T + nT tSt
Typ-2 kontextfrei monoton nT tSt
Typ-3 kontextfrei monoton nT tS oder St

Wobei:

T Terminalsymbol
nT Nichtterminalsymbol
t Terminalsymbol
S Nichtterminalsymbol

Hierarchie der Sprachen

Die Chomsky-Hierarchie ordnet die Sprachen nach ihren Mengenbeziehungen untereinander ein:


\begin{displaymath}REG_\Sigma \subset kfS_\Sigma \subset ksS_\Sigma \subset RE_\Sigma \subset 2^{\Sigma^*}\end{displaymath}

oder

\begin{displaymath}TYP3_\Sigma \subset TYP2_\Sigma \subset TYP1_\Sigma \subset TYP0_\Sigma \subset 2^{\Sigma^*}\end{displaymath}

Zuordnung von Sprachen und Automaten

Die Grammatiken stellen erzeugende Konzepte für Sprachen dar, während Automaten akzeptierende Konzepte sind. Im vorherigen Kapitel wurden die Typen der Grammatiken den einzelnen Sprachtypen zugeordnet. Auch die einzelnen Automatentypen akzeptieren verschiedene Sprachtypen.

Automat Sprachtyp Beispiel
endliche Automaten TYP-3 Sprachen $a^n$
Kellerautomaten TYP-2 Sprachen $a^nb^n$
linear beschr. Turingautomaten TYP-1 Sprachen $a^nb^nc^n$
Turingautomaten TYP-0 Sprachen  

Einfache endliche Automaten sind nur in der Lage die einfachen TYP-3 Sprachen zu erkennen. Das Wortproblem ist für sie nur entscheidbar, wenn keine Forderung an die Sybole eines Wortes der Form

\begin{displaymath}a^nb^n\end{displaymath}

vorliegt, wie es bei TYP-2 Sprachen vorkommt. In einem solchen Falle benötigt der Automat einen zusätzlichen Speicher, in dem er die Anzahl der schon eingelesenen Symbole $a$ ablegt, um diese später mit der Zahl der $b$ Symbole vergleichen zu können.
Um dieses Wortproblem entscheiden zu können benötigt der Automat einen einfachen Stackspeicher wie er beim Kellerautomaten vorhanden ist. Dieser ist im Beispiel so konstruiert, daß er jedes eingelesene Symbol $a$ auf den Stack legt um es beim Einlesen eines Symbols $b$ wieder vom Stack zu entfernen. Wenn der Stack geleert ist, stimmt die Anzahl der Symbole überein.

Eine TYP-1 Sprache verlangt, daß Wörter in der Form $a^nb^nc^n$ vorkommen können. Dieses Wortproblem ist vom Kellerautomaten nicht entscheidbar, da er nur über einen Specher mit sequentiellem Zugriff verfügt und somit nicht für den Vergleich der Anzahl von Buchstaben nicht je nach Eingabesymbol wahlfrei zugreifen kann. Die Erweiterung des Kellerautomaten, der Turingautomat ist in der Lage dieses Problem zu lösen. Er ist aufgrund seines Speicherbandes in der Lage einen wahlfreien Zugriff zum Vergleich beliebiger Symbole durchzuführen.


Entscheidbarkeit des Wortproblems

Das Wortproblem ist für alle Typen von Sprachen außer den den Typ-0 Sprachen entscheidbar. Je nach Automaten- bzw. Sprachtyp wird jedoch die Komplexizität größer. Das heißt, daß die Laufzeit bis zur Akzeptanz eines Wortes größer wird. Bei TYP-3- und DPDA-S liegt hier noch ein linearer Zusammenhang zwischen Wortlänge und Laufzeit bzw. Anzahl der durchzuführenden Operationen vor. Bei den TYP-2-Sprachen mit gegebener Grammatik in Chomsky-Normalform steigt die Laufzeit schon in der 3. Potenz an um bei TYP-1-Grammatiken exponentiell mit der Wortlänge zu steigen. TYP-0-Sprachen schließlich sind hinsichtlich des Wortproblems unlösbar.

next up previous contents
Nächste Seite: Anhang Aufwärts: aut Vorherige Seite: Automaten, Reguläre Ausdrücke und   Inhalt

< zurück