Informatikmaterialien 
von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges |

| Inhalt | Vorherige Seite | Nächste Seite


Richard-Wossidlo-Gymnasium Ribnitz-Damgarten
Fachbereich Informatik


Chomsky-Hierarchie


Der amerikanische Informatiker Noam Chomsky (geb. 1928) gilt als Pionier der Sprach-Theorie. Von ihm stammt eine Einteilung der Grammatiken in Typen. 

Einteilung

Chomsky teilte die Grammatiken in 4 Typen ein:

Typ 0
(allgemein)
Jede Grammatik ist zunächst automatisch vom Typ 0.
Typ 1
(kontextsensitiv)
Eine Grammatik ist vom Typ 1, wenn gegenüber Typ 0 einschränkend für alle Regeln u v gilt: die Worte auf der rechten Seite einer Regel sind mindestens so lang, wie die auf der linken Seite (|u| ≤ |v|).
Typ 2
(kontextfrei)
Eine Grammatik ist vom Typ 2, wenn gegenüber Typ 1 einschränkend  für alle Regeln u v gilt: u ist eine einzelne Variable.
Typ 3
(regulär)
Eine Grammatik ist vom Typ 3, wenn gegenüber Typ 2 einschränkend  für alle Regeln u v gilt: auf der rechten Seite sind entweder einzelne Terminalzeichen oder ein Terminalzeichen gefolgt von einer Variablen (linkslinear).

Kurzfassung 
(aus G. Röhner: Informatik mit Prolog)

Grammatik Typ Produktionsformen
allgemein 0 beliebig
kontextsensitiv 1 αAβ αγβ
kontextfrei 2 A α
regulär 3 A a | aB

α, β, γ sind Symbolfolgen bestehend aus Terminalen und Variablen, A und B sind Variablen, a ist ein Terminal

Übungen

  1. Man ordne die bisher entwickelten Grammatiken den Typen 0 bis 3 zu.



zur Startseite
© Tino Hempel 1997 - 2003
Letztes Update 03.2003
Im Web vertreten seit 1994.
Eine Internet-Seite aus dem Angebot von Tino Hempel.

Für alle Seiten gilt der 
Haftungsausschluss/Disclaimer.