Sitzung: Jeden Freitag in der Vorlesungszeit ab 16 Uhr c. t. im MAR 0.005. In der vorlesungsfreien Zeit unregelmäßig (Jemensch da?). Macht mit!

Lösungen TheGI TI Probeklausur vom 19.01.06: Unterschied zwischen den Versionen

(Aufgabe 6)
(Aufgabe 3)
 
(47 dazwischenliegende Versionen von 14 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent (Sebastian Bab?) war sich beim Vorrechnen oft selbst nicht sicher...
+
Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...
 
===Aufgabe 1===
 
===Aufgabe 1===
 
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar
 
:im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar
Zeile 29: Zeile 29:
  
 
===Aufgabe 3===
 
===Aufgabe 3===
# {''x'' ∈ Σ*; ''x'' beginnt mit ''a'' und endet mit ''b''}
+
# {''x'' &isin; &Sigma;* : ''x'' beginnt mit ''a'' und endet mit ''b''} <br> auch: {''axb'' : ''x'' &isin; &Sigma;*}
# {''x'' &isin; &Sigma;*; ''x'' beginnt mit ''a'' oder ''b''}
+
# {''x'' &isin; &Sigma;<sup>+</sup> : ''x'' beginnt mit ''a'' oder ''b''}
# {''x'' &isin; &Sigma;*; ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
+
# {''x'' &isin; &Sigma;* : ''x'' beginnt mit ''a'' oder ''b'' oder ist das leere Wort}
# {''x'' &isin; &Sigma;*; ''x'' beginnt nicht mit ''a''}
+
# {''x'' &isin; &Sigma;* : ''x'' beginnt nicht mit ''a''}
 
# {&oslash;,{''a''},{''b''},{''a,b''}}
 
# {&oslash;,{''a''},{''b''},{''a,b''}}
 
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}
 
# {(''a,a''),(''a,b''),(''b,a''),(''b,b'')}
Zeile 38: Zeile 38:
 
===Aufgabe 4===
 
===Aufgabe 4===
 
:''hier müßte man irgendwie Bilder hochladen können...''
 
:''hier müßte man irgendwie Bilder hochladen können...''
 +
 +
::{|  border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 +
!
 +
!a
 +
!b
 +
|-
 +
|&rarr;q<sub>0</sub>
 +
|q<sub>1</sub>
 +
|q<sub>0</sub>
 +
|-
 +
|q<sub>1</sub>
 +
|q<sub>1</sub>
 +
|q<sub>1</sub>
 +
|}
  
 
===Aufgabe 5===
 
===Aufgabe 5===
  
:a) ''L<sub>2</sub>'' = {''x'' &isin; &Sigma;*; ''x'' beginnt mit ''ab''}
+
:a) ''L<sub>2</sub>'' = {''abx'' | x &isin; &Sigma;*}  = {''x'' &isin; &Sigma;*; ''x'' beginnt mit ''ab''}  
 +
 
 
:b)
 
:b)
 
::{|  border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 
::{|  border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
Zeile 64: Zeile 79:
 
|q<sub>3</sub>
 
|q<sub>3</sub>
 
|}
 
|}
:c) einfach nur normale und Endzustände vertauschen
+
:c) einfach nur normale und Endzustände vertauschen:
 +
::{|  border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 +
!
 +
!a
 +
!b
 +
|-
 +
|&rarr;*q<sub>0</sub>
 +
|q<sub>1</sub>
 +
|q<sub>3</sub>
 +
|-
 +
|*q<sub>1</sub>
 +
|q<sub>3</sub>
 +
|q<sub>2</sub>
 +
|-
 +
|q<sub>2</sub>
 +
|q<sub>2</sub>
 +
|q<sub>2</sub>
 +
|-
 +
|*q<sub>3</sub>
 +
|q<sub>3</sub>
 +
|q<sub>3</sub>
 +
|}
  
 
===Aufgabe 6===
 
===Aufgabe 6===
:a) ''L<sub>3</sub>'' = {''x'' &isin; &Sigma;*; ''x'' = (a<sup>n</sup>b)*a<sup>m</sup>; n,m &ge; 1}  ''dies ist meine Lösung. Über diese Aufgabe wurde lange diskutiert ohne dass etwas Vernünftiges heraus kam.''
+
:a) ''L<sub>3</sub>'' = {''x'' &isin; &Sigma;*; ''x'' = a(a+ba)*}  = {''x'' &isin; &Sigma;*; ''x'' beginnt mit ''a'' und es folgen beliebig viele ''a'' oder ''ba''}
 
:b)
 
:b)
 
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
Zeile 82: Zeile 118:
 
|q<sub>0</sub>
 
|q<sub>0</sub>
 
|}
 
|}
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeform werden muß. D.h. man muß einen Zustand q<sub>2</sub> hinzufügen, der von q<sub>0</sub> aus mit dem ''b'' erreicht wird. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.
+
:c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q<sub>2</sub> hinzufügen, der von q<sub>0</sub> aus mit dem ''b'' erreicht wird und mit jedem weiteren ''a'' oder ''b'' in q<sub>2</sub> bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.
  
 
===Aufgabe 7===
 
===Aufgabe 7===
Zeile 88: Zeile 124:
 
:b) ''bild einfügen''
 
:b) ''bild einfügen''
 
:c)
 
:c)
::{| border="1"
+
::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 
!
 
!
 
!a
 
!a
Zeile 102: Zeile 138:
 
|}
 
|}
  
===Aufgabe 8,9,10===
+
===Aufgabe 8, 9, 10===
:''Lösungen werden in einer kommenden Vorlesung nachgereicht''
+
 
 +
Es gilt allgemein: E*=(a*b*)*=(a+b)*.
 +
Ist halt so... Wer nicht faul ist, kann nachrechnen ;-)
 +
Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache.<br> Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.
 +
 
 +
====8====
 +
 
 +
  L1 = {x aus E* : in x kommt a mind. einmal vor}
 +
  L2 = {x aus E* : x fängt mit a oder endet mit b}
 +
  L3 = {x aus {aa, bb}*}
 +
    = {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
 +
  L4 = {x aus (ab)*}
 +
    = {x : x ist die Iteration des Strings ab oder das leere Wort}
 +
  L5 = {&epsilon;}
 +
 
 +
====9====
 +
  F1 = E*(aab)E*
 +
    = (a*b*)*aab(a*b*)*
 +
  F2 = (aab)E*
 +
    = aab(a*b*)*
 +
  F3 = (aab)+            (Iteration setzt mindestens das einmalige Vorkommen voraus)
 +
 
 +
====10====
 +
 
 +
  (1) R+S = S+R (Richtig, braucht keinen Nachweis)
 +
 
 +
  (2) RS = SR  (Falsch, braucht keinen Nachweis)
 +
 
 +
  (3) (RS)* = (R*S*)*  (Falsch)
 +
      Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)* -
 +
      Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!
 +
 
 +
  (4) (R+S)* = (R*+S*)* (Richtig)
 +
      Direkter Beweis: (R+S)* = (R*S*)*
 +
                              = ((R*)*(S*)*)*
 +
                              = (R*+S*)*
  
 
===Aufgabe 11===
 
===Aufgabe 11===
Zeile 113: Zeile 184:
 
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
 
: Es gelten die drei Eigenschaften des Pumping-Lemmas:
 
:#''y'' &ne; &epsilon; : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
 
:#''y'' &ne; &epsilon; : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
:#''|xy|'' &lt; ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
+
:#''|xy|'' &le; ''n'' : gilt, da wir die erste Schleife in A gewählt haben.
 
:#''xy''<sup>k</sup>''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.
 
:#''xy''<sup>k</sup>''z'' in ''L'' : Schleifen können mehrfach oder gar nicht abgearbeitet werden.
  
Zeile 121: Zeile 192:
  
 
===Aufgabe 13===
 
===Aufgabe 13===
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy<sup>2</sup>z &isin; L. Für dieses Wort gilt aber xy<sup>2</sup>z = a<sup>n-|y|</sup>a<sup>|y|+|y|</sup>a<sup>n</sup>. Da n-|y|+|y|+|y| = n+|y| &ne; n gilt, stehen zu Beginn des Wortes mehr a's als am Ende &rarr; Widerspruch!
+
: (weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich ''w'' in ''w''=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy<sup>2</sup>z &isin; L. Für dieses Wort gilt aber xy<sup>2</sup>z = a<sup>n-|y|</sup>a<sup>|y|+|y|</sup> b a<sup>n</sup>. Da n-|y|+|y|+|y| = n+|y| &ne; n gilt, stehen zu Beginn des Wortes mehr a's als am Ende &rarr; Widerspruch!
  
 
===Aufgabe 14===
 
===Aufgabe 14===
Zeile 130: Zeile 201:
  
 
===Aufgabe 15===
 
===Aufgabe 15===
:von oben nach unten
+
 
:*Typ-0; allgemeine
+
Von oben nach unten einzutragen:
:*Typ-1; kontext-sensitive
+
 
:*Typ-2; kontext-freie
+
* Typ-0: allgemeine Sprachen
:*Typ-3; reguläre
+
* Typ-1: kontextsensitive Sprachen
 +
* Typ-2: kontextfreie Sprachen
 +
* Typ-3: reguläre Sprachen
 +
 
 +
Ergänzung: Typ-0 kann noch einmal in ''semientscheidbar'' und ''enscheidbar'' aufgeteilt werden (von oben nach unten).
  
 
===Aufgabe 16===
 
===Aufgabe 16===
 
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (<u>&Sigma;,V,S,P</u>), wobei <u> &Sigma;</u> ein <u> Alphabet</u>, <u>V</u> eine Menge von <u> Variablen</u>, <u>S</u> die <u> Startvariable</u> und <u> P </u> eine Menge von <u> Produktionsregeln </u> ist.
 
:''Lückentext'': Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik ''G'' ist ein Tupel ''G'' = (<u>&Sigma;,V,S,P</u>), wobei <u> &Sigma;</u> ein <u> Alphabet</u>, <u>V</u> eine Menge von <u> Variablen</u>, <u>S</u> die <u> Startvariable</u> und <u> P </u> eine Menge von <u> Produktionsregeln </u> ist.
:Die Klasse der regulären Sprachen enthält Sprachen, die über <u>...</u> Grammatiken gebildet werden können. Eine Grammatik heißt <u>...</u>, wenn alle ihre Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Eigenschaften u &isin; <u> V </u> sowie ''v'' &isin; <u> &Sigma; </u> oder ''v'' &isin; <u> &Sigma; &omicron; V </u> erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''L<sub>rg</sub>'' = <u>{a<sup>n</sup> | n &ge; 1}</u>. Reguläre Sprachen können entweder <u> endlich</u> oder <u>unendlich</u> sein. Die Klasse der <u>endlichen</u> Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei <u> gleich </u> der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
+
:Die Klasse der regulären Sprachen enthält Sprachen, die über <u>regulären</u> Grammatiken gebildet werden können. Eine Grammatik heißt <u>regulär</u>, wenn alle ihre Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Eigenschaften u &isin; <u> V </u> sowie ''v'' &isin; <u> &Sigma; </u> oder ''v'' &isin; <u> &Sigma; &omicron; V </u> erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache ''L<sub>rg</sub>'' = <u>{a<sup>n</sup> | n &ge; 1}</u>. Reguläre Sprachen können entweder <u> endlich</u> oder <u>unendlich</u> sein. Die Klasse der <u>endlichen</u> Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei <u> gleich </u> der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
 
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Form ''u'' &isin; <u>V</u> sowie ''v'' &isin; <u> (&Sigma;&cup;V)*</u> haben. Damit ist natürlich jede <u>reguläre</u> Grammatik auch eine <u> kontextfreie</u> Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''L<sub>kf</sub>'' = <u>{a<sup>n</sup>b<sup>n</sup>|n &gt; 1} </u>. Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in <u>Chomsky-Normalform</u> konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei <u>gleich</u>. Die Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' von Grammatiken in <u> Chomsky-Normalform</u> sind hierbei von der Form ''u'' &isin; <u>V</u> und ''v'' &isin; <u> &Sigma;</u> oder ''u'' &isin; <u> V</u> und ''v'' &isin; <u> V &omicron; V</u>. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei <u> ungleich </u> der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von <u> deterministischen</u> Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von <u>nichtdeterministischen</u> Kellermaschinen akzeptiert wird.
 
:Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Form ''u'' &isin; <u>V</u> sowie ''v'' &isin; <u> (&Sigma;&cup;V)*</u> haben. Damit ist natürlich jede <u>reguläre</u> Grammatik auch eine <u> kontextfreie</u> Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist ''L<sub>kf</sub>'' = <u>{a<sup>n</sup>b<sup>n</sup>|n &gt; 1} </u>. Jede kontextfreie Grammatik ''G'' läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik ''G'' ' in <u>Chomsky-Normalform</u> konvertieren. Die von ''G'' und ''G'' ' erzeugten Sprachen sind hierbei <u>gleich</u>. Die Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' von Grammatiken in <u> Chomsky-Normalform</u> sind hierbei von der Form ''u'' &isin; <u>V</u> und ''v'' &isin; <u> &Sigma;</u> oder ''u'' &isin; <u> V</u> und ''v'' &isin; <u> V &omicron; V</u>. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei <u> ungleich </u> der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von <u> deterministischen</u> Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von <u>nichtdeterministischen</u> Kellermaschinen akzeptiert wird.
 
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Eigenschaft ''u'' &isin; <u> (&Sigma;&cup;V)*&omicron;V&omicron;(&Sigma;&cup;V)*</u> und ''v'' &isin; <u>(&Sigma;&cup;V)* </u> mit |''u''| <u> &le; </u> |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''L<sub>ks</sub>'' = <u>{a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>| n &ge; 1}</u>
 
:Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln ''u'' &rarr; ''v'' &isin; ''P'' die Eigenschaft ''u'' &isin; <u> (&Sigma;&cup;V)*&omicron;V&omicron;(&Sigma;&cup;V)*</u> und ''v'' &isin; <u>(&Sigma;&cup;V)* </u> mit |''u''| <u> &le; </u> |''v''| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist ''L<sub>ks</sub>'' = <u>{a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>| n &ge; 1}</u>
Zeile 144: Zeile 219:
  
 
===Aufgabe 17===
 
===Aufgabe 17===
 +
:{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 +
!
 +
!Schnitt
 +
!Vereinigung
 +
!Komplement
 +
!Verkettung
 +
!Stern
 +
|-
 +
|Typ 3
 +
|ja
 +
|ja
 +
|ja
 +
|ja
 +
|ja
 +
|-
 +
|Det. kf
 +
|nein
 +
|nein
 +
|ja
 +
|nein
 +
|nein
 +
|-
 +
|Typ 2
 +
|nein
 +
|ja
 +
|nein
 +
|ja
 +
|ja
 +
|-
 +
|Typ 1
 +
|ja
 +
|ja
 +
|ja
 +
|ja
 +
|ja
 +
|-
 +
|Typ 0
 +
|ja
 +
|ja
 +
|nein
 +
|ja
 +
|ja
 +
|}
 +
 +
===Aufgabe 18===
 +
 +
#
 +
#* Die Sprache L<sub>2</sub> ist komplementär zur Sprache L<sub>1</sub>
 +
#* L<sub>1</sub> ist das spezielle Halteproblem für Turingmaschinen
 +
#*Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. &omega; ist Eingabe und Codierung von M<sub>&omega;</sub>
 +
#
 +
#* Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
 +
#* Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
 +
#* Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
 +
#
 +
::{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 +
!Aussage
 +
!wahr
 +
!falsch
 +
|-
 +
|Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen.
 +
|x
 +
|
 +
|-
 +
|Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen.
 +
|
 +
|x
 +
|-
 +
|Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind.
 +
|x
 +
|
 +
|-
 +
|Das spezielle Halteproblem ist nicht entscheidbar.
 +
|x
 +
|
 +
|-
 +
|Das spezielle Halteproblem ist semi-entscheidbar.
 +
|x
 +
|
 +
|-
 +
|Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar.
 +
|x
 +
|
 +
|}
 +
 +
===Aufgabe 19===
 +
1.
 +
: - SAT &isin; NP
 +
: - Für alle L &isin; NP muss L polynomiell reduzierbar auf SAT sein.
 +
2.
 +
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 +
!Aussage
 +
!wahr
 +
!falsch
 +
|-
 +
|Die Klasse P enthält nur entscheidbare Sprachen.
 +
|x
 +
|
 +
|-
 +
|Die Klasse NP enthält nur entscheidbare Sprachen.
 +
|x
 +
|
 +
|-
 +
|Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt.
 +
|x
 +
|
 +
|-
 +
|Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
 +
|
 +
|x
 +
|-
 +
|Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP.
 +
|x
 +
|
 +
|}
 +
3.
 +
:{| border="1" style="margin:1em 1em 1em 0; text-align:left; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
 +
!Aussage
 +
!bekannt
 +
!unbekannt
 +
|-
 +
|Die Klasse P ist Teilklasse der Klasse NP.
 +
|x
 +
|
 +
|-
 +
|Die Klasse NP ist Teilklasse der Klasse P.
 +
|
 +
|x
 +
|-
 +
|Die Klasse P ist gleich der Klasse NP.
 +
|
 +
|x
 +
|-
 +
|Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat.
 +
|
 +
|x
 +
|}
 +
 +
:Quelle [http://www-fs.informatik.uni-tuebingen.de/skripte/info3.pdf für det.kf.] und [http://de.wikipedia.org/wiki/Chomsky-Hierarchie Restliche]
 +
:Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89

Aktuelle Version vom 16. Februar 2011, 11:52 Uhr

Für die Lösungen wird natürlich keine Garantie übernommen. Der Assistent Sebastian Bab war sich beim Vorrechnen manchmal selbst nicht sicher...

Aufgabe 1

im Lückentext einsetzen: endliche, endlich, abzählbar unendlich, endlich, abzählbar unendlich, Mächtigkeit, Mächtigkeit, überabzählbar

Aufgabe 2

a ∈ Σ Σⁱ = Σ ε ∉ Σ+ ε ∈ Σ*
ø ⊆ Σ+ ø ⊆ Σ* a ∈ Σ* {ε} ∉ Σ*
Σ² ⊆ Σ* ø ∈ P(Σ*) {ε} ∈ P(Σ*) Σ² ∈ P(Σ*)
{aa,bb,ab,ba} = Σ² {xab : x ∈ Σ*} = {x ∈ Σ* : x endet mit ab}
{ab,bb,aba} ⊆ Σ* {axab : x ∈ Σ*} ⊆ {x ∈ Σ* : x endet mit ab}

Aufgabe 3

  1. {x ∈ Σ* : x beginnt mit a und endet mit b}
    auch: {axb : x ∈ Σ*}
  2. {x ∈ Σ+ : x beginnt mit a oder b}
  3. {x ∈ Σ* : x beginnt mit a oder b oder ist das leere Wort}
  4. {x ∈ Σ* : x beginnt nicht mit a}
  5. {ø,{a},{b},{a,b}}
  6. {(a,a),(a,b),(b,a),(b,b)}

Aufgabe 4

hier müßte man irgendwie Bilder hochladen können...
a b
→q0 q1 q0
q1 q1 q1

Aufgabe 5

a) L2 = {abx | x ∈ Σ*} = {x ∈ Σ*; x beginnt mit ab}
b)
a b
→q0 q1 q3
q1 q3 q2
*q2 q2 q2
q3 q3 q3
c) einfach nur normale und Endzustände vertauschen:
a b
→*q0 q1 q3
*q1 q3 q2
q2 q2 q2
*q3 q3 q3

Aufgabe 6

a) L3 = {x ∈ Σ*; x = a(a+ba)*} = {x ∈ Σ*; x beginnt mit a und es folgen beliebig viele a oder ba}
b)
a b
→q0 q1 -
*q1 q1 q0
c) Der Trick ist, dass der DEA erst in einen totalen DEA umgeformt werden muss. D.h. man muss einen Zustand q2 hinzufügen, der von q0 aus mit dem b erreicht wird und mit jedem weiteren a oder b in q2 bleibt. Danach wie bei Aufgabe 5 einfach die Zustände invertieren.

Aufgabe 7

a) L4 = {x ∈ Σ*; x endet mit a}
b) bild einfügen
c)
a b
→q0 {q1,q0} {q0}
*q1 ø ø

Aufgabe 8, 9, 10

Es gilt allgemein: E*=(a*b*)*=(a+b)*. Ist halt so... Wer nicht faul ist, kann nachrechnen ;-) Mit der Iteration ist es ein wenig verwirrend. Als Informatiker könnte man ja auch sagen "die 0-te Iteration von irgendwas". Hier ist aber offensichtlich unter Iteration eine nichtleere Wiederholung gemeint. Ist aber eigentlich eine Vereinbarungssache.
Und bei uns in der Klausur vom 12.02.2009 hab ich einen Tutoren gefragt und der meinte bei Iteration ist auch die 0-mal wiederholung gemein also ein *.

8

 L1 = {x aus E* : in x kommt a mind. einmal vor}
 L2 = {x aus E* : x fängt mit a oder endet mit b}
 L3 = {x aus {aa, bb}*}
    = {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
 L4 = {x aus (ab)*}
    = {x : x ist die Iteration des Strings ab oder das leere Wort}
 L5 = {ε}

9

 F1 = E*(aab)E*
    = (a*b*)*aab(a*b*)*
 F2 = (aab)E*
    = aab(a*b*)*
 F3 = (aab)+            (Iteration setzt mindestens das einmalige Vorkommen voraus)

10

 (1) R+S = S+R (Richtig, braucht keinen Nachweis)
 
 (2) RS = SR   (Falsch, braucht keinen Nachweis)
 
 (3) (RS)* = (R*S*)*  (Falsch)
     Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)* -
     Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!
 
 (4) (R+S)* = (R*+S*)* (Richtig)
     Direkter Beweis: (R+S)* = (R*S*)*
                             = ((R*)*(S*)*)*
                             = (R*+S*)*

Aufgabe 11

(Fortsetzung des Ansatzes) Da das Wort w mehr Zeichen enthält als der Automat Zustände hat, muß bei der Ableitung von w ein Zustand in A mindestens 2x besucht worden sein. Sei qs der erste Zustand in der Ableitung von w, bei dem dies auftritt.
Zerlege w wie folgt: w=xyz mit:
  • x ist das Wort, welches bis zum ersten Auftreten von qs von A gelesen wird.
  • y ist das Wort, welches vom Automaten in der Schleife von qs nach qs gelesen wird.
  • z ist der Rest des Wortes w.
Es gelten die drei Eigenschaften des Pumping-Lemmas:
  1. y ≠ ε : offensichtlich, da jede Schleife mindestens eine Zahl beinhaltet.
  2. |xy|n : gilt, da wir die erste Schleife in A gewählt haben.
  3. xykz in L : Schleifen können mehrfach oder gar nicht abgearbeitet werden.

Aufgabe 12

a) wähle n=5
b) w=abaaa ; x=ab, y=a, z=aa; xy3z=abaaaaa

Aufgabe 13

(weiter nach Ansatz) Nach Definition des Pumping-Lemma läßt sich w in w=xyz zerlegen. Nach Eigenschaft (2) des PL kann der Teil xy nur aus a's bestehen. y ist mindestens ein a. Nach (3) ist dann auch das Wort xy2z ∈ L. Für dieses Wort gilt aber xy2z = an-|y|a|y|+|y| b an. Da n-|y|+|y|+|y| = n+|y| ≠ n gilt, stehen zu Beginn des Wortes mehr a's als am Ende → Widerspruch!

Aufgabe 14

a) bilder...
b)
  1. S⇒ aS⇒ aaSbS⇒ aaaSbSbS⇒ aaabSbS⇒ aaabbS⇒ aaabb
  2. S⇒ aSbS⇒ aaSbS⇒ aaaSbSbS⇒ aaabSbS⇒ aaabbS⇒ aaabb

Aufgabe 15

Von oben nach unten einzutragen:

  • Typ-0: allgemeine Sprachen
  • Typ-1: kontextsensitive Sprachen
  • Typ-2: kontextfreie Sprachen
  • Typ-3: reguläre Sprachen

Ergänzung: Typ-0 kann noch einmal in semientscheidbar und enscheidbar aufgeteilt werden (von oben nach unten).

Aufgabe 16

Lückentext: Die Chomsky-Hierarchie klassifiziert die durch Grammatiken erzeugbaren Sprachen über Eigenschaften der Produktionsregeln der Grammatiken. Eine Grammatik G ist ein Tupel G = (Σ,V,S,P), wobei Σ ein Alphabet, V eine Menge von Variablen, S die Startvariable und P eine Menge von Produktionsregeln ist.
Die Klasse der regulären Sprachen enthält Sprachen, die über regulären Grammatiken gebildet werden können. Eine Grammatik heißt regulär, wenn alle ihre Produktionsregeln uvP die Eigenschaften u ∈ V sowie v Σ oder v Σ ο V erfüllen. Ein Beispiel einer typischen regulären Sprache ist die Sprache Lrg = {an | n ≥ 1}. Reguläre Sprachen können entweder endlich oder unendlich sein. Die Klasse der endlichen Sprachen bildet hierbei eine Teilklasse der regulären Sprachen. Reguläre Sprachen werden von enlichen Automaten erkannt. Endliche Automaten können deterministisch oder nichtdeterministisch sein. Die Klasse der von deterministischen endlichen Automaten akzeptierten Sprachen ist hierbei gleich der Klasse der von nichtdeterministischen endlichen Automaten akzeptierten Sprachen.
Die kontextfreien Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln uvP die Form uV sowie v (Σ∪V)* haben. Damit ist natürlich jede reguläre Grammatik auch eine kontextfreie Grammatik. Ein typisches Beispiel einer kontextfreien Sprache ist Lkf = {anbn|n > 1} . Jede kontextfreie Grammatik G läßt sich durch geeignetes Umformen der Regeln der Grammatik in eine Grammatik G ' in Chomsky-Normalform konvertieren. Die von G und G ' erzeugten Sprachen sind hierbei gleich. Die Produktionsregeln uvP von Grammatiken in Chomsky-Normalform sind hierbei von der Form uV und v Σ oder u V und v V ο V. Kontextfreie Sprachen werden von deterministsischen oder nichtdeterministischen Kellermaschinen erkannt. Die Klasse der don deterministischen Kellermaschinen akzeptierten Sprachen ist hierbei ungleich der Klasse der von nichtdeterministischen Kellerautomaten akzeptierten Sprachen. Palindrome sind Worte über einem Alphabet, die von vorne gelesen das selbe Wort ergeben wie von hinten gelesen. Die Sprache der Palindrome mit Trennzeichen läßt sich hierbei auch von deterministischen Kellermaschinen akzeptieren, wohingegen die Sprache der Palindrome ohne Trennzeichen nur von nichtdeterministischen Kellermaschinen akzeptiert wird.
Die kontextsensitiven Sprachen werden durch solche Grammatiken gebildet, deren Produktionsregeln uvP die Eigenschaft u (Σ∪V)*οVο(Σ∪V)* und v(Σ∪V)* mit |u| |v| erfüllen. Ein Beispiel einer typischen kontextsensitiven Sprache ist Lks = {anbncn| n ≥ 1}
Die allgemeinen Sprachen werden ebenfalls über Grammatiken gebildet, wobei die Produktionsregeln dieser Grammatiken keinen Einschränkungen unterliegen. Ein typisches Beispiel einer allgemeinen Sprache ist das Halteproblem.

Aufgabe 17

Schnitt Vereinigung Komplement Verkettung Stern
Typ 3 ja ja ja ja ja
Det. kf nein nein ja nein nein
Typ 2 nein ja nein ja ja
Typ 1 ja ja ja ja ja
Typ 0 ja ja nein ja ja

Aufgabe 18

    • Die Sprache L2 ist komplementär zur Sprache L1
    • L1 ist das spezielle Halteproblem für Turingmaschinen
    • Jede Turingmaschine lässt sich selbst mit Hilfe ihres Eingabealphabetes codieren. ω ist Eingabe und Codierung von Mω
    • Eine Sprache ist entscheidbar, wenn es einen Automaten gibt der nach Eingabe eines endlichen Wortes hält und dann entschieden ist, ob dieses Wort zu der Sprache gehört oder nicht.
    • Eine Sprache ist semi-entscheidbar, wenn es einen Automaten/Algorithmus gibt, der für Wörter aus dieser Sprache terminiert (und "ja" antwortet). Allerdings ist sein Zustand für Wörter, die nicht aus der Sprache sind, undefiniert und er terminiert möglicherweise nicht für diese und läuft unendlich weiter.
    • Eine Sprache ist unentscheidbar, wenn es Wörter aus der Sprache gibt für die keine Turing-Maschine hält. Oder, Zitat aus der Vorlesung: "Alles was nicht entscheidbar ist." ;-)
Aussage wahr falsch
Die Klasse der kontextfreien SPrachen enthält nur entscheidbare Sprachen. x
Die Klasse der allgemeinen (Typ-0-)Sprahcen enthält nur semi-entscheidbare Sürachen, aber keine entscheidbaren Sprachen. x
Es gibt allgemeine (Typ-0-)Sprachen, welche nicht kontextfrei, die aber dennoch entscheidbar sind. x
Das spezielle Halteproblem ist nicht entscheidbar. x
Das spezielle Halteproblem ist semi-entscheidbar. x
Das Komplement des speziellen Halteproblems ist unentscheidbar, also weder entscheidbar noch semi-entscheidbar. x

Aufgabe 19

1.

- SAT ∈ NP
- Für alle L ∈ NP muss L polynomiell reduzierbar auf SAT sein.

2.

Aussage wahr falsch
Die Klasse P enthält nur entscheidbare Sprachen. x
Die Klasse NP enthält nur entscheidbare Sprachen. x
Es gibt Sprachen A in NP, für die eine deterministische, polynomiell zeitbeschränkte Turingmaschine M existiert, so dass L(M)=A gilt. x
Sei A eine Sprache aus NP, welche auf das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP. x
Sei A eine Sprache aus NP, auf welche das Erfüllbarkeitsproblem für boolsche Ausdrücke SAT reduziert werden kann. Lässt sich nun eine deterministische, polynomiell zeitbeschränkte Turingmaschine M finden, für die L(M)=A gilt, so gilt notwendigerweise P = NP. x

3.

Aussage bekannt unbekannt
Die Klasse P ist Teilklasse der Klasse NP. x
Die Klasse NP ist Teilklasse der Klasse P. x
Die Klasse P ist gleich der Klasse NP. x
Jede NP-vollständige Sprache A kann nur dann von einer deterministischen Turingmaschine entschieden werden, wenn diese Turingmaschine exponentiellen Aufwand hat. x
Quelle für det.kf. und Restliche
Siehe gleiche Tabelle bei Schöning: Theoretische Informatik - kurzgefasst , S 89