• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Sprachen, Automaten und Grammatiken: Ein Überblick

Contents

  • Weitere Aussagen
  • Quellen

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

Published

Jan 28, 2012
by Martin Thoma

Category

German posts

Tags

  • Abstract machine 4
  • Chomsky hierarchy 1
  • Formal grammar 1
  • Formal language 1
  • TGI 1
  • Theoretical computer science 9

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor