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
