Formale Sprache

• ${\Sigma }^{\ast }$ ist die Menge aller Wörter über $\Sigma$
• ${\Sigma }^{+}={\Sigma }^{\ast }\backslash \{\epsilon \}$

Definition

Eine Sprache über $\Sigma$ ist eine Menge $L\subseteq {\Sigma }^{\ast }$

Die Chomsky-Hierarchy
Kontextfreie Sprache ⇒ Deterministisch kontextfreie Sprachen ⇒ Reguläre Sprache ⇒ Endlichen Sprache

Operationen

• Konkatenation

• Kleene-Stern

Abgeschlossenheit

• Abschlusseigenschaften der regulären Sprachen
• Abschlusseigenschaften der kontextfreien Sprachen