Theoretische Informatik

Nächste Seite: Komplettes Schaubild der Chomskyhierarchie Aufwärts: Deterministische kontextfreie Sprachen Vorherige Seite: Präfixeigenschaft Inhalt

Beispiele

Sprache	Art
$L=\{w\in\Sigma^{*}:a^{n}b^{n}\,\,n\geq 1\}$	deterministisch kontextfrei mit Präfixeigenschaft
$L=\{w\in\{0,1,\char93 \}:x_{1}\$x_{2}$ $x_{1}\in\{0,1\}^{}$ $x_{2}\in\{0,1\}^{}\}$	deterministisch kontextfrei ohne Präfixeigenschaft, da sobald das Dollarzeichen gelesen wurde es noch weitergehen kann, aber dieses Teilwort auch schon akzeptiert werden könnte. Diese Sprache ist des weiteren auch noch regulär
$L=\{xx^{R}\}$	nicht deterministisch kontextfrei
$L=\{x\$x^{R}\}$	deterministisch kontextfrei mit Präfixeigenschaft