\documentstyle[11pt,german,a4]{article}

\parindent 0.0em
\input pgf
\input tikz
\usetikzlibrary{arrows,automata}

\newcounter{z}
\setcounter{z}{0}
\newcommand{\aufgabe}[1]{\refstepcounter{z}\subsection*{\arabic{z}.~Aufgabe }}

\begin{document}
 \hrule \vspace*{0.3em}

Vorlesung Theoretische Informatik\\
Sommersemester 2017
\vspace*{0.3em}\hrule

\begin{center} {\large\bf 2.\ Musterl\"osung} \end{center}

\aufgabe

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,semithick]
  \tikzstyle{every state}=[fill=none,draw=black,text=black]

  \node[initial,state] 	(z0)                {$Z_0$};
  \node[state]         	(z1) [right of=z0]	{$Z_1$};
  \node[state]         	(z2) [right of=z1]	{$Z_2$};
  \node[state,accepting](z3) [right of=z2]	{$Z_3$};
  \node[state]         	(zm) [right of=z3]	{$Z_m$};

  \path (z0) edge [loop below]	node {b} (z0)
             edge               node {a} (z1)
        (z1) edge [loop below]  node {b} (z1)
             edge               node {a} (z2)
        (z2) edge [loop below]  node {b} (z2)
             edge 				node {a} (z3)
        (z3) edge [loop below]  node {b} (z3)
             edge               node {a} (zm)
        (zm) edge [loop below]  node {a,b} (zm);
\end{tikzpicture}
\end{center}

\medskip

\aufgabe

L1:

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,semithick]
  \tikzstyle{every state}=[fill=none,draw=black,text=black]

  \node[initial,state]  (z0)                {$Z_0$};
  \node[state]          (z1) [right of=z0]  {$Z_1$};
  \node[state]          (z2) [right of=z1]  {$Z_2$};
  \node[state,accepting](z3) [right of=z2]  {$Z_3$};

  \path (z0) edge [loop above]  node {0} (z0)
             edge               node {1} (z1)
        (z1) edge [loop above]  node {1} (z1)
             edge               node {0} (z2)
        (z2) edge [bend left]   node {0} (z0)
             edge               node {1} (z3)
        (z3) edge [loop above]  node {0,1} (z3);
\end{tikzpicture}
\end{center}

\medskip

L2:

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,semithick]
  \tikzstyle{every state}=[fill=none,draw=black,text=black]

  \node[initial,state]  (z0)                {$Z_0$};
  \node[state]          (z1) [right of=z0]  {$Z_1$};
  \node[state]          (z2) [right of=z1]  {$Z_2$};
  \node[state,accepting](z3) [right of=z2]  {$Z_3$};
  \node[state]			(z4) [below right of=z2] {$Z_4$};
  \node[state]          (zm) [below right of=z0] {$Z_m$};



  \path (z0) edge 				node {1} (z1)
             edge               node {0} (zm)
        (z1) edge 				node {1} (zm)
             edge               node {0} (z2)
        (z2) edge [loop above]  node {0} (z2)
             edge [below]              node {1} (z3)
        (z3) edge [bend right, above]   node {0} (z2)
			 edge				node {1} (z4)
		(z4) edge [loop below]  node {1} (z4)
		     edge 				node {0} (z2)
		(zm) edge [loop below]  node {0,1} (zm);
\end{tikzpicture}
\end{center}

\medskip

\aufgabe

\begin{tabular}{| l | l | l |}
    \hline
    $R_5(nat(w))$ & $R_5(nat(w\cdot 0))$ & $R_5(nat(w\cdot 1))$ \\ \hline
    0 & 0 & 1 \\ \hline   
	1 & 2 & 3 \\ \hline
	2 & 4 & 0 \\ \hline
	3 & 1 & 2 \\ \hline 
	4 & 3 & 4 \\ \hline
\end{tabular}

\medskip

\begin{center}
\begin{tikzpicture}[->,>=stealth',shorten >=1pt,auto,node distance=2cm,semithick]
  \tikzstyle{every state}=[fill=none,draw=black,text=black]

  \node[initial,state]  (z5)        	  	      {$R_5$};
  \node[state,accepting](z0) [above right of=z5]  {$R_0$};
  \node[state]          (z1) [below right of=z5]  {$R_1$};
  \node[state]			(z2) [above right of=z1]  {$R_2$};
  \node[state]          (z3) [below right of=z1]  {$R_3$};
  \node[state]          (z4) [right of=z2]		  {$R_4$};

  \path (z5) edge               node {0} (z0)
             edge               node {1} (z1)
        (z0) edge [loop above]  node {0} (z0)
             edge               node {1} (z1)
        (z1) edge  node {0} (z2)
             edge  [bend right,below] node {1} (z3)
        (z2) edge  node {0} (z4)
             edge               node {1} (z0)
        (z3) edge  [bend right] node {0} (z1)
             edge               node {1} (z2)
        (z4) edge  node {0} (z3)
			 edge  [loop above] node {1} (z4);
\end{tikzpicture}
\end{center}

\aufgabe

$K(A,Z_0)=\{\varepsilon\}$ \\
$K(A,Z_1)=\{v\cdot a|v \in \Sigma^*\}$ \\
$K(A,Z_2)=\{v\cdot b|v \in \Sigma^*\}$

\end{document}