Grundlegende Begriffe

Abzählbarkeit und Mächtigkeit

Wieviele Funktionen `g: NN -> {0,1}` existieren?	Unendlich viele
	`>`
Wieviele Programme existieren?	Unendliche viele
	`=`
Wieviele natürliche Zahlen existieren?	Unendlich viele

Wir benötigen ein "Handwerkszeug" um verschiedene Stufen der Unendlichkeit unterscheiden zu können.

Abzählbarkeit

Eine Menge A heisst abzählbar, wenn es eine bijektive Abbildung `f: A -> NN` gibt.

Mächtigkeit

Wir schreiben dann `|A|=|NN|=omega=oo`.

Weitere Mengenschreibweisen

endlich	`|A| < omega`
unendlich, aber abzählbar	`|A| = omega`
unendlich, nicht abzählbar	`|A| > omega`

Beispiel:

`|{1,2,3,4,5}| < omega` `|NN| = omega` `|RR| > omega`

Beweistechniken für die Abzählbarkeit

explizite Angabe einer Abzählung

Sprich: Einfach abzählen.

Teilmengenbeziehung

Sei `A` eine abzählbare Menge, dann ist jede Teilmenge `B` von `A` abzählbar oder endlich. bsp-Q abzählen- TODO grafik einfügen

Obermengenbeziehung

Sei `A` eine überabzählbare Menge, so ist jede Obermenge von `A` ebenfalls überabzählbar.

Beispiel:

TODO bild `| QQ | > omega`, da `| RR | > omega ^^ QQ sub RR`

Diagonalisierung

TODO bild Wir konstruieren eine Funktion `f: NN -> {0,1}` entlang der Diagonalen.

Offensichtlich ist ist `f(n) in A`, kommt aber in der Abzählung nicht vor, denn gäbe es ein `g` mit `g_i = f(n)`, so müsste gelten, dass `g_i(i) = f(i) = not g_i(i)`. Widerspruch! `=> {g:NN -> {0,1}}` ist überabzählbar. Beobachtung: Wir können nur abzählbar viele Dinge (Automaten, mathematische Funktionen, Sprachen) syntaktisch repräsentieren. Damit können wir sagen: "Es existieren überabzählbar viele Funktionen, die wir nicht syntaktisch repräsentieren bzw. berechnen können.

Grammatiken

... bilden eine syntaktische Repräsentation einer Sprache (z.B. Programmiersprache, syntaktische Ausdrücke, XML, HTML, ...).

Grammatik

Eine Grammatik `G` über einem Alphabet `Sigma` ist ein Tupel `G = (V, Sigma, P, S)`, das folgende Bedingungen erfüllt:

`V`	Menge der Variablen (endlich)
`Sigma`	endliche Menge, sog. terminales Alphabet (die Operatoren), wobei `V sub Sigma = 0`
`P`	Produktionen/Regeln
`S`	Startvariable

Beispiel:

`G = (V, Sigma, P, S) = (V, Sigma, P, A)` `V = {A, I}` `Sigma = {(,),+,*,a,b,c}` `P = { A -> A + A, A -> A*A, A -> (A), A -> I, A -> a, A -> b, A -> c, I -> a, I -> b, I -> c}` Welche Sprache wird durch G definiert? Ableitung von Satzformen ausgehend vom Axiom: TODO papier

Definitionen

Sei `G=(V,Sigma,P,S)` eine Grammatik und seien `u,v in (V uu Sigma)^**`:

1. `v` heisst aus `u` direkt ableitbar, wenn `alpha, beta, gamma, delta in (V uu Sigma)^**` existieren, so dass gilt: `alpha -> beta in P ^^ u = gamma alpha delta` und `v = gamma, beta, delta`

07-07-12

Äquivalenz von endlichen Automaten und regulären Ausdrücken

Die von endlichen Automaten akzeptierten Sprachen sind genau die Sprachen, die durch reguläre Ausdrücke spezifiziert werden können. Diese Sprachen werden als reguläre Sprachen bezeichnet.

Satz

Sei `r` ein regulärer Ausdruck, dann gibt es einen NEA mit `epsilon`-Transitionen, der `L(r)` akzeptiert. (Beweis: siehe Literatur)

Beispiel:

Wir wollen einen NEA für den regulären Ausdruck `01*+1` konstruieren. Nach unserer Prioritätsregel gilt:

`01^"*"+1 = (0(1^"*"))+1`

-> der Ausdruck ist von der Form

r	=	`r_1`	+	`r_2`
		`01^"*"`		`1`

TODO bild

Beachten Sie, dass die Notwendigkeit, die Zustandsmengen verschiedener Automaten disjunkt zu halten, uns davon abhält den gleichen NEA für `r_2` und `r_5` zu benutzen, obwohl es sich eigentlich um den selben regulären Ausdruck handelt. Um einen NEA `r_4 = r_5**` zu konstruieren benutzen wir die Hüllenbildung. Zunächst sind Zustände `q_7` und `q_8` zu erzeugen, die die Rollen von `q_0` (Anfangszustand) und `f_0` (Endzustand) übernehmen. TODO bild Dann wird die Konstruktion für `r_1 = r_3 r_4` verwendet. TODO bild Abschliessend gilt: `r = r_1 + r_2`

Eigenschaften regulärer Mengen

Nachdem wir nun verschiedene Hilfsmittel zur Repräsentation regulärer Mengen kennengelernt haben, werden wir uns nun mit der Fragestellung in Bezug auf spezielle gegebene Sprachen `L` beschäftigen. Welche Fragen sind in diesem Zusammenhang von Interesse?

1. Ist eine wie auch immer spezifizierte Sprache regulär (oder ist sie es nicht)?
2. Welches ist der EA mit den wenigsten Zuständen, der die gleiche Sprache wie ein gegebener EA beschreibt?
3. Aussagen bzgl. der Abgeschlossenheit regulärer Mengen
4. Akzeptiert ein bestimmter EA eine unendliche Sprache?

Das Pumping-Lemma für reguläre Sprachen

Das Pumping-Lemma ist ein mächtiges Hilfsmittel um zu zeigen, dass gewisse Sprachen nicht regulär sind. Es hilft ebenso um gewisse Aussagen über EA zu beweisen (z.B. ob die jeweils akzeptierte Sprache endlich oder unendlich ist, sprich zyklen existieren). Sei `A = (Q,Sigma,delta,q_0,F)` ein deterministischer endlicher Automat mit `n = |Q|`. Betrachten sie eine Eingabe, die aus `n` oder mehr Zeichen besteht. `a_1 a_2 ... a_m` `m >= n` für `i = 1,2,...,m` sei `delta(q_0,a_1a_2...a_i) = q_i` es kann nicht sein, dass alle `n+1` Zustände `q_0,q_1,...,q_n` verschieden sind, da es nur `n` Zustände gibt. => es gibt `j,k in NN` mit `0 <= j < k <= n`, sodass `q_j = q_k`. TODO bild da `j < k` ist die Länge von `a_(j+1)...a_k >= 1` da `k < n` ist die Länge von `a_(j+1)...a_k <= n`

Wenn `a_1...a_j a_(j+1)...a_k a_(k+1)...q_m in L(A)`, dann `a_1...a_j a_(k+1)...a_m in L(A)` und `a_1...a_j(a_(j+1)...a_k)^i a_(k+1)...a_m in L(A)`. `AAi>=0`

Pumping Lemma:

`L` sei eine reguläre Menge. Es gibt eine Konstante `n`, sodass sich ein Wort `z` aus `L` mit `|z| >= n` als `z = uvw` schreiben lässt und für alle `i >= 0` gilt, dass `uvw` in `L` enthalten ist. Zusätzlich ist `n` nicht grösser als die Anzahl der Zustände in dem kleinsten endlichen Autoamten, der `L` akzeptiert.

Wichtig

Das Pumping-Lemma besagt nur, dass eine reguläre Menge, wenn sie eine lange Zeichenkette `Z` enthält, auch unendlich viele Zeichenketten der Form `uv^iw` enthält. Es besagt aber nicht, dass jede genügend lange Zeichenkette in einer regulären Menge von der Form `uv^iw` für ein grosses `i` ist.

Beispiel:

Frage: Ist die Sprache `L={0^(k^2)|k in NN, k>=1}, die aus allen aus Nullen zusammengesetzten Zeichenketten, deren Länge eine Quadratzahl ist, regulär?

Beweis durch Widerspruch

Nehmen wir an, `L` wäre regulär: `n` sei die ganze Zahl aus dem Pumping-Lemma `z` sei `0^(n^2)`. Klarerweise ist `|z| > n`. Nach dem Pumping-Lemma kann `0^(n^2)` geschrieben werden als `uvw`, wobei `1 <= |v| <= n` und `uv^iw in L` für alle `i`. Dies gilt natürlich auch für ein konkretes `i=2`! ABER: ToDo bild2 -> Die Länge von `uv^2w` liegt echt zwischen `n^2` und `(n+1)^2` und ist somit kein perfektes Quadrat. -> Widerspruch D.h. die Annahme, dass `L` regulär sei ist falsch. => L ist nicht regulär

3.2 Entscheidungsverfahren für reguläre Sprachen

• Wortproblem: `w in L`?
• Endlichkeit: `|L|<omega` oder `|L|=omega`?
• Leerheit `L=O/`
• Äquivalenz `L_1 = L_2` (Disjunktheit `L_1 nn L_2 = O/`)? po- Inklusion `L_1 sube L_2`
  Das Wortproblem brauchen wir für reguläre Mengen nicht weiter zu betrachten, da der zugehörige deterministische Automat das Verfahren selbst liefert. Wir gehen davon aus, dass `L` (bzw. `L_1` und `L_2`) duch einen regulären Ausdruck oder einen EA gegeben ist.
  Entscheidbarkeit: (Leerheit, (Un)endlichkeit) Für eine reguläre Sprache ist entscheidbar, ob `L=O/` und ob `|L| = omega`.

3. Kontextfreie Sprachen und Kellerautomaten

Die kontextfreien Sprachen sind, wie die regulären Mengen, von großer Bedeutung bei der Definition von Programmiersprachen. z.B. Beschreibung korrekt geklammerter Ausdrücke begin-end Strukturen in Programmiersprachen -> durch reguläre Ausdrücke nicht darstellbare Konstrukte. Kontextfreie Grammatiken (kfG) sind vergleichbar mit der bereits bekannten Backus-Naur-Form (BNF) zur Beschreibung von Programmiersprachen.

3.1 kontextfreie Grammatiken

zur Definition von Grammatiken, Satz und Satzform siehe Abschnitt 1.1.2.4. :kontextfreie Grammatik: Eine Grammatik `G = (V,Sigma, P, S)` heisst kontextfrei, wenn gilt `P sube V xx (V uu Sigma)^** ` und jede Produktion der Grammatik die Form `A -> w` hat, wobei `A in V` und `w in (V uu Sigma)^**`. :kontextfreie Sprache: Eine Sprache `L` heisst kontextfrei, wenn es eine kfG gibt, die `L` erzeugt (`L=L(G)`). Wir werden folgende Konventionen in Bezug auf Grammatiken benutzen (Variablen, Terminal und Startsymbole):

• Die Großbuchstaben A,B,C,D,E, ... und S sind Variablen, wobei S das Startsymbol ist.
• Die Kleinbuchstaben a,b,c,d,e,f,... und Ziffern sind Terminale.
• Die Großbuchstaben X,Y,Z bezeichnen Symbole, die sowohl Terminale als auch Variablen sein können.
• Die Kleinbuchstaben u,v,w,x,y,z bezeichnen Zeichenketten aus Terminalen.
• Die griechischen Buchstaben `alpha, beta` und `gamma` bezeichnen Zeichenketten aus Variablen und Terminalen.

  Beispiel:

  Grammatik `G = (V, Sigma, P,S)` `V={S}` `Sigma={a,b}` `P={S->aSb, S->ab}` ToDo bildchen 2 `L(G)={a^n b*n| n>=1}

  Beispiel:

  Grammatik `G=({S,A,B},{a,b},P,S})` `P = {S -> aB, S -> bA, A -> a, A -> aS, A -> bAA, B -> b, B -> bS, B -> aBB }` L(G) = {w<Sigma^+`, die gleich viele a und b enthalten `}`

3.2 Ableitungen und Ableitungsbäume

Die Ableitung der Sätze einer Grammatik läßt sich auch graphisch in Form eines Baumes darstellen. Die so dargestellte Struktur der Wörter einer Sprache ist insbesondere für die Compilierung von Programmiersprachen von Bedeutung.

ToDo Beispiel3

3.3 Mehrdeutigkeit von Ableitungen

Unter Umständen kann ein Wort einer Sprache auf unterschiedlichen Wegen mittels der angegebenen Grammatik abgeleitet werden.

ToDo Bsp4

Eine kontextfreie Grammatik, in der es ein Wort mit mehr als einem Ableitungsbaum gibt, heißt mehrdeutig. Eine kfS, für die jede kfG mehrdeutig ist, heißt ererbt mehrdeutige kfS (inherently ambigous). Wird im Rahmen einer Ableitung bei jedem Schritt eine Produktion auf die linksstehende Variable angewendet, so sprechen wir von einer Linksableitung. Wird die Produktion bei jedem Schritt auf die rechtsstehende Variable angewendet, so sprechen wir von einer Rechtsableitung.

Linksableitung zu (1) `A -> A + A -> a + A -> a + A * A -> a + b * A -> a + b * c`

Rechtsableitung zu (1) `A -> A + A -> A + A * A -> A + A * c -> A + b * c -> a + b * c`

3.4 Kellerautomaten

So wie die regulären Ausdrücke den endlichen Automaten Äquivalent sind, haben auch die kfG ein Automaten-Gegenstück, die sogenannten Kellerautomaten. Allerdings ist hier die Äquivalenz leider nicht gleich ausgeformt wie das bei den endlichen Automaten der Fall war. Kellerautomaten sind nichtdeterministische Konstrukte (die deterministische Variante akzeptiert nur eine Teilmenge der kfS - diese umfasst allerdings die Syntax der meisten Programmiersprachen).

Beispiel:

`L={wcw^R|w in (0+1)^**}` kontextfreie Sprache, nicht regulär (Pumping-Lemma) `=^ S -> 0S0 | 1S0 | c`

ToDo Bild Das beschriebene Gerät akzeptiert eine Eingabe, wenn ebi der Bearbeitung des letzten Zeichens der Tellerstapel leer wird. Ist der Stapel einmal leer, so können keine weiteren Bewegungen gemacht werden.

3.4.1 Definition Kellerautomat

Ein Kellerautomat `A` über einem Alphabet `Sigma` besteht aus

• einem Eingabealphabet `Sigma`
• einer endlichen Menge `Q` von Zuständen
• einem Anfangszustand `q_0 in Q`
• einem Kelleralphabet `Gamma` (`Gamma = Sigma` ist möglich, aber nicht notwendig)
• einem Anfangssymbol `z_0 in Gamma`
• eine Menge `F` von Endzuständen
• einer Übergangsrelation `delta <= (Qxx(Sigma uu {epsilon} xx Gamma) xx (Q xx Gamma^**)`
• Wir schreiben `A = (Q, Sigma, Gamma, delta, q_0, z_0, F)`
  Eingabeband (`Sigma^**`) kann nur gelesen werden.

3.4.2 Konfiguration

Sei `A = (Q, Sigma, Gamma, delta, q_0, z_0, F)` ein Kellerautomat. Ein Wort `delta in Sigma^** Q Gamma^**` heisst Konfiguration von `A`.

`epsilon q_0 z_0` heisst Startkonfiguration von `A`. das heisst `epsilon` = ich stehe ganz vorn auf `q_0` und habe da `z_0` stehen Für `gamma = omega q y alpha` mit `omega in Sigma^** , q in Q, y in Gamma, alpha in Gamma^** ` und `x in Sigma uu {epsilon}, beta in Gamma^**` mit `((q,x,y)(p,beta)) in gamma` heißt `gamma' = omega x p beta alpha` eine Folgekonfiguration von `gamma` in `A`, wir schreiben `gamma |-> A gamma'`.

3.4.3 Akzeptierte Sprache

Sei `A=(Q, Sigma, Delta, delta, q_0, z_0, F)` ein Kellerautomat. Wir nennen `L(A) = { w in Sigma^** | q_0z_0 |-> w q alpha, q in F}` die (über den Endzuständen) akzeptierte Sprache zu `A`.

Wir nennen `N(A) = { w in Sigma^** | q_0z_0 |-> w q epsilon, q in Q}` die mit leerem Keller akzeptierte Sprache von `A`.

Dies ist gleichbedeutend mit:

• Für jeden Kellerautomaten `A` gibt es (effektiv) einen Kellerautomaten `A'` mit `L(A)=N(A')`.
• Für jeden Kellerautomaten `A` gibt es (effektiv) einen Kellerautomaten `A'` mit `N(A)=L(A')`.

3.4.4 Deterministische Kellerautomaten

Ein Kellerautomat `A=(Q, Sigma, Gamma, delta, q_0, z_0, F)` heißt deterministisch, wenn für `q,q_1,q_2 in Q, x in Gamma, a in Sigma` und `alpha_1, alpha_2 in Gamma^**` gilt:

`((q,a,x),(q_1,alpha_1)) in delta ^^` `((q,a',x),(q_2,alpha_2)) in delta`

`=> q_1 = q_2 ^^ alpha_1=alpha_2`, wenn `a=a'`.

Man sieht leicht, dass für einen deterministischen Kellerautomaten für jede Konfiguration `delta` höchstens eine Folgekonfiguration `delta'` existiert.

3.4.5 Kellerautomaten und kontextfreie Sprachen

Die von (nichtdeterministischen) Kellerautomaten akzeptierten Sprachen sind genau die kontextfreien Sprachen.

Jede kontextfreie Sprache wird von einem Kellerautomaten mit leerem Keller akzeptiert. Im Gegenschluß gilt: Jede von einem Kellerautomaten akzeptierte Sprache ist kontextfrei.

3.5 Eigenschaften kontextfreier Sprachen

3.5.1 Abschlusseigenschaften

Eine Menge ist hinsichtliche einer bestimmten Operation abgeschlossen, wenn das Ergebnis wieder Element der Menge ist. So sind z.B. die Addition und Multiplikation über den natürlichen Zahlen abgeschlossen, die Division jedoch nicht.

Die kontextfreien Sprachen sind abgeschlossen unter:

• Vereinigung
  • (`S |-> S_1|S_2` wobei `S_1,S_2` Startaxiome der ursprünglichen Sprachen sind)
  • `L_1 uu L_2 : S |-> S_1|S_2` `<- Produktionen von `L_1` und `L_2`
• Konkatenation
  • (`S -> S_1 S_2` wobei `S_1,S_2` Startaxiome der ursprünglichen Sprachen sind)
  • `L_1 @ L_2 : S -> S_1 S_2` + Produktionen von `L_1` und `L_2`
• Kleen'sche Hülle
  (`S -> epilon | S_1 S`)
  `L^** : S -> epsilon | S_1 S` + Produktionen von `L_1`

3.5.2 Entscheidungsverfahren

Für jede kontextfreie Sprache `L` (repräsentiert durch eine kontextfreie Grammatik oder einen Kellerautomaten) ist entscheidbar (grundsätzlich lösbar), ob

• `L = O/` (ob er überhaupt Wörter akzeptiert)
• `|L| = omega` (ob Mächtigkeit unendlich)

Für ein Wort `omega in Sigma^**` und eine kontextfreie Sprache `L` ist entscheidbar, ob `omega in L` gilt.

3.5.3 Unentscheidbarkeit

Viele Probleme, die für reguläre Sprachen entscheidbar sind, sind bereits für kontextfreie Sprachen unentscheidbar.

• `L(G) = Sigma^**`
• `L(G_1) = L(G_2)` (Äquivalenz)
• `L(G_1) sube L(G_2)` (Inklusion)
• `L(G_1) ^^ L(G_2) = 0` (Disjunktion)
• `L(G_1) ^^ L(G_2)` kontextfrei?
• `L(G)` irregulär?
• `not(L(G))` kontextfrei?

Diese Fragen können nicht in jedem Fall geklärt werden.

4. Turing Maschinen und rekursiv aufzählbare Mengen

4.1 Turing Maschinen

Es wird an dieser Stelle die Turing-Maschine als einfaches mathematisches Modell für einen Computer eingeführt. Trotz ihrer Einfachheit modelliert die Turing Maschine die durch einen Allzweck-Computer gegebene Berechenbarkeit.

In einem engen Zusammenhang mit dem hier auftretenden Begriff der "Berechenbarkeit" steht auch der Begriff des "Algorithmus". Eine intuitive Vorstellung von einem Algorithmus kann vorausgesetzt werden -- doch was versteht man formal darunter?

Formales Modell eines Algorithmus:

• Jeder Algorithmus soll endlich beschreibbar sein.
• Jeder Algorithmus soll aus diskreten Schritten bestehen, von denen Jeder maschinell ausführbar ist.

Die Turing-Maschine ist ein anerkannter Formalismus für die Beschreibung von Algrorithmen. Das zugrunde liegende Modell wurde 1936 von Alan Turing in der hier beschriebenen Variante vorgestellt.

Basismodell der Turing-Maschine

TODO Bild

Ausgangssituation

• Die `n (n >= 0)` links stehenden Felder enthalten die Eingabe (pro Feld ein Zeichen aus einer endlichen Menge von Bandsymbolen)
• Verbleibende (unendlich viele) Felder mit `B` (Blank) = spezielles Bandsymbol (`~in` Eingabesymbole)

Bewegungen

Abhängig vom gelesenen Bandsymbol und dem Zustand der endlichen Kontrolle kommt es zu folgenden

• Zustandsänderung der endliche Kontrolle
• Schreiben eines Symbols in das gelesene Bandfeld (Überschreiben des gelesenen Feldes)
• Bewegung des Schreib-/Lesekopfes um eine Stelle nach rechts bzw. links
  Formal lässt sich das wie folgt beschreiben:
  `M = (Q, Sigma, Delta, delta, q_0, B, F)`

`M`	Maschine
`Q`	Zustände
`Sigma`	Eingabesymbole (Teilmenge der erlaubten Bandsymbole ohne `B`)
`Delta`	erlaubte Bandsymbole
`delta`	Übergangsfunktion `Q x Sigma -> Q x Delta x {LR}`
`q_0`	Anfangszustand `in Q`
`B`	Blank
`F`	Menge der Endzustände (`F sube Q`)

Eine Konfiguration einer Turing-Maschine

`M` ist ein Tripel `<alpha_1, q, alpha_2> in Gamma^** x Q x Gamma^**` geschrieben `alpha_1 q alpha_2` und beschreibt die Situation, dass sich auf dem Arbeitsband vom `M` die Zeichenkette `alpha_1 alpha_2` befindet (gefolgt von Blanks `B`), `M` den Zustand `q` innehat und der Kopf von `M` das erste Zeichen von `alpha_2` liest. (`alpha_1 alpha_2` kann Blanks `B` enthalten!) Im Falle `alpha_2 = sigma` (leer) bedeutet das, dass sich der Kopf von `M` über einem Blank `B` befindet. ToDo Bild

Ein Schritt

Sei `alpha_1 q alpha_2` die aktuelle Konfiguration mit `alpha_1 = A_1 A_2 ... A_i-1` und `alpha_2 = A_i A_i+1 ... A_n`.
Wir nehmen an, dass der Schreib-/Lesekopf das am weitesten links stehende Symbol von `alpha_2` liest bzw. falls `alpha_2 = sigma` ein Blank `B` liest.

Sei nun `x_1 x_2 ... x_(i-1) q x_i x_(i+1) ... x_n` eine Zustandsbeschreibung und `delta ( q, x_i ) = ( p, y, L )`.

• Falls `i-1 = n`, dann ist `x_i = B`.
• Falls `i = 1`, dann gibt es keine nächste Zustandsbeschreibung, da sich der Kopf nicht über das linke Ende hinausbewegen darf.
• Falls i > 1, dann `x_1 x_2 ... x_i-1 q x_i x_(i+1) ... x_n |-> x_1 x_2 ... x_i-2 p x_(i-1) y x_(i+1) ... x_n` und `delta ( q, x_i ) = (p, y, R)

`x_1 x_2 ... x_(i-1) q x_i x_(i+1) ... x_n |-> x_1 x_2 ... x_(i-1) y p x_(i+1) ... x_n`

Stehen zwei Konfigurationen vom `M` in Relation `|->_M`, so können wir sagen, dass die zweite Konfiguration aus der ersten mittels einer Bewegung folgt. Resultiert eine Zustandsbeschreibung aus einer anderen durch eine endliche Anzahl von Bewegungen, so stehen diese beiden Zustandsbeschreibungen in der Relation `|->_M` (da meist klar ist, welche Macshine betrachtet wird, kann `_M` auch weggelassen werden - wir schreiben `|->` statt `|->_M` und `|->^**` statt `|->_M`.

Von M akzeptierte Sprache

Als von `M` akzeptierte Sprache `L(M)` bezeichnet man die Menge der Wörter aus `Sigma^**`, die `M` veranlassen in einen Endzustand überzugehen.
Dazu wird das entsprechende Wort linksbündig auf das Eingabeband geschrieben und die Turing-Maschine mit dem Kopf auf dem ersten Zeichen des Eingabewortes im Zustand `q_0` gestartet. D.h. die von `M = (Q, Sigma, Gamma, delta, q_0, B, F)` erkannte Sprache `L(M) = { omega | omega in Sigma^** ^^ q_0 omega |-> alpha_1 p alpha_2` für ein `p in F` und `alpha_1, alpha_2 in Gamma^**}`

Zu beachten ist, dass die Turing-Maschine

ToDO Ergänzung

Turing-Berechenbarkeit

Eine Funktion `f(x) = y | x, y in Sigma^**` ist Turing-berechenbar, wenn es eine Folge von Zustandsübergängen gibt, mit denen die Turing-Maschine aus jeder Anfangskonfiguration mit dem Wort `x` in eine Endkonfiguration mit dem Wort `y` übergeht. Die Turing-Maschine transformiert also die Eingabe `x` in die Ausgabe `y`, die dann auf dem Band abgelesen werden kann.
Hält die Turing-Maschine für bestimmte Eingaben nicht an, so ist die Übergangsfunktion `f` eine partielle Funktion.

Auch bei Turing-Maschinen gibt es eine deterministische und eine nicht-deterministische Variante. Man kann zeigen, dass jede nicht-deterministische Turing-Maschine durch eine Deterministische ersetzt werden kann, welche die selbe Ausgabe liefert. Allerdings muß diese deterministische Turing-Maschine nicht notwendigerweise anhalten.

4.2 Rekursiv aufzählbare Sprachen

Aus der Definition von endlichen Turing-Maschinen folgt, dass die Menge aller üiberhaupt möglichen Turing-Maschinen aufzählbar sein muß. Man kann damit zeigen, dass jede Turing-Maschine einer rekursiv aufzählbaren formalen Sprache zugeordnet werden kann und umgekehrt.

rekursiv aufzählbar

Eine Sprache `L sube Sigma^** ` heißt rekursiv aufzählbar, wenn es eine Funktion `f: NN_0 -> Sigma^**` gibt, so dass `L = {f(0), f(1), ...}` gibt.
Das bedeutet, eine Sprache heißt dann rekursiv aufzählbar, falls es eine berechenbare Funktion `f` (bzw. einen Algorithmus) gibt, die (der) die Worte der Sprache `L` aufzählt.

Beispiel:

`Sigma^* = {0,1}**` Zusätzlich gilt, dass die rekursiv aufzählbaren Sprachen genau den durch die Chomsky-Typ 0 Grammatiken erzeugten Sprachen entsprechen.

5. Die Chomsky Hierarchie

In den letzten Kapiteln haben wir drei Familien formaler Sprachen kennengelernt:

• reguläre Sprachen
• kontextfreie Sprachen
• rekursiv aufzählbare Sprachen

Abhängig von den Einschränkungen, die an die Grammatik gestellt werden, können wir ebenfalls Sprachfamilien unterscheiden.

Eine Sprache `L sube Sigma^** ` heisst Sprache vom Typ `i` (`i=0,1,2,3`), wenn es eine Typ-i-Grammatik gibt, die `L` erzeugt.
In den folgenden Abschnitten werden die einzelnen Sprachfamilien noch genauer charakterisiert.

5.1 Typ-3-Grammatiken

Die stärksten Restriktionen hatten wir an Grammatiken gestellt, die die regulären Sprachen erzeugen. Diese Grammatiken werden als reguläre Grammatiken oder auch als Typ-3-Grammatiken bezeichnet.

Typ-3-Grammatik

Eine Grammatik `G = (V, Sigma, P, S)` ist eine Typ-3-Grammatik, wenn alle Produktionen `P` von folgender Form sind:

`A -> sigma|omega|omega B|`	rechts-linear
`A -> sigma|omega|B omega|`	links-linear |\\

wobei `omega in Sigma^** ^^ A,B in V`

Beispiel:

`S -> ab|ac|ad|adS|aaS`
`S -> ab|ac|Sac` ist gleich `{(ab)^n(ac)^m | 0 <= n <= 1, m >= 0}`
nicht Typ-3: `S -> ab | Sab | abS`, weil rechtslinear und linkslinear nicht vermischt werden darf ("S nur entweder immer rechts oder immer links stehen darf")

5.2 Typ-2-Grammatiken

Die Produktionen einer kontextfreien Grammatik sind ein wenig allgemeiner:

Typ-2-Grammatik

Eine Grammatik `G = (V, Sigma, P, S)` ist eine Typ-2-Grammatik oder kontextfreie Grammatik, wenn alle Produktionen `P` von folgender Form sind:

`A -> alpha | A in V, alpha in (V uu Sigma)^** `

Beispiel:

`A -> aXb`
`X -> abX | epsilon`

5.3 Typ-1-Grammatiken

Bei den kontextsensitiven Sprachen ist es zulässig, dass auf der linken Seine einer Produktion sowohl Variablen als auch Terminale stehen.

Beispiel:

`bSb -> baaSab`

Typ-1-Grammatik

Eine Grammatik `G = (V, Sigma, P, S)` ist eine Typ-1-Grammatik oder kontextsensitive Grammatik, wenn alle Produktionen `P` von folgender Form sind:
`alpha_1 A alpha_2 -> alpha_1 beta alpha_2 | alpha_1, alpha_2, beta in (V uu Sigma^**), beta != sigma, A in V`

Durch den Ersetzungsprozeß darf die Zeichenkette also nicht kürzer werden!!! (`beta != sigma`!!!)

5.4 Typ-0-Grammatiken

Bei den Typ-0-Grammatiken werden dann schließlich keine Einschränkungen mehr an die Produktionen gestellt, außer dass aus dem leeren Wort nichts erzeugt werden darf.
Die erzeugten Sprachen entsprechen den von Turing-Maschinen erkannten Sprachen sowie den rekursiv aufzählbaren Sprachen.

Typ-0-Grammatik

Eine Grammatik `G = (V, Sigma, P, S)` ist eine Typ-0-Grammatik, wenn alle Produktionen `P` von folgender Form sind:
`alpha -> beta | alpha, beta in (V uu Sigma)^**, alpha != sigma`

Beispiel:

AbaaC -> sigma
Abaa -> bbaa

Der Erzeugungsprozeß mus mit einem Startsymbol beginnen. Diese Grammatiken werden auch als Semi-Thui-System bezeichnet.

Beispiel:

Die folgende Grammatik erzeugt die Sprache `{a^i | i `ist pos. Zweierpotenz`}`
`G = ({S,A,B,C,D,E}, {a}, P, S)`
`P = ToDo vervollständigen

5.5 Die Chomsky Hierarchie

Typ 0 == Turing-Maschine
Typ 1 == kontextsensitiv
Typ 2 == Kellerautomat / kontextfrei
Typ 3 == endliche Automaten / reguläre Ausdrücke

6. Algorithmen und Berechenbarkeit

6.1 Der Algorithmenbegriff

Al Chwerizmi ~ 700 - 850

Aufgabensammlung für Kaufleute und Testamentsvollstrecker -> liber algorithmi

6.1.1 Definition des Algorithmus

Alle Algorithmen haben unabhängig von wechselnden Notationen und Mechanismen zwei gemeinsame Eigenschaften:

• Finitheit der Beschreibung
  Der vollständige Algorithmus muß in einem endlichen Text aufgeschrieben sein.

• Effektivität
  jeder der Schritte, die den Algorithmus beschreiben, muß ausführbar sein, d.h. der Algorithmus muß operativ sein.

6.1.2 Terminierung

Eine Eigenschaft von Algorithmen, an der man aus theoretischen wie praktischen Gründen interessiert ist, ist die Terminierung:

Der Algorithmus kommt in endlich vielen Schritten zu einem Ende ("terminierender Algorithmus").

6.1.3 Determinismus

Unter Determinismus eines Algorithmus ist zu verstehen, dass die Reihenfolge des Ablaufes der Einzelschritte des Algorithmus eindeutig vorgeschrieben ist.

6.1.4 Effizienz

Dieser gerne mit der Effektivität verwechselte Begriff beschreibt mit welchem Aufwand ein Algorithmus eine Aufgabe löst. Dabei wird der Aufwand möglicherweise in der Anzahl der benötigten Rechenschritte oder in der Belegung von Speicher gemessen. Die Effizienz ist lediglich eine praktische Frage -- allerdings eine sehr wichtige!

6.2 Berechenbarkeit

Grundsätzlich sind folgende Fragestellungen von Interesse:

• Kann jedes Problem durch einen Algorithmus gelöst werden?

• Kann jeder Algorithmus ein ein Programm transformiert werden? (Welchen Anforderungen muß dabei eine Programmiersprache genügen?)

• Ist ein Computer grundsätzlich in der Lage einen als Programm formulierten Algorithmus auszuführen?

• Welches formale System ist ein Computer?

Diese Fragestellungen beziehen sich auf die Berechenbarkeit von Problemen, auf die Theorie von Programmiersprachen sowie auf die Komplexität von Algorithmen. Dabei stellt sich immer wieder die Frage, wie sichein Computer als formales System beschreiben läßt. Insofern ist etwa zu klären, in wie weit formale Ansätze (Turing
ToDo complete

6.2.1 Entscheidungsproblem und Church-Turing-These

Ansicht: Man kann für jedes Problem zeigen, dass es entweder lösbar ist oder nicht.

f(Problem) -> {lösbar, unlösbar}

Gödel - Hilbert 1931 "Mathematikerstreit"

Möchte man beweisen, dass zu einem bestehenden Problem kein Algorithmus zu dessen Lösung existiert, so muss man den Begriff Algorithmus formalisieren.

Verwendet man das Konzept der Turing-Maschine als Modell zur formalen Beschreibung von Algorithmen, so ist jedes Problem dann algorithmisch lösbar, wenn es als Turing-Maschine dargestellt werden kann.

Computer sind äquivalent zur universellen Turing-Maschine `U`, d.h. zu einer Turing-Maschine, die jede andere Turing-Maschine `T` simlulieren kann.

ToDo Bild1

`U` ist eine abstrakte Beschreibung für jeden Computer.
`U` simuliert `T`.

Es gibt noch andere Beschreibungsmöglichkeiten von Algorithmen, etwa rekursive Funktionen, die sich aus einfachen, offensichtlich berechenbaren Funktionen bilden lassen.

Es besteht daher nach Alonzo Church und Alan Turing eine starke Evidenz (ohne dass ein streng mathematischer Beweis möglich wäre!) dafür, dass nicht nur die oben genannten Möglichkeiten der Formalisierung von Algorithmen gleichwertig sind und zu denselben Ergebnissen über die Berechenbarkeit von Problemen führen, sondern dass dies allgemein für alle im intuitiven Sinn vernünftigen Formalisierungen gilt.

Wenn ein Problem nicht durch eine Turing-Maschine gelöst werden kann, so ist es überhaupt nicht algorithmisch lösbar.

Berechenbarkeit

Eine Funktion `f(x)` heißt berechenbar, wenn es einen Algorithmus gibt, der bei gegebenem `x` das Ergebnis `f(x)` liefert.

oder alternativ:

Ist eine Menge `M` gegeben, so heißt `M` entscheidbar, wenn es einen Algorithmus gibt, der für jedes vorgegebene Element `x` als Ergebnis die Aussage liefert, ob `x` in `M` enthalten ist oder nicht.

Vermutung: nicht jede Funktion ist berechenbar

1. Die Menge aller Funktionen ist überabzählbar.

Ein Algorithmus muss wegen der Abbildung auf eine Turing-Maschine in jedem Fall durch ein Alphabet A mit einem endlichen Zeichenvorrat und einer endlcihen Zeichenfolge dargestellt werden können. (Bei TM reicht sogar A={0,1})

`A^** ` umfasst abzählbar unendlich viele Zeichenreihen

=> Zeichenreihen, die TM repräsentieren < `A^** `
=> { alle TM } ist abzählbar
jede TM entspricht einer Funktion

2. die durch TM repräsentierten (d.h., die berechenbaren) Funktionen sind abzählbar.

Aus 1. und 2. folgt: - Es muss nicht berechenbare Funktionen geben - die Menge der nicht berechenbaren Funktionen ist überabzählbar (d.h. es gibt mehr nicht berechenbare als berechenbare Funktionen!!)

6.2.2 Das Halteproblem

Es wird nicht nur behauptet, es gäbe Probleme, zu deren Lösung noch kein Algorithmus bekannt sei, sondern es wird die stärkere Aussage gemacht, dass deshal kein lgorithmus zur Lösung dieser Probleme gefunden werden konnte, weil ein solcher grundsätzlich nicht existiert.

Frage:
Gibt es einen Algorithmus, mit dessen Hilfe man für ein beliebiges Programm `P` bestimmen kann, ob es mit den beliebigen Eingabedaten `D` jemals stoppen wird oder nicht?

Annahme: Es existiert ein Algorithmus zur Lösung des Halteproblems.

ToDo Bild2

Nun wird das Programm TEST1 mit dem Programmtext von TEST1 als Eingabe aufgerufen.

Nimmt man an, TEST1 stoppt, so folgt, dass TEST1 nicht stoppt und umgekehrt.

=> ToDo Widerspruch

Es ist somit bewiesen, dass das Halteproblem nicht berechenbar ist.

Die zum Beweis der Nichtberechenbarkeit des Halteproblems verwendete Technik des Beweises durch Widerspruch wird in diesem Zusammenhang häufig verwendet.

Neben dem Halteproblem gibt es eine ganze Reihe weiterer nicht berechenbarer Probleme, so z.B. das Äquivalenzproblem.

Fragestellung: Lösen zwei Programme dieselbe Aufgabenstellung?

Ein Vergleich von Halteproblem und Äquivalenzproblem zeigt, daß es zwei Klassen von Nichtberechenbarkeit gibt.

				 /									 \
				/											\
	Halteproblem				Äquvalenzproblem
				|											|
	Prog. stoppt in			auch bei direkt
	vielen Fällen				ersichtlicher
				|							Äquivalenz keine
	partiell nicht 			maschinelle
	berechenbar					Überprüfbarkeit

6.2.3 Primitiv rekursive Funktionen

Die primitiv rekursiven Funktionen entstehen aus einigen einfachen Grundfunktionen über einem beliebigen Alphabet, welche man endlich oft anwendet. Da jedes Alphabet definitionsgemäß auf die natürlichen Zahlen mit Null abbildbar ist, genügt es `NN_0` zu betrachten.

---

Quellcode