Grundlagen Der Theoretischen Informatik

Grundlagen der Theoretischen Informatik
Adrian Neumann 4. Juli 2007
Vorlesung 1
Motivation
In der theoretischen Informatik sucht man mathematische Formalisierungen von Begrien aus der Informatik (Algorithmus, Programmiersprache etc.). Beispiel 1. In den 50er Jahren hat man den ersten Compiler, fr die Sprache FORTRAN, gebaut. u Die Konstruktion hat insgesamt 18 Personenjahre bentigt. Heute baut man Compiler innerhalb o eines Studentenpraktikums. Diese Beschleunigung ist nur mglich durch die Formalisierung der o Begrie Syntax, Semantik und Programmiersprachen.
Inhalt der Vorlesung

Regulre Ausdrcke und Sprachen, endliche Automaten a u Textverarbeitung Hardwaredesign kontextfreie Grammatiken und Sprachen, Pushdown/Kellerautomaten Syntax von Programmiersprachen Compilerbau Linguistik Berechenbarkeit und Entscheidbarkeit, Turingmaschinen
Regulre Sprachen und endliche Automaten a

Regulre Sprachen a Denition 1. Es sei eine endliche Menge (genannt Alphabet). Jede Folge von Buchstaben aus dieser Menge heit Wort. Jede Menge von Wrter heit Sprache. o ist die Menge aller endlichen Folgen von Buchstaben aus . ist natrlich eine unendliche u heien Wrter (Strings, Words). Menge, es sei denn ist leer. Elemente von o Die Lnge eines Wortes: a w , w = a1 , . . . , an ai , i = 1, . . . , n
n heit Lnge von w, n = |w|. Es gibt nur ein Wort der Lnge 0. Ublicherweise wird es , das leere a a Wort uber , genannt. Zwei Wrter w1 , w2 aneinanderhngen liefert ein neues Wort w1 w2 ( wird gelegentlich auch o a weggelassen). Diese Operation heit Konkatenation von w1 , w2 .
\
CC BY: $
http://muhserva.dyndns.org
Bemerkungen |w1 w2 | = |w1 | + |w2 | w = w = w, d.h. ist das neutrale Element bezglich der Konkatenation u (w1 w2 ) w3 = w1 (w2 w3 ), d.h. ist assoziativ. Eine solche Struktur (assoziativ, mit neutralem Element) nennt man Monoid oder Halbgruppe mit neutralem Element. Beispiel 2. = {0, 1}, sog. binres Alphabet. a = {, 0, 1, 00, 01, 10, 11, . . .} Denition 2. Sei ein Alphabet, u, v (also Wrter). u heit Prx von v, wenn es ein o a w gibt, mit v = u w. u ist also ein Anfangsstck von v (oder gleich v). Umgekehrt heit u u Sux, wenn es ein Endstck (oder gleich) ist. u Wenn u irgendwo in der Mitte von v vorkommt (v = w1 u w2 ), heit es Teilwort. Das sind Ordnungsrelationen. Denition 3. Eine Menge L von Wrtern uber einem Alphabet also L heit (formale) o Sprache uber . ist immer eine formale Sprache. Operationen zwischen Sprachen Sei ein Alphabet, L1 , L2 Sprachen. Dann bezeichnen wir mit L1 L2 = {w1 w2 |w1 L1 , w2 L2 }. L = {w|w hat die Form w = w1 w2 . . . wn n 0 wi L}, also alle Wrter die o wir bilden knnen. o L = {} L L L L L L . . . Mit Hilfe dieser Operationen und der Vereinigung lassen sich aus einfachen Sprachen kompliziertere konstruieren. L = {0, 1} {0} {0, 1} = {00, 01, 000, 001, 100, 101, . . .} = ({0} {1}) {0} ({0} {1}) = {w {0, 1} |das vorletzte Zeichen ist eine 0} Man kann nicht alle Sprachen durch Konkatenation, Vereinigung und Sternbildung beschreiben. Diejenigen, bei denen es geht, nennt man regulre Ausdrcke. a u Vereinfachte Schreibweise ohne Klammern (soweit eindeutig) und Konkatenationspunkte: (0 1) 0(0 1) Dabei bindet
strker als , das strker bindet als . a a
Denition 4. Sei ein Alphabet, Menge R der regulren Ausdrcke uber wird induktiv a u deniert durch: 1. (leere Ausdruck) und jedes a sind in R 2. Wenn , R , dann auch () R , ( ) R 3. R . R ist die kleinste Menge mit diesen Eigenschaften.
\
CC BY: $
Vorlesung 2
Regulre Ausdrcke bezeichnen Sprachen L() wie folgt: a u L() = L() = {} L(()) = L() L() L(( )) = L() L() L( ) = L() Das ist natrlich rekursiv. u Beispiel 3. Wir suchen den regulren Ausdruck zu a {w {0, 1} |w enthlt 10 nicht als Teilwort a (Man hat eine Folge von Nullen, dann kann irgendwann eine 1 kommen, dann aber darf keine weitere Null kommen.) = L(0 1 ) Es gibt nicht immer nur einen regulren Ausdruck, der eine Sprache beschreibt. a Denition 5 (Regulre Sprache). Eine Sprache L, zu der es einen regulren Ausdruck gibt, mit a a L = L() heit regulre Sprache. a Es gibt auch Sprachen, zu denen es keine regulren Ausdrcke gibt (z.b. die Menge aller Wrter, a u o die aus n a und n b bestehen). Beispiel 4. L = L((0 1) 101(1 0) ))= {w {0, 1} |w enthlt 101 als Teilwort}. Gibt es auch a eine regulre Sprache, die 101 nicht als Teilwort enthlt? Ja, fr das Komplement einer regulren a a u a Sprache gibt es immer auch einen regulren Ausdruck. In diesem Fall ist das a = (0 1 100) 0 1 ( 0) Beweis a) L L(). Sei w L beliebig. Dann hat w die Form w = w1 10 0 w2 10 0 . . . wk 10 0wk+1 u wi enthlt dabei die Zeichenfolge 10 nicht (k=0 zugelassen). u ist entweder 0 oder . Also ist a wi L(0 1 ). Damit ist wi 100 L(0 1 100). Davon haben wir beliebig viele, deswegen noch ein Stern. Der nchste Abschnitt im regulren Ausdruck beschreibt das wk und das u. a a Fr einen formal korrekten Beweis msste man eine Induktion uber k machen. u u b) L() L w L() w hat die Form w = w1 100 . . . wk 100 wk+1 u
L((0 1 100) )
In einem Stck wi 100 kommt 101 nicht als Teilwort vor, da wi 10 nicht als Teilwort hat. u Ebensowenig wk+1 bzw wk+1 0
\
CC BY: $
Endliche Automaten Man kann sich endliche Automaten als einfache Rechner zur Erkennung von Sprachen vorstellen. Modellhaft kann man ein Eingabeband hernehmen, mit Zellen, die je einen Buchstaben eines Alphabets enthalten. Auf dem Band gibt es einen Lesekopf. Das Gehirn des endlichen Automaten ist eine Black-Box, die sog. endliche Kontrolle, die in endlich vielen Zustnden sein kann. a Auf dem Band steht ein Wort. In einem Schritt liest er das Zeichen unter dem Lesekopf ein und in Abhngigkeit vom gelesenen Zeichen und dem derzeitigen Zustand geht er in einen neuen Zustand a und bewegt den Lesekopf eine Zelle weiter. Ein Wort gilt als akzeptiert, wenn der Lesekopf uber der am weitesten rechts stehenden Zelle ist und der Zustand ein Endzustand ist. Denition 6 (endlicher Automat). Ein endlicher Automat ist ein 5-Tupel M = (Q, , , s, F ) Q ist eine endliche Menge von Zustnden a ist das Alphabet :: Q Q ist die Uberfhrungsfunktion u s ist der Startzustand F Q ist die Menge der Endzustnde a Beispiel 5. Wir suchen einen endlichen Automaten fr die Sprache: u L = {w {0, 1} |das vorletzte Symbol ist 0} Man braucht 4 Zustnde. a Q s F q1 q2 q3 q4 = = = = {q1 , q2 , q3 , q4 } q1 {0, 1} {q3 , q4 }
unter den letzten beiden gelesenen Zeichen war keine 0 die letzten zwei Zeichen waren 10 oder 0 (am Anfang des Wortes) die letzten zwei Zeichen waren 01 die letzten zwei Zeichen waren 00
Die Uberfhrungsfunktion denieren wir also wie folgt. u q1 q2 q3 q4 0 q2 q4 q2 q4 1 q1 q3 q1 q3
Denition 7 (Akzeptanz). lsst sich auf Q durch a (q, ) = q q Q (q, aw) = ((q, a), w) w wird von M akzeptiert, wenn (s, w) F L(M ) = {w |M akzeptiert w} ist die von M akzeptierte Sprache.
\
CC BY: $
Zustandsdiagramm Man kann endliche Automaten etwas kompakter durch ein Zustandsdiagramm darstellen. Das ist ein gerichteter Graph, in dem jeder Knoten einem Zustand entspricht. Wenn (q, a) = r ist, existiert eine Kante von q nach r (die mit a beschriftet ist). Mehrfachkanten/Mehrfachbeschriftungen sind dabei mglich. Der Startzustand wird durch einen Pfeil, der o Endzustand durch einen doppelten Rand markiert.
Vorlesung 3
Nicht deterministische endliche Automaten
Nicht-deterministische endliche Automaten unterscheiden sich von den endlichen Automaten darin, dass nach dem Lesen eines Zeichens nicht nur ein Folgezustand in Abhngigkeit der Eingabe erreicht a werden kann, sondern es mehrere Mglichkeiten gibt. o Das heit, fr ein gegebenes Eingabewort gibt es im Allgemeinen eine Auswahl von Mglichkeiten u o von Rechnungen (d.h. Folgen von angenommenen Zustnden beim Lesen des Wortes). Das Wort a gilt als akzeptiert, wenn es eine Rechnung gibt, die in einem Endzustand endet. Beispiel 6. L = {w {0, 1} |das vorletzte Symbol ist 0} (deterministischer Automat siehe oben).
Da wir von q2 keine Ubergnge mehr haben hlt der Automat hier an. Wenn das Wort noch nicht a a ganz gelesen ist, gilt das nicht als akzeptierende Rechnung! Denition 8. Ein nicht deterministischer endlicher Automat ist ein 5-Tupel M = (Q, , , s, F ) Q ist eine endliche Menge von Zustnden a ist das Alphabet :: Q P(Q) ist die Uberfhrungsfunktion. Hier geht sie in die Potenzmenge von Q. u s ist der Startzustand
\
CC BY: $
F Q ist die Menge der Endzustnde a Denition 9 ( fr Wrter). lsst sich durch folgende Denitionen auf Wrter erweitern u o a o (q, ) = {q} q Q (q, ua) =
p(q,u)
(p, a)
Da wir hier mehrere Zustnde beim Lesen eines Buchstabens erreichen knnen, mssen wir die a o u Vereinigung aller mglichen Folgezustnde nehmen. o a w gilt akzeptiert gdw (s, w) F = (es ist ein Endzustand in der Ergebnismenge enthalten). Denition 10. Sei M ein nicht-deterministischer endlicher Automat. Dann heit L(M ) = {w|M akzeptiert w} die von M akzeptierte Sprache Beispiel 7.
L(M ) = {w {a, b} |w enthlth aba als Teilwort} a Bemerkung Jeder deterministische endliche Automat kann auch als nicht deterministischer endlicher Automat aufgefasst werden. Denn falls beim deterministischen endlichen Automaten (q, a) = p kann man das auch als Menge mit einem Element betrachten (q, a) = {p}. Daraus folgt, dass die Klasse, der von deterministischen endlichen Automaten akzeptierbaren Sprachen, in der Klasse der von nicht-deterministischen endlichen Automaten akzeptierbaren Sprachen enthalten ist. Obwohl diese Denition suggeriert, dass nicht-deterministische endliche Automaten mchtiger sind a als deterministische, kann man zu jedem nicht-deterministischen Automaten einen deterministischen konstruieren. Satz Zu jedem nichtdeterministischen endlichen Automaten M gibt es einen quivalenten detera ministischen endlichen Automaten M. (L(M ) = L(M )) Beweis Sei M = (Q, , , s, F ), dann denieren wir den deterministischen Automaten M = (Q , , , {s}, F ), wobei Q = P(Q) (k, a) k P(Q) = k P(Q), a pk (p, a) F = {k Q|k F = }
CC BY: $
Behauptung L(M ) = L(M ). Wir zeigen dazu, dass w : (s, w) = ({s}, w) Daraus folgt mit der Denition von F L(M ) = L(M ). Wir beweisen durch Induktion uber l = |w|. Induktionsanfang l=0 w = . (s, ) = {s} Beides nach Denition Induktionsschritt l=l+1 Sei w , |w| = l + 1. Also w = va mit a , v , |v| = l (s, w) = (s, va) =
p(s,v)
({s}, ) = {s}
(p, a)
Nach I.V. ist =

p (s,v)
(p, a)
Nach Def. = ( ({s}, v), a) = ({s}, va) Beispiel 8. Wir konstuieren den deterministischen endlichen Automaten zum nicht-deterministischen aus dem obigen Beispiel.
Einige der 8 Zustnde kann man nicht vom Startzustand erreichen. Sie werden gar nicht erst a eingezeichnet. n.d. e. Automaten mit -Ubergngen a Wir lass jetzt auch Zustandsbergnge zu ohne, dass ein Zeichen gelesen wurde. u a
CC
BY:
formal : Q ( {}) P(Q) Das knnen wir jetzt wieder auf Wrter erweitern o o (q, ) = E(q) Wobei E(q) die Menge der von q aus durch -Ubergnge erreichbaren Zustnde (auch mehrere a a Schritte nacheinandergehngt). a (q, ua) =
p(q,u)
E((p, a))
q Q, u , a
Ein Wort w heit akzeptiert, wenn (s, w) F = Behauptung Zu jedem nicht-deterministischen endlichen Automaten mit -Ubergngen M, gibt a es einen quivalenten nicht-deterministischen endlichen Automaten (und damit auch einen detera ministischen). Beweisidee Wir entfernen von jedem Zustand q alle -Ubergnge und fhren neue Ubergnge a u a ein (praktisch ein transitiver Abschluss) a neu (q, a) =
pE(q)
E((p, a))
Wenn man vom Zustand q uber der Zustand p erreichen kann und von dem durch Lesen des Zeichens a Zustnde r1,r2, so fgt man Ubergnge von q -> r1,r2 durch Lesen des Zeichens a ein. a u a Beispiel 9.
Welche Menge wird akzeptiert? L({w {0, 1} | dritt- oder vorletzte Zeichen ist 0})
Vorlesung 4
Was konnen endliche Automaten?
Wir kennen bereits die regulren Sprachen. Interessanterweise sind die Sprachen, die man mit a endlichen Automaten beschreiben kann genau die selben, die man auch mit regulren Ausdrcken a u beschreiben kann. Satz Eine Sprache ist von einem endlichen Automaten akzeptierbar gdw sie regulr ist. a
\
CC BY: $
Beweis zz: 1. Jede regulre Sprache wird von einem endlichen Automaten akzeptiert a a) Jede Sprache der Form {a} mit a wird von einem endlichen Automaten erkannt Der Automat hierfr ist leicht u ->s (a->Q) - Q b) Die leere Sprache wird von einem endlichen Automaten akzeptiert Der Automat hierfr hat lediglich den Startzustand, keinen akzeptierenden Zustand. (Es u geht eigentlich jeder ohne akzeptierende Zustnde) a c) wird L von einem endlichen Automaten akzeptiert, dann auch L Zu einem Automaten M, der L akzeptiert, konstruieren wir einen Automaten M, wobei wir zu jeden akzeptierenden Zustand einen Ubergang zum Startzustand hinzufgen. u ) = L+ = {w . . . w |n 1, w L} (so ahnlich wie L , aber das leere Behauptung L(M 1 n i Wort ist nicht unbedingt drin). Beweis Sei w L(M ). Dann gibt es eine akzeptierende Rechung: q0 q1 qi1 qi1 +1 . . . qik qik +1 . . . qm Dabei ist qi1 die erste Stelle an der eine neue Kante auftritt, und qik die letzte. Man kann also ein Zusammengesetztes Wort w in ein w1 . . . wk , wk+1 L, das uns bis qi1 , qi2 , . . . , qik bringt. wk+1 ist dann das Endstck bis qm . So zusammengesetzte u Wrter sind aber alle in L+ o Diese Richtung luft eigentlich genauso. Sei w L+ . Dann lsst sich w zerlegen in a a w = w1 , . . . , wk mit wi L. Dann gibt es eine Rechnung von M, w1 , w2 ... wk s q1 F s q2 F qk1 s qk F Damit gibt es einen e.A., der L+ erkennt. Aussage folgt fr L mit Aussage d), da L = u + {}. (Der Automat, der das leere Wort erkennt besteht nur aus dem Startzustand, L der gleichzeitig akzeptierender Zustand ist). d) werden L1 , L2 akzeptiert, dann auch L1 L2 Sei Mi = (Qi , , i , si , Fi ) endlicher Automat, der Li erkennt, i=1,2. oBdA nehmen wir an, Q1 Q2 = . Wir konstruieren M=(Q, , , s, F ) fr L1 L2 wie folgt: u
CC
BY:
Mit Q = Q1 Q2 {s}, (q, a) = (s, e) = {s1 , s2 } Oensichtlich akzeptiert er die Vereinigung. e) werden L1 , L2 akzeptiert, dann auch L1 L2 M1 , M2 wie bei d). 1 (q, a) 2 (q, a) falls q Q1 falls q Q2
M = (Q1 Q2 , , , s1 , F2 ) (q, a) = 1 (q, a) 2 (q, a) q Q1 q Q2 und (q, ) = s2 q F1
Wenn das gezeigt ist, folgt die Behauptung durch Induktion (vgl Denition regulrer Spraa chen). 2. Zu jedem endlichen Automaten gibt es einen regulren Ausdruck, der die selbe Sprache bea schreibt (d.h. sie ist regulr). a Sei L eine solche Sprache und M = (Q, , , s, F ) deterministisch
Wir wollen aus M einen regulren Ausdruck konstruieren. Sei Q = {q1 , . . . , ql } mit s = q1 . a Wir denieren Lk = {w |(qi , w) = qj Zwischenzustnde haben Index 1 . . . k} a ij . z.b. ist L0 = {a |(qi , a) = qj } {} entweder leer oder enthlt genau ein Element (bzw a ij { a} falls i=j). Lemma Lk ist eine regulre Sprache fr alle 1 i, j l und 0 k l. a u ij Beweis Durch Induktion uber k. I.A k=0 L0 besteht aus einem Wort der Lnge 1 oder ist leer. Damit ist sie regulr a a ij I.S. k 1 k Beh. es ist
k1 k1 Lk = Lij Lik Lkk ij (k1) k1 Lkj (k1) k1 Lkj ,
k1 k1 Falls w Lij dann auch w Lk nach Denition. Falls w Lik Lkk ij dann existiert eine Zerlegung w = w0 w1 . . . wr wr+1
(k1) Lk1 Lkk ik
Lk1 kj
Wir haben also wr+1 w w w qj qi 0 qk 1 qk . . . qk r qk Da die Zwischenzustnde {q1 . . . qk } sind, ist es enthalten. a
\
CC BY: $
10
Fall w Lk , betrachte die Rechung ij qi

w
qj
Die Zwischenstnde sind alle {q1 , . . . , qk }. Wir unterscheiden 2 Flle a a

k1 (a) qk kommt nicht vor (alle Zustnde k 1) w Lij a
(b) qk kommt (eventuell mehrfach) vor. Die Rechnung sieht so aus qi mit
k1 w0 Lik , k1 w1 . . . wr Lkk (k1) k1 wr+1 Lkj k1 also ist w Lij Lik k1 Lkk . Damit sind Lk eine regulre Sprache. a ij w0
qk
w1
qk
...
wr
qk
wr+1
qj
Damit ist auch die Sprache L regulr, denn a L=

qj F
Ll 1j
eine endliche Vereinigung regulrer Sprachen ist wieder eine regulre Sprache. a a Damit ist der Satz bewiesen. Die Formeln L0 = {a|a , (qi , a) = qj } {} falls i=j ij
k1 k1 k1 k1 Lk = Lij Lik (Lkk ) Lkj ij
liefern einen Algorithmus um zu einem endlichen Automaten einen regulren Ausdruck a zu konstruieren (Algorithmus von Kleene). L_ij^0:=...* fr k=1,...,l u fr i=1,...,l u fr j=1,...,l u L_ij^j=...*
Vorlesung 5
Beispiel 10 (Algorithmus von Kleene). Wir konstruieren einen regulren Ausdruck zu den Autoa maten
Wir machen uns eine Tabelle: 1,1 a = a 1,2 b a b (a ba b) 11 2,1 b ba 2,2 a
k=0 1 2
CC
BY:
L1 = 11 = 1 L12 = = 1 L21 = = L1 = 22 = L2 = 11 =
L0 L0 (L0 ) L0 11 11 11 11 ( a) ( a) ( a) = a L0 L0 (L0 ) L0 12 11 11 12 b ( a)( a) b = ab L0 L0 (L0 ) L0 11 11 21 21 b b(a) ( a) = ba L0 L0 (L0 ) L0 22 21 11 12 a b( a) b = a ba b L1 L1 (L1 ) L0 21 22 12 11 a a b( a ba b) ba
einfacher L = a a b(a ba b) ba , ganz einfach L = (a ba b) . Abschlusseigenschaften regulrer Sprachen a Satz Seien L, L1 , L2 regulre Sprachen. Dann sind auch regulr: a a a) L Beweis nach Dention regulrer Ausdrcke (einfach in Klammern setzen und a u b) L1 L2 Beweis nach Detion regulrer Ausdrcke (in Klammern und machen) a u c) \L Beweis Man bildet den deterministischen endlichen Automaten zur Sprache L. Dann tauscht man Endzustnde und nicht-Endzustnde. Der neue Automat erkennt genau das Komplement a a der Sprache. Dann kann man wieder einen regulren Ausdruck dazu bauen. a d) L1 L2 Beweis L1 L2 = \(( \L1) ( \L2 )) nach de Morgan e) L1 L2 Beweis nach Denition regulrer Ausdrcke (in Klammern und machen) a u
machen)
Nicht-regulre Sprachen a
Beweis der Nichtregulritt a a z.B. L = {an bn |n N0 } = {, ab, aabb, . . .} Diese Sprache ist nicht regulr. Angenommen sie wird von einem Automaten erkannt. Er muss sich a die Anzahl der as merken, damit er gleich viele bs erkennt. Das geht nicht mehr wenn es mehr as als Zustnde gibt (es gibt ja nur endlich viele). Es muss also mindestens ein Zustand wiederholt a werden. Dann kann man den Abschnitt zwischen diesem Zustand beliebig oft wiederholen, ohne dass das entstehende Wort aus L rausfllt (das ist fr diese Sprache aber nicht gegeben s.u.). Diese a u Eigenschaft muss fr alle regulren Sprachen erfllt sein. Man nennt sie: u a u Pumping-Lemma Sei L regulr. Dann gibt es ein k N, so dass jedes Wort w L mit a |w| > k sich zerlegen lsst a w = uvx, v=
sodass uv i x L i N Man bemerke, dass fr endliche Sprachen (die alle regulr sind), die Wrter alle nicht hinreichend u a o lang sind, so dass das Pumping-Lemma eine Aussage uber die leere Menge ist (und gilt..).
\
CC BY: $
12
Beweis Sei M = (Q, , , s, F ) ein endlicher deterministischer Automat, der L akzeptiert. Sei k = |Q|. Sei w L mit |w| > k. Wenn wir uns die Rechnung zu diesem Wort ansehen ------------------| | | | | | | ------------------s q q r \in F u v x mindestens ein Zustand q Q muss mehrfach vorkommen. d.h. Zerlegung w = uvx (s, u) = q (q, v) = q (q, x) = r Dann gilt aber auch fr wi = uv i x u (s, wi ) = (((s, u), v i ), x)
=q
aber (q, v i ) = . . . ((q, v), v) . . . , v) = q also ist (s, wi ) = (q, x) = r F und damit auch das Wort wi L fr alle i N. u Behauptung L = {an bn |n N0 } = {, ab, aabb, . . .} ist nicht regulr. Angenommen, L wre a a regulr dann gibt es nach dem Pumping-Lemma ein k N, so dass jedes w L mit |w| > k sich a zerlegen lsst . . . (siehe oben). a Sei also w L mit |w| > k, also w = am bm fr ein m N. Nach dem Pumping Lemma existiert u eine Zerlegung w = uvx mit uv i x L. Es gibt drei Mglichkeiten fr v. o u Es besteht nur aus as (liegt in der ersten Hlfte des Wortes). Wenn wir jetzt pumpen hat a man mehr as als bs. Damit liegt das Wort aber nicht mehr in der Sprache. Es besteht aus as und bs (liegt in der Mitte). Wenn wir jetzt pumpen, dann wechseln a und b mehr als einmal. Dann liegt das Wort nicht mehr in der Sprache Es besteht nur aus bs. Analog zur ersten Mglichkeit liegt das Wort nicht mehr in der Sprache o wenn wir pumpen. Alle drei Mglichkeiten fr v fhren zu Widersprchen. Damit ist L nicht regulr, weil das Pumping o u u u a Lemma nicht erfllt ist. u Beispiel 11 (Klammerstrukturen). Wir denieren die Sprache der richtigen Klammerausdrcke u L = {w |what gleichviele ( wie ) jed. Prx hat ()} a = {(, )}
Behauptung L ist nicht regulr a Beweis angenommen L wre regulr, dann wre auch L(n )n (das heit alle Wrter mit n nenden a a a o o gefolgt von n schlieenden Klammern). Wir haben aber oben gezeigt dass diese Sprache nicht regulr a sein kann. Damit ist auch L nicht regulr. a
\
CC BY: $
13
Vorlesung 6
Beispiel 12. L = {11, 111, 11111, . . .} also {1n |n Primzahl} die sogenannte Unrdarstellung von Primzahlen. Behauptung Diese Sprache ist nicht regulr. a a Beweis Angenommen doch, dann existiert nach dem Pumping-Lemma eine Zahl k>0, so dass man Wrter dieser Lnge aufpumpen kann. Sei w L mit |w| > k o a w = 11 . . . 1 1 . . . 1 . . . 11
u v x
Das kann man nach dem Pumping-Lemma zerlegen in u = 1r v = 1s x = 1t , damit |w| = r + s + t, also eine Primzahl. Nach dem Pumping-Lemma wrde gelten u 1r 1is 1t L fr i=0,1,2. . . u d.h. r + i s + t eine Primzahl fr alle i. Whle i = r + t. Dann ist u a r + i s + t = (s + 1)(r + t)
nicht prim
falls r + t > 1. Wenn r + t = 0, dann ist z.B. fr i=2 Wort L. Wenn r + t = 1, dann whle i=0 u a (1 ist keine Primzahl). Wir sehen, dass bereits einfache Sprachen nicht mit regulren Ausdrcken beschreibar sind. Regula u a re Ausdrcke sind also kein sehr mchtiger Formalismus. Trotzdem haben sie wichtige Anwendungen u a (siehe ganz oben).
Kontextfreie Sprachen
Grammatische Regeln (auch bei natrlichen Sprachen) sind formalisierbar u <Satz>=<Subjekt><Prdikat><Objekt> a <Subjekt>=<Artikel><Substantiv>|<Personalpronomen> <Artikel>=der|die|das|ein|eine (die Notation wurde in ALP I eingefhrt, BNF, EBNF etc.). Regelsysteme ( Grammatiken) beu schreiben die Syntax von natrlichen oder Programmiersprachen. u Denition 11 (Kontextfreie Grammatik). ist ein 4-Tupel G = (V, T, P, S) V eindliche Menge, Elemente heien Nichtterminale T endliche Menge, Elemente heien Zeichen (Variablen) S V ist das Startsymbol (Axiom) P V (T V ) heien Produktionen. (A, ) P mit a V, (T V ) schreibt man auch A Beispiel 13 (Arithmetische Ausdrcke). V = {A}, T = {id, +, , , /, (, )} S = A P = {A u id, A A + A, A A A, . . .} (abkrzend A id|A + A| . . .). u
\
CC BY: $
14
Wir deneren eine Relation auf (V T ) , mit der Bedeutung: heit in der Zeichenreihe ein Nichtterminalzeichen A durch ein Wort ersetzen. Formal a gdw (V T ) mit a = A und = wobei A P . Wir denieren eine weitere Relation . Das ist der reexive, transitive Abschluss der Relation . Das heit a = 0 . . . n = Denition 12. G=(V,T,P,S). Ein (V T ) mit S heit Satzform der Grammatik G. L(G) = {w T |S w} heit die von G erzeugte Sprache. Am Beispiel oben uber arithmetische Ausdrcke erklrt u a A A A A (A) A (A + A) A (A + id) A (id + id) id (id + id) id (id + id) lsst sich also ableiten und ist damit L(G). a Beispiel 14. Denition 13. Eine Sprache L heit kontextfrei, gdw es eine kontexfreie Grammitk G mit L=L(G) gibt. Beispiel 15. {an bn |n N} ist kontextfrei. Beweis S aSb| Produktion Startsymbol S, T = {a, b}, v = {S} L(G)=L Sei w L(G) d.h. es gibt eine Ableitung S 1 . . . n = w Jede Satzform i hat nur ein Vorkommen von S. Dies wird beim Ubergang von i nach i+1 durch aSb ersetzt (bzw. , falls i=n). Es werden also links genausoviele as wie rechts bs erzeugt. Ein formal korrekter Beweis geht mit Induktion. Sei w L. Dann erzeugt die Ableitung S aSb aaSbb . . . an Sbn an bn = w Oensichtlich kann man mit kontexfreien Grammatiken Sprachen erzeugen, die nicht regulr sind. a Beispiel 16. Dycksprache uber einem Klammertyp. G=(V,T,P,S). T = {(, )} V = {S} P : S (S)|SS|
\
CC BY: $
15
Vorlesung 7
Beispiel 17. L = {w {a, b} |w hat gleichvie as wie bs}. Ist L kontextfrei? Ja, denn die Grammatik, die sie beschreibt ist G = (V, T, P, S) V = {S, A, B} T = {a, b} Die ist Idee ist 1. A w gdw w hat ein a mehr als bs. 2. B w gdw w hat ein b mehr als as. 3. S w gdw w hat gleichviele as wie bs Also schreiben wir S | aB | bA A aS | bAA B bS | aBB Bsp abaababbba S aB abS abaB abaaBB abaabSB abaabaBB abaababSB abaababB . . . Man muss an sich beweisen, dass 1,2 und 3 gelten (durch Induktion uber n = |w|). n=0 dann ist w = , die einzige Mglichkeit das herzuleiten ist S . w ist also herleitbar und o hat gleichviele as wie bs. n n + 1 Sei w T mit |w| = n + 1. Es gibt verschiedene Flle: a Fall 1 w beginnt mit a, also w = av. Es gilt S w gdw S aB w = av. d.h. B v, da die Lnge von |v|=n. Man kann also die Induktionsvoraussetzung anwenden. Da Wrter, a o die aus B hergeleitet sind ein b mehr als as hat (eigentlich noch zu zeigen), ist w = av in L. Fall 2 w beginnt mit b. Luft analog zu Fall 1 a Wenn man die Ableitung so wie im Beispiel hinschreibt, ist das ein bischen mhselig. Es gibt aber u eine (coolere?) Art das zu machen, nmlich mit einem sog Ableitungsbaum. Dabei ist die Wurzel das a Startsymbol. Ein Knoten mit seinen Kindern entspricht einer Produktion, die angewendet wurde. Die Bltter des Baumes enthalten das abgeleitete Wort. a Ein Wort aus dem Beispiel von oben wird also z.B. so dargestellt: S a/ \B b/ \S a/ \B a/ B \B -Reihenfolge? b/ S b \S e/ b/ \A a/ \S e
\
CC BY: $
16
Aus dem Ableitungsbaum ist im Allgemeinen die Ableitung nicht eindeutig rekonstruierbar, da die Reihenfolge in der man die Produktionen anwendet nicht festgelegt ist. Wenn man sich auf die Reihenfolge (z.B. von links) einigt, erhlt man eine eindeutige sog. Linksableitung. a Denition 14. Eine kontextfreie Grammatik G heit eindeutig, gdw es zu jedem Wort w L(G) genau eine Linksableitung gibt. Eine kontextfreie Sprache L heit eindeutig, wenn es dazu eine eine eindeutige kontextfreie Grammatik gibt, die sie erzeugt. Die Sprache aus Beispiel 15 ist eindeutig, denn jede hergeleitete Folge hat nur ein Vorkommen von S, wenn man irgendwann die 2. Produktion anwendet, verliert man gleich alle Nichtterminalzeichen und ist am Ende der Ableitung angekommen. Hingegen ist die Grammatik fr die Dycksprache aus Beispiel 16 mehrdeutig. Zum Beispiel kann u man das Wort ()()() erzeugen als (e) (e) (e) S S S S S S \S/ / S (e) (e) (e) S S S S S S \ \S/ S/
Aus die Grammatik aus Beispiel 17 ist auch nicht eindeutig, da wir bei A bAA ja das Restwort in zwei Wrter mit einem A zu viel zerlegt, diese Zerlegung aber nicht unbedingt eindeutig sein o muss. Die Grammatik fr arithmetische Ausdrcke ist auch nicht eindeutig. Wenn man sich zum Beispiel u u den Ausdruck id + id + id ankuckt kann man den herleiten aus id + id + id A | A | A \ A / | A \___A / id + id + id A A A A A
Das ist natrlich nicht sehr wnschenswert, wenn man Programmiersprachen schreibt. Insbesondere u u wenn man - nimmt 5 - 3 - 2 A | A | A \ A / | A \___A / =0 5 A - 3 A A =4 - 2 A A
Wir wollen also den linken Baum haben. - ist linksassoziativ. Das und anderes (z.b. Bindungsstrke a von Operatoren) sollte dann ja auch in der Grammatik zum Ausdruck kommen. Das macht die Grammatik natrlich komplizierter u E T | E+T | ET T F | T F lll F (E) | id Mit dieser Grammatik sieht ein Ausdruck mit -, bzw * so aus: id F T E \ - id - id | F | F | T | T | / | / E / | / \ E / id F T E + id * id | F | F | T | / | \T/ \| / E
\
CC BY: $
17
Die Grammatik ist eindeutig, da man z.b. bei * mit dem * Anfangen muss, da man den Operator sonst nicht loswird und nie auf ein E kommt. Ein formaler Beweis wre aber ziemlich aufwndig. a a Naturliche Sprachen Natrliche Sprachen sind meistens nicht eindeutig. Sprachen, zu denen keine eindeutige Grammatik u existiert nennt man inherent mehrdeutig. Beispiel 18. die maurer aen ihre brote und bauten Sie wird morgen auf der Bank sein und ihr Geld abheben (sein und ihr). time ies like an arrow (time kann verb sein, time iesals subjekt)
Vergleich regulre kontextfreie Sprachen a

Satz Die regulren Sprachen bilden eine echte Teilmenge der kontextfreien Sprachen. Jede regua lre Sprache ist sogar eindeutig kontextfrei. a Beweis Dass es nicht regulre kontextfreie Sprachen gibt, haben wir oben schon mehrfach gezeigt. a Sei L eine beliebige regulre Sprache und M ein deterministischer endlicher Automat, der diese a Sprache akzeptiert. Wir konstruieren eine kontextfreie Grammatik fr L : G = (V, , P, S). Als u Nichtterminalzeichen nehmen wir die Zustnde des endlichen Automaten V = Q. Fr S nehmen a u wir den Startzustand des Automaten. Produktionen whlen wir a q1 aq2 und ausserdem q f r alle q F Dann gilt: M akzeptiert w genau dann w von G erzeugt wird. Denn es gibt eine Rechnung w = a1 a2 . . . an an
q0 q1 qn1 qn F
gdw
(q1 , a) = q2
Daraus knnen wir direkt eine Herleitung erzeugen o S a1 q1 a1 a2 q2 . . . a1 a2 . . . an qn a1 a2 . . . an = w
Vorlesung 8
Die kontextfreien Sprachen enthalten die eindeutigen Kontextsprachen, die die regulren Sprachen a enthalten. Eine inherent mehrdeutige Sprache ist zum Beispiel L = {an bn cm |n, m N} {am bn cn |n, m N} Der Beweis, dass eine Sprache nicht eindeutig ist, ist meistens schwer. Spter werden wir sehen, a dass es auch Sprachen gibt, die auerhalb der kontextfreien Sprachen liegen.
Normalformen von kontextfreien Grammatiken

Wir haben gezeigt, dass alle regulren Sprachen sich durch die Produktionen a Aa A bC
erzeugen lassen. Das ist ein einfaches Beispiel fr Normalformen, also eine Einschrnkung der u a mglichen Produktionen. o
\
CC BY: $
18
Entfernung von -Produktionen Eine -Produktion ist ein Produktion der Form A mit A V
Es gilt folgendes Lemma Lemma Sei G eine kontexfreie Grammatik, dann existiert eine quivalente kontextfreie Grama matik G, die die gleiche Sprache erzeugt, aber keine -Produktionen hat. L(G ) = L(G)\{} Das leere Wort lsst sich natrlich nicht ohne eine -Produktion erzeugen. a u Wir denieren ein annulliebares Nichtterminalzeichen: A V mit A Auf diese Zeichen mssen wir achten, wenn wir eine Grammatik ohne -Produktionen erzeugen u wollen. Dazu mssen wir die erstmal bestimmen. Das geht in einer Schleife aus zwei Schritten u 1. Falls A P , dann erklre A als annullierbar. a P und alle Ai annullierbar sind, dann erklre auch B als annullierbar. a
2. Falls B A1 . . . Ak 3. Gehe zu Schritt 1
Wir durchlaufen die Menge der Produktionen so lange, bis sich nichts mehr ndert. Dann haben a wir alle annullierbaren Produktionen gefunden. Beispiel 19. Produktion A a||B B A|b|CC C AB S BAC Annullierbar? X X X X
Die Produktionen sind alle annulierbar, z.B. S BAC AAC AAAB . . . Beweis Sei G=(V,T,P,S). Falls A X1 . . . Xn P
fhre alle Produktionen der Form u A 1 2 . . . n in P ein mit einer der folgenden Eigenschaften 1. i = Xi fr nicht annullierbare Xi u 2. fr annullierbare Xi : i = Xi u 3. nicht alle i sind 4. entferne alle Produktionen
\
CC BY: $
i =
19
Beispiel 20. S aB|bA| A aS|bAA B bS|aBB (Die Menge aller Wrter mit gleich vielen o as und bs). Wir kucken zuerst welche Nichtterminalzeichen annullierbar sind. Nur aus S kann man herleiten. Nur S ist annulliebar. Mit der obigen Regeln knnen wir die umformen zu o S aB|bA A aS|a|BAA B bS|b|aBB Behauptung fr die so konstruierte Grammatik G gilt u L(G ) = L(G)\ Wir zeigen das in zwei Schritten 1. A P dann kann man auch A Wenn ist A 1 . . . n mit
=
A X1 . . . Xn P und aus dem Xi i nmlich Xi = i oder i = und Xi ist annullierbar. Da man aus a jedem Xi i herleiten kann, kann man auch aus A herleiten. Damit gilt, dass die von G erzeugte Sprache in der von G erzeugten Sprache enthalten ist L(G ) L(G) Denn jeder Schritt in einer Ableitung bezglich G lsst sich durch eine Folge von Schritten u a in G simulieren. 2. A = X1 . . . Xn = mit Xi V T dann kann man auch i mit den Eigenschaften 1, 2, 3 (von oben) gilt auchA 1 . . . n . Zum Beweis machen wir eine Induktion uber die Lnge a k der Ableitung machen. I.A k=0. Dann ist = A (in Null schritten herleitbar). Natrlich lsst sich mit den Ersetu a zungen aus 1,2,3 auch A A I.S. k k + 1 Sei A 1 . . . k+1 = = X1 . . . Xn eine Ableitung in G der Lnge k+1. Damit muss sein a 1 = Y1 , . . . Yr und Y1 1 ,

A 1 P
Y2 2
Yr r
so dass, wenn man die wieder zusammensetzt 1 2 . . . r = Es gibt zwei Mglichkeiten o 1 Falls i = . Dann gilt nach Induktionsvoraussetzung: Yi i in G
\
CC BY: $
20
2 Falls i = . Dann ist Yi annulierbar und mit A Y1 . . . Yr existiert auch eine Produtkion in P, wo Yi durch ersetzt ist. Wir wenden die an allen Stellen i an, wo i = und lassen das entsprechende Yi weg. Wir verwenden als erste Produktion also Y1 . . . Yr wo allerdings die entsprechenden Yi fehlen. Nach Induktionsvoraussetzung lsst sich a dann in der Grammatik G erzeugen. Aus 2 folgt, dass falls alle Xi T , so ist immer Xi = i , also L(G) L(G )\{} Da wir Hin- und Rckrichtung gezeigt haben, gilt die Behauptung. u Entfernen von Einzelproduktionen Eine Einzelproduktion ist eine von der Form A B mit A, B V Satz Jede kontextfreie Sprache ohne kann von einer kontextfreien Grammatik ohne - oder Einzelproduktionen erzeugt werden. Beweisidee Sei G eine kontexfreie Grammatik fr ide Sprache L. Zuerst entfernen wir die u Produktionen wie oben beschrieben. Die Einzelproduktionen: fr alle A V bestimme alle B V u mit A B (das muss natrlich eine Folge von Einzelproduktionen sein, da keine Nichtterminale dau zukommen und es keine -Produktionen mehr gibt) (Grammatik als gerichteten Graphen darstellen und mit BFS/DFS durchsuchen). Wenn immer dies der Fall ist: Nimm in P alle Produktionen der Form A auf, wo B eine Produktion in G, aber keine Einzelproduktion ist. Wir entfernen alle Einzelproduktionen. Der Bweis, dass L(G ) = L(G)\{} ist eigentlich analog zu dem Beweis mit den -Prodktionen. Chomsky Normalforn (CNF) Satz Jede kontetfreie Sprache L ohne kann durch eine kontextfreie Grammatik G=(V,T,P,S) erzeugt werden, deren Prodktionen von der Form A BC mit A, B, C V A a mit A V, a T sind. Beweis Sei G0 irgendeine kontextfreie Grammatik fr L. u 1. Wir entfernen die - und Einzelproduktionen. Wie beschrieben. G1 2. Damit Terminalzeichen nur noch in der Form Aa
\
CC BY: $
21
auftauchen, fhren wir fr jedes Terminalzeichen x ein zustzliches Nichtterminalzeichen X u u a mit der Produktion X x ein (und ersetzen alle x durch X). G2 mit Produktionen der Form A B1 . . . Bn n2 oder Aa
Mit A, B1 , . . . , Bn V, a T . 3. Schritt zwei hat noch eine beliebige Anzahl von Produktionen, das reduzieren wir jetzt auf 2. Fr jede Produktion der Form u A B1 . . . Bn fhren wir n-2 neue Produktionen ein, u A B1 C1 C1 B2 C2 C2 . . . Die neue Grammatik nennen wir G3 , sie ist in Chomsky-Normalform. All diese Umformungen erzeugen quivalente Grammatiken. Etwa G2 G3 . Wenn wir z.b. einen Ableitung in G2 a haben und es wird irgendein Schritt durchgefhrt, der eine Produktion u A B1 . . . Bn Dazu nden wir in G3 eine Ableitung A B1 C1 B1 B2 C2 . . . Beispiel 21 (Grammatik fr arithmetische Ausdrcke). E E + T |T T T F |F F id|(E). u u 1. Entfernen der Einzelproduktionen: ET F wir fhren zustzliche Produktionen ein (man kann von T F erreichen, muss also F wegmachen u a und durch das ersetzen durch was man F ersetzen kann.) E id|(E) T id|(E) E T F 2. Ersetze alle Terminalzeichen durch Nichtterminalzeichen. Wir fhren ein u C C( ( C+ + C) )
\
CC BY: $
neues Nt-Zeichen
22
3. Setze aus allen Produktionen neue Grammatik zusammen E id|C( EC) |T C F |EC+ T T id|C( EC) |T ( F F id|C( EC) C C( ( C+ + C) ) 4. Ersetze alle Produktionen so, dass nur noch zwei Nichtterminalzeichen drin vorkommen. Wird durch einfhren neuer Nichtterminale gemacht. Etwa so: u E EA1 T T A2 F C( A3 A1 C+ T A2 C F A3 EC)
Vorlesung 9
Pumping-Lemma fur kontextfreie Sprachen
Satz Sei L eine kontextfreie Sprache, dann existiert eine natrliche Zahl n, so dass fr alle Worte u u z L, die lnger sind als n, gilt: Es existiert eine Zerlegung in 5 Teilworte a z = uvwxy mit folgenden Eigenschaften a) |vx| 1 (mindestens eines ist nicht das leere Wort b) |vwx| n c) uv i wxi y ist aus L, fr alle i N0 u Beweis Sei G eine kontextfreie Grammatik ohne - und Einzelproduktionen fr die Sprache L\{}. u k sei die Lnge der lngsten rechten Seite einer Produktion. Wir betrachten die Hhe eines Ableia a o tungsbaums. Ein Ableitungsbaum der Hhe h hat hchstens k h1 Bltter (die lngste Ableitung ist ja k lang, o o a a man kann ihn also hchstens ver-k-fachen). o Sei h die Anzahl der Nichtterminalzeichen von G plus 1. Sei n = k h1 . Sei z L ein Wort der Lnge n. Wir bertrachten den Ableitungsbaum von z. Er muss die Hhe h haben, weil er a o |z| n = k k1 Bltter hat. Es gibt im Ableitungsbaum von z einen Weg der Lnge h, der vom a a Startzustand zu einem Nichtterminalzeichen fhrt. Der Weg ist aber Lnger als die Anzahl der u a Nichtterminalzeichen, eine Nichtterminalzeichen A muss also mehrfach vorkommen.
\
CC BY: $
23
Wir betrachten die beiden letzten Auftreten von A (Knoten A und A). Die beiden A beschreiben jeweils Teilbume. Links des Teilbaums von A stehen Nichtterminalzeichen in den Blttern, die a a wir zu einem Wort u zusammenfassen. Zwischen dem Teilbaum vom A und dem Teilbaum von A stehende Terminalzeichen fassen wir zu v zusammen. Terminale aus A zu w. Dann analog x und y. Es ist |vx| 1, denn wir haben keine oder Einzelproduktionen in unserer Grammatik. Deswegen mssen aus A noch andere Zeichen erzeugt werden als nur A. Damit ist die Eigenschaft a des u Satzes gezeigt. Desweiteren ist |vwx| n, denn die Hhe des Baumes von A h, weil alle Nichtterminalzeichen o verschieden sind. Es lasst sich jedes uv i wxi y erzeugen, denn z.B. uv 2 wx2 y durch ersetzen des Baumes von A durch den Baum von A
Induktiv schlieen wir auf n.
Nicht-Kontextfreie Sprachen
Man kann das Pumping-Lemma benutzen, um zu zeigen, dass manche Sprachen nicht-kontextfrei sind. Zum Beispiel ist diese Sprache L = {an bn cn |n N} nicht kontextfrei.
\
CC BY: $
24
Beweis Angenommen doch, dann msste das Pumping-Lemma fr kontextfreie Sprachen gelten. u u Wir betrachet ein hinreichend langes Wort z in L. Man msste es wie oben beschrieben zerlegen u knnen in o z = uvwxy so dass uv i wxi y L. Das Pumpen geht hier aber schief. Es sind mehrere Flle mglich a o
Fall 1 Pumpen erzeugt mehr as bs und cs. nicht in L Fall 2 Reihenfolge von as und bs durcheinander Fall 3 mehr bs als cs Es gibt noch zahllose weitere Flle, aber w ist nie in L. Man kann aber auch cooler argumentieren: a Falls in v oder x nicht immer das gleiche Zeichhtritt, z.b. v=aaaabbb), dann folgt daraus, dass pumpen die Reihenfolge durcheinander bringt. Falls in v und x jeweils immer das gleiche Zeichen auftritt, werden zwei der drei Zeichen vervielfltigt, das dritte jedoch nicht. Sie haben also nicht a mehr die selbe Anzahl. Man muss beachten, dass man fr allealle Flle Widepsprche nden muss, sonst hat man nicht u a u erfolgreich gezeigt, dass sie nicht kontextfrei ist.
Abschlusseigenschaften Kontextfreier Sprachen

abgeschlossen uber Vereinigung L1 , L2 kontextfrei L1 L2 kontextfrei Sei Gi = (Vi , Ti , Pi , Si ) eine kontextfreie Grammatik fr Li . oBdA V1 V2 = . Eine kontextu freie Grammatik Fr L ist dann folgende Grammatik u G = (V1 V2 {s}, T, P1 P2 {s S1 , s S2 }, s) Das ist also ganz hnlich wie bei den regulren Sprachen, wo wir die Automaten vereinigt a a haben und einen neuen Startzustand eingefhrt. Hier fhren wir ein neues Startsymbol ein u u und machen im Prinzip das Selbe. abgeschlossen uber Konkatenation L1 , L2 ktf L1 L2 ktf
Die Grammatiken seien wie vorher. Wir fgen eine zustzliche Produktion dazu. u a G = (V1 V2 {s}, T, P1 P2 {s S1 S2 }, s) Wenn wir vom Startsymbol S1 S2 herleiten, sind das oensichtlich die Konkatenationen von Wrtern aus L1 und L2 o abgeschlossen uber -Bildung L ktf L ktf
Wenn G = (V, T, P, S) eine kontextfreie Grammatik fr L ist, dann ist u G = (V {s }, T, P {s s s |}, s ) Wir knnen unser Startsymbol also beliebig vervielfachen, so dass die Sternbildung funktioo niert
\
CC BY: $
25
nicht abgeschlossen uber Die Kontextfreien Sprachen sind unter Durschnitt nicht abgeschlos sen. Beweis durch Beispiel L1 = {an bn cm |n, m N} L2 = {am bn cn |n, m N}
sind beide kontextfrei. Eine Grammatik fr L1 wre zum Beispiel: u a S AC A aAb| C cC|
L2 geht analog. Wenn wir aber den Durchschnitt bilden erhalten wir L1 L2 = {an bn cn } Fr die haben wir oben gezeigt, dass sie nicht kontextfrei ist. u nicht abgeschlossen uber Komplementierung Wenn die Kontextfreien Sprachen unter Kom plementierung abgeschlossen wren, knnte man nach de-Morgan den Durchschnitt durch a o Komplement und Vereinigung darstellen, das kann also nicht sein (Durchschnitt geht ja nicht).
Vorlesung 10
Das Analyseproblem kontextfreier Sprachen
Wir suchen einen Algorithmus, der zu einer gegebenen kontextfreien Grammatik G=(V,T,P,S) entscheidet, ob ein Wort w T in L(G) ist (Wortproblem) und ggf einen Ableitungsbaum bzw eine Linksableitung liefert (Analyseproblem). Dieses Problem ist sehr interessant fr die Informatik, da bei durch kontextfreie Grammatiken u denierten Programmiersprachen der Compiler die Struktur eines Programmes untersuchen und feststellen muss, ob das Programm korrekt ist. Dieser Teil des Compilers heit Parser (gleiches gilt natrlich fr die Ubersetzung natrlicher Sprache). u u u Fr manche Sprachen ist das Analyseproblem leicht zu lsen. z.B. u o L = {w {a, b} |w hat gleichviele as und bs} Oensichtlich ist das Wortproblem durch einen einfachen Algorithmus zu lsen, indem man einfach o die Anzahl der as und bs vergleicht. Der Algorithmus hat eine Komplexitt von O(n). a Man kann fr alle regulren Sprachen das Wortproblem in O(n) lsen, da man sich einen determiu a o nistischen endlichen Automaten bauen kann und damit das Wort einmal durchluft. a Fr kontextfreie Sprachen ist das im Allgemeinen nicht so einfach. Es ist noch ein oenes Problem u in welcher Laufzeit man das allgemeine Problem fr kontextfreie Sprachen lsen kann. u o Algorithmus von Cocke-Kasami-Younger Dieser Algorithmus lst das Analyseproblem fr kontextfreie Sprachen allgemein. Wir nehmen an, o u die kontextfreie Grammatik liegt in Chomsky-Normalform vor (ggf kann man sie umwandeln). Gegeben sei ein Wort w = a1 . . . an , ai T, i N
Der Algorithmus legt eine Tabelle an

\
CC BY: $
26
a1
an
Die Zelle (i,j) dieser Tabelle enthlt alle Nichtterminale A aus denen das Teilwort ai , ai+i , . . . , ai+j1 a ableitbar ist. A ai , . . . , ai+j1 Fr j=1 falls A ai eine Produktion ist. Fr j 2 u u A BC ai . . . ai+k1 ai+k . . . ai+j1 es muss gelten: es gibt B, C V, k N und B ai . . . ai+x1 sowie C ai+x . . . ai+j1 . d.h. B muss in Zelle (i,k), C in Zelle (i+k,j-1). Wir haben also folgenden Algorithmus in zelle (i,1) platziere alle A aus V mit A->a_i ist Produktion fr j=2..n u fr i=1..n-j+1 u fr k=1..j-1 u fr alle B in Zelle (i,k) u fr alle C in Zelle (i+k,j-k) u schreibe in Zelle (i,j) alle Zeichen A mit A->BC ist Produktion w ist in L, falls Startsymbol in Zelle (1,n) Um z.b. die Zelle (3,3) zu fllen, kucken wir uns alle(?) Kombinationen der Nichtterminalzeichen u die Zellen (2,3) und (1,5) an (aber wohl in der Reihenfolge, zuerst eins aus (2,3), dann aus (1,5)). Wenn es eine Produktion gibt, schreiben wir die Nichtterminalzeichen in Zelle (3,3) rein. Beispiel 22. kfG fr arithmetische Ausdrcke u u E E + E|E E|(E)|id Die mssen wir dann in Chomsky Normalform umwandeln u E EG|EH|C( I|id G C+ E H C E I EC) Sei w = id + id id. Wir brauchen eine 5x5 Tabelle. 5 4 3 2 1 E,E E E 1 id G G C+ 2 +

??? vielleicht au
E E 3 id
H C 4 *
E 5 id
\
CC BY: $
27
Um (3,1) zu nden mssen wir uns sowohl (2,1)/(1,3) als auch (1,1)/(2,1) ankucken (immer die u ganze Spalte runter und die ganze Diagonale hoch!). Die Nichtterminalzeichen in einer beliebigen Zelle (i,j) knnen das Teilwort rechts von ihnen herleiten (Position i Lnge j). o a Das Wort ist aus E herleitbar, da E in Zelle (1,n) Um ein Problem zu lsen, lsen wir zuerst die kleineren Teilprobleme und bauen aus diesen Lsuno o o gen die fr grere Teilprobleme. Dieses Voregehen nennt man dynamisches Programmieren. Die u o Laufzeit des Algorithmus in Abhngigkeit von der Lnge des n des Eingabewortes ist O(n3 ). a a 3 ) geht die Matrizenmultiplikation. Will man 2 n n Matrizen Auch in O(n A = (aij )ii,jn dann C = A B
n
B = (bij )1i,jn
cij =
k=1
aik bkj
Der Younger Algorithmus kann auf Matrizenmultiplikation zurckgefhrt werden. Dafr gibt es u u u 2.375 ). schnellere Verfahren, der coolste Algorithmus liegt bei O(n O(n3 ) ist in der Praxis nicht zu gebrauchen, da reale Programme ja teilweise ewig lang sein knnen o und man nicht so ewig warten kann bis der Parser fertig ist. Deswegen betrachtet man eingeschrnka te kontexfreie Grammatiken benutzt, fr die das Analyseproblem einfacher (O(n)) lsbar ist. Diese u o Grammatiken heien LR(k)-Grammatiken
Push-Down Automaten (Kellerautomaten)

Ahnlich wie die endlichen Automaten, die die regulren Sprachen beschrieben haben, gibt es auch a tollere Automaten, die kontextfreie Grammatiken beschreiben.
Kellerautomaten sind im allgemeinen nicht deterministisch (man kann sie nicht durch deterministische ersetzen). Am Anfang steht der Lesekopf auf der 1. Zelle, die endliche Kontrolle im Startzustand und der Stack enthlt das Startsymbol Z0 . a Abhngig vom gelesenen Zeichen auf dem Band, vom Zustand der endlichen Kontrolle und vom a obersten Stackzeichen wird ein neuer Zustand angenommen und das oberste Stackzeichen gelscht o oder ein neues draufgelegt. Der Kopf bewegt sich um eine Position nach rechts.
\
CC BY: $
28
Denition 15. Ein Kellerautomat ist ein System M = (Q, , , , q0 , Z0 ) Q endl Menge von Zustnden der endl. Kontrolle a Eingabealphabet Kelleralphabet Q ( {}) 2Q q0 Q Startzustand Z0 Startsymbol (liegt iA aufm Stack) (q, a, Z) = {(qi , 1 ) . . . (qk , k )} heit: im Zustand q, gelesen Zeichen a, oberstes Kellersymbol Z, kann der PDA in den Zustnd q1 a gehen und Z durch die Folge 1 ersetzen (gelesen von links nach rechts von oben nach unten auf dem Stack) oder . . . qk , k . ggf gehen das auch ohne ein Zeichen zu lesen ( Ubergang).
Vorlesung 11
Denition 16. Sei M = (q, , , , q0 , Z0 ) PDA. Eine Konguration von M ist ein Tripel (q, w, ) mit q Q, w , . Gemeint ist folgende Situation: Der Automat bendet sich im Zustand q, hat noch das Restwort w zu lesen und im Keller steht das Wort . Eine Konguration ist quasi eine Momentaufnahme eines Kellerautomatens, whrend er rechnet. a Auf Kongurationen wird eine Relation deniert k1
M k2 M,
die Folgekonguration von k1 . Bedeutung
PDA kann durch einen Schritt (eine Anwendung von ) von k1 nach k2 gelangen Formal es gilt (q, aw, A)
M (p, w, )
fr alle q Q, a , w ,A , ,p Q, ; wobei (p, ) (q, a, A). Falls das auch u mit einem -Ubergang geht, sieht es so aus: (q, w, A)
M (p, w, a) M
Wir denieren als die reexive und transitive Hlle von u M k k k = k0 M

M k1 . . .
d.h.
M kn
= k
n0
Die von einem Kellerautomaten akzeptierte Sprache L(M)

Das ist L(M ) = {w |(q0 , w, Z0 ) (q, , ) f. irgendein q Q} M Das nennt man akzeptierend mit leerem Keller. Alternativ kann man quivalente Automaten dea nieren, die mit Endzustnden arbeiten. a
\
CC BY: $
29
Beispiel 23. Kellerautomat fr L = {w {a, b} |w ist Palindrom 2| |w|}. Die Sprache der u Palindrome mit gerader Lnge. a Wir programmieren unseren Kellerautomaten so, dass er die erste Hlfte des Wortes auf den a Stack liest und dann mit der zweiten Hlfte des Wortes vergleicht. Da er nicht deterministisch ist, a brauchen wir uns keine Gedanken darber zu machen wie wir die Mitte nden, sondern Vertrauen u darauf, dass der Automat das schon macht. Wir schreiben also den Automaten hin: M = (Q, , , , q0 , Z0 ) Q = {q0 , q1 } = {a, b} = {A, B, Z0 } (q0 , a, Z) (q0 , a, Z) (q0 , x, X) (q1 , a, A) (q1 , b, B) (q1 , , Z0 ) = = = = = = {(q0 , A Z)} A auf den Stack packen (Z=A o. B o. Z0) {(q0 , B Z)} B auf den Stack packen (Z=A o. B o. Z0) {(q1 , X)} aufhren mit Speichern o {(q1 , )} wenn a und A, dann A runter {(q1 , )} {(q1 , )}
Solange wir uns im Zustand q0 benden speichern wir die Zeichen auf den Stack. Irgendwann wechseln wir in den Zustand q1 und fangen an die Zeichen zu vergleichen. Beispiel 24. L = {an bn |n N}. Wir packen fr jedes a ein a auf den Stack und nehmen fr jedes u u b eins runter. Am Ende entfernen wir noch Z0 . (q0 , a, Z0 ) (q0 , a, a) (q0 , b, a) (q1 , b, a) (q1 , , Z0 ) = = = = = (q0 , aZ0 ) (q0 , aa) (q1 , ) (q1 , ) (q1 , )
Das ist eigentlich ein deterministischer Kellerautomat, weil pro Schritt je nur eine Folgekongu ration mglich ist. o Satz Eine Sprache L ist von einem Kellerautomaten erkennbar, gdw sie kontextfrei ist. Beweis fur eine Richtung kontextfrei Kelleautomat. Sei L eine kontexfreie Sprache. Es sei G = (V, T, P, S) eine kontextfreie Grammatik mit L = L(G). Wir konstruieren einen Kellerautomaten M = ({q}, T, V T, , q, S) mit (q, , A) = {(q, 1 ), . . . , (q, n )} A V
wobei A i die Produktionen mit A auf der linken Seite sind. Wir wenden also auf dem Keller eine Produktion an (wegen des Nichtdeterminismus treen wir auch immer die Richtige). (q, a, a) = {(q, )} a T
Wenn wir ein Terminalzeichen haben (nachdem wir die richtigen Produktionen angewandt haben), uberprfen wir nur ob es mit dem Wort ubereinstimmt (und holen es dadurch vom Stack runter). u
\
CC BY: $
30
Hilfsbehauptung L(G)=L(M) Beweis fr zeigen fr alle Zeichenketten (V T ) und u u gilt: innerhalb der Grammatik kann man wT w (q, w, ) M
(q, , )
akzeptierend
Sei = 0 1 . . . ak = w eine Linksableitung von w aus . Wir machen eine Induktion uber k. I.A. k=0, dann ist natrlich = w (in Null Schritten herleitbar). Dann ist auch (q, w, w) u M (q, , , denn auf dem Stack stehen nur noch Terminalzeichen, die alle gleich den Buchstaben des Wortes sind. Wir knnen sie also vom Stack runternehmen und enden mit o einem leeren Stack. I.S. k 1 k. Wir kucken uns den ersten Schritt der Linksableitung an 0 = = uA Dann ist also a1 = u mit A P u T , A V, (V T )
und es ist w = uv mit v
in k-1 Schritten
fr die restlichen Schritte gilt die I.V. u (q, w, ) = (q, uv, uA) (q, v, A) M
M (q, v, , )
(q, , ) M
I.V.
Wir nehmen an (q, w, ) (q, , ) in j Schritten. Wir zeigen das durch Induktion uber j. M I.A. j=0. Wenn das in 0 Schritten gehen soll, dann ist w = und = . d.h. I.S. j 1 j. Wir betrachten den ersten Schritt in der Rechnung. Wir machen eine Fallunterscheidung Fall 1 = A, es beginnt mit einem Nichtterminalzeichen und eine Folge von Zeichen. Dann ist der erste Schritt das Ersetzen des NT-Zeichens durch seine Produktion (q, w, A) M (q, w, ) A P Weitere Rechnung: (q, w, ) (q, , ) j-1 Schritte M Nach Induktionsvoraussetzung passt die Behauptung fr . Da wir aus heru leiten knnen stimmt die Behauptung fr diesen Fall. o u Fall 2 = a; w = aw , es beginnt mit einem Terminalzeichen (das muss auch das erste Terminalzeichen des Wortes w sein). Man kommt also mit dem PDA (q, aw , a) M (q, w , ) (q, , )(j-1 Schritte) M Nach die I.V. passt der Teil. M Die andere Richtung ist noch belastender, darum lassen wir sie weg.
\
CC BY: $
31
Vorlesung 12
Die Konstruktion des PDA im Beweis liefert einen nichtdeterministischen Kellerautomaten. In der Praxis ist das nicht anwendbar (wer will schon nichtdeterministische Compiler haben?). Ein deterministischer Kellerautomat wrde direkt einen Algorithmus fr das Analyseproblem mit der u u Laufzeit O(n) liefern. Das Problem dabei ist, dass es nicht zu jeder kontextfreien Sprache einen deterministischen Kellerautomaten gibt. Die Unterklasse, zu der es einen deterministischen PDA gibt, nent man manchmal auch deterministische Kontextfreie Sprachen. Nur solche werden zur Denition der Syntax von Programmiersprachen benutzt. Weitere Einschrnkung Wir nehmen den PDA wie im Beweis, nur dass durch Inspektion des a nchsten Eingabezeichens ist eindeutig klar, welche Produktion auf das oberste Kellerzeichen ana gewandt werden muss. Solche Grammatiken heien LL(1)-Grammatiken Beispiel 25. S > (S)S|[S]S|. Diese Grammatik erzeugt die Dycksprache mit zwei Klammertypen. Wie sieht der PDA aus, der daraus konstruiert wird? Bei der Eingabe ([])[] wendet er zuerst Produktion 1 an, entfernt dann (. Da er [ liest, wendet er Produktion 2 an und entfernt [ vom Stack. Dann liest er ] und wendet Produktion 3 an. usw. Wenn wir uns die Produktionen hintereinander ankucken, dann erhalten wir genau die Linksableitung des Wortes aus der Grammatik.
Turing Maschinen
Der Zweck der Turingmaschine ist die Formalisierung der Begrie Algorithmus, berechenbare Funktion etc. Die wichtigste Erkenntnis ist dabei die Einsicht, dass es Probleme gibt, die nicht berechenbar sind. d.h. es gibt keinen Algorithmus um sie zu lsen. o Zum Beispiel hat Hilbert um 1900 gefragt, ob es einen Algorithmus, der fr alle mathematischen u Stze (ber natrliche Zahlen) entscheidet, obs ie wahr oder falsch sind? Gdel hat 1931 bewiesen, a u u o dass es sowas nicht geben kann (Unvollstndigkeitssatz). a
Die Turingmaschine kann in einem Schritt in Abhngigkeit vom gelesenen Zeichen und dem Zustand a der endlichen Kontrolle eine von drei Aktionen ausfhren: u neuen Zustand annehmen
\
CC BY: $
32
Zeichen in der zelle durch ein neues uberschreiben Kopf nach links oder rechts bewegen Denition 17. Eine Turingmaschine ist ein Tupel: M = (Q, , , , q0 , B, F )
Q q0 B F
: : : : : : :
Zustnde (endlich) a Eingabealphabet (endlich) Bandalphabet (endlich) part. Uberfhrungsfunktion : Q Q {R, L} u Startzustand Leerzeichen \ Endzustnde a
Turingmaschinen zum Akzeptieren von Sprachen Die Eingabe, ein Wort w aus steht auf den linkesten Zellen des Bandes, der Rest des Bandes sind Leerzeichen. Der Kopf steht auf dem ersten Zeichen, die Maschine bendet sich in Zustand q0 . Gem der Uberfhrungsfunktion fhrt die Maschine eine Reihe von Schritten durch. Wenn die a u u Turingmaschine irgendwann in einen Endzustand kommt, gilt das Wort als akzeptiert.
Formen der Nichtakzeptierung Es gibt mehrere Mglichkeiten fr Nichtakzeptierung: o u 1. irgendwann wird ein Zeichen a gelesen, whrend die Maschine im Zustand q (kein Endzustand) a ist, so dass die Uberfhrungsfunktion (q, a) nicht deniert ist. Oder sie steht auf der linkesten u Zelle und soll weiter nach links gehen. Die Maschine hlt in einem nicht-akzeptierenden a Zustand. 2. die Maschine luft unendlich weiter ohne einen akzeptierenden Zustand zu erreichen (sie hlt a a nicht).
Vorlesung 13
Beispiel 26. Eine Turingmaschine zum Akzeptieren von {an bn cn |n N}. Wir wissen, dass diese Sprache nicht kontextfrei ist, sie liegt also auerhalb der Sprachklassen, die wir bisher kennen. Q = {q0 , q1 , q2 , q3 , q4 , q5 } = {a, b, c = a, b, c, B, , #, $} F = {q5 }
Die Uberfhrungsfunktion wird durch folgende Tabelle beschrieben, wir schreiben statt (q, a) = u , a , D) diese Schreibweise nennt man auch Turingtabelle: (q
\
CC BY: $
33
q0 q1 q1 q1 q2 q2 q2 q3 q3 q3 q3 q3 q0 q4 q4 q4
a a # b b $ c $ b # a * # # $ B
q1 q1 q1 q2 q2 q1 q3 q3 q3 q3 q3 q0 q4 q4 q4 q5
* a # # b $ $ $ b # a * # # $ B
R R R R R R L L L L L R R R R R
lsche ein a o uberlaufe restliche as uberlaufe Rauten lsche ein b o uberlaufe die bs uberlaufe die Dollar lsche ein c o uberlaufe Dollar uberlaufe b uberlaufe # uberlaufe a gehe wieder an der Anfang der Tabelle alle as wurden gelscht o prfen ob keine bs und cs mehr u
Diese Maschine hlt immer an. a Formale Denition Denition 18. Eine Konguration einer Turingmaschin M = (Q, , , , B, q0 , F ) ist ein Wort der Form: 1 q2 mit 1 , 2
soll bedeuten M bendet sich im Zustand q und links vom LeseSchreibKopf steht 1 und rechts vom Kopf steht 2 (der Kopf steht auf dem ersten Zeichen des Wortes 2 ). Nach 2 folgen Blanks. Denition 19 (Schritt). Ein Schritt von M sei Konf iguration von M = X1 . . . Xi1 q Xi . . . Xn
Die Folgekonguration lsst sich aus der Turingtabelle ablesen: a (q, Xi ) = (r, A, L) (q, Xi ) = (r, A, R) = X1 . . . Xi2 r Xi1 AXi+1 . . . Xn = X1 . . . Xi1 Ar Xi+1 . . . Xn
Die Folgedenition ist oensichtlich nicht deniert, falls die Uberfhrungsfunktion an der Stelle u nicht deniert ist. Der Schritt deniert eine Relation, die Folgekongurationsrelation (mit einem Schritt kann man. . . ), auf der Menge der Relationen. Wir benutzen das Zeichen M . Der reexive und transitive Abschluss (also es gibt eine Folge von Schritten, so dass) wird durch das Zeichen das Zeichen bezeichnet. M Denition 20 (Akzeptanz). Eine Turingmaschine M akzeptiert ein w , gdw q0 w 1 p 2 M pF
Es muss eine Rechnung geben, so dass wir in einen Endzustand p kommen. Die von M akzeptierte Sprache ist die Menge der akzeptierten Worte L(M ) = {w |M akzeptiert w}
\
CC BY: $
34
Denition 21. Eine formale Sprache L, fr die eine Turingmaschine M existiert, die die Sprache u akzeptiert, heit rekursiv aufzhlbar (recursively enumerable). Hlt die Maschine fr jede Eingabe, a a u so heit die Sprache entscheidbar (recursive, decidable). z.B. {an bn cn |n N}. Fr rekursiv aufzhlbare Sprachen L muss die akzeptirende Turingmaschine fr Eingaben w L u a u nicht unbedingt halten (sie kann auch unendlich lange laufen). Damit sie aber entscheidbar ist, muss immer angehalten werden. Jede entscheidbare Sprache ist natrlich rekursiv aufzhlbar (umgekehrt u a nicht!).
Turingmaschinen zum Rechnen

Denition 22. Sei ein Alphabet, f : eine partielle Funktion, d.h. sie ist nicht unbedingt fr alle Eingaben deniert. Man sagt, eine Turingmaschine M berechnet die Funktion f, wenn u q0 w u1 qu2 M mit u1 u2 = f (w) und u1 qu2 ist eine Haltekonguration. Beispiel 27. f : {0, 1} {0, 1} ersetzt jede 1 durch eine 0 und umgekehrt f (0100) = 1011. Die Konstruktion von M ist ziemlich trivial, wir laufen einmal das Wort entlang und ersetzen dabei halt immer: q0 0 q0 1 R q 0 1 q0 0 R
Man kann die Denition leicht auf natrliche Zahlen ausweiten, da man sie ja in einem endlichen u (sogar einelementigen) Alphabet kodieren kann. Denition 23. Eine Funktion f : heit berechenbar (rekursiv), wenn es eine Turingmaschine gibt, die sie berechnet.
Vorlesung 14
Beispiel 28. f : N N, k k + 1 Nachfolgerfunktion. Behauptung: ist berechenbar. Wir uberlaufen alle Nullen, bis wir das erste Blank erreichen. Das uberschreiben wir mit einer Null und halten. Turingtabelle: q0 0 q0 0 R q0 B q1 O R Denition 24. Eine partielle Funktion f : Nk Nm k, m N heit berechenbar, gdw f : {0, 1} {0, 1} 0n 10n2 . . . 0p 1 . . . 10pm
(1 als Grenzsymbol und 0k um die Zahlen darzustellen, Tupel kodieren). Wenn (p1 , . . . , pm ) = f (n1 , . . . , nk ) ist berechenbar Beispiel 29. f : N2 N (x, y) x + y ist berechenbar. Turingtabelle: q0 0 q0 0 R q0 1 q1 0 R q1 0 q1 0 R q1 B q2 B L q2 0 q3 B R
CC
BY:
35
Zusammenhang berechenbarrekursiv aufzhlbar a Es gilt 1. Eine Sprache L ist entscheidbar, gdw die charakteristische Funktion l : {0, 1} w berechenbar ist. 2. L ist rekursiv aufzhlbar, gdw L Denitionsberechein einer berechenbaren Funktion a f : Mehrband Turingmaschinen Weil normale Turingmaschinen so belastend sind, haben schlaue Leute sind coolere Turingmaschinen ausgedacht. Die Mehrband-Turingmaschine sieht genauso aus wie die normale Turingmaschine, nur hat sie halt k Bnder. Ein Schritt dieser Mehrbandturingmaschine ist: abhngig von den k a a gelesen Zeichen und dem Zustand der endlichen Kontrolle, werden die k Zeichen durch neue uber schrieben, die k Kpfe unabhngig voneinander bewegt (oder sie bleiben stehen) und es wird ein o a neuer Zustand der endlichen Kontrolle angenommen. Eine Eingabe steht auf den ersten Zellen von Band 1. Sie gilt als akzeptiert, wenn es eine Rechnung gibt, whrend der ein akzeptierender Zustand angenommen wird. Beim Berechnen von Funktionen a f : hlt die Turingmaschine mit f (w) auf Band 1. Mehrbandturingmaschinen sind nicht a mchtiger als Einbandturingmaschinen. a Denition 25. Eine k-Band Turingmaschine ist ein System M = (Q, , , , q0 , B, F ), wie bei einer Einbandturingmaschine. Nur ist anders. : Q k Q k {R, L, S}k Denition 26 (Konguration). enier k-bd.TM ist ein (2k + 1) Tupel (q, (u1 , v1 ), (u2 , v2 ), . . . , (uk , vk )) Gemeint ist: auf dem ersten Band haben wir u1 , v1 stehen, der Lesekopf steht auf dem ersten Zeichen von v1 usw fr alle Bnder und die endliche Kontrolle ist im Zustand q. u a M ist analog zur Einband TM Denition 27. Eine k-Bd.-TM M akzeptiert ein w gdw (q0 , (, w), (, ) . . .) (qi , (u1 , v1 ), . . . , (uk , vk )) M mit qi F 0 falls w L 1 falls w L
Eine k-Bd.-TM M berechnet eine partielle Funktion f : gdw (q0 , (, w), (, ) . . .) (qi , (, f (w)), (u2 , v2 ), . . . , (uk , vk )) M mit qi F
fr alle w im Denitionsbereich von f. Analog fr natrliche Zahlen. u u u Beispiel 30 (Ganzzahlige Division). f : N2 N (x, y) xy auf einer dreiband-Turingmaschine:
\
CC BY: $
36
q0 q1 q1 q2 q2 q3 q3 q4 q4
(0,B,B) (0,B,B) (1,B,B) (0,0,B) (0,*,B) (0,0,B) (B,0,B) (0,0,B) (1,0,B)
(0,*,B) (0,0,B) (1,B,B) (0,0,B) (0,*,B) (0,0,B) (B,0,0) (0,0,B) (1,0,B)
q1 q1 q2 q2 q3 q3 q4 q4 q3
(R,R,S) (R,R,S) (R,L,S) (S,L,S) (R,R,S) (R,R,S) (L,S,R) (L,S,S) (R,S,S)
markiere erste Zelle auf Band 2 kopiere 0x auf Band 2 laufe auf Band 2 zurck u
Ende von 0y ist erreicht auf Band 1 zurcklaufen u
Am Schluss muss man das Ergebniss von Band 3 noch auf Band 1 kopiert werden. Denition 28. Zwei Turingmaschinen heien quivalent, gdw sie die selbe Sprache akzeptieren a oder die selbe Funktion berechenen und fr die selben Eingaben halten. u Satz Zu jeder k-Bd.TM M kann man eine quivalent Einbandturingmaschine M a
Beweisidee Wir denieren die Einbandturingmaschine M = (Q , , , , q0 , B , F ). M hat auf dem Band 2k sog. Spuren. Auf der ersten Spur der die Inschrift von Band 1. Auf der zweiten Spur steht irgendwo ein x, eine Markierung, wo sich der Kopf von Band 1 von M ist. usw. Man muss das Bandalphabet jetzt so whlen, dass man die Tupel fr die Spuren (sind ja eine endliche Menge) a u darin abbilden kann, weil man natrlich nur eine Spur hat. u
= ( {x} )2k Die endliche Kontrolle von M ist viel grer als die von M. Sie enthlt, neben Bereichen die zur o a Steuerung dienen, ein Register, das alle Zustnde von M enthlt, k Register fr gelesene Zeichen a a u und k Register zum speichern von Bewegungsrichtungen der Kpfe. o Um mit den Einband-Turingmaschine einen Schritt der Mehrbandversion zu simulieren, mssen so u vorgehen: 1. Aufsammeln der ntigen Information o Wir uberstreichen das Band von M. Fr jede gefundene Markierung x speichern wir die u darberliegende Zeichen in Registern der endlichen Kontrolle. Wir kennen dann die Zeichen u Ai und den Zustand q 2. Uberfhrungsfunktion von M sieht so aus: u (q, A1 , . . . , Ak ) = (q , B1 , . . . , Bk , D1 , . . . , Dk )
Zeichen Richtungen
Zur Simulation uberschreiben wir die in den Registern gespeicherten Ai mit den Bi und speichern die Richtungen in den Richtungsregistern. 3. Wir haben alle ntigen Informationen und streichen erneut uber das Band um die ntigen o o Anderungen vorzunehmen. Fr jedes x in der j-ten Spur uberschreibt man das darberliegende u u Aj mit Bj und bewegt die Markierung x durch die in Dj angegebene Richtung. Auerdem a ndern wir noch den Zustand q zu q in der endlichen Kontrolle. Wir mssen uns noch uberlegen wie wir die ganzen suspekten Register in der endlichen Kontrolle u realisieren. Wir machen das wieder uber ein Tupel Q = Q k {R, L, 0}k
Zeichen/Richtungsregister
Z
Steuerung
CC
BY:
37
Q wird also vielleicht riesig gro, aber ist immernoch endlich. Die akzeptierenden Zustnde F sind a natrlich u F = F k {R, L, 0}k Z Anfangszustand
q0 = (q0 , l, . . . , l, l . . . , l, p0 )
Vorlesung 15
Es gibt noch andere Modelle von Turingmaschinen Nichtdeterministische Mit mehreren Kpfen o Mehrdimensionales Band komibationen von allem Es stellt sich aber heraus, dass alle diese Modelle Aquivalent mit der einband-einkopf-eindimensionalendeterministischen Turingmaschine. Man kann also insbesondere Nichtdeterministische Turingmaschinen durch deterministische simulieren. Das geht relativ leicht, indem man eine BFS auf dem Baum der mglichen Kongurationen o der ND-Turingmaschine machen und halten sobald man einen akzeptierenden trit.
Abschlusseigenschaften entscheidbarer und rekursiv aufzhlbarer Mengen a

a) die entscheidbaren und rekursiv aufzhlbaren Mengen sind unter Durschnitt und Vereinigung a abgeschlossen b) die entscheidbaren Mengen sind unter Komplement abgeschlossen. c) rekursiv aufzhlbare Mengen sind unter Komplement nicht abgeschlossen a d) Wenn L und L rekursiv aufzhlbar sind, dann ist L entscheidbar. a Beweise Auswahl a) Durchschnitt rekursiver/entscheidbarer aufzhlbarer Mengen: Seien L1 und L2 rekursiv aufa zhlbar/entscheidbar. Wir wollen zeigen, dass der Durchschnitt r.a./entscheidbar ist. Angea nommen M1 und M2 seien Turingmaschinen. Wir denieren eine neue Turingmaschine, die genau dann akzeptiert wenn beide Turingmaschinen (nacheinander) M1 M2 akzeptieren. Wir benutzen sie sozusagen als Unterprogramme und fhren beide auf die Eingabe aus. u Vereinigung rekursiv aufzhlbarer Sprachen. Wir haben wieder zwei TM M1 und M2 , die a die beiden Sprachen akzeptieren. Wir knnen sie nicht nacheinander als Unterprogramme o aufrufen, weil es ja sein knnte dass M1 nicht hlt. Wenn M2 das Wort aber akzeptieren o a wrde, wrden wir das nicht erkennen (wir kommen ja nicht aus M1 raus). Darum lassen wir u u beide Maschinen gleichzeitig laufen (auf zwei Bndern, immer einen Schritt von M1 , dann a einen von M2 ). Wenn eine hlt is dann gut. Genauso fr entscheidbare. a u b) einfach c) spter a
\
CC BY: $
38
d) Ubungsaufgabe Denition 29. entscheidbare und rekursiv aufzhlbare Mengen von natrlichen Zahlen. a u k |k K} rekursiv aufzhlbar/ entK N heit rekursiv aufzhlbar bzw entscheidbar wenn {0 a a scheidbar ist. Beispiel 31. Es gibt nur abzhlbar viele rekursiv aufzhlbare Mengen, denn zu jeder r.a. Menge a a gehrt eine Turingmaschine. Es gibt aber nur abzhlbar viele Turingmaschinen (weil sie eine endliche o a Beschreibung hat). (Sehen wir spter noch genauer). Die Potenzmenge der natrlichen Zahlen ist a u aber uberabzhlbar, es muss also uberabzhlbar viele nicht-rekursiv aufzhlbare Mengen geben. a a a G=Menge der geraden Zahlen ist entscheidbar P=Menge der Primzahlen ist entscheidbar
Vorlesung 16
Andere Anstze zur Denition berechenbarer Funktionen a
Die Menge der rekursiven Funktionen Nk N ist deniert durch ein paar primitve Funktionen und Operationen, die komplizierte Funktionen aus einfachen zusammensetzen:
0 a) Grundfunktionen: Die nullstelligen Konstante C0 : N0 N () 0. Die Nachfolgerfunktion i N : N N x x + 1. Die n-stelligen Projektionen Un : Nn N (x1 , . . . , xn ) xi .
b) Abgeschlossenheit: Die rekursiven Funktionen sind abgeschlossen gegen Einsetzung Wenn man rekursive Funktionen h1 , . . . , hr : Nn N und g : Nr N, dann auch f : Nn N (x1 , . . . , xn ) g(h1 (x1 , . . . xn ), h2(x1 , . . . , xn ), . . . , hr (x1 , . . . , xn )) Rekursionsschema Seien g : Nn N und h : Nn+2 N rekursive Funktionen, dann auch f : Nn+1 N f (x1 , . . . , xn , 0) = g(x1 , . . . , xn ) f (x1 , . . . xn , x + 1) = h(x1 , . . . , xn , x, f (x1 , . . . , xn , x))
eine rekursive Funktion Die kleinste Menge die die obigen Anforderungen erfllt, heit die Menge der primitiv rekursiven u Funktionen. Die rekursiven Funktionen sind eine echt grere Menge, denn dort gibt es noch den o -Operator f : Nk+1 N primitiv rekursiv, dann auch f : Nk N (x1 , . . . , xk ) min{y|f (x1 , . . . , xn , y) = 0} (ist natrlich nicht immer deniert) u Denition 30 (Rekursive Funktionen). Die kleinste Klases von Funktionen, die die Grundfunktionen enthlt und gegenber Einsetzung, Rekursionsschema und -Operator abgeschlossen ist, heit a u Klasse der rekursiven Funktionen. Beispiel 32. mehrstellige Konstanten
0 C1 : N N x 0 0 0 C1 (0) = C0 () 0 0 2 0 0 C1 (x + 1) = h(x, C1 (x)) = U2 (x, C1 (x)) = C1 (x)
CC
BY:
39
Addition plus : N2 N : (x, y) x + y

1 plus(x, 0) = U2 (x, 0) 3 plus(x, y + 1) = N (U3 (x, y, plus(x, y)))
Multiplikation (geht genauso wie die Addition) mal : N2 N : (x, y) x + y

0 1 1 mal(x, 0) = C1 (x) mal(x, y + 1) = plus(U3 (x, y, mal(x, y)), U3 (x, y, mal(x, y)))
Vorgngerfunktion a v:NNx
0 v(0) = C0 ()
x1 0 f alls x = 0
1 v(x + 1) = U2 (x, v(x))
modizierte Subtraktion xy = xy 0 x>y sonst
Ubungsaufgabe ganzzahlige Division x div : N2 N (x, y) y div(x, y) = f mit f (x, y, a) = x(mal(a, y))
Satz Die Klasse der rekursiven Funktionen ist gleich der Klasse der berechenbaren Funktionen (auf N). Weitere Beispiele sind: -Kalkl u hhere Programmiersprachen (Haskell, C,. . . ) o alle diese Funktionsklassen sind gleich Churchsche These Diese Funktionsklasse sind die Funktionen, die man auch intuitiv als bere chenbar ansieht.
Normierung von Sprachen und Turingmaschinen

Wir wollen jeder Turingmaschine eine Zahl in der Art zuordnen, dass alle eindeutig durchnummeriert sind. Um das einfacher zu machen verwenden wir nur noch {0, 1, B} als Alphabet. Sei ein Alphabet. Falls || = 1 o.w.E. = {0}, falls || = 2 owE = {0, 1}. Falls || 3 kodieren wir die Zeichen als 01 Folgen. Wir denieren eine Kodierung c : {0, 1} 11 0 . . . 0 1 0 . . . 0
i1 ki
c kann ausgedehnt werden auf indem man c(b1 , . . . , bN ) := c(b1 ) . . . c(bn ). c ist ein Prxcode a und damit ist es injektiv, man kann also aus der gegebenen Binrfolge das Urbild rekonstruieren. a Abbildungen mit dieser Eigenschaft heien auch Homomorphismus.
\
CC BY: $
40
Satz Eine Sprache L ist entscheidbar/rekursiv aufzhlbar, gdw c(L) {0, 1} entscheidbar/ a rekursiv aufzhlbar ist. Es gibt eine Turingmaschine, die das Bandalphabet {0, 1, B} hat und sie a akzeptiert. Analog fr berechenbare Funktionen. u Beweisidee Sei M eine Turingmaschine, die L entscheidet/akzeptiert. Wir konstruieren eine TM M, die c(L) mit dem Bandalphabet {0, 1, B} macht. Auf ihrem Band steht am Anfang nicht w = a1 . . . aN , sondern w = c(a1 ) . . . c(an ). Es luft jetzt ganz hnlich wie bei dem Umbau von a a Mehrband- zu Einbandturingmaschinen. Wir haben wieder ganz viele Register in der endlichen Kontrolle. Q = Q {p1 , . . . , pk }
Steuerung q0 )(q0 , B, p0 )
Um einen Schritt von M zu simulieren kodiert M erstmal c(A1 ) zurck zu Ai (wir lesen immer u eine Null von der Kodierung und schreiben fr die k-te Null Ak ins Register). Intern haben wir u den Zustand von M gespeichert und knnen dann natrlich mit dem dekodierten A1 einen Schritt o u simulieren. Den Buchstaben, den M auf das Band schreiben wrde, merken wir uns im Register, u laufen zurck zum Anfang des c(A1 ) Blocks und schreiben dann die Kodierung hin (verschieben u dabei, wenn ntig der Rest des Bandes). o Zum berechnen von Funktionen machen wir genau das gleiche.
Vorlesung 17
Codierung von Turingmaschinen
Jede Turingmaschine mit dem Bandalphabet {0, 1, B} (ohne wesentliche Einschrnkungen) lsst a a sich als {0, 1}-Wort codieren. Sei M = (Q, {0, 1}, {0, 1, B}, , q1 , B, {q2 }) Q = {q1 , q2 , . . . , qr } (zu jeder Turingmaschine kann man eine konstruieren, die nur einen Endzustand hat, indem man zu den vorherigen Endzustnden immer noch einen Ubergang zu dem einen Endzustand gibt). Wir a kodieren einen Ubergang (qi , Aj ) = (ql , Am , Dn )
r
oBdA A1 = 0 A2 = 1 A3 = B D1 = R D2 = L
3 r 3
111 0 . . . 0 1 0 . . . 0
T renner ites
11
T renner
0 . . . 1 . . . 0 11 0 . . . 10 . . . 0 11 0 . . . 1 . . . 0 11 01
jtes Dn
Wenn man das fr alle Zeilen macht, hat man die ganze Turingmaschine beschrieben. z.B. u 111100111001110011100111011110011010110011101011001110011100111010110011101 beschreibt q1 A1 q1 A1 R q1 A2 q3 A2 R q3 A3 q2 A3 L Uber diese Kodierung wird eineindeuting jeder Turingmaschine eine natrliche Zahl zugeordnet u (Binrdarstellung). Die obige Turingmaschine ist Nr. 35950919592676365858205 (denke ich). Uma gekehrt geht das auch, wenn die Binrdarstellung von n die richtige Form hat, ist die Interpretation a klar, sonst ordnen wir der Zahl einfach die Turingmaschine zu, die gar nichts macht (leere Turingtabelle). Daraus folgt, dass es nur abzhlbar viele Turingmaschinen und damit nur abzhlbar viele rekursiv a a aufzhlbare Sprachen und abzhlbar viele berechenbaren Funktionen a a
\
CC BY: $
41
Nicht-rekursiv aufzhlbare Sprachen a

Obwohl es uberabzhlbar viele gibt, sind sie ziemlich schwierig zu nden (warum ist das eigentlich a immer so). Eine ist zum Beispiel LD = {w {0, 1} |w L(Mw )} Mw akzeptiert ihre eigene Beschreibung nicht als Eingabe Beweis Angenommen doch, dann gibt es eine Turingmaschine, die LD akzeptiert die Kodierung dieser Turingmaschine sei u {0, 1} . Es gibt zwei Mglichkeiten Mu akzeptiert sich selbst als o Eingabe, d.h. u L(Mu ) also u LD u LD das ist aber ein Widerspruch. Demnach muss u L(Mu ) sein, das heit aber u LD , aber die Maschine Mu akzeptiert LD , das ist ein Widerspruch. Beide Flle fhren zu Widersprchen, also muss die Annahme falsch sein und es gibt keine a u u Turingmaschine, die LD akzeptiert. Diese Beweisidee (Diagonalisierung, Selbstbezug) kann man auch noch fr andere Sachen benutzen u (Russelsche Antinomie, vgl Barbier von Sevilla; Ich lge gerade; Sei ungehorsam) u
Vorlesung 18
Jetzt wo wir diese eine nicht rekursiv aufzhlbare Sprache haben, knnen wir von vielen anderen a o Problemen zeigen, dass sie nicht entscheidbar sind. Denition 31 (Universelle Sprache). Wrter dieser Sprache haben die Form o Lu = {w 111111 v|Mw akzeptiert v} Wir interpretieren w als Kodierung einer Turingmaschine und v als Eingabe. Die 6 Einsen sind ein Trennzeichen und kommen in w nicht vor. Die Turingmaschine, die diese Sprache akzeptiert ist sozusagen eine programmierbare Turingmaschine, der man ein Programm w und eine Eingabe v gibt und die dann w auf v ausfhrt. u
Satz Lu ist rekursiv aufzhlbar, aber nicht entscheidbar. a Beweis Rekursiv aufzhlbar: Wir konstruieren eine Turingmaschine, die bei Eingabe w111111v a Mw auf v simuliert (sog. Universelle Turingmaschine) Nicht entscheidbar: Angenommen doch, mit Turingmaschine M. Wenn wir das knnten, dann knnte o o man LD wie folgt entscheiden: Wir haben eine Eingabe w und konstruieren eine Turingmaschine die aus w w111111w macht. Das geben wir dann als Eingabe an M und akzeptieren wenn M nicht akzeptierend hlt. a Da LD aber nicht rekursiv aufzhlbar (und damit nicht entscheidbar) ist (wie oben gezeigt) kann a es eine solche Maschine nicht geben. 1. Die Klasse der rekursiv aufzhlbaren Sprachen ist nicht unter Komplement abgeschlossen, a insb. ist die Sprache Lu nicht rekursiv aufzhlbar (sonst wre Lu ja entscheidbar) a a 2. Die Klasse der rekursiv aufzhlbaren Sprachen ist echt grer als die Klasse der entscheidbaren a o Sprachen. 3. Betrachte Lu = {w111111v|Mw akzeptiert v nicht}. Sie ist nicht rekursiv aufzhlbar a
\
CC BY: $
42
Die Universelle Turingmaschine

Mu , akzeptiert Lu . Bei Eingabe w11111v, simuliert sie Mw auf v (sie ist also eigentlich program mierbar). Mu hat das Bandalphabet {0, 1, B} und drei Bnder. a Auf dem ersten Band steht die Eingabe, auf dem zweiten Band wird Mw simuliert. Das dritte Band enthlt die Zustnde von Mw . a a Mu operiert wie folgt: 1. Mu prft das Format von Band 1, d.h. sie bestimmt ein Anfangsstck der Form u u 111 0 . . . 010 . . . 0 11 001 11 0 . . . 010 . . . 0 11 010 11 01
k 3 k 3 2
auf das 6 Einsen folgen und dann ein beliebiger 01-String v. Auerdem muss die kodierte Turingtabelle eindeutig sein. Falls die Eingabe nicht dieses Format hat, hlt Mu nicht akzepa tierend. 2. Initialisiere Band 2 mit v 3. Initialisiere Band 3 mit 100 . . . 0 (k Zeichen) 4. Falls ins Band 3 der Endzustand 010 . . . 0 erreicht ist, halten wir akzeptierend 5. Simulation eines Schritts von Mw . Aj sei das von Kopf 2 gelesene Symbol. Wir durchlaufen das Band 1 und suchen nach einer entsprechenden Zeile in der kodierten Turingtabelle. Falls wir sowas nden (sonst nicht akz. halten), schreiben wir den Zustand auf das dritte Band und das im Block kodierte Zeichen auf das zweite Band. Dann bewegen wir den Kopf auf Band zwei in die kodierte Richtung. 6. Gehe zu Schritt 4 Damit knnen wir tolle andere Sachen beweisen: o Folgende Probleme sind nicht entscheidbar Halteproblem Lk = {w11111v|Mw hlt bei Eingabe v} a Lh = {w|es gibt eine Eingabe fr die Mw hlt} analog Lh , Lh u a Leerheitsproblem L = {w|L(Mw ) = } analog L Lh und Lh sind rekursiv aufzhlbar aber nicht entscheidbar. Lh , Lh , L und L sind nichtmal a rekursiv aufzhlbar. a Beweise von diesen Behauptungen beruhen auf der Idee der Reduktion: Seien L1 , L2 {0, 1} Sprachen und es existiere eine berechenbare Funktion f : {0, 1} {0, 1} mit w L1 f (w) L2 . Dann gilt natrlich, dass wenn L2 entscheidbar/rekursiv aufzhlbar ist auch L1 entscheidu a bar/rekursiv entscheidbar ist (und umgekehrt). Man kann ja einfach die Turingmaschine, die f berechnet an die Turingmaschine, die L2 entscheidet vorne dranmachen und so L1 entscheiden.
L1 ist also enfacher als L2 , man schreibt L1 L2

\
CC BY: $
43
Beweis (Halteproblem) Sei w {0, 1} Mw zugehrige Turingmaschine. Konstruierene TM o , die nicht hlt, falls M nichtakzeptierend hlt und sich sonst wie M verhlt. Wir konstruieren Mw a a a w w damit eine Abbildung f : {0, 1} {0, 1} w111111v w 111111v
Diese Abbildung ist berechenbar. Dann gilt x Lu gdw f (x) Lh . Damit haben wir eine Reduktion von Lu auf Lh , also Lu Lh Da Lu aber nicht entscheidbar ist, kann auch Lh nicht entscheidbar sein.
Vorlesung 19
Beweis Lh Sei x=w111111v. Wir konstruieren daraus eine Turingmaschine Mx , die ihre eigene Eingabe ignoriert und simuliert nur dieses Mw auf v.
Die Funktion
f : x < Mx > Kodierung
ist berechenbar. Es gilt

x Lh f (x) =< Mx > Lh
Damit ist Lh reduzierbar auf Lh . Da Lh nicht entscheidbar ist, kann auch Lh nicht entscheidbar sein. Der Beweis fr Lh geht genauso. u Die beiden anderen folgen aus dem Satz von Rice
Satz von Rice

Eine Eigenschaft rekursiv aufzhlbarer Sprachen heie nichttrivial, gdw nicht alle rekursiv aufzhla a baren Sprachen diese Eigenschaft haben, aber es wenigstens eine Sprache gibt, die die Eigenschaft hat. z.b. sind = -sein, = {0, 1} -sein, kontextfrei-sein, regulr-sein, endlich-sein, aus-n-worten-bestehend, a nichttriviale Eigenschaften Satz Jede nichttriviale Eigenschaft nichtrekursiver Eigenschaften ist unentscheidbar. Das heit: gegeben eine Turingmaschine M. Sprache {< M > |L(m)hat Eigenschaft} ist immer nicht entscheidbar
\
CC BY: $
44
Beweis Sei Lp = {< M > |L(m) hat die Eigenschaft P} (P nichttrivial). Wir wollen zeigen
Lu Lp
Wir machen folgende Konstruktion: Sei L eine r.a. Sprache mit der Eigenschaft P und ML eine Turingmaschine, die sie akzeptiert. Aus einer Eingabe < M, w > fr Lu wird eine Eingabe f (< u M, w >) fr Lp wie folgt konstruiert: u
Fall a hat nicht die Eigenschaft P. M ignoriert zunchst ihre Eingabe x und simuliert M auf w, falls M akzeptierend hlt, wird a a ML auf Eingabe x gestartet (sonst Endlosschleife). Die Maschine hlt akzeptierend, wenn ML a akzeptierend hlt. a
L(M ) =
falls M w nicht akzeptiert L falls M w akzeptiert
Bei Fall 1 hat es die Eigenschaft P nicht, sonst schon. L(M ) hat Eigenschaft P (d.h. < M > Lp ) M akzeptiert w (d.h. < M, w > Lu ). Damit Lu Lp
Fall b hat die Eigenschaft P gehe von Eigenschaft P zu der Eigenschaft P . hat nicht die Eigenschaft P und P ist ent scheidbar gdw P entscheidbar ist. Dann knnen wir Fall a) auf P anwenden. o
\
CC BY: $
45
Ubersicht
Sprachklasse regulr a det. kontextfrei kontextfrei entscheidbar rek. aufzhlbar a andere
Automat endlicher Automat (det. o. n-det.) det. Kellerautomat (ndet.) Kellerautomat Turingmaschine (hlt immer) a Turingmaschine (mit Endlosschleife) gibbets nicht
typische Sprache L = {w|w, binr, ist durch drei teilbar} a L = {an bn |n N} L = {wwR|w {0, 1} } (Palindrome) L = {0n 1n 0n |n N } Lu LD
Chomsky-Hierarchie Die Chomsky-Hierachie ist eine traditionelle Art Sprachen aufzuzhlen, die nicht auf Automatena modellen, sondern auf Grammatiken basiert. Es werden vier Typen von Sprachen unterschieden: Typ 0 Werden erzeugt von Grammatiken, mit Produktionen von der Form , wobei und Folgen von Nichtterminalzeichen und Terminalzeichen sind. (sonsts wie kontextfreie Spra chen). Typ 0 Sprachen sind genau die rekursiv aufzhlbaren. Aquivalent zur Turingmaschine a Typ 1 Genau wie Typ 0, nur dass || ||. Das abgeleitete Wort darf also unterwegs nicht krzer u werden. {ktf } {T yp 1} {entscheidbar}. Diese Sprachen nennt man auch kontextsensitiv, denn es gibt Produktionen uAv uv, dabei sind u und v der Kontext. Aquivalent zum sog. linear beschrnkten Automat LBA (eine ndet. Turingmaschine, die nicht mehr Platz benutzen a darf, als was durch die Eingabe eingenommen wird). Typ 2 Produktionen der Form A , das sind genau die kontextfreien Sprachen. Aquivalent zum ndet Pushdown Automaten Typ 3 Produktionen von der Form A a oder A aB. Das sind genau die regulren Grammaa tiken, die regulre Sprachen erzeugen. Aquvalent zu endlichen Automaten a
\
CC BY: $
46
Vorlesung 20
Nicht berechenbare Funktionen
Wenn es nicht entscheidbare Sprachen gibt, muss es auch nicht berechenbare Funktionen geben, denn jede Sprache hat eine charakteristische Funktion. Wenn die Sprache nicht entscheidbar ist, ist die charakteristische Funktion L nicht berechenbar. z.b. f = Lu f : {0, 1} {0, 1} 1 w L(M ) 0 sonst
f : (< M, w >) = Betrachte:
f : {0, 1} {0, 1}
f : (< M, w >) =
1 w L(M ) undef iniert sonst
Diese Funktion ist berechenbar, da Lu rekursiv aufzhlbar ist (der sonst Fall war ja das Proa blem, weil die Turingmaschine, die f berechnet, nicht unbedingt halten muss. Jetzt ist er einfach undeniert).
Konsequenzen der Nichtentscheidbarkeit

Programmierung Es gibt u.a. keine Algorithmen, zum Lsen/ Entscheiden folgender Probleme: o Gegeben ein Programm (in einer Programmiersprache), terminiert es fr alle Eingaben? u Hlt es fr eine gegebene Eingabe? a u Berechnet es die durch eine formale Spezikation gegebene Funktion? (Korrektheit des Programms) Also: Terminations/ Korrektheitsbeweise mssen fr alle Programme einzeln gefhrt werden. u u u Mathematische Logik Die Prdikatenlogik ist eine Formalisierung mathematischer Aussagen und Schlssen. Eine Prdia u a katonlogische Formal ist eine Zeichenfolge uber dem Alphabet = {, , , , , (, ), x, y, z . . . , 0, 1, , , =} Wir betrachten Formeln, die Aussagen uber den natrlichen Zahlen formalisieren sollen. z.B. u xy(x y = y) xyz : (x z = y) yz((y = 1) (y = x) x = y z))
f (x)
Bei der letzten Formel existieren freie Variablen, die nicht durch Quantoren gebunden sind. Wir interpretieren das uber den natrlichen Zahlen (N, +, ). Formeln, die keine freien Variablen haben, u erhalten dann einen Wahrheitswert. Solche mit freien Variablen knnen als Funktionen aufgefasst o werden. f (x) von oben bedeutet unter der Interpretation x ist keine Primzahl. Nennen wir die Menge aller prdikatenlogischen Formeln, die, interpretiert uber die natrlichen a u Zahlen, wahr sind T h(N, +, ). Diese Menge ist eine formale Sprache, denn sie ist .
\
CC BY: $
47
Die Menge ist nicht entscheidbar. Zahlentheoretiker lassen sich also nicht so einfach durch Maschinen ersetzen. Ein Beruf mit Zukunft. Beweisidee: Wir konstruieren zu einer gegebenen Turingmaschine M und einem Wort w eine prdikatenlogische Formel M,w mit einer freien Variablen x, die a genau dann wahr wird, wenn x die Kodierung einer akzeptierenden Berechnung von M bei Eingabe w ist. Die Formel xM,w ist wahr ( T h(N, +, )), wenn es eine akzeptierende Eingabe gibt. Damit haben wir eine Reduktion von der universellen Sprache auf die Menge aller wahren Ausgaben.
Lu T h(N, +, )
Sie ist auch nicht rekursiv aufzhlbar, sonst knnte man die Turingmaschine, die wahre erkennt a o zu einer entscheidenden umgebaut werden, indem man sie parallel auf und laufen lsst. a
Axiomsysteme Formalisierungen mathematischen Schlieens. Sie bestehen aus Axiomen (prdikatenlogische Fora meln)
S1 , S2 , . . .
und Schlussregeln,
T1 , T2 , . . . T
die ahnlich den Typ 0 Grammatiken sind. Wenn man T1 , . . . , Tn hat (Axiome oder hergeleitet) kann man auch T herleiten. z.b.
A, A B B
Die Menge aller herleitbaren Formeln ist rekursiv aufzhlbar (in jedem Axiomensystem). Da die a Menge der wahren Formeln uber den natrlichen Zahlen (T h(N, +, )) ist nicht rekursiv aufzhlu a bar. Deswegen kann es kein Axiomensystem geben, in dem alle wahren Aussagen herleitbar sind (Gdelscher Unvollstndigkeitssatz) o a
\
CC BY: $
48
Inhaltsverzeichnis
Vorlesung 1 Motivation . . . . . . . . . . . . . . . . . . Inhalt der Vorlesung . . . . . . . . . . . . . Regulre Sprachen und endliche Automaten a Regulre Sprachen . . . . . . . . . . . a Operationen zwischen Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 1 2 3 4 5 5 7 8 8 11 12 12 12
Vorlesung 2 Endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Vorlesung 3 Nicht deterministische endliche Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . n.d. e. Automaten mit -Ubergngen . . . . . . . . . . . . . . . . . . . . . . . . . . . a Vorlesung 4 Was knnen endliche Automaten? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Vorlesung 5 Abschlusseigenschaften regulrer Sprachen . . . . . . . . . . . . . . . . . . . . . . . . a Nicht-regulre Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a Beweis der Nichtregulritt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a a
Vorlesung 6 14 Kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Vorlesung 7 16 Natrliche Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 u Vergleich regulre kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . 18 a Vorlesung 8 Normalformen von kontextfreien Grammatiken Entfernung von -Produktionen . . . . . . Entfernen von Einzelproduktionen . . . . Chomsky Normalforn (CNF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 18 19 21 21 23 23 24 25
Vorlesung 9 Pumping-Lemma fr kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . u Nicht-Kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abschlusseigenschaften Kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . . . . . .
Vorlesung 10 26 Das Analyseproblem kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . 26 Algorithmus von Cocke-Kasami-Younger . . . . . . . . . . . . . . . . . . . . . . . . . 26 Push-Down Automaten (Kellerautomaten) . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Vorlesung 11 29 Die von einem Kellerautomaten akzeptierte Sprache L(M) . . . . . . . . . . . . . . . . . . 29 Vorlesung 12 32 Turing Maschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 Turingmaschinen zum Akzeptieren von Sprachen . . . . . . . . . . . . . . . . . . . . 33
\
CC BY: $
49
Vorlesung 13 33 Formale Denition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Turingmaschinen zum Rechnen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Vorlesung 14 35 Zusammenhang berechenbarrekursiv aufzhlbar . . . . . . . . . . . . . . . . . . . . 36 a Mehrband Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 Vorlesung 15 38 Abschlusseigenschaften entscheidbarer und rekursiv aufzhlbarer Mengen . . . . . . . . . 38 a Vorlesung 16 39 Andere Anstze zur Denition berechenbarer Funktionen . . . . . . . . . . . . . . . . . . 39 a Normierung von Sprachen und Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . 40 Vorlesung 17 41 Codierung von Turingmaschinen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Nicht-rekursiv aufzhlbare Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 a Vorlesung 18 42 Die Universelle Turingmaschine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Vorlesung 19 Satz von Rice . . . . . . . . . . . . . . . Ubersicht . . . . . . . . . . . . . . . . . Chomsky-Hierarchie . . . . . . . . Nicht berechenbare Funktionen . . . . . Konsequenzen der Nichtentscheidbarkeit Programmierung . . . . . . . . . . Mathematische Logik . . . . . . . . Axiomsysteme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 44 46 46 47 47 47 47 48
CC
BY:
50

Grundlagen Der Theoretischen Informatik

Hochgeladen von

Copyright:

Verfügbare Formate

Grundlagen Der Theoretischen Informatik

Hochgeladen von

Dokumentinformationen

Originaltitel

Copyright

Verfügbare Formate

Dieses Dokument teilen

Dokument teilen oder einbetten

Freigabeoptionen

Stufen Sie dieses Dokument als nützlich ein?

Sind diese Inhalte unangemessen?

Copyright:

Verfügbare Formate

Grundlagen Der Theoretischen Informatik

Hochgeladen von

Copyright:

Verfügbare Formate

Grundlagen der Theoretischen Informatik

Adrian Neumann 4. Juli 2007

Inhalt der Vorlesung

Regulre Sprachen und endliche Automaten a

strker als , das strker bindet als . a a

Die Uberfhrungsfunktion denieren wir also wie folgt. u q1 q2 q3 q4 0 q2 q4 q2 q4 1 q1 q3 q1 q3

Nach I.V. ist =

M = (Q1 Q2 , , , s1 , F2 ) (q, a) = 1 (q, a) 2 (q, a) q Q1 q Q2 und (q, ) = s2 q F1

Fall w Lk , betrachte die Rechung ij qi

Die Zwischenstnde sind alle {q1 , . . . , qk }. Wir unterscheiden 2 Flle a a

Damit ist auch die Sprache L regulr, denn a L=

Wir machen uns eine Tabelle: 1,1 a = a 1,2 b a b (a ba b) 11 2,1 b ba 2,2 a

L0 L0 (L0 ) L0 11 11 11 11 ( a) ( a) ( a) = a L0 L0 (L0 ) L0 12 11 11 12 b ( a)( a) b = ab L0 L0 (L0 ) L0 11 11 21 21 b b(a) ( a) = ba L0 L0 (L0 ) L0 22 21 11 12 a b( a) b = a ba b L1 L1 (L1 ) L0 21 22 12 11 a a b( a ba b) ba

Vergleich regulre kontextfreie Sprachen a

Daraus knnen wir direkt eine Herleitung erzeugen o S a1 q1 a1 a2 q2 . . . a1 a2 . . . an qn a1 a2 . . . an = w

Normalformen von kontextfreien Grammatiken

2. Falls B A1 . . . Ak 3. Gehe zu Schritt 1

Induktiv schlieen wir auf n.

Abschlusseigenschaften Kontextfreier Sprachen

Der Algorithmus legt eine Tabelle an

Push-Down Automaten (Kellerautomaten)

die Folgekonguration von k1 . Bedeutung

Wir denieren als die reexive und transitive Hlle von u M k k k = k0 M

Die von einem Kellerautomaten akzeptierte Sprache L(M)

und es ist w = uv mit v

Turingmaschinen zum Rechnen

(0,B,B) (0,B,B) (1,B,B) (0,0,B) (0,*,B) (0,0,B) (B,0,B) (0,0,B) (1,0,B)

(0,*,B) (0,0,B) (1,B,B) (0,0,B) (0,*,B) (0,0,B) (B,0,0) (0,0,B) (1,0,B)

(R,R,S) (R,R,S) (R,L,S) (S,L,S) (R,R,S) (R,R,S) (L,S,R) (L,S,S) (R,S,S)

Ende von 0y ist erreicht auf Band 1 zurcklaufen u

Abschlusseigenschaften entscheidbarer und rekursiv aufzhlbarer Mengen a

Addition plus : N2 N : (x, y) x + y

Multiplikation (geht genauso wie die Addition) mal : N2 N : (x, y) x + y

1 v(x + 1) = U2 (x, v(x))

modizierte Subtraktion xy = xy 0 x>y sonst

Normierung von Sprachen und Turingmaschinen

Nicht-rekursiv aufzhlbare Sprachen a

Die Universelle Turingmaschine

L1 ist also enfacher als L2 , man schreibt L1 L2

ist berechenbar. Es gilt

Satz von Rice

falls M w nicht akzeptiert L falls M w akzeptiert

Sprachklasse regulr a det. kontextfrei kontextfrei entscheidbar rek. aufzhlbar a andere

f : (< M, w >) = Betrachte:

1 w L(M ) undef iniert sonst

Konsequenzen der Nichtentscheidbarkeit

Vorlesung 9 Pumping-Lemma fr kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . u Nicht-Kontextfreie Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Abschlusseigenschaften Kontextfreier Sprachen . . . . . . . . . . . . . . . . . . . . . . . .

Das könnte Ihnen auch gefallen

(0,,B) (0,0,B) (1,B,B) (0,0,B) (0,,B) (0,0,B) (B,0,0) (0,0,B) (1,0,B)