Sprache auf andere Sprache reduzieren

09.11.2016, 22:05	Auf diesen Beitrag antworten »
boxb	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


11.11.2016, 15:46	Auf diesen Beitrag antworten »
boxb	Keiner eine Idee, freue mich auch über Gedankengänge

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »