Theoretische Informatik - Chomsky Hierarchie

Nächste Seite: Inklusion der Chomskyhierarchie Aufwärts: Grammatiken Vorherige Seite: Definitionen Inhalt

Unterabschnitte

Chomsky Hierarchie

Typ	Bezeichnung	Eigenschaften
Typ 0	keine Bezeichnung	beliebig
Typ 1	kontextsensitiv	Für jede Relation $u\rightarrow v$ gilt $\vert u\vert\leq\vert v\vert$ , d.h. daß das Wort nicht wieder abnehmen darf. Ausnahme ist hier die $\epsilon$ -Sonderregel. $S\rightarrow\epsilon$ ist erlaubt
Typ 2	kontextfrei	Links muß ein einzelnes Nonterminal stehen.
Typ 3	regulär	Die Regeln im Regelsystem müssen die folgende Form haben $A\rightarrow\epsilon$ $A\rightarrow a$ $A\rightarrow aA$ wobei A Nonterminal und a Terminal ist.

Aussagelogische Formel für SAT Typ 2 - kontextfrei

$\begin{displaymath}S\rightarrow true\vert x_{i}\vert(S\wedge S)\vert(\neg S)\end{displaymath}$

Mittels De-Morgan kann aus ,,oder'' ,,und'' gemacht werden.
Grammatik für die Sprache $L=\{a^{n}b^{n}c^{n}\}$ $n\geq 1$ Typ 1 - kontextsensitiv

S $\rightarrow$ aSBC|aBC Aufbau des Wortes

CB $\rightarrow$ BC umsortieren

aB $\rightarrow$ ab umwandeln in Terminale

bB $\rightarrow$ bb umwandeln in Terminale

bC $\rightarrow$ bc umwandeln in Terminale

cC $\rightarrow$ cc umwandeln in Terminale

Nächste Seite: Inklusion der Chomskyhierarchie Aufwärts: Grammatiken Vorherige Seite: Definitionen Inhalt