diff --git a/ub06/fs06.pdf b/ub06/fs06.pdf index de110df..ac2fbff 100644 --- a/ub06/fs06.pdf +++ b/ub06/fs06.pdf Binary files differ diff --git a/ub06/fs06.tex b/ub06/fs06.tex index adcf31d..63550e9 100644 --- a/ub06/fs06.tex +++ b/ub06/fs06.tex @@ -111,7 +111,12 @@ \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}\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: @@ -123,7 +128,18 @@ \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 ??? + \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}