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