Seite 1 von 1

Übungsblatt 13 Aufgabe 13.4 b)

BeitragVerfasst: 31 Jan 2014, 11:48
von s9evgres
Hallo,

wollt mal nachfragen, ob bei der Aufgabe wirklich die Sprache mit dem Wort epsilon gemeint ist, oder einfach die leere Sprache?

Falls das kein Fehler ist bin ich mir nämlich nicht sicher wie ich die Aufgabe lösen kann.

Danke schon mal

Re: Übungsblatt 13 Aufgabe 13.4 b)

BeitragVerfasst: 31 Jan 2014, 15:01
von jkaiser
Es wird hier bewusst nach der Sprache gefragt, welche genau epsilon erkennt.

Hier ein paar Hinweise:

  1. Beide Reduktionen nutzen H
  2. Das epsilon selbst hat keine besondere Bedeutung, es könnte auch ein beliebiges anderes, aber fixes, wort y sein.
  3. Die Lösung lässt sich auch auf zwei-elementige Mengen, 3-elementige Mengen, ... generalisieren
  4. Die Lösung verwendet eine geschickte kombination aus Konditional-Konstruktion und selbst-applikation

Ich denke das sollte ausreichen um eine Idee zu bekommen, für einen konkreteren Ansatz müssten SIe in eine der Officehours kommen

Re: Übungsblatt 13 Aufgabe 13.4 b)

BeitragVerfasst: 05 Feb 2014, 13:47
von s9evgres
ok vielen Dank.

Ich hätte noch eine Frage zum Teil a)...die Argumentation, mit der die letzte Äquivalenz gilt ist mir nicht ganz klar...kann mir die nochmal jemand erklären?
danke

Re: Übungsblatt 13 Aufgabe 13.4 b)

BeitragVerfasst: 10 Feb 2014, 19:14
von Dominik.Kirst
Hallo,

ich nehme an, es geht um den Schritt {y in S*|~pi' [x@x] e |y|} = S* äquivalent zu ~pi x x?
Die Überlegung ist folgende (Erinnerung pi x y := es gibt n in N, pi' x y n):

{y in S*|~pi' [x@x] e |y|} = S*
alle y in S* erfüllen ~pi' [x@x] e |y| (Mengengleichheit gilt, wenn alle y die "Spezialisierung" erfüllen)
alle n in N erfüllen ~pi' [x@x] e n (in S* finden sich beliebig lange Worte)
es gibt kein N, dass pi' [x@x]e n (Prädikatenlogische Negation von Quantoren)
~ pi [x@x] e (Definition wie in Erinnerung oben)
~ pi x x (Definition von [.] auf @)

Ist die Argumentation damit klar geworden?

Liebe Grüße,
Dominik