Sprache | Komplement | Vereinigung | Durchschnitt | Konkatenation | Kleeneabschluss | Wortproblem | Konstrukt |
Typ 0 | nein | ja | ja | ja | ja | unent. | DTM![]() |
Typ 1 | ja | ja | ja | ja | ja | PSP.C | LBA |
Typ 2 | nein | ja | nein | ja | ja | kubisch | NKA |
det. kontextfr. | ja | nein | nein | nein | nein | linear | DKA![]() |
det. kontextfr. | '' | '' | '' | '' | '' | linear | DKA
![]() |
mit Präfixeig. | ![]() ![]() |
||||||
regulär | ja | ja | ja | ja | ja | linear | DFA![]() |