\documentclass[a4paper,12pt]{scrartcl}
\usepackage[ngerman]{babel}
\usepackage{graphicx} %BIlder einbinden
\usepackage{amsmath} %erweiterte Mathe-Zeichen
\usepackage{amsfonts} %weitere fonts
\usepackage[utf8]{inputenc} %Umlaute & Co
\usepackage{hyperref} %Links
\usepackage{ifthen} %ifthenelse
\usepackage{enumerate}
\usepackage{ stmaryrd }

\usepackage{color}
\usepackage{algpseudocode} %Pseudocode
\usepackage{dsfont} % schöne Zahlenräumezeichen
\usepackage{amssymb, amsthm} %noch stärker erweiterte Mathe-Zeichen
\usepackage{tikz} %TikZ ist kein Zeichenprogramm
\usetikzlibrary{trees,automata,arrows,shapes}
\usepackage{pgfplots}

\pagestyle{empty}


\topmargin-50pt

\newcounter{aufgabe}
\def\tand{&}

\newcommand{\makeTableLine}[2][0]{%
\setcounter{aufgabe}{1}%
\whiledo{\value{aufgabe} < #1}%
{%
#2\tand\stepcounter{aufgabe}%
}
}

\newcommand{\aufgTable}[1]{
\def\spalten{\numexpr #1 + 1 \relax}
\begin{tabular}{|*{\spalten}{p{1cm}|}}
\makeTableLine[\spalten]{A\theaufgabe}$\Sigma$~~\\ \hline
\rule{0pt}{15pt}\makeTableLine[\spalten]{}\\
\end{tabular}
}

\def\header#1#2#3#4#5#6#7{\pagestyle{empty}
\begin{minipage}[t]{0.47\textwidth}
\begin{flushleft}
{\bf #4}\\
#5
\end{flushleft}
\end{minipage}
\begin{minipage}[t]{0.5\textwidth}
\begin{flushright}
#6 \vspace{0.5cm}\\
%                 Number of Columns    Definition of Columns      second empty line
% \begin{tabular}{|*{5}{C{1cm}|}}\hline A1&A2&A3&A4&$\Sigma$\\\hline&&&&\\\hline\end{tabular}\\\vspace*{0.1cm}
\aufgTable{#7}
\end{flushright}
\end{minipage}
\vspace{1cm}
\begin{center}
{\Large\bf Blatt #1}

{(Abgabe #3)}
\end{center}
}



%counts the exercisenumber
\newcounter{n}

%Kommando für Aufgaben
%\Aufgabe{AufgTitel}{Punktezahl}
\newcommand{\Aufgabe}[1]{\stepcounter{n}
\textbf{Aufgabe \arabic{n}: #1}}

\newcommand{\textcorr}[1]{\textcolor{red}{#1}}
\newenvironment{corr}{\color{red}}{\color{black}}
\newcommand{\ok}{\begin{corr}
      $\checkmark$
  \end{corr}}

\begin{document}
%\header{BlattNr}{Tutor}{Abgabedatum}{Vorlesungsname}{Namen}{Semester}{Anzahl Aufgaben}
\header{1}{}{2015-12-01}{Formale Sprachen II}{\textit{Maximus Mutschler}\\\textit{Jan-Peter Hohloch}}{WS 15/16}{2}
\vspace{1cm}
\Aufgabe{Aperiodizität}\\
    Sei $(M,\cdot, 1)$ aperiodisches Monoid.
    \begin{enumerate}[a)]
        \item \textit{Behauptung:} $N\subseteq M$ Untergruppe $\Rightarrow$ $N=\{1\}$\\
        Angenommen es gäbe $a\in N,\ a\not=1$. Da $(N,\cdot,1)$ Gruppe, muss $a^{-1}$ existieren.\\
        Sei nun $N<n\in\mathds{N}$, also $a^{n+1}=a^n$.\\
        Aufgrund von Assoziativität von $\cdot$ muss gelten:
        \begin{align*}
            &a^n\cdot (a\cdot a^{-1}) &=& (a^n\cdot a)\cdot a^{-1}\\
            \Leftrightarrow & a^n\cdot 1 &=& a^n\cdot a^{-1}\\
            \Leftrightarrow & 1&=&a^{-1}\\
            \Leftrightarrow & a&=& 1\ \hfill\lightning
        \end{align*}
        Es ist also jede Untergruppe eines aperiodischen Monoides trivial.\qed
        \item Sei $c\in\Sigma,\ a\in x^{n}=[c]^n,b\in x^{n+1}=[c]^{n+1}$\\
            $Synt(L)$ aperiodisch \\
            $\Leftrightarrow \exists n_0\in\mathds{N}\forall n\geq n_0: x^n=x^{n+1}\\
            \Leftrightarrow a\sim_L b\\
            \Leftrightarrow uav\in L\Leftrightarrow ubv\in L$\\
            $\overset{[c]^n = [c^n]}{\Leftrightarrow} uc^{n}v\in L\Leftrightarrow uc^{n+1}v\in L$\qed
        \item Da $\exists n_0\in\mathds{N}\forall n\geq n_0: x^n=x^{n+1}$ und $pqr=q$, existieren vier Fälle:\\
            \begin{enumerate}[F 1:]
                \item $p=r=1$\checkmark
                \item $p=1,r$ beliebig \checkmark
                \item $r=1,p$ beliebig \checkmark
                \item $r=x^a,p=x^b$ beliebig, $q= x^n\\
                    pqr=x^ax^nx^b=x^{n+(a+b)}=x^n$, da aperiodisch
            \end{enumerate}\qed\\
            \begin{corr}
                Induktiv: $pqr=p^nqr^n\forall n\in\mathds{N}$\\
                Für $n\geq n_0: p^n=p^{n+1}$\\
                $pq=pp^nqr^n=p^{n+1}qr^n=p^nqr^n=q$\dots
            \end{corr}
    \end{enumerate}\pagebreak
\Aufgabe{Sternfreie Sprachen}\\
    Beweis durch Induktion:
    \begin{itemize}
        \item[IA:] $\emptyset$, trivialerweise aperiodisch, da kein  Wort in der Sprache ist\\
        $\{a\}$, aperiodisch, da für $n_0=2$ für alle $n\geq n_0$ alle möglichen Worte nicht in der Sprache liegen
        \item[IV:] Seien $L_1,L_2$ sternfreie aperiodische Sprachen.
        \item[IS:]
        \begin{itemize}
            \item $\Sigma^*\setminus L_1$ ist aperiodisch, da die Äquivalenz auf beiden Seiten verneint immernoch eine Äquivalenz ist
            \item $L_1\cup L_2$ ist aperiodisch, da die Bedingung für Aperiodizität für die einzelnen Wörter gilt (IV) also auch für die Vereinigung all dieser.
            \item $L_1L_2$ ist aperiodisch, da :\\\begin{corr}
                $N_1,N_2$ jeweils Beginn der Aperiodik. Sei $N=N_1+N_2+1$\\
                Für $n\geq N, u,v,w\in\Sigma^*$:\\
                $uv^nw\in L\Leftrightarrow uv^nw=xy$, $x\in L_1$, $y\in L_2$\\
                Falls $x=uv^nw'$:\\
                $uv^nw'\in L_1 \Leftrightarrow uv^{n+1}w'\in L_1$\\ %Betrachte Zerlegung beliebiger uvw
                Falls $y=u'v^nw$: wie oben\\
                Falls $x=uv^{m_1}r$, $y=sv^{m_2}w$, mit $rs=v$\\
                Dann ist $m_1+m_2\geq N-1=N_1+N_2$, also $m_1\geq N_1$ oder $m_2\geq N_2$.\\
                OBdA sei $m_1\geq N_1$:\\
                $uv^{m_1}r\in L_1\Leftrightarrow uv{m_1+1}r\in L_1$\qed
            \end{corr}
        \end{itemize}
    \end{itemize}
\end{document}