Vorlage:Formale Sprachen und Grammatiken
aus Wikipedia, der freien Enzyklopädie
Automatentheorie: Formale Sprachen und Formale Grammatiken | |||
---|---|---|---|
Chomsky- Hierarchie |
Grammatiken | Sprachen | Minimaler Automat |
Typ-0 | uneingeschränkt | rekursiv aufzählbar | Turingmaschine |
uneingeschränkt | rekursiv | Turingmaschine | |
Typ-1 | kontextsensitiv | kontextsensitiv | linear beschränkt |
Typ-2 | kontextfrei | kontextfrei | Kellerautomat |
Typ-3 | Regulär | Regulär | Endlich |
Jede Klasse einer Sprache oder Grammatik ist eine echte Teilmenge der Klasse darüber. |
de:Vorlage:Formale Sprachen und Grammatiken