Grundlagen der Informatik 2 Felix Hummel Sommersemester 2007 %!includeconf: loader.t2t %%%%%% BEGIN CONTENT %%%%%% = 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 http://de.wikipedia.org/wiki/Abz%C3%A4hlbarkeit], wenn es eine [bijektive http://de.wikipedia.org/wiki/Bijektion] 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` | bsp-- `|{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. bsp-- 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 | bsp-- `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)^**`: + `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` %%mtime(%y-%m-%d) ==Ä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 http://de.wikipedia.org/wiki/Regul%C3%A4re_Sprache] bezeichnet. : Satz Sei `r` ein regulärer Ausdruck, dann gibt es einen NEA mit `epsilon`-Transitionen, der `L(r)` akzeptiert. (Beweis: siehe Literatur) bsp-- 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? + Ist eine wie auch immer spezifizierte Sprache regulär (oder ist sie es nicht)? + Welches ist der EA mit den wenigsten Zuständen, der die gleiche Sprache wie ein gegebener EA beschreibt? + Aussagen bzgl. der Abgeschlossenheit regulärer Mengen + Akzeptiert ein bestimmter EA eine unendliche Sprache? ==Das Pumping-Lemma für reguläre Sprachen==[pumping] 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. bsp-- 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| 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. bsp-- 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} bsp-- 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 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). bsp-- `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 ` 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.\\ bsp-- `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` bsp-- `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)^** ` bsp-- `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.\\ bsp-- `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` bsp--\\ ``AbaaC -> sigma``\\ ``Abaa -> bbaa`` Der Erzeugungsprozeß mus mit einem Startsymbol beginnen. Diese Grammatiken werden auch als Semi-Thui-System bezeichnet. bsp-- 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 [img/blitz.gif] 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 %%infile(%f)]