07.tex

\documentclass{exercisesheet}
\usepackage{ wasysym }
\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage[noend]{algpseudocode}

\algdef{SE}[DOWHILE]{Do}{doWhile}{\algorithmicdo}[1]{\algorithmicwhile\ #1}
\usetikzlibrary{shapes.misc,shapes.geometric,arrows,fit,matrix,positioning,automata}
\title{Advanced Automata Theory, Exercises 7}
\setcounter{exercisenumber}{20}
\author{
	Roman Karwacik \\ 357965
	\and
	Raphael Valentin Merkle \\ 335727
	\and 
	Jasper Manousek \\ 313400
}
\newcommand{\negation}{{\sim}}

\begin{document}
\maketitle
\pointtable

\begin{exercise}{3}
	\begin{subexercise}
		Let $\Sigma=\{a\}$, $L_1=L((aa)^*)$ and $L_2=L(a(aa)^*)$, which are counting languages. Thus $L_1\cup L_2=L((aa)^*\lor (a(aa)^*))=a^*=\Sigma^*$, which is non-counting, because $\Sigma^*$ is star-free. Thus, the statement is false.
	\end{subexercise}
	\begin{subexercise}
		Let $\Sigma=\{b,c\}$, $L_1=L((ccc)^+)$ and $L_2=L((bbb)^+)$, which are counting languages. Thus $L_1\cap L_2=\emptyset$, which is not counting because it is trivially star-free. Thus, the statement is false.
	\end{subexercise}
	\begin{subexercise}
		Let Let $\Sigma=\{a\}$, $L_1=L((aa)^*+a)$ and $L_2=L((aaa)^*)$, which are counting languages. Thus $L_1\cdot L_2=L(((aa)^*+a)\cdot (aaa)^*))=a^*=\Sigma^*$, which is non-counting, because $\Sigma^*$ is star-free. Thus, the statement is false.
	\end{subexercise}
\end{exercise}
\begin{exercise}{4}
	\begin{subexercise}
	The minimal automata for $L$ is:
	\begin{center}		
		\begin{tikzpicture}[-stealth, shorten >=1pt,node distance=2cm, initial text={}, on grid,auto] 
			\node[state,initial] (eps)  				 		{$1$}; 
			\node[state] (b) [right=of eps] 	 		{$2$};
			\node[state,accepting] (bb) [right=of b]  	{$3$}; 
			\node[state] (ba) [below=of b]  		{$4$}; 
			\path[-stealth] 
			(eps) edge node {$b$} (b)
			(b) edge node {$a$} (ba)
			(bb) edge node {$a$} (ba)
			(b) edge [ bend left=20]  node {$b$} (bb)
			(bb) edge [ bend left=20]  node {$b$} (b)
			(eps) edge [loop above] node {$a$} ()
			(ba) edge [loop left] node {$a,b$} ();
		\end{tikzpicture}
	\end{center}
	Because the syntactic monoid of $L$ is isomorphic to the transition monoid of the minimal automata, we build it:
	\begin{center}		
		\begin{tikzpicture}[-stealth, shorten >=1pt,node distance=2cm, initial text={}, on grid,auto] 
			\node[state] (1234)  				 		{$\substack{1234\\\epsilon}$}; 
			\node[state] (2324) [right=of 1234]  	{$\substack{2324\\b}$}; 
			\node[state] (1444) [below=of 2324] 	 		{$\substack{1444\\a}$};
			\node[state] (2444) [right=of 1444] 	 		{$\substack{2444\\ab}$};
			\node[state] (3444) [below=of 2444] 	 		{$\substack{3444\\abb}$};
			\node[state] (4444) [right=of 2444] 	 		{$\substack{4444\\ba}$};
			\node[state] (3234) [above=of 4444]  		{$\substack{3234\\bb}$};
			\path[-stealth] 
			(1234) edge node {$a$} (1444)
			(1234) edge node {$b$} (2324)
			(3234) edge node {$a$} (4444)
			(2324) edge node {$a$} (4444)
			(1444) edge node {$b$} (2444)
			(2444) edge node {$a$} (4444)
			(2444) edge [ bend left=20]  node {$b$} (3444)
			(3444) edge [ bend left=20]  node {$b$} (2444)
			(3444) edge node[swap] {$a$} (4444)
			(2324) edge [ bend left=14]  node {$b$} (3234)
			(3234) edge [ bend left=14]  node[swap] {$b$} (2324)
			(1444) edge [loop below] node {$a$} ()
			(4444) edge [loop below] node {$a,b$} ();
		\end{tikzpicture}
	\end{center}
	\end{subexercise}
	\begin{subexercise}
		There are subgroups in the syntactic monoid, namely those defined by $G_1=\{2324,3234\}$. Thus $L$ is not FO-definable, because of the Characterization of FO-definable languages Theorem.
	\end{subexercise}
\end{exercise}
\begin{exercise}{4}
	First, we generalize the definition of a transition monoid from DFAs to NFAs such that the monoid elements are not functions, but binary relations over $Q$:\\
	For $u\in \Sigma^*$ let $u^\mathcal{A}\subseteq Q \times Q$, $(q_i,q_j)\in u^\mathcal{A} \iff q_i\xrightarrow{u}q_j$.\\
	\n
	\textbf{Present a suitable monoid (and show it is indeed a monoid).}
	\[ \mathcal{M}:=(\{u^\mathcal{A} \seperator u\in \Sigma^*\}, \circ, \epsilon^\mathcal{A}) \]
	with
	\[ x^\mathcal{A} \circ y^\mathcal{A} :=\{ (q_i,q_j)\seperator q_i\xrightarrow{xy} q_j \} \]
	$\mathcal{M}$ is a monoid.
	\begin{proof}
	~
		\begin{itemize}
			\item \textbf{Associativity:}\\
				For $x,y,z\in \Sigma^*$:
				\begin{alignat*}{2}
					(x^\mathcal{A}\circ y^\mathcal{A}) \circ z^\mathcal{A} &= \{ (q_i,q_j)\seperator q_i\xrightarrow{xy} q_j \} \circ z^\mathcal{A}\\
					&= \{ (q_i,q_j)\seperator q_i\xrightarrow{xyz} q_j \}\\
					&= x^\mathcal{A}\circ\{ (q_i,q_j)\seperator q_i\xrightarrow{yz} q_j \}\\
					&= x^\mathcal{A}\circ(y^\mathcal{A}\circ z^\mathcal{A})
				\end{alignat*}
				Thus $\circ$ is associative.
			\item \textbf{Neutral Element:}\\
				For $x\in \Sigma^*$:
				\begin{alignat*}{2}
					\epsilon^A\circ x^\mathcal{A} &= \{ (q_i,q_j)\seperator q_i\xrightarrow{\epsilon x} q_j \} = \{ (q_i,q_j)\seperator q_i\xrightarrow{x} q_j \} = x^\mathcal{A}\\
					x^\mathcal{A} \circ \epsilon^\mathcal{A} &= \{ (q_i,q_j)\seperator q_i\xrightarrow{x\epsilon } q_j \} = \{ (q_i,q_j)\seperator q_i\xrightarrow{x} q_j \} = x^A\\
				\end{alignat*}
				Thus $\epsilon^A$ is the neutral element.
		\end{itemize}
		Thus $\mathcal{M}$ is a monoid.
	\end{proof}
	As $u^A$ is a subset of $Q\times Q$, there are at most $|Q|^2$ possible relations. $\mathcal{M}$ therefore contains all combinations of those sets, whichs means $|\mathcal{M}|\leq 2^{|Q|^2}$.\\
	\n
	\textbf{Present a suitable subset and a suitable monoid homomorphism (and show that it is indeed a homomorphism).}\\
	\n
	For the subset $P$ we choose:
	\[ P:=\{ w^\mathcal{A}\in M \seperator \forall (q_i,q_j)\in w^\mathcal{A}: q_i=q_0, q_j\in F^\mathcal{A}, w\in \Sigma^* \}\subseteq M \]
	and $h$:
	\[ h:\Sigma^*\to M, w\mapsto w^\mathcal{A}\]
	$h$ is a homomorphism.
	\begin{proof}
	~
	\begin{itemize}
		\item \textbf{Compatibility with} $\circ$:\\
		For $u,v\in \Sigma^*$:
		\[ h(u)\circ h(v)= u^\mathcal{A}\circ v^\mathcal{A}= (uv)^\mathcal{A} = h(uv) \]
		\item \textbf{Neutral Element:}\\
		$h(\epsilon)=\epsilon^\mathcal{A}$.
	\end{itemize}
	Thus $h$ is a homomorphism.
	\end{proof}
	\n
	At last, we show that $L(\mathcal{M},P,h)=L(\mathcal{A})$:
	\begin{alignat*}{2}
		u\in L(\mathcal{A}) &\iff q_0\xrightarrow{u}q_i&\quad ,q_i\in F^\mathcal{A}\\
		&\iff (q_0,q_i)\in u^\mathcal{A}\\
		&\iff h(u)=u^\mathcal{A}\in P\\
		&\Rightarrow L(\mathcal{A})=L(\mathcal{M},P,h)
	\end{alignat*}
\end{exercise}
\begin{exercise}{4}
	\begin{subexercise}
		Start and end with $aabc$, never $aaa$, $ac$, $bb$, $cc$, $cb$, $cab$, $ba$.
		\begin{alignat*}{2}
			&(aabc\Sigma^*) \cap (\Sigma^*aabc)\\
			 \cap~& \negation(\Sigma^*aaa\Sigma^*) \\
			 \cap~& \negation(\Sigma^*ac\Sigma^*)\\
			 \cap~& \negation(\Sigma^*bb\Sigma^*)\\
			 \cap~& \negation(\Sigma^*cc\Sigma^*) \\
			 \cap~& \negation(\Sigma^*cb\Sigma^*)\\
			 \cap~& \negation(\Sigma^*cab\Sigma^*)\\
			 \cap~& \negation(\Sigma^*ba\Sigma^*) 
		\end{alignat*}
		\[ =\negation{}(\Sigma^*(ac+aa(a+c)+b(a+b)+c(b+c)+cab)\Sigma^*)\cap aabc\Sigma^* \cap \Sigma^*aabc \]
	\end{subexercise}
	\begin{subexercise}
		\[ G((P_b\land XP_a)\rightarrow X(((\neg(P_b\land XP_a))U(P_c \land XP_a)) \lor \neg F(P_b\land XP_a))) \]
		When $ba$ occurs, there is no $ba$ until $ca$ occured or $ba$ doesn't occur after that.
	\end{subexercise}
\end{exercise}
\end{document}