\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}