\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 W/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{ contém  {\tt a}, mas não contém {\tt ba}}\}$, com 3 estados;
			  \item $L_2=\{{\tt a},{\tt b}\}^*\{{\tt b},{\tt c}\}^*\{{\tt a},{\tt c}\}$, com 3 estados.
			 \end{list}}

        \textit{Solução}: O número mínimo é 4 estados (\textbf{na correção dei 2,5 pontos de graça\ldots}):\\
				
				      \begin{picture}(75,20)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node(1)(10,10){}
               \node[Nmarks=i, iangle=270](2)(25,10){}
               \node[Nmarks=r](3)(40,10){}
               \node[Nmarks=r](4)(55,10){}

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

               \put(0,20){\makebox(0,0)[l]{(b)}}
               \drawloop[loopangle=90](1){{\tt a},{\tt b}}
               \drawedge[curvedepth=0](1,2){{\tt a},{\tt b}}
               \drawloop[loopangle=90](2){{\tt b},{\tt c}}
               \drawedge[curvedepth=0](2,3){{\tt a},{\tt c}}
              \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}(75,25)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
						
               \node(1)(10,12){}
               \node[Nmarks=i, iangle=270](2)(25,12){}
               \node(3)(40,12){}
               \node(4)(55,12){}

               \put(0,20){\makebox(0,0)[l]{(a)}}
               \drawloop[loopangle=90](1){{\tt b}}
               \drawedge[curvedepth=3](1,2){{\tt c}}
               \drawloop[loopangle=90](2){{\tt c}}
               \drawedge[curvedepth=3](2,1){{\tt b}}
               \drawedge[curvedepth=3](2,3){{\tt a}}
               \drawloop[loopangle=90](3){{\tt a},{\tt c}}
               \drawedge[curvedepth=3](3,4){{\tt b}}
               \drawloop[loopangle=90](4){{\tt b}}
               \drawedge[curvedepth=3](4,3){{\tt c}}


               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node(1a)(80,12){}
               \node(2a)(100,12){}
               \node[Nmarks=r](3a)(120,12){}

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

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

 \item {\footnotesize Encontre expressões regulares que denotem as linguagem $L_1$ e $L_2$ da primeira questão e também daquela
       reconhecida pelo AFN:

       \begin{picture}(120,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(20,10){1}
        \node[Nmarks=ir, iangle=0](2)(40,10){2}

        \drawloop[loopangle=90](1){{\tt a}}
        \drawedge[curvedepth=4](1,2){{\tt a}}
        \drawloop[loopangle=90](2){{\tt c}}
        \drawedge[curvedepth=4](2,1){{\tt b}}
       \end{picture}}

        \textit{Solução}:

        ER para $L_1$: $(c+bb^*c)^*a(a+c+bb^*c)^*(\lambda+bb^*)$.

				ER para $L_2$: $(a+b)^*(b+c)^*(a+c)$.
				
				Para o AFN, será construída uma ER por partes. Começa-se com o diagrama ER:

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

        \drawedge[curvedepth=0](0,1){$\lambda$}
        \drawedge[curvedepth=-10, ELside=r](0,2){$\lambda$}
        \drawloop[loopangle=90](1){$a$}
        \drawedge[curvedepth=3](1,2){$a$}
        \drawloop[loopangle=90](2){$c$}
        \drawedge[curvedepth=3](2,1){$b$}
        \drawedge[curvedepth=0](2,3){$\lambda$}
        \drawedge[curvedepth=11](1,3){$\lambda$}
       \end{picture}

       Eliminando-se o estado 1:

       \begin{picture}(120,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](0)(20,10){0}
        \node(2)(60,10){2}
        \node[Nmarks=r](3)(80,10){3}

        \drawedge[curvedepth=0](0,2){$\lambda+a^*a$}
        \drawedge[curvedepth=-6, ELside=r](0,3){$a^*$}
        \drawloop[loopangle=90](2){$c+ba^*a$}
        \drawedge[curvedepth=0](2,3){$\lambda+ba^*$}
       \end{picture}

       Eliminando-se o estado 2, obtém-se a ER: $a^*+(\lambda+a^*a)(c+ba^*a)^*(\lambda+ba^*)$.

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

			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item GLC que gera $L$:
				      \begin{quote}
							 $P \,\rightarrow\, {\tt a}AC \,|\, AC{\tt c}$ \\
							 $A \,\rightarrow\, {\tt a}A{\tt b} \,|\, {\tt a}A \,|\, \lambda$ \\
							 $C \,\rightarrow\, {\tt b}C{\tt c} \,|\, C{\tt c} \,|\, \lambda$
							\end{quote}
			  \item APN que reconhece $L$:

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

				      $\begin{array}{lll}
							 \delta(1,\lambda,\lambda)=[2,P] & \delta(2,\lambda,A)=[2,\lambda] & \delta(2,{\tt a},{\tt a})=[2,\lambda] \\
							 \delta(2,\lambda,P)=[2,{\tt a}AC]&\delta(2,\lambda,C)=[2,{\tt b}C{\tt c}]& \delta(2,{\tt b},{\tt b})=[2,\lambda] \\
							 \delta(2,\lambda,P)=[2,AC{\tt c}]&\delta(2,\lambda,C)=[2,C{\tt c}]    & \delta(2,{\tt c},{\tt c})=[2,\lambda] \\
							 \delta(2,\lambda,A)=[2,{\tt a}A{\tt b}]& \delta(2,\lambda,C)=[2,\lambda]  \\
							 \delta(2,\lambda,A)=[2,{\tt a}A]       \\
							\end{array}$
							
							Outra solução:
							
				      \begin{picture}(175,20)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,10){}
               \node(2)(45,10){}
               \node(3)(70,10){}
               \node[Nmarks=r](4)(95,10){}
               \node[Nmarks=r](5)(120,10){}

               \drawedge[curvedepth=0](1,2){$\lambda$,$\lambda$/F}
               \drawloop[loopangle=90](2){{\tt a},$\lambda$/X}
               \drawedge[curvedepth=0](2,3){$\lambda$,$\lambda$/$\lambda$}
               \drawloop[loopangle=90](3){{\tt b},X/$\lambda$}
               \drawedge[curvedepth=0](3,4){{\tt b},F/$\lambda$}
               \drawloop[loopdepth=90](4){\shortstack{{\tt b},$\lambda$/$\lambda$\\ {\tt b},$\lambda$/X}}
               \drawedge[curvedepth=0](4,5){{\tt c},X/$\lambda$}
               \drawloop[loopangle=90](5){{\tt c},X/$\lambda$}
             \end{picture}
			 \end{list}

 \item {\footnotesize Seja a GLC
       \begin{quote}
			  \item $G$: $A \,\rightarrow\, {\tt 0}A \,|\, {\tt 0}A{\tt 11} \,|\, \lambda$
			 \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 0011}:
				
							\begin{picture}(55,55)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node(1)(20,50){A}
               \node(2)(13,35){\tt 0}
               \node(3)(27,35){A}
               \node(4)(12,20){\tt 0}
               \node(5)(22,20){A}
               \node(6)(32,20){\tt 1}
               \node(7)(42,20){\tt 1}
               \node(8)(22,5){$\lambda$}

               \drawedge[curvedepth=0](1,2){}
               \drawedge[curvedepth=0](1,3){}
               \drawedge[curvedepth=0](3,4){}
               \drawedge[curvedepth=0](3,5){}
               \drawedge[curvedepth=0](3,6){}
               \drawedge[curvedepth=0](3,7){}
               \drawedge[curvedepth=0](5,8){}
             \end{picture}
							\begin{picture}(75,55)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node(1)(27,50){A}
               \node(2)(12,35){\tt 0}
               \node(3)(22,35){A}
               \node(4)(32,35){\tt 1}
               \node(5)(42,35){\tt 1}
               \node(6)(16,20){\tt 0}
               \node(7)(28,20){A}
               \node(8)(28,5){$\lambda$}

               \drawedge[curvedepth=0](1,2){}
               \drawedge[curvedepth=0](1,3){}
               \drawedge[curvedepth=0](1,4){}
               \drawedge[curvedepth=0](1,5){}
               \drawedge[curvedepth=0](3,6){}
               \drawedge[curvedepth=0](3,7){}
               \drawedge[curvedepth=0](7,8){}
             \end{picture}
			  \item Duas GLCs equivalentes a $G$ não ambíguas:

              \begin{quote}
							 $A \,\rightarrow\, {\tt 0}A \,|\, B$ \\
							 $B \,\rightarrow\, {\tt 0}B{\tt 11} \,|\, \lambda$
							\end{quote}
              e
              \begin{quote}
							 $A \,\rightarrow\, {\tt 0}A{\tt 11} \,|\, B$ \\
							 $B \,\rightarrow\, {\tt 0}B \,|\, \lambda$ \\
							\end{quote}
			 \end{list}

	\end{enumerate}

\end{document}
