\documentclass[12pt]{article}

\usepackage{a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}
\usepackage{cancel}
\usepackage{fancyhdr}
\usepackage{gastex}
\usepackage{ngerman}

\title{\textsc{Einführung in die Computerlinguistik \\ \large Übung 5}}
\author{\shortstack[c]{Jan Hendrik Dithmar \\ \footnotesize Matrikelnummer 2031259}}
\date{}

\pagestyle{fancy}

\lhead{Übung 5}
\chead{}
\rhead{Dithmar (2031259)}
\lfoot{Einf. i. d. Computerlinguistik}
\cfoot{Seite \thepage}
\rfoot{WS 2006/2007}

\begin{document}

\renewcommand{\headrulewidth}{0.4pt}
\renewcommand{\footrulewidth}{0.4pt}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\pfr}{\ensuremath{\rightarrow}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\thispagestyle{empty}

\newpage
\setcounter{page}{1}

\section*{Aufgabe 5.1}

\subsection*{(a)}

Hier die Variante, bei der führende Nullen zulässig sind: \\
\begin{picture}(71,39)(0,-39)
\node[NLangle=0.0,ilength=7.0,Nmarks=i](n0)(20.54,-28.29){1}

\node[NLangle=0.0,Nmarks=r](n2)(60.54,-28.29){2}

\drawedge[ELdist=2.5](n0,n2){0,2,4,6,8}

\drawloop[ELdist=2.5](n0){0,...,9}
\end{picture}

\noindent Hier die Variante, bei der führende Nullen nicht zulässig sind: \\
\begin{picture}(122,53)(0,-53)
\node[NLangle=0.0,ilength=7.0,Nmarks=i](n3)(16.0,-32.27){1}

\node[NLangle=0.0](n4)(64.0,-32.27){2}

\node[NLangle=0.0,Nmarks=r](n5)(112.0,-32.27){3}

\drawedge[ELdist=2.5](n3,n4){1,...,9}

\drawedge[ELdist=2.5](n4,n5){0,2,4,6,8}

\drawedge[ELside=r,ELdist=3.0,curvedepth=-8.0](n3,n5){2,4,6,8}

\drawloop[ELdist=2.5](n4){0,...,9}
\end{picture}

\subsection*{(b)}
Die Idee ist die folgende: Eine Zahl ist durch 4 teilbar, wenn ihre vorletzte Stelle gerade und ihre letzte Stelle durch 4 teilbar ist. Außerdem ist eine Zahl durch 4 teilbar,
wenn ihre vorletzte Stelle ungerade und ihre letzte Stelle durch 4 modulo 2 teilbar ist. \\
\begin{picture}(91,52)(0,-52)
\node[NLangle=0.0,ilength=7.0,Nmarks=i](n6)(20.0,-28.27){1}

\node[NLangle=0.0](n7)(48.0,-28.0){2}

\node[NLangle=0.0,Nmarks=r](n8)(76.0,-28.0){3}

\node[NLangle=0.0](n9)(60.0,-40.0){4}

\node[NLangle=0.0,Nmarks=r](n10)(80.0,-40.0){5}

\drawedge[ELdist=2.5](n6,n7){0,2,4,6,8}

\drawedge[ELdist=2.5](n7,n8){0,4,8}

\drawedge[ELdist=2.5](n9,n10){2,6}

\drawedge[ELdist=-8.5](n6,n9){1,3,5,7,9}

\drawloop[ELdist=2.5](n6){0,...,9}
\end{picture}

\subsection*{(c)}
Ist eine Zahl durch 3 teilbar, so ist auch ihre Quersumme durch 3 teilbar. Teilt man die letzte Ziffer durch 3, so muss Rest 0 herauskommen. Die Zustände des Automaten
repräsentieren also den jeweiligen Rest. Die Frage ist nun: In welche Restklasse \glqq rutscht\grqq\ man bei welcher Ziffer am Ende? Dies muss man im Automaten entsprechend
berücksichtigen und fertig ;-) \\
\begin{picture}(115,89)(0,-89)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir](n0)(16.02,-48.25){0}

\node[NLangle=0.0](n1)(56.0,-48.0){1}

\node[NLangle=0.0](n2)(96.0,-48.0){2}

\drawloop[ELdist=2.5](n0){\{0,3,6,9\}}

\drawloop[ELdist=2.5](n1){\{0,3,6,9\}}

\drawloop[ELdist=2.5](n2){\{0,3,6,9\}}

\drawedge[ELdist=-4.5,curvedepth=-25.06](n0,n2){\{2,5,8\}}

\drawedge[ELdist=-3.5,curvedepth=-28.45](n2,n0){\{1,4,7\}}

\drawedge[ELdist=3.5,curvedepth=8.0](n0,n1){\{1,4,7\}}

\drawedge[ELdist=3.5,curvedepth=8.0](n1,n2){\{1,4,7\}}

\drawedge[ELdist=2.5,curvedepth=8.13](n1,n0){\{2,5,8\}}

\drawedge[ELdist=2.5,curvedepth=9.14](n2,n1){\{2,5,8\}}
\end{picture}


\section*{Aufgabe 5.2}
1. Schritt: Mehrsymbolkanten entfernen \\
\begin{picture}(131,74)(0,-74)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir](n3)(16.48,-48.08){1}

\node[NLangle=0.0](n4)(44.0,-24.0){1a}

\node[NLangle=0.0](n5)(68.0,-24.0){2}

\node[NLangle=0.0](n6)(92.0,-24.0){2a}

\node[NLangle=0.0,Nmarks=r](n7)(120.0,-24.0){3}

\node[NLangle=0.0](n8)(68.0,-56.0){4}

\node[NLangle=0.0](n9)(92.0,-56.0){5}

\node[NLangle=0.0,Nmarks=r](n10)(120.0,-56.0){6}

\drawedge[ELdist=2.5,curvedepth=8.0](n5,n7){t}

\drawedge[ELdist=2.5,curvedepth=8.0](n9,n10){$\varepsilon$}

\drawedge[ELdist=2.5](n3,n8){t}

\drawedge[ELdist=-3.5,curvedepth=-8.0](n3,n8){$\varepsilon$}

\drawedge[ELdist=2.5](n8,n9){e}

\drawedge[ELdist=2.5](n9,n10){n}

\drawedge[ELdist=2.5](n4,n5){e}

\drawedge[ELdist=-3.5](n6,n7){t}

\drawedge[ELdist=-3.5](n5,n6){s}

\drawedge[ELdist=2.5](n3,n4){t}

\drawedge[ELdist=-3.5](n3,n5){$\varepsilon$}
\end{picture}

\noindent 2. Schritt: $\varepsilon$-Kanten entfernen \\
\begin{picture}(131,86)(0,-86)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir](n3)(16.48,-48.08){1}

\node[NLangle=0.0](n4)(44.0,-24.0){1a}

\node[NLangle=0.0](n5)(68.0,-24.0){2}

\node[NLangle=0.0](n6)(92.0,-24.0){2a}

\node[NLangle=0.0,Nmarks=r](n7)(120.0,-24.0){3}

\node[NLangle=0.0](n8)(68.0,-56.0){4}

\node[NLangle=0.0,Nmarks=r](n9)(92.0,-56.0){5}

\node[NLangle=0.0,Nmarks=r](n10)(120.0,-56.0){6}

\drawedge[ELdist=2.5,curvedepth=8.0](n5,n7){t}

\drawedge[ELdist=-3.5](n3,n8){t}

\drawedge[ELdist=2.5](n8,n9){e}

\drawedge[ELdist=2.5](n9,n10){n}

\drawedge[ELdist=2.5](n4,n5){e}

\drawedge[ELdist=2.5](n6,n7){t}

\drawedge[ELdist=-3.5](n5,n6){s}

\drawedge[ELdist=2.5](n3,n4){t}

\drawedge[ELdist=2.5,curvedepth=-6.38](n3,n7){t}

\drawedge[ELdist=-3.5,curvedepth=-19.49](n3,n9){e}

\drawedge[ELdist=1.5,eyo=-4.0](n3,n6){s}
\end{picture}

\newpage
\noindent 3. Schritt: Konstruktion des Potenzautomaten \\
\begin{picture}(136,88)(0,-88)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir,Nw=18.0,Nh=18.0,Nmr=9.0](n17)(28.27,-40.21){\{1\}}

\node[NLangle=0.0,Nmarks=r,Nw=18.0,Nh=18.0,Nmr=9.0](n18)(72.27,-20.21){\{1a,3,4\}}

\node[NLangle=0.0,Nmarks=r,Nw=18.0,Nh=18.0,Nmr=9.0](n19)(120.27,-20.21){\{2,5\}}

\node[NLangle=0.0,Nw=18.0,Nh=18.0,Nmr=9.0](n20)(76.27,-48.21){\{2a\}}

\node[NLangle=0.0,Nmarks=r,Nw=18.0,Nh=18.0,Nmr=9.0](n21)(120.27,-72.21){\{3\}}

\node[NLangle=0.0,Nmarks=r,Nw=18.0,Nh=18.0,Nmr=9.0](n22)(28.27,-72.21){\{5\}}

\node[NLangle=0.0,Nmarks=r,Nw=18.0,Nh=18.0,Nmr=9.0](n23)(68.27,-72.21){\{6\}}

\drawedge[ELdist=2.5](n17,n22){e}

\drawedge[ELdist=2.5](n22,n23){n}

\drawedge[ELdist=2.5](n17,n18){t}

\drawedge[ELdist=2.5](n17,n20){s}

\drawedge[ELdist=2.5](n18,n19){e}

\drawedge[ELdist=2.5](n19,n20){s}

\drawedge[ELdist=2.5](n19,n21){t}

\drawedge[ELdist=2.5](n20,n21){t}
\end{picture}


\section*{Aufgabe 5.3}

\subsection*{(a)}
Der Automat akzeptiert beliebige Zeichenketten aus $a$'s und $b$'s, wobei die Anzahl der $a$'s keine Rolle spielt, $b$'s jedoch nur in Blöcken mit gerader Anzahl vorkommen
dürfen. Das Wort darf nicht mit $b$ beginnen, es dürfen keine $b$'s am Ende stehen und nach einem Block aus $bb$ müssen mindestens 2 $a$'s oder kein $a$ kommen.

\subsection*{(b)}
1. Schritt: Mehrsymbolkanten entfernen \\
\begin{picture}(85,57)(0,-57)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir](n24)(20.0,-28.0){1}

\node[NLangle=0.0](n25)(52.0,-8.0){2}

\node[NLangle=0.0](n26)(52.0,-48.0){3}

\node[NLangle=0.0](n27)(76.0,-28.0){2a}

\drawloop[ELdist=2.5](n24){a}

\drawedge[ELdist=2.5](n24,n25){a}

\drawedge[ELdist=2.5](n26,n24){a}

\drawedge[ELdist=2.5,curvedepth=8.0](n25,n27){b}

\drawedge[ELdist=2.5,curvedepth=8.0](n27,n26){b}

\drawedge[ELdist=2.5](n26,n25){$\varepsilon$}
\end{picture}

\noindent 2. Schritt: $\varepsilon$-Kanten entfernen \\
\begin{picture}(85,57)(0,-57)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir](n24)(20.0,-28.0){1}

\node[NLangle=0.0](n25)(52.0,-8.0){2}

\node[NLangle=0.0](n26)(52.0,-48.0){3}

\node[NLangle=0.0](n27)(76.0,-28.0){2a}

\drawloop[ELdist=2.5](n24){a}

\drawedge[ELdist=2.5](n24,n25){a}

\drawedge[ELdist=2.5](n26,n24){a}

\drawedge[ELdist=2.5,curvedepth=8.0](n25,n27){b}

\drawedge[ELdist=2.5,curvedepth=8.0](n27,n26){b}

\drawedge[ELdist=2.5,curvedepth=5.14](n27,n25){b}

\drawedge[ELdist=2.5,curvedepth=5.59](n26,n27){b}
\end{picture}

\noindent 3. Schritt: Konstruktion des Potenzautomaten \\
\begin{picture}(111,75)(0,-75)
\node[NLangle=0.0,ilength=7.0,Nmarks=ir,Nw=12.0,Nh=12.0,Nmr=6.0](n32)(20.0,-36.0){\{1\}}

\node[NLangle=0.0,Nmarks=r,Nw=12.0,Nh=12.0,Nmr=6.0](n33)(64.0,-24.0){\{1,2\}}

\node[NLangle=0.0,Nw=12.0,Nh=12.0,Nmr=6.0](n34)(100.0,-44.0){\{2a\}}

\node[NLangle=0.0,Nw=12.0,Nh=12.0,Nmr=6.0](n35)(60.0,-64.0){\{2,3\}}

\drawedge[ELdist=2.5](n32,n33){a}

\drawloop[ELdist=2.5](n33){a}

\drawedge[ELdist=2.5](n35,n32){a}

\drawedge[ELdist=2.5,curvedepth=8.0](n33,n34){b}

\drawedge[ELdist=2.5,curvedepth=8.0](n34,n35){b}

\drawedge[ELdist=2.5,curvedepth=8.0](n35,n34){b}
\end{picture}

\end{document}
