\begin{slide}{Entscheidungsverfahren (Kodierung)}

Kodierung ist nötig,

denn $\Mod(F)\subseteq \NN^k$, 
aber $\Lang(A)\subseteq \Sigma^*$.

\bigskip

wählen $\Sigma=\{0,1\}^k$, benutze Ideen:
\begin{itemize}\itemsep 0pt
\item Kodierung einer Zahl: binär (LSB links)

  $c(3) = 11, c(13)=1011$

\item Kodierung eines Tupels: durch Stapeln

  $c(3,13) = (1,1)(1,0)(0,1)(0,1)$
\end{itemize}

Beispiele: Automat oder reg. Ausdruck für
\begin{itemize}\itemsep 0pt\parskip 2pt
\item 
$\{ c(x) \mid \text{$x$ ist gerade} \}$,
$\{ c(x) \mid \text{$x$ ist durch $3$ teilbar} \}$,
\item $\{ c(x,y) \mid x+x=y \}$,
$\{ c(x,y,z) \mid x+y=z \}$,
\item $\{ c(x,y) \mid x \le y \}$,
$\{ c(x,y) \mid x < y \}$
\end{itemize}



\end{slide}
