Typ 3 | reguläre Grammatik, DFA, NFA, reguläre Ausdrücke |
det. kontextfrei | - Grammatik |
Typ 2 | kontextfreie Grammatik, Kellerautomat (PDA) |
Typ 1 | kontextsensitive Grammatik, linear beschränkter Automat (LBA) |
Typ 0 | Typ 0 - Grammatik, Turingmaschine (TM) |