Übungsblatt 13 Aufgabe 13.4 b)

Hier könnt ihr euch über die Inhalte der Übungsblätter austauschen und Fragen stellen.

Übungsblatt 13 Aufgabe 13.4 b)

Beitragvon s9evgres » 31 Jan 2014, 11:48

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
s9evgres
 
Beiträge: 3
Registriert: 24 Okt 2013, 10:05

Re: Übungsblatt 13 Aufgabe 13.4 b)

Beitragvon jkaiser » 31 Jan 2014, 15:01

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
jkaiser
 
Beiträge: 17
Registriert: 13 Okt 2013, 16:50

Re: Übungsblatt 13 Aufgabe 13.4 b)

Beitragvon s9evgres » 05 Feb 2014, 13:47

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
s9evgres
 
Beiträge: 3
Registriert: 24 Okt 2013, 10:05

Re: Übungsblatt 13 Aufgabe 13.4 b)

Beitragvon Dominik.Kirst » 10 Feb 2014, 19:14

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
Dominik.Kirst
 
Beiträge: 7
Registriert: 17 Okt 2013, 12:36


Zurück zu Übungsblätter

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron