Formale Sprachen

Bei einer formalen Sprache steht nicht die Kommunikation (z. B. von Mensch zu Mensch), sondern die mathematische Verwendung im Vordergrund.

Alphabet

Ein Alphabet $A$ ist eine endliche, nichtleere Menge von Zeichen.

Syntax

Der Syntax einer Sprache (eines Zeichensystems) beschreibt die Regeln, nach denen die Sprachkonstrukte (Zeichen des Zeichensystems) gebildet werden.

Semantik

Die Semantik einer Sprache beschreibt die Bedeutung der Sprachkonstrukte.

Akzeptierte Sprache

Eine akzeptierte Sprache besteht aus Eingabewörtern, welche akzeptiert werden. Sie führen aus einen akzeptierten Zustand (z. B. in einem Zustandsdiagramm eines Automaten).

Abzählbare Menge

Eine Menge ist entweder endlich wie z. B. $\{1, 4, 11, 7, 5, 19\}$ und ich kann die Elemente abzählen und bin irgendwann fertig, oder man kann die Elemente der Menge nach einer bestimmten folge aufzählen obwohl man niemals fertig werden würde (Natürliche Zahlen $\mathbb{N}$ ). Bei beiden Mengen können die Elemente eins nach dem anderen abgezählt werden.

Eine nicht Abzählbare Menge sind die Reellen Zahlen $\mathbb{R}$ , weil zwischen jeder natürlichen Zahl unendlich Dezimalzahlen sind. Solche Mengen nennt man Überabzählbar.

Grammatik

Eine formale Grammatik wird als 4-Tupel $G=(N, T, S, P)$ dargestellt. Sie entscheidet darüber welche Elemente für den Wortbau verwendet werden dürfen. Buchstaben sind die kleinste Einheit einer Sprache und werden Terminale genannt. Dazu gibt auch Nicht-Terminale $\subseteq$ $N$ , die als Platzhalter dienen und vergleichbar mit den Satzgliedern (Subjekt, Prädikat, Objekt, …) natürlicher Sprachen sind.

Produktionsregeln

Regeln, die angeben, wie aus Wörtern durch eine Grammatik neue Wörter bzw. Symbolfolgen produziert werden.

Ableitungen

Eine Folge von Regelanwendungen, die letztendlich zu einem Wort führen.

$R_1 \rightarrow R_3 \rightarrow R_4 \rightarrow R_7 \rightarrow R_{11}\rightarrow \text{Wort}$