Aus StudiWiki

siehe http://de.wikipedia.org/wiki/Chomsky-Hierarchie

Inhaltsverzeichnis 1 Die Chomsky-Hierachie: Kurzfassung 1.1 Typ 0 1.2 Typ 1 (kontextsensitiv) 1.3 Typ 2 (kontextfrei) 1.4 Typ 3 (regulär)

[bearbeiten] Die Chomsky-Hierachie: Kurzfassung

Teilt Grammatiken in 4 Typen!

[bearbeiten] Typ 0

Jede Grammatik ist automatisch Typ 0 (keine Einschränkungen)

[bearbeiten] Typ 1 (kontextsensitiv)

Für alle Regeln w1 -> w2 in P gilt: Die Länge des Wortes von w1 ist kleinergleich die Länge des Wortes w2. Oder auf Deutsch: In einem Ableitungsschritt wird das Wort niemals kürzer.

z.B.: aB -> aBb ( 2 <= 3 )

[bearbeiten] Typ 2 (kontextfrei)

Für alle Regeln w1 -> w2 in P gilt: w1 ist eine einzelne Variable, also hat w1 immer die Länge 1. Außerdem gilt natürlich die gleiche Einschränkung wie für kontextsensitive Sprachen: Dass das Wort nicht wieder kürzer werden darf.

z.B.: B -> bBb ( w1=B hat die Länge 1 )

[bearbeiten] Typ 3 (regulär)

falls zusätzlich gilt: w2 ist Element von (Sigma) vereinigt mit (Sigma V). Die rechten Seiten der Regeln sind entweder einzelne Terminalzeichen oder ein Terminalzeichen gefolgt von einer Variablen. Und links steht wieder nur eine einzelne Variable.

z.B.: A -> aB oder A -> a