Die folgende Tabelle gibt einen Überblick über formale Sprachen, die Automaten die sie akzeptieren und die Grammatiken, die sie erzeugen. Dabei haben die Grammatiken die Form $G = (V, \Sigma, P, S)$:
- V: Die Menge der Nicht-Terminale. Für sie benutze ich Großbuchstaben.
- $\Sigma$: Die Menge der Terminale. Für sie benutze ich Kleinbuchstaben.
- P: Die Produktion, also die Regeln mit denen die Grammatik die Sprache erzeugt. Nur diese hat unterschiedliche Bedingungen, je nach dem welchem Typ die Grammatik angehört.
- S: Das Startsymbol aus $\Sigma$.
| Typ | Bezeichnung | Regeln | Abgeschlossen unter | Modell | |||
|---|---|---|---|---|---|---|---|
| $\cup$ | $\cap$ | $\cdot$ | ${}^C$ | ||||
| 0 | semientscheidbar | alles | ✔ | ✔ | ✔ | ✘ | D. Turingmaschine, ND. Turingmaschine |
| 1 | kontextsensitiv | $u \rightarrow v, |a| \leq |v|$ | ✔ | ✔ | ✔ | ✔ | (ND.?) Längenbeschränkter Automat |
| 2 | kontextfrei | $A \rightarrow v$ | ✔ | ✘ | ✔ | ✘ | ND. Kellerautomat |
| 3 | regulär | $A \rightarrow \varepsilon, A \rightarrow aB$ | ✔ | ✔ | ✔ | ✔ | Endliche Automaten (Moore, Mealy, Akzeptoren) |
Legende:
Typ.: Der Typ der Grammatik in der Chomsky-Hierarchie
D.: "Deterministisch"
ND.: "Nicht Deterministisch"
semi-entscheidbar
entscheidbar, es kann also in endlicher Zeit entschieden werden, ob ein Wort in der Sprache liegt (vgl. Wortproblem).
Nicht-Abeschlossenheit der Kontextfreien Sprachen:
$$L_1 = {a^jb^ic^i | j \in \mathbb{N}_0, i \in \mathbb{N}_0}$$
$$L_2 = {a^ib^ic^j | j \in \mathbb{N}_0, i \in \mathbb{N}_0}$$
$$L_1 \cap L_2 = {a^ib^ic^i | i \in \mathbb{N}_0}$$
$$(L_1 \cup L_2)^C = L_1^C \cap L_2^C$$
Weitere Aussagen
Sei L eine Sprache. $L \in {\cal L_3} \Leftrightarrow$ Es existiert ein regulärer Ausdruck für L. $L \in {\cal L_3} \Leftrightarrow$ Die Anzahl der Äquivalenzklassen der Nerode-Relation bzgl. der Sprache ist endlich. $L \in {\cal L_3} \Rightarrow$ Das Pumping-Lemma ist erfüllt.
Für reguläre Sprachen ist das Leerheitsproblem ($L(G) \stackrel{?}{=} \emptyset$) entscheidbar. Für reguläre Sprachen ist das Endlichkeitsproblem ($L(G) \stackrel{?}{<} \infty$) entscheidbar.
Für kontextfreie Sprachen ist das Leerheitsproblem entscheidbar. Für kontextfreie Sprachen ist das Endlichkeitsproblem entscheidbar.
Für Typ 0 und Typ 1 Sprachen ist das Leerheitsproblem nicht entscheidbar.
$L \in {\cal L_2} \Leftrightarrow L$ wird von einem nichtdeterministischem Kellerautomaten erkannt.
Quellen
- Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, DNB 986529222.
- Tutorium, Skript, Vorlesung: Theoretische Grundlagen der Informatik am KIT bei Prof. Dr. Dorothea Wagner