\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 1 \\
	Übungsgruppe 7 - Mi, 16-18 Uhr \\
	Thomas Klöcker}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}

\subsubsection*{(a)}

$$1+\sin n, \; \sqrt{n}\log n, \; n, \; n\log\log n, \; n\sqrt{\log n}, \; n\log n, \; n^2, \; n^{\log n}, \; n2^{\sqrt{\log n}}, \; n2^{3\sqrt{\log n}}$$


\section*{Aufgabe 2} 
 
\subsubsection*{(a)}
\begin{eqnarray*} 
        \varepsilon q_{0} 00110  & \vdash \varepsilon q_{1} 10110 & \vdash         1 q_{0} 0110 \\
	\vdash         1 q_{1} 1110 & \vdash         11 q_{0} 110 & \vdash         11 q_{1} 010 \\
	\vdash         110 q_{0} 10 & \vdash         110 q_{1} 00 & \vdash         1100 q_{0} 0 \\
	\vdash         1100 q_{1} 1 & \vdash         11001 q_{0}  & \vdash         11001 q_{2}
\end{eqnarray*} 
 
\subsubsection*{(b)}
M invertiert die Eingabe.

\section*{Aufgabe 3}
\begin{tabular}{c|cccc}
					&		0			&		1			&		$\#$		&		B				\\
\hline $q_0$		&	$(q_0,0,R)$		&	$(q_1,1,R)$		&	$(q_1,\#,R)$	&		-				\\
\hline $q_1$		&	$(q_1,0,R)$		&	$(q_2,1,R)$		&		-			&	$(q_6,B,L)$			\\
\hline $q_2$		&	$(q_2,0,R)$		&	$(q_2,1,R)$		&		-			&	$(q_3,B,L)$			\\
\hline $q_3$		&	$(q_3,1,L)$		&	$(q_4,0,L)$		&		-			&		-				\\
\hline $q_4$		&	$(q_4,0,L)$		&	$(q_4,1,L)$		&	$(q_5,\#,L)$	&		-				\\
\hline $q_5$		&	$(q_0,1,R)$		&	$(q_5,0,L)$		&		-			&	$(q_0,1,R)$			\\
\hline $q_6$		&	$(q_7,B,L)$		&		-			&		$(q_7,B,R)$	&		-				\\
\hline $q_7$		&	-			&		-			&		-			&		-			\newline
\end{tabular}
\newline \\ \newline
$q_0$ geht bis Raute und springt von da nach $q_1$ \\
$q_1$ fragt ab, ob die Zahl b nur aus Nullen besteht, wenn ja dann springt sie nach $q_6$ welches die Raute entfernen soll, sonst ist $b > 0$, wir springen nach $q_2$ \\
$q_2$ wandert ganz nach rechts, um die Inkrementierung ab der letzten Stelle einzuleiten mit Zustand $q_3$ \\
$q_3$ dekremtiert die Zahl b um 1 und geht über nach $q_4$ \\
$q_4$ jetzt wird die Raute von b aus nach links gehend gesucht um in den Zustand $q_5$ überzugehen \\
$q_5$ inkrementiert die Zahl a um 1 (nachdem 1 von b abgezogen wurde, und startet wieder von neu ab Zustand $q_0$ \\
$q_6$ ist dafür zuständig, die Raute nach B zu setzen \\
$q_7$ ist der akzeptierende Endzustand

\end{document}