- Chomskyhierarchie
- Sprachklassen durch
Beschränkungen des allgemeinen
Regelformats w1→w2
Beziehungen zwischen Beschränkung im Regelformat und Beschränkungen in der Sprache (Mächtigkeit), sowie Sprachklasse und Verarbeitungszeit.
|
Je nach Beschränkung des Regelformats entstehen Sprachen unterschliedlicher Klassen.
Vier Klassen fasst die Chomskyhierarchie zusammen: reguläre (Typ 3), kontextfreie (Typ 2), kontextsensitive (Typ 1) und unbeschränkte Grammatiken (Typ 0).
| Typ | Linke Seite | Rechte Seite |
|---|
| 0 | mind. 1 Nichtterminal | beliebig |
| 1 | mind. 1 Nichtterminal | Länge mind. wie linke Seite |
| 2 | 1 Nichtterminal | beliebig |
| 3 | 1 Nichtterminal | Terminale gefolgt von maximal 1 Nichtterminal (rechtslinear)
max. 1 Nichtterminal gefolgt von Terminalen (linkslinear) |
Regeln eines höheren Typs sind zugleich Spezialfälle von Regeln eines kleineren Typs.
Somit ist eine reguläre Sprache auch gleichzeitig eine kontextfreie oder kontextsensitive.
Andersherum lässt sich zeigen (vgl. Pumpinglemma), dass es kontextsensitive Sprachen gibt, die nicht kontextfrei sind.
Und es gibt kontextfreie Sprachen, die nicht durch reguläre Grammatiken dargestellt werden können.
Die Inklusionsbeziehung ist echt.
Je unbeschränkter der Grammatiktyp, desto mächtiger.
So lässt sich bspw. mit kontextsensitiven Grammatiken erzwingen, dass 3, 4 und sogar 5 Terminalsymbole in jeweils gleicher Anzahl und nacheinander angeordnet auftreten.
Zwar lässt sich auch mit regulären Grammatiken eine bestimmte Anzahl von Terminalsymbolen erzwingen, aber nur über die Einführung von Nichtterminalen.
Die Forderung nach kleinen, endlichen Alphabeten grenzt diese Möglichkeit erheblich ein.
Bei sinnvollen Anwendungen, z.B. Compiler, Übersetzungssysteme für natürliche Sprachen, usw., ist zu überlegen, welche Sprachklasse geeignet ist.
Dabei wird einerseits die generative Kraft, also die Möglichkeit bestimmte Sprachkonstrukte durch einen gegebenen Grammatiktyp auszudücken,
andererseits die Effizienz in der Verarbeitung berücksichtigt.
Natürliche Sprachen enthalten mindestens kontextsensitive Konstrukte, also Wörter, die erst durch Typ-1-Regeln beschrieben werden können.
Allerdings sind kontextsensitive Sprachen bisher nicht effizient verarbeitbar.
Die Bearbeitungszeit steigt in dieser Sprachklasse exponentiell zur Länge der Eingabe.
Auch beim Design von künstlichen Sprachen wird man eher auf Kompromisse eingehen - bestmögliche Qualität in angemessener Zeit.
Dies wird z.B. dadurch erreicht, dass Sprachkonstrukte vereinfacht dargestellt werden, bestimmte Analysen ausgelagert werden oder Teilanalysen in mehren Zyklen stattfinden
|
1
2
3
4
5
Zusammenfassung