Informatiker Board | Druckvorschau: Sprache auf andere Sprache reduzieren

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Sprache auf andere Sprache reduzieren (http://www.informatikerboard.de/board/thread.php?threadid=3288)

Geschrieben von boxb am 09.11.2016 um 22:05:

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]$

$[latex]A := \{ <M>x\,\,|\,\,M \mbox{ist DTM, die die Eingabe $x$ akzeptiert.} \}[/latex]$

Okay, also ich muss zeigen $[latex]A\leq L[/latex]$

Also muss ich eine Funktion "erfinden", damit gilt: $[latex]w \in A \iff f(w) \in L[/latex]$

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