Formale Sprache und Grammatik

Mit Akzeptor, Kellerautomat und Turingmaschine haben wir Automatenmodelle kennengelernt, die formale Sprachen erkennen können. Nun betrachten wir die andere Richtung: Formale Sprachen können auch mithilfe von Regeln erzeugt werden. Solche Regelsysteme heißen Grammatiken. Am Ende werden wir untersuchen, welcher Grammatiktyp zu welchem Automatenmodell gehört.

In Klasse 10 haben wir natürliche und künstliche Sprachen miteinander verglichen. Dabei spielten bereits die Begriffe Alphabet, Syntax, Semantik und Grammatik eine Rolle. Für formale Sprachen konzentrieren wir uns nun auf die Syntax: Welche Zeichenfolgen gehören zu einer Sprache und durch welche Regeln können sie erzeugt werden?

Aufgabe zum Syntaxdiagramm (Tafelwerk?)

Prüfe ob Befehl korrekt ist -> Akzeptorrolle

Gib einen Befehl an, der ... -> Generatorrolle

Verschiedene Möglichkeiten zur Beschreibung einer Syntax

Die Syntax einer formalen Sprache kann auf unterschiedliche Weise beschrieben werden. Aus dem Umgang mit SQL kennen wir bereits Syntaxdiagramme. Beispielsweise findet sich eine Beschreibung des SELECT-Befehl in der SQLite-Dokumentation auszugsweise wie folgt:

ÜBERARBEITUNG notwendig!!!

1. Produktionsregeln als alternative Beschreibung mit Grammatikbeispiel und Baum
2. Theorie Definition G = (T, N, P, S) und Ableitungsbaum
3. Anwendung: Grammatiken entwickeln und untersuchen
4. unterschiedliche Einschränkungen der Produktionsregeln --> Chomsky-Hierarchie
5. Zusammenführung mit den bekannten Automaten

Formale Sprache

Im Zusammenhang mit Automaten haben wir bereits festgelegt:

• Ein Alphabet ist eine endliche Menge von Zeichen.
• Ein Wort ist eine endliche Folge von Zeichen eines Alphabets.
• X* bezeichnet die Menge aller Wörter über dem Alphabet X.
• Eine formale Sprache L über X ist eine Teilmenge von X*.

Sprachklassifikation

Natürliche Sprachen wie Deutsch sind historisch entstanden und besitzen häufig Mehrdeutigkeiten.

Künstliche Sprachen wurden gezielt geschaffen. Dazu gehören beispielsweise Plansprachen und Programmiersprachen.

Formale Sprachen sind Sprachen, deren syntaktisch gültige Wörter bzw. Ausdrücke eindeutig nach festgelegten Regeln bestimmt werden können. Programmiersprachen sind wichtige Anwendungen formaler Sprachen. Formale Sprachen besitzen eine eindeutig festgelegte Syntax. Sie kann beispielsweise durch Grammatiken, Syntaxdiagramme oder andere Sprachbeschreibungen angegeben werden. Die Untersuchung formaler Sprachen begann in den 1950er-Jahren durch Noam Chomsky.

Bild: Σ, retouched by Wugapodes and Jonnmann, CC BY-SA 4.0 via Wikimedia Commons