Theoretische Informatik

Theoretische Informatik (ThInf)
Vertiefungsrichtung	Alle
Vorlesende	Hübel
URL	Link

Klausur
Termin
Datum:	08.02.2007
Zeit:	10:30 - 11:30 (Sb 60 min)
Ort:	Helmholtz-Hörsaal (GrHs)

• Patrics Zusammenfassung
• Probeklausur
• Klausur

Chomsky Hierarchie

Chomsky-Typ 0

• Chomsky-Type 0 Grammatiken enthalten keinerlei Einschränkungen.
• Type 0 Sprachen können nur von Turingmaschinen erkannt werden und damit ist es auch gleich der Menge der rekursiv aufzählbaren Sprachen
• es gibt auch Sprachen die nicht rekursiv aufzählbar sind (z.B. Halteproblem)

Chomsky-Type 1

• Dieser Typ ist gleich der Menge von Sprachen die durch kontextsensitive Grammatiken erzeugt werden können
• Dieser Typ von Sprache wird bereits von einer linear Platzbeschränkten Turingmaschine erkannt
• Dieser Typ ist eine Teilmenge des Chomsky-Type 0

Chomsky-Typ 2

• Dieser Typ ist gleich der Menge von Sprachen die durch kontextfreie Grammatiken erzeugt werden
• Diese Sprache wird durch einen deterministischen oder nichtdeterministischen Kellerautomat erkannt
• Chomsky-Typ 2 ist eine Teilmenge des Chomsky-Typ 1

Chomsky-Typ 3

• Dies ist der am stärksten eingeschränkte Typ
• Die Menge der Sprachen die diesem Typ angehört wird durch links oder rechts lineare Grammatiken erzeugt
• Diese Menge von Sprachen kann auch durch reguläre Ausdrücke erzeugt werden
• Erkannt werden diese Sprache bereits durch einen endlichen Automaten
• Chomsky-Typ 3 ist eine Teilmenge der Chomsky-Typ 2 Sprachen

Grammatiken

Grundlagen

Eine Grammatik ist ein 4-Tupel aus Nichtterminalsymbolen, Terminalsymbolen, Produktionsregeln und einem Startsymbol. Mathematisch kann es damit wie folgt geschrieben werden: $G=(N,T,P,S)$
Terminalsymbole sind dabei Zeichen des endgültigen Alphabets der Sprache die mit der Grammatik erzeugt werden soll.
Nichtterminalsymbole sind hingegen eine Art Variablen.
Um ein Wort einer Sprache abzuleiten muss man die Produktionsregel so lange anwenden bis alle Nichtterminalsymbole in Terminalsymbole umgewandelt worden sind. Man beginnt immer mit dem Startsymbol, welches implizit durch das 4-Tupel vorgegeben ist.
Je nach Einschränkungen der Grammatiken unterscheidet man verschiedene Typen.

kontextsensitive Grammatiken

Die Produktionsregeln dieser Grammatiken haben immer folgende Form:
$v_{1}Av_{2}$→$v_{1}wv_{2}$
Dabei sind:
$v_{1}$ und $v_{2}$ Terminal oder Nichtterminalsymbole
A ist immer ein Nichtterminalsymbol
w ist immer ein nichtleeres Wort aus Terminal und/oder Nichtterminalsymbolen
Es gibt eine einzige Ausnahme von dieser Regel um das leere Wort ableiten zu könne darf eine Regel existieren die das Startsymbol zum leeren Wort ableitet (S → $\epsilon$) Beispiele für Sprachen mit kontextsensitiven Grammatiken: $L_{1}=\{a^{n}b^{m}a^{n}b^{m}|n,m\geq 1\}$
$L_{2}=\{a^{n}b^{n}c^{n}|n\geq 1\}$

kontextfreie Grammatiken

Kontextfreie Grammatiken sind die wichtigsten Formalismn zur Beschreibung von Programmiersprachen.
Die Produktionsregeln dieser Grammatik haben dabei die Folgende Form:
A → w
A ist dabei ein Nichtterminalsymbol und
w ist ein ein Wort aus Terminal und Nichtterminalsymbolen
Man kann aus der Form der Produktionsregeln erkennen, warum dies Grammatik kontextfrei heißt. Die Ableitung eines Zeichen in einem Wort geschieht unabhängig von den Benachbarten Zeichen.
Beispiel für eine kontextfreie Sprache
$L_{1}=\{a^{n}b^{n}|n\geq 1\}$

rechts-/linkslineare Grammatiken

Die rechts- bzw. linkslinearen Grammatiken haben die am Stärksten eingeschränkten Produktionsregeln.
Bei einer rechtslinearen Grammatik haben alle Produktionsregeln immer die Form
$A\to wB$ oder $A\to w$
und bei einer linkslinearen die Form
$A\to Bw$ oder $A\to w$
Dabei sind $A$ und $B$ Nichtterminalsymbole und $w$ Wörter aus Terminalsymbolen.

Beispiel für eine Sprache die mit Hilfe einer rechts/linkslinearen Grammatik erzeugt werden kann:
$L_{1}=\{a^{n}|n\geq 1\}$

Theoretische Maschinen zum Überprüfen der Sprachen

Endlicher Automat (EA/FA/SM)

Ein endlicher Automat enthält eine Eingabeeinheit und eine Steuereinheit.
Die Eingabeeinheit besteht aus einem Band, auf welchem Zeichen notiert sind, die der Automat verarbeiten soll und einem Lesekopf, welcher diese Zeichen lesen kann.
Die Steuereinheit enthält eine endliche Tabelle, in der steht, in welchen Zustand der Automat wechseln soll, wenn er ein bestimmtes Zeichen vom Band liest. Im Betrieb liest dieser Automat ein Zeichen ein und muss es sofort verarbeiten. Ein endlicher Automat kann nur reguläre Sprachen erkennen, weil im die Fähigkeit fehlt, sich komplexe Dinge zu "merken".

Der Keller Automat

Ein Kellerautomat besteht aus einem Eingabeband, einen Kellerband und einer Steuereinheit. Damit kann er mathematisch wie folgt durch ein 7-Tupel beschrieben werden:
A = (Q,E,K,$\delta$,q0,z0,F)
Q Menge von Zuständen
E Eingabe Alphabet
K Keller Alphabet
$\delta$ Überführungfunktion
q0 Startzustand
z0 Kellerende Zeichen
F Menge von Endzuständen aus Q
Die Überführungfunktion sorgt wie beim endlichen Automaten für die Steuerung der Funktion des Kellerautomaten.
Der Kellerautomat bekommt für seine Entscheidung, welches der nächste Zustand ist, nicht nur die Eingabe vom Band mitgeteilt sondern auch das Zeichen, welches zuletzt in den Keller geschrieben wurde. Daraufhin kann der Automat entweder das Zeichen im Keller löschen oder ein weiteres in den Keller legen.
Somit kann sich der Automat komplexere Zustände merken als der endliche Automat und ist aufgrund dessen in der Lage, auch kontextfreie Sprachen zu erkennen.

Die Turingmaschine

Die Turingmaschine besteht aus einem oder mehren Eingabebändern welche sie beliebig bewegen, lesen und beschreiben kann. Mathematisch beschreibt man eine Turingmaschine als 6-Tupel
T = (Q,E,$\delta$,q0,b,F)
Q Menge von Zuständen
E Eingabe Alphabet
q0 Startzustand
F Menge von Endzuständen aus Q
Eine Turingmaschine ist in der Lage, alle rekursiv aufzählbaren Sprachen zu erkennen.