====== 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".

===== Einteilung von Sprachen =====

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

{{ :faecher:informatik:oberstufe:automaten:sprachtypen:chie.drawio.png |}}((Die rot umrandeten sind nicht Teil des Bildungsplans im Baden-Württemberg))

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.

==== Klassifizierung der Typen ====

=== Typ 0 ===
 
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''.

{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t0.drawio.png |}}

=== Typ 1 ===

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 ((Ausnahme: ''S->ε'' (Leeres Symbol) )). 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 0 und Typ 1 Sprachen können von Turingmaschinen erkannt werden.))

{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t1.drawio.png |}}

=== Typ 2 ===
 
**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.

{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t2.drawio.png |}}

=== Typ 3 ===

**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.

{{ :faecher:informatik:oberstufe:automaten:sprachtypen:t3.drawio.png |}}


===== Dateien =====

{{simplefilelist>:faecher:informatik:oberstufe:automaten:sprachtypen:*}}