 |
|||
| HSG |
|
Chomsky-Hierarchie
Artikel bei wikipediaAchtung: Man beachte den Unterschied bei den zugelassenen Produktionen für kontextsensitive Grammatiken zu folgender Definition.
In obiger Übersicht bezeichnen A und B einzelne nonterminale Symbole (Variablen), α, β, γ Symbolfolgen aus Terminalen und Nonterminalen, a ein einzelnes Terminal. |α|≤|β| bedeutet, dass die Folge β mindestens so viele Zeichen hat wie die Folge α.
Beispiele
- L1 = {römische Zahlen von 1 bis 3999} ist regulär.
- L2 = {anbn | n ∈ IN} ist kontextfrei, aber nicht regulär, .
- L3 = {anbncn | n ∈ IN} ist kontextsensitiv, aber nicht kontextfrei.