BuK-Übung06

Aus ProgrammingWiki

< BuK < IIm11

Archivierte Version vom 2012-05-09T08:08:01+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Reduzierbarkeit
- 1.1 Aufgabe 1 (Max Wielsch, Raik Bienik)
- 1.2 Aufgabe 2 (Stefan Lüttke, Felix Nitsche)
2 Unentscheidbarkeitsbeweis
- 2.1 Aufgabe 1 (Ingo Körner, Christoph Ochmann)

Vorlesungsfolien

Aufgaben werden am 08.05. um 23:00 übertragen

Reduzierbarkeit

Aufgabe 1 (Max Wielsch, Raik Bienik)

(Aufgabe siehe: VL Slide 14)

Konstruieren sie eine Prozedur, welche prüft ob w die Form uu besitzt!

(define sublist
  (lambda (list start)
    (if (= start 0)
      list
      (sublist (cdr list) (- start 1)))))

(define size
  (lambda (list)
    (if (null? list)
      0
      (+ (size (cdr list)) 1))))

;checks if wordAsList has letterCount letter(s) at position start.
(define checkLetters
  (lambda (wordAsList start letter letterCount)
    (letrec ((worker (lambda (list letterCount)
        (if (= letterCount 0)
          '#t
          (if (equal? (car list) letter)
            (worker (cdr list) (- letterCount 1))
            '#f)))))
      (worker (sublist wordAsList start) letterCount))))

(define acceptor
  (lambda (w)
    (let* ((wAsList (string->list w))
	  (sizeofW (size wAsList)))
      (if (not (= (modulo sizeofW 6) 0))
        '#f
        (let ((letterCount (quotient sizeofW 6)))
          (if
            (and
              (checkLetters wAsList (* 0 letterCount) #\a letterCount)
              (checkLetters wAsList (* 1 letterCount) #\b letterCount)
              (checkLetters wAsList (* 2 letterCount) #\c letterCount)
              (checkLetters wAsList (* 3 letterCount) #\a letterCount)
              (checkLetters wAsList (* 4 letterCount) #\b letterCount)
              (checkLetters wAsList (* 5 letterCount) #\c letterCount))
            '#t
            '#f))))))

(acceptor "aaabbbcccaaabbbccc")

Aufgabe 2 (Stefan Lüttke, Felix Nitsche)

(Aufgabe siehe: VL Slide 15/16)

Beweisen Sie diesen Satz, indem Sie mittels Aussagenlogik die Äquivalenz dieser Aussage zum vorhergehenden Satz zeigen. Es handelt sich um die Kontraposition:

A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A

Verwenden Sie im Beweis die folgenden Aussagen:

A: P' ist entscheidbar. B: P ist reduzierbar auf P'. C: P ist entscheidbar.

Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:

A: P' ist entscheidbar

B: P ist reduzierbar auf P'

C: P ist entscheidbar

Als gegeben kann dabei nach Satz 1 betrachtet werden dass:

A \wedge B \Rightarrow C

zu beweisen ist:

\neg C \wedge B \Rightarrow \neg A

Beweis:

Zeile	A	B	C	E=A \wedge B	F=E\Rightarrow C	G=\neg C \wedge B	H = G \Rightarrow \neg A	I = F \Leftrightarrow H	Kommentar
\| 1	1	1	1	1	1	0	1	1	gegeben durch Satz 1
\| 2	1	1	0	1	0	1	0	1	falsch nach Satz 1
\| 3	1	0	1	0	1	0	1	1	...
\| 4	1	0	0	0	1	0	1	1	...
\| 5	0	1	1	0	1	0	1	1	...
\| 6	0	1	0	0	1	1	1	1	Einzig verbleibende Möglichkeit für \neg C \wedge B
\| 7	0	0	1	0	1	0	1	1	...
\| 8	0	0	0	0	1	0	1	1	...

In Zeile 6 befindet sich die einzig verbleibende Möglichkeit für \neg C \wedge B. Daraus kann abgelesen werden dass in dem Fall \neg A gilt, womit Satz 2 bewiesen ist.

Unentscheidbarkeitsbeweis

Aufgabe 1 (Ingo Körner, Christoph Ochmann)

(Aufgabe siehe: VL Slide 13)

Zeigen Sie die Unentscheidbarkeit von L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \} durch Reduktion des Halteproblems.

Lösungsansatz: Berechne aus der Eingabe <m> die Kodierung der Maschine M'. M' ist die Maschine, die ihre Eingabe löscht, dann <m> auf das Band schreibt und dann auf <m> weiterrechnet. <m> ist \in L_{\Sigma^{*}} genau dann, wenn M' termiert.</m></m></m></m>

BuK-Übung06

Inhaltsverzeichnis

Reduzierbarkeit

Aufgabe 1 (Max Wielsch, Raik Bienik)

Aufgabe 2 (Stefan Lüttke, Felix Nitsche)

Unentscheidbarkeitsbeweis

Aufgabe 1 (Ingo Körner, Christoph Ochmann)

Suche