 Sprache auf andere Sprache reduzieren |
boxb
unregistriert
 |
|
| Sprache auf andere Sprache reduzieren |
     |
Hallo, ich bräuchte Hilfe bei einer Aufgabe und zwar geht es um Reduktionen von Sprachen.
Also ich soll das Akzeptanzproblem auf L reduzieren:
![[latex]L := \{ \left( <M>, <M'> \right)\,\, |\,\, L(M) \cap L(M') \neq \emptyset \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?L := \{ \left( <M>, <M'> \right)\,\, |\,\, L(M) \cap L(M') \neq \emptyset \})
![[latex]A := \{ <M>x\,\,|\,\,M \mbox{ist DTM, die die Eingabe $x$ akzeptiert.} \}[/latex]](http://www.matheboard.de/latex2png/latex2png.php?A := \{ <M>x\,\,|\,\,M \mbox{ist DTM, die die Eingabe $x$ akzeptiert.} \})
Okay, also ich muss zeigen ![[latex]A\leq L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?A\leq L)
Also muss ich eine Funktion "erfinden", damit gilt: ![[latex]w \in A \iff f(w) \in L[/latex]](http://www.matheboard.de/latex2png/latex2png.php?w \in A \iff f(w) \in L)
Nur wie mache ich das am besten?
(Noch zum Verständnis, die Sprache L sagt doch nur, dass zwei TMs M und M' gleich sind oder?)
Freu mich auf Tipps!!
LG
|
|
09.11.2016 22:05 |
|
|
boxb
unregistriert
|
|
Keiner eine Idee, freue mich auch über Gedankengänge 
|
|
|
11.11.2016 15:46 |
|
|
|
