Informatik

Wann ist eine Sprache $L_1$ auf eine Sprache $L_2$ reduzierbar?

Eine Sprache $L_1$ ist many-one auf eine Sprache $L_2$ reduzierbar ($L_1\le_m L_2$), wenn es eine total berechenbare Funktion $f:\Sigma^*\to\Gamma^*$ gibt mit $w\in L_1 \Leftrightarrow f(w)\in L_2$.

Erklärung

Die Funktion $f$ muss für jedes Eingabewort definiert sein; ihr Ausgabewort muss nicht immer in $L_2$ liegen. Ist $L_2$ entscheidbar und $L_1\le_m L_2$, dann ist auch $L_1$ entscheidbar.

Beispiel

Sei $L_1=\{w\in\{a\}^*\mid |w|\text{ ist gerade}\}$ und $L_2=\{\varepsilon\}$. Eine Reduktion ist:

$$f(w) = \begin{cases} \varepsilon & \text{wenn } |w| \text{ gerade ist}\\ a & \text{wenn } |w| \text{ ungerade ist} \end{cases}$$

Denn $\varepsilon\in L_2$ und $a\notin L_2$.