Beschreibungsarten für Sprachklassen

Sprachklasse Grammatik Maschinentyp Sonstiges
Typ-3 reguläre Grammatik DEA, NEA reguläre Ausdrücke
det. kont.frei \(LR(k)\)-Grammatik DPDA
Typ-2 kontextfreie Grammatik PDA
Typ-1 kontextsensitive Grammatik LBA
Typ-0 beliebige Grammatik TM

Determinismus und Nicht-Determinismus

Sprachklasse nicht-det. Automat det. Automat äquivalent
Typ-3 NEA DEA ja
Typ-2/det. kont.frei PDA DPDA nein
Typ-1/? LBA DLBA ?
Typ-0 (N)TM DTM ja

Abschlusseigenschaften

Sprachklasse Schnitt Vereinigung Komplement Produkt Stern
Typ-3 ja ja ja ja ja
det. kont.frei nein nein ja nein nein
Typ-2 nein ja nein ja ja
Typ-1 ja ja ja ja ja
Typ-0 ja ja nein ja ja

Entscheidbarkeiten

Sprachklasse Wortproblem Leerheit Äquivalenz Schnittproblem
Typ-3 ja ja ja ja
det. kont.frei ja ja ja nein
Typ-2 ja ja nein nein
Typ-1 ja nein nein nein
Typ-0 nein nein nein nein

Wortproblem

Sprachklasse Komplexität Sonstiges
Typ-3 linear falls durch DEA gegeben (sogar in „Echtzeit“)
det. kont.frei linear
Typ-2 \(\O (n^3)\) falls in CNF gegeben (mit CYK-Algorithmus)
Typ-1 exponentiell (?) NP-hart
Typ-0 unlösbar