Lösungen TheGI TI Probeklausur vom 19.01.06 - Versionsgeschichte

130.149.17.59: /* Aufgabe 3 */

2011-02-16T11:52:34Z

‎Aufgabe 3

130.149.17.59: /* Aufgabe 3 */

2011-02-16T11:51:35Z

‎Aufgabe 3

Bastla: format + typo

2010-02-11T02:10:08Z

format + typo

Bastla: format

2010-02-11T02:07:50Z

format

Bastla: typo

2010-02-11T01:58:52Z

typo

Bastla: hübscher

2010-02-11T01:57:26Z

hübscher

Bastla: format

2010-02-11T01:47:45Z

format

Bastla: Ergänzung + typos

2010-02-11T01:16:30Z

Ergänzung + typos

Bastla: ja, kann man

2010-02-11T00:53:21Z

ja, kann man

Bastla: typos und Formulierung angepasst

2010-02-11T00:10:34Z

typos und Formulierung angepasst

@@ Zeile 30: / Zeile 30: @@
 ===Aufgabe 3===
 # {''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 nicht mit ''a''}

@@ Zeile 30: / Zeile 30: @@
 ===Aufgabe 3===
 # {''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;+ : ''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 nicht mit ''a''}

@@ Zeile 163: / Zeile 163: @@
 ====10====
-   R+S = S+R (Richtig, braucht keines Nachweises)
+   (1) R+S = S+R (Richtig, braucht keinen Nachweis)
-   RS = SR   (Falsch, braucht keines Nachweises)
+   (2) RS = SR   (Falsch, braucht keinen Nachweis)
-   (RS)* = (R*S*)*  (Falsch)
+   (3) (RS)* = (R*S*)*  (Falsch)
-  Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)* -
+      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!
+      Mit (RS)* lässt sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!
-   (R+S)* = (R*+S*)* (Richtig)
+   (4) (R+S)* = (R*+S*)* (Richtig)
-  Direkter Beweis: (R+S)* = (R*S*)*
+      Direkter Beweis: (R+S)* = (R*S*)*
-                          = ((R*)*(S*)*)*
+                              = ((R*)*(S*)*)*
-                          = (R*+S*)*
+                              = (R*+S*)*
 ===Aufgabe 11===

@@ Zeile 162: / Zeile 162: @@
 ====10====
    R+S=S+R (Richtig, braucht keines Nachweises)
-   RS=SR   (Falsch, braucht keines Nachweises)
+   RS = SR   (Falsch, braucht keines Nachweises)
-   (RS)*= (R*S*)*  (Falsch)
+   (RS)* = (R*S*)*  (Falsch)
-   Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)*, mit (RS)* laesst sich aber z.B. (RR...R) i.A. nicht bilden => Widerspruch!
+   Angenommen es gilt: Da (R*S*)*=(R+S)*, muss gelten (RS)*=(R+S)* -
-   (R+S)*=(R*+S*)* (Richtig)
+   (R+S)* = (R*+S*)* (Richtig)
-   Direkter Beweis: (R+S)*=(R*S*)*=((R*)*(S*)*)*=(R*+S*)*
+   Direkter Beweis: (R+S)* = (R*S*)*
 ===Aufgabe 11===

@@ Zeile 159: / Zeile 159: @@
    F2 = (aab)E*
       = aab(a*b*)*
-   F3 = (aab)+            (Iteration setz mind. das einmalige Vorkommen voraus)
+   F3 = (aab)+            (Iteration setzt mindestens das einmalige Vorkommen voraus)
 ====10====

@@ Zeile 155: / Zeile 155: @@
 ====9====
-   F1=E*(aab)E*=(a*b*)*aab(a*b*)*
+   F1 = E*(aab)E*
-   F2=aabE*=aab(a*b*)*
+     = (a*b*)*aab(a*b*)*
-   F3=(aab)+ (Iteration setz mind. das einmalige Vorkommen voraus)
+   F2 = (aab)E*
 ====10====

@@ Zeile 145: / Zeile 145: @@
 ====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}
+   L1 = {x aus E* : in x kommt a mind. einmal vor}
-   L3={x aus {aa, bb}*}={x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
+   L2 = {x aus E* : x fängt mit a oder endet mit b}
-   L4={x aus (ab)*}={x : x ist die Iteration des Strings ab oder das leere Wort}
+   L3 = {x aus {aa, bb}*}
-   L5={e}
+     = {x : x ist ein Wort beliebiger Länge bestehend aus den Strings aa und bb}
 ====9====

@@ Zeile 103: / Zeile 103: @@
 ===Aufgabe 6===
-:a) ''L<sub>3</sub>'' = {''x'' &isin; &Sigma;*; ''x'' = a(a+ba)*}
+: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)
 ::{| border="1" style="margin:1em 1em 1em 0; border-style:solid; border-width:1px; border-collapse:collapse; empty-cells:show"
@@ Zeile 118: / Zeile 118: @@
 |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 und mit jedem weiteren ''a'' oder ''b'' in q<sub>2</sub> bleibt. 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===

@@ Zeile 55: / Zeile 55: @@
 ===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)

@@ Zeile 258: / Zeile 258: @@
 ===Aufgabe 18===
+#
 #* Die Sprache L<sub>2</sub> ist komplementär zur Sprache L<sub>1</sub>
@@ Zeile 263: / Zeile 264: @@
 #*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 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 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 ein Automat für diese Sprache terminiert für Wörter aus der Sprache, sein Zustand für Wörter die nicht aus der Sprache sind aber undefiniert ist, er möglicherweise also nicht terminiert für Wörter die nicht aus der Sprache sind.
+#* 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.
+#* 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"