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:
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