Sprachtypen

Es gibt unterschiedliche Typen von Sprachen und Automaten - bei der Betrachtung von Automaten stand bisher die (maschinelle) Erkennung einer Sprache im Zentrum. der Automat konnte testen: "Gehört eine gegebene Zeichenfolge zu einer gegebenen Sprache?".

Außerdem haben wir Grammatiken kennengelernt - diese dienen der Beschreibung einer Sprache. Es ist angebracht, die beiden Aufgabenstellungen "Spracherkennung" und "Sprachbeschreibung" zunächst getrennt zu betrachten, obwohl die beiden Aspekte natürlich verbunden sind und eine häufige Fragestellung ist: "Finde einen Automaten der die durch folgende Grammatik beschriebene Sprache erkennt".

Der Linguist Noam Chomsky formulierte gemeinsam mit Marcel Schützenberger 1956 eine Hierarchie von Klassen formaler Grammatiken, die formale Sprachen erzeugen, in der sich 4 "Sprachtypen" wiederfinden:

¹⁾

Wie im Schaubild zu erkennen ist, sind die Typen der Grammatiken hierarchisch ineinander enthalten, jede Typ 2 Sprache ist also auch stets vom Typ 0 und vom Typ 1.

Jede Grammatik ist automatisch vom Typ 0. Typ 0 Grammatiken erzeugen "rekursiv aufzählbare Sprachen". Die Produktionen der Grammatik unterliegen hier keinen Regeln, es sind beliebige Zuordnungen möglich:abcdAABCC → abAAD.

Schränkt man die zulässigen Regeln etwas ein, erhält man eine Typ 1 Grammatik: Hier sind nur Regeln erlaubt, die auf der rechten Seite mindestens gleich lang sind wie auf der linken Seite ²⁾. Erlaubt sind also z.B. AbNc→abacdABCc oder Nab → Naabc, nicht aber das Beispiel von oben: abcdAABCC → abAAD da hier die linke Seite länger ist als die rechte. Typ 1 Grammatiken beschreiben kontextsensitive Sprachen.³⁾

Typ 2 Grammatiken erlauben ausschließlich Regeln der Form Genau ein nichtterminales Symbol → Beliebige Kombination aus terminalen und nichtterminalen Symbolen Erlaubt: A→BC, B→abACba. Nicht erlaubt: AB→abaCD, bA→abACacB. Typ 2 Grammatiken erzeugen kontextfreie Sprachen. Sie können mit Kellerautomaten erkannt werden.

Typ 3 Grammatiken erlauben bei jeder Regel auf der rechten Seite nur

• ε oder
• einzelne Zeichen des Alphabets oder
• ein einzelnes Zeichen des Alphabets und danach eine einzelne Variable stehen (rechtsregulär) oder
• eine einzelne Variable und danach ein einzelnes Zeichen stehen (linksregulär)

Erlaubt: A→aB, B→c, C→ε, A→Ba. Verboten: A→aBa, C→abD Typ 3 Grammatiken erzeugen reguläre Sprachen, diese können von DEAs erkannt werden.