Ψ Die Informatikseite

Menü

Tabellarische Aufführung der Abschlußeigenschaften verschiedener Sprachtypen

Sprache Komplement Vereinigung Durchschnitt Konkatenation Kleeneabschluss Wortproblem Konstrukt
Typ 0 nein ja ja ja ja unent. DTM$\&$NTM
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$_{Endzustand}$
det. kontextfr. '' '' '' '' '' linear DKA $_{leerer\,Kel.}$
mit Präfixeig.             $=$DKA$_{\epsilon}$
regulär ja ja ja ja ja linear DFA$\&$NFA