wilhelm büchner_728x90_bachelor_informatik
 

next up previous contents
Nächste Seite: Inklusion der Chomskyhierarchie Aufwärts: Grammatiken Vorherige Seite: Definitionen   Inhalt

Unterabschnitte

Chomsky Hierarchie

Tabellarische Übersicht

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.

Beispiele

  • 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

next up previous contents
Nächste Seite: Inklusion der Chomskyhierarchie Aufwärts: Grammatiken Vorherige Seite: Definitionen   Inhalt