 |
powered by 
|
| Nachrichten | Lexikon | Protokolle | Bücher | Foren | Freitag, 24. Mai 2013 |
Chomsky-HierarchieDieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier. Die Chomsky-Hierarchie ist eine Hierarchie von Klassen formaler Grammatiken die formale Sprachen erzeugen. Sie wurde 1956 von Noam Chomsky beschrieben. Sei im Folgenden die formale Grammatik <math>G = \left( N \Sigma P \right)</math> angenommen. <math>N</math> stellt wie üblich die der Nichtterminalsymbole <math>\Sigma</math> die Menge der Terminalsymbole die Menge von Regeln und <math>S</math> das dar (Einzelheiten siehe unter formale Grammatik ).
Die HierarchieDie Chomsky-Hierarchie besteht aus folgenden Ebenen:
Typ-0-GrammatikenTyp-0-Grammatiken werden auch unbeschränkte Grammatiken genannt. handelt sich dabei um alle definierbaren Grammatiken. Man schreibt <math>G \in Typ_0</math>. Jede Typ-0-Grammatik erzeugt eine Sprache die einer Turing-Maschine akzeptiert werden kann und für jede Sprache von einer Turing-Maschine akzeptiert werden kann existiert Typ-0-Grammatik die diese Sprache erzeugt. Eine Sprache von einer Turing-Maschine akzeptiert werden kann ist definiert als eine Sprache zu der eine existiert die genau bei den Wörtern hält zur Sprache gehören. Diese Sprachen sind auch bekannt als rekursiv aufzählbaren Sprachen (oft auch semientscheidbare Sprachen genannt). Man beachte dass sich diese von Sprachen von der Menge der rekursiven Sprachen (oft auch entscheidbare Sprachen genannt) unterscheidet welche durch Turing-Maschinen erkannt werden können d. h. die zugehörige hält bei jedem Wort und liefert als 0 (Wort gehört nicht zur Sprache) oder (Wort gehört zur Sprache).
Typ-1-GrammatikenTyp-1-Grammatiken werden auch kontextsensitive Grammatiken genannt. handelt sich dabei um Grammatiken mit <math>\forall \rightarrow w_2) \in P : \left| w_1 \le \left| w_2 \right|</math>.Man schreibt <math>G \in Typ_1</math>. Sie erzeugen genau die kontextsensitiven Sprachen h. jede Typ-1-Grammatik erzeugt eine kontextsenstive Sprache zu jeder kontextsensitiven Sprache existiert eine Typ-1-Grammatik diese erzeugt. Typ-1-Grammatiken besitzen nur Regeln der Form A \beta \rightarrow \alpha \gamma \beta</math> wobei ein Nichtterminal und <math>\alpha \beta \gamma</math> Wörter aus Terminalen (<math>\Sigma</math>) und Nichtterminalen (<math>N</math>) sind. Wörter <math>\alpha</math> und <math>\beta</math> können leer sein <math>\gamma</math> muss mindestens ein Symbol (also ein oder ein Nichtterminal) enthalten. Die einzige Ausnahme ist dass die die Regel <math>S \rightarrow \epsilon</math> ausgehend vom <math>S</math> enthalten darf. Diese Regel wird eventuell um das leere Wort <math>\epsilon</math> ableiten zu können. Die kontextsensitiven Sprachen sind genau die die von einem nichtdeterministischen LBA erkannt werden können d. h. von nichtdeterministischen Turing-Maschine deren Band linear durch die der Eingabe beschränkt ist (d. h. es eine konstante Zahl <math>a</math> so dass das der Turing-Maschine höchstens <math>a \cdot x</math> Felder wobei <math>x</math> die Länge des Eingabewortes ist).
Typ-2-GrammatikenTyp-2-Grammatiken werden auch kontextfreie Grammatiken genannt. handelt sich dabei um Grammatiken mit <math>\forall \rightarrow w_2) \in P : w_1 \inMan schreibt <math>G \in Typ_2</math>. Sie erzeugen genau die kontextfreien Sprachen h. jede Typ-2-Grammatik erzeugt eine kontextfreie Sprache zu jeder kontextfreien Sprache existiert eine Typ-2-Grammatik diese erzeugt. Typ-2-Grammatiken besitzen nur Regeln der Form \rightarrow \gamma</math> wobei <math>A</math> ein Nichtterminal und ein Wort bestehend aus Terminalen und Nichtterminalen Die kontextfreien Sprachen sind genau die Sprachen von einem nichtdeterministischen Kellerautomaten (NPDA) erkannt werden können. Eine Teilmenge Sprachen bilden die theoretische Basis für die der meisten Programmiersprachen .
Typ-3-GrammatikenTyp-3-Grammatiken werden auch reguläre Grammatiken genannt. handelt sich dabei um Grammatiken mit <math>\forall \rightarrow w_2) \in P : w_1 \in und <math>w_2 \in \Sigma \cup \Sigma \cdot \cup \{ \epsilon \}</math>.Man schreibt <math>G \in Typ_3</math>. Sie erzeugen genau die regulären Sprachen h. jede Typ-3-Grammatik erzeugt eine reguläre Sprache zu jeder regulären Sprache existiert eine Typ-3-Grammatik diese erzeugt. Typ-3-Grammatiken besitzen entweder nur Regeln die der linken Seite aus einem Nichtterminal und der rechten Seite aus einem Terminal eventuell von einem Nichtterminal bestehen (rechtsreguläre Grammatik) oder Regeln die auf der linken Seite aus Nichtterminal und auf der rechten Seite aus Terminal eventuell mit vorangestelltem Nichtterminal bestehen (linksreguläre Zu jeder linksregulären Grammatik gibt es eine rechtsreguläre Grammatik (und umgekehrt) die die Sprache erzeugt. Aus demselben Grund wie bei ist auch hier die Regel <math>S \rightarrow als Ausnahme erlaubt allerdings nur wenn <math>S</math> auf der rechten Seite einer Regel erscheint. Reguläre Sprachen können alternativ auch durch reguläre Ausdrücke beschrieben werden und die regulären Sprachen genau die Sprachen die von endlichen Automaten erkannt werden können. Sie werden gewöhnlich um Suchmuster oder die lexikalische Struktur von zu definieren.
Chomsky-Hierarchie für formale SprachenEine formale Sprache <math>L \subseteq \Sigma^*</math> ist vom Typ (<math>i \in \{ 0 ... 3 \}</math>) es eine Grammatik <math>G \in Typ_i</math> mit \left( G \right)</math> gibt. Man schreibt dann \in \mathcal{L}_i</math>.Jede reguläre Sprache ist kontextfrei jede Sprache ist kontextsensitiv und jede kontextsensitive Sprache rekursiv aufzählbar. Dabei handelt es sich um echte d. h. es gibt rekursive aufzählbare Sprachen nicht kontextsensitiv sind kontextsensitive Sprachen die nicht sind und kontextfreie Sprachen die nicht regulär Formal ausgedrückt bedeutet dies für die Klassen der durch die obigen Grammatiken erzeugten <math>\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset wobei gelegentlich auch folgende Symbole verwendet <math>REG \subset CF \subset CS \subset
ÜbersichtDie folgende Tabelle fasst die vier die Form ihrer Regeln die Sprachen die erzeugen und die Automatentypen die sie erkennen zusammen.
Menschliche SprachenVon den formalen Sprachen werden die Sprachen unterschieden. Um jedoch maschinelle Übersetzung Expertensysteme und ähnliches zu ermöglichen muss menschliche Sprache als formale Sprache dargestellt werden. Ließe sich für eine menschliche Sprache Grammatik vom Typ 2 oder 3 aufstellen könnte diese auf einem Computer effizient ausgeführt Wäre menschliche Sprache vom Typ 0 so sie unlösbar (da es keine Computer gibt diese Aufgabe in endlicher Zeit bearbeiten können). Hypothese besagt dass die menschliche Sprache schwach ist (d. h. der Großteil menschlicher Sprache sich kontextfrei darstellen einige Aspekte jedoch benötigen kontextsensitive Representation ohne dass die Mächtigkeit von dabei ausgeschöpft wird).
Literatur
| |||||||||||||||||||||||
| Impressum • Lesezeichen setzen • Seite versenden • Seite drucken |
<a href="http://www.uni-protokolle.de/Lexikon/Chomsky-Hierarchie.html">Chomsky-Hierarchie </a>