\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{.5cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turma D/Solução do professor \hfill {22/11/2012}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Construa AFNs que reconheçam:
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item $L_1=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ não contém } {\tt abc}\}$, com 3 estados;
			  \item $L_2=\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\geq 2 \mbox{ e o primeiro e o último símbolos de $w$ são idênticos}\}$,
				      com 4 estados.
			 \end{list}}

       \textit{Solução}: \\
				
				      \begin{picture}(75,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=ir, iangle=180](1)(20,15){}
               \node[Nmarks=r](2)(40,20){}
               \node[Nmarks=r](3)(60,15){}

               \put(0,30){\makebox(0,0)[l]{(a)}}
               \drawloop[loopangle=90](1){{\tt b},{\tt c}}
               \drawedge[curvedepth=4](1,2){{\tt a}}
               \drawloop[loopangle=90](2){{\tt a}}
               \drawedge[curvedepth=4, ELside=r](2,1){{\tt c}}
               \drawedge[curvedepth=4](2,3){{\tt b}}
               \drawedge[curvedepth=4, ELside=r](3,2){{\tt a}}
               \drawedge[curvedepth=7](3,1){{\tt b}}
              \end{picture}
				      \begin{picture}(75,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,15){}
               \node(2)(35,20){}
               \node(3)(35,10){}
               \node[Nmarks=r](4)(50,15){}

               \put(0,30){\makebox(0,0)[l]{(b)}}
               \drawedge[curvedepth=0](1,2){{\tt a}}
               \drawedge[curvedepth=0, ELside=r](1,3){{\tt b}}
               \drawloop[loopangle=90](2){{\tt a},{\tt b}}
               \drawedge[curvedepth=0](2,4){{\tt a}}
               \drawloop[loopangle=270](3){{\tt a},{\tt b}}
               \drawedge[curvedepth=0, ELside=r](3,4){{\tt b}}
              \end{picture}

 \item {\footnotesize Como construir um AFN$\lambda$ que reconheça $L_1L_2$ a partir de AFNs que reconheçam $L_1$ e $L_2$?
       Exemplifique com os AFNs obtidos na questão anterior.}

       \textit{Solução}:

        Sejam $(E_1,\Sigma_1,\delta_1,I_1,F_1)$ um AFN que aceite $L_1$ e $(E_2,\Sigma_2,\delta_2,I_2,F_2)$ um AFN que aceite
				$L_2$ tais que $E_1\cap E_2=\emptyset$. Um AFN$\lambda$ que aceita $L_1L_2$ é
				$(E_1\cup E_2,\Sigma_1\cup \Sigma_2,\delta_3,I_1,F_2)$, em
				que:
				\begin{itemize}
					\item $\delta_3(e,a)=\delta_1(e,a)$ para todo $(e,a)\in E_1\times\Sigma_1$;
					\item $\delta_3(e,a)=\delta_2(e,a)$ para todo $(e,a)\in E_2\times\Sigma_2$;
					\item $\delta_3(e,\lambda)=I_2$ para todo $e\in F_1$; e
					\item $\delta_3(e,\lambda)=\emptyset$ para todo $e\in (E_1\cup E_2)-F_1$.
				\end{itemize}

        Exemplificando:

				      \begin{picture}(175,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,15){}
               \node(2)(40,20){}
               \node(3)(60,15){}

               \drawloop[loopangle=90](1){{\tt b},{\tt c}}
               \drawedge[curvedepth=4](1,2){{\tt a}}
               \drawloop[loopangle=90](2){{\tt a}}
               \drawedge[curvedepth=4, ELside=r](2,1){{\tt c}}
               \drawedge[curvedepth=4](2,3){{\tt b}}
               \drawedge[curvedepth=4, ELside=r](3,2){{\tt a}}
               \drawedge[curvedepth=6](3,1){{\tt b}}
   
               \node(1a)(90,15){}
               \node(2a)(105,20){}
               \node(3a)(105,10){}
               \node[Nmarks=r](4a)(120,15){}

               \drawedge[curvedepth=0](1a,2a){{\tt a}}
               \drawedge[curvedepth=0, ELside=r](1a,3a){{\tt b}}
               \drawloop[loopangle=90](2a){{\tt a},{\tt b}}
               \drawedge[curvedepth=0](2a,4a){{\tt a}}
               \drawloop[loopangle=270](3a){{\tt a},{\tt b}}
               \drawedge[curvedepth=0, ELside=r](3a,4a){{\tt b}}

               \drawedge[curvedepth=10](2,1a){$\lambda$}
               \drawedge[curvedepth=0](3,1a){$\lambda$}
               \drawedge[curvedepth=-14, ELside=r](1,1a){$\lambda$}
              \end{picture}

 \item {\footnotesize Encontre expressões regulares que denotem as linguagem $L_1$ e $L_2$ da primeira questão.}

       \textit{Solução}:

       Para $L_1$, a ER será construída a partir do AFN obtido no item (a) da primeira questão:

				      \begin{picture}(175,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,15){1}
               \node(2)(40,20){2}
               \node(3)(60,15){3}

               \drawloop[loopangle=90](1){$b+c$}
               \drawedge[curvedepth=4](1,2){$a$}
               \drawloop[loopangle=90](2){$a$}
               \drawedge[curvedepth=4, ELside=r](2,1){$c$}
               \drawedge[curvedepth=4](2,3){$b$}
               \drawedge[curvedepth=4, ELside=r](3,2){$a$}
               \drawedge[curvedepth=6](3,1){$b$}
   
               \node[Nmarks=r](4)(90,15){4}
               \drawedge[curvedepth=10](2,4){$\lambda$}
               \drawedge[curvedepth=0](3,4){$\lambda$}
               \drawedge[curvedepth=-14, ELside=r](1,4){$\lambda$}
             \end{picture}

       Eliminando-se o estado 3:

				      \begin{picture}(175,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(30,15){1}
               \node(2)(50,20){2}

               \drawloop[loopangle=90](1){$b+c$}
               \drawedge[curvedepth=4, ELside=r](1,2){$a$}
               \drawloop[loopangle=90](2){$a+ba$}
               \drawedge[curvedepth=4, ELside=r](2,1){$c+bb$}
   
               \node[Nmarks=r](4)(90,15){4}
               \drawedge[curvedepth=0](2,4){$\lambda+b$}
               \drawedge[curvedepth=-8, ELside=r](1,4){$\lambda$}
             \end{picture}

       Eliminando-se o estado 2:

				      \begin{picture}(175,25)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(30,10){1}
 
               \drawloop[loopangle=90](1){$b+c+a(a+ba)^*(c+bb)$}
   
               \node[Nmarks=r](4)(90,10){4}
               \drawedge[curvedepth=0, ELside=r](1,4){$\lambda+a(a+ba)^*(\lambda+b)$}
             \end{picture}

        ER: $(b+c+a(a+ba)^*(c+bb))^*(\lambda+a(a+ba)^*(\lambda+b))$.
				
				Uma ER para $L_2$ é: $a(a+b)^*a+b(a+b)^*b$.

 \item {\footnotesize Seja $L=\{{\tt a}^n{\tt b}^i{\tt c}^j\,|\,n > i+j\}$.
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Construa uma GLC que reconheça $L$.
				\item Construa uma GLC que gere $(LL)^*L$.
			  \item Construa um APN que reconheça $L$.
			 \end{list}}

       \textit{Solução}:

			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item GLC que gera $L$:

              \begin{quote}
							 $X \,\rightarrow\, {\tt a} X {\tt c} \,|\, Y$ \\
							 $Y \,\rightarrow\, {\tt a} Y {\tt b} \,|\, A$ \\
							 $A \,\rightarrow\, {\tt a} A \,|\, {\tt a}$
							\end{quote}
				\item GLC que gera $(LL)^*L$:

              \begin{quote}
							 $P \,\rightarrow\, X X P \,|\, X$ \\
							 mais as regras acima.
							\end{quote}
			  \item APN que reconhece $L$:

              Usando a GLC acima, seria $(\{1,2\},\{{\tt a},{\tt b},{\tt c}\},\{P,X,Y,A,{\tt a},{\tt b},{\tt c}\},\delta,1,\{2\})$
				      em que:

				      $\begin{array}{lll}
							 \delta(1,\lambda,\lambda)=[2,P] & \delta(2,\lambda,Y)=[2,{\tt a}Y{\tt b}] & \delta(2,{\tt a},{\tt a})=[2,\lambda] \\
							 \delta(2,\lambda,P)=[2,XXP]     & \delta(2,\lambda,Y)=[2,A]               & \delta(2,{\tt b},{\tt b})=[2,\lambda] \\
							 \delta(2,\lambda,P)=[2,X]       & \delta(2,\lambda,A)=[2,{\tt a}A]        & \delta(2,{\tt c},{\tt c})=[2,\lambda] \\
							 \delta(2,\lambda,X)=[2,{\tt a}X{\tt c}]& \delta(2,\lambda,A)=[2,{\tt a}]  \\
							 \delta(2,\lambda,X)=[2,Y]       \\
							\end{array}$
							
							Outra solução:
							
				      \begin{picture}(175,35)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,20){}
               \node(2)(50,20){}
               \node(3)(80,20){}
               \node[Nmarks=r](4)(50,0){}

               \drawloop[loopangle=90](1){{\tt a},$\lambda$/X}
               \drawedge[curvedepth=0](1,2){{\tt b},X/$\lambda$}
               \drawedge[curvedepth=15](1,3){{\tt c},X/$\lambda$}
               \drawloop[loopangle=90](2){{\tt b},X/$\lambda$}
               \drawedge[curvedepth=0](2,3){{\tt c},X/$\lambda$}
               \drawloop[loopdepth=90](3){{\tt c},X/$\lambda$}
               \drawedge[curvedepth=0, ELside=r](1,4){$\lambda$,X/$\lambda$}
               \drawedge[curvedepth=0](2,4){$\lambda$,X/$\lambda$}
               \drawedge[curvedepth=0](3,4){$\lambda$,X/$\lambda$}
               \drawloop[loopangle=270](4){$\lambda$,X/$\lambda$}
             \end{picture}

			 \end{list}

 \item {\footnotesize Seja a GLC
       \begin{quote}
			  \item $G$: $A \,\rightarrow\, AA \,|\, {\tt 01} \,|\, {\tt 1}$
			 \end{quote}
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Mostre que $G$ é ambígua apresentando duas árvores de derivação para a menor palavra para a qual existam
			        duas árvores de derivação.
			  \item Construa duas GLCs equivalentes a $G$, ambas não ambíguas.
			 \end{list}}

       \textit{Solução}:

			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Duas árvores de derivação para {\tt 111}:
				
							\begin{picture}(75,40)(-15,0)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node(1)(17.5,35){A}
               \node(2)(10,25){A}
               \node(3)(25,25){A}
               \node(4)(5,15){A}
               \node(5)(15,15){A}
               \node(6)(25,15){\tt 1}
               \node(7)(5,5){\tt 1}
               \node(8)(15,5){\tt 1}

               \drawedge[curvedepth=0](1,2){}
               \drawedge[curvedepth=0](1,3){}
               \drawedge[curvedepth=0](2,4){}
               \drawedge[curvedepth=0](2,5){}
               \drawedge[curvedepth=0](3,6){}
               \drawedge[curvedepth=0](4,7){}
               \drawedge[curvedepth=0](5,8){}
             \end{picture}
							\begin{picture}(75,40)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node(1)(17.5,35){A}
               \node(2)(10,25){A}
               \node(3)(25,25){A}
               \node(4)(10,15){\tt 1}
               \node(5)(20,15){A}
               \node(6)(30,15){A}
               \node(7)(20,5){\tt 1}
               \node(8)(30,5){\tt 1}

               \drawedge[curvedepth=0](1,2){}
               \drawedge[curvedepth=0](1,3){}
               \drawedge[curvedepth=0](2,4){}
               \drawedge[curvedepth=0](3,5){}
               \drawedge[curvedepth=0](3,6){}
               \drawedge[curvedepth=0](5,7){}
               \drawedge[curvedepth=0](6,8){}
             \end{picture}

			  \item Duas GLCs equivalentes a $G$ não ambíguas:

              \begin{quote}
							 $P \,\rightarrow\, P X \,|\, X$ \\
							 $X \,\rightarrow\, {\tt 1} \,|\, {\tt 01}$
							\end{quote}
              e
              \begin{quote}
							 $P \,\rightarrow\, X P \,|\, X$ \\
							 $X \,\rightarrow\, {\tt 1} \,|\, {\tt 01}$
							\end{quote}
			 \end{list}
\end{enumerate}
\end{document}

