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.