Next: Wortproblem 21
Up: Allgemeines zu Sprachen
Previous: Grammatiken 13
Contents
Index
Subsections
Chomsky-Hierarchie 17
Die Menge aller Grammatiken (und der dazugehörigen Sprachen) lässt
sich in folgende Kategorien unterteilen. Die Sprachen werden abgekürzt
mit
. Dabei gilt:
Typ 0 oder rekursiv aufzählbar
Jede Grammatik ist automatisch vom Typ 0. Es gibt hier also keine
Einschränkungen. (Außer das es eine korrekte Grammatik sein muss)
- sind nicht entscheidbar (ob ein Wort in
der Sprach liegt oder nicht, siehe Wortproblem)
Typ 1 oder kontextsensitiv
wenn:
Typ 2 oder kontextfrei
wenn:
Typ 3 oder regulär
wenn:
- Es gibt keine reguläre Sprache, die inhärent Mehrdeutig
ist
Next: Wortproblem 21
Up: Allgemeines zu Sprachen
Previous: Grammatiken 13
Contents
Index
Marco Möller 18:11:27 24.10.2005