diff --git a/ub06/fs06.tex b/ub06/fs06.tex index a7d3370..adcf31d 100644 --- a/ub06/fs06.tex +++ b/ub06/fs06.tex @@ -97,7 +97,33 @@ \Leftrightarrow & 1&=&a^{-1}\\ \Leftrightarrow & a&=& 1\ \hfill\lightning \end{align*} - Es ist also jede Untergruppe eines aperiodischen Monoides trivial. - \end{enumerate} + 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 + \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 ??? + \end{itemize} + \end{itemize} \end{document} -