\documentclass[12pt,a4paper]{report}

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

\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\textbf{Segunda Prova}/especial/Solução do professor \hfill 30/10/2015 \\
 
\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Encontre uma expressão regular que denote a linguagem:
       $$\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ tem um único {\tt b} e
			 não termina com {\tt cc}}\}\mbox{.}$$}

       \textit{Solução}: $(a+c)^*b(c^*a)^*(\lambda+c)$

 \item {\footnotesize Construa um AFD  reconheça $((aa+bb)^*cc)^*$.}

       \textit{Solução}:

	        		\mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(90,40)\footnotesize
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

                \node[Nmarks=ir, iangle=180](0)(20,20){}
                \node(1)(40,35){}
                \node(2)(40,20){}
                \node(3)(40,5){}
                \node(4)(60,20){}

                \drawedge[curvedepth=3](0,1){\tt a}
                \drawedge[curvedepth=3](0,2){\tt c}
                \drawedge[curvedepth=-3, ELside=r](0,3){\tt b}
                \drawedge[curvedepth=3](1,4){\tt a}
                \drawedge[curvedepth=3](2,0){\tt c}
                \drawedge[curvedepth=3](3,4){\tt b}
                \drawedge[curvedepth=3](4,1){\tt a}
                \drawedge[curvedepth=0, ELside=r](4,2){\tt c}
                \drawedge[curvedepth=3](4,3){\tt b}
               \end{picture}
              }

 \item {\footnotesize Construa uma GLC e um AP para a linguagem $\{{\tt 0}^m{\tt 1}^{m+n}{\tt 0}^n \,|\, m+n\geq 2\}$.}

       \textit{Solução}:
       \begin{quote}
			  $P\,\rightarrow\, {\tt 00}A{\tt 11}B \,|\, {\tt 0}A{\tt 11}B{\tt 0} \,|\, A{\tt 11}B{\tt 00}$ \\
			  $A\,\rightarrow\, {\tt 0}A{\tt 1} \,|\, \lambda$ \\
			  $B\,\rightarrow\, {\tt 1}B{\tt 0} \,|\, \lambda$
			 \end{quote}
 \item {\footnotesize Descreva como seria possível, dada uma gramática regular $G$, determinar uma gramática
       regular $G'$ tal que $L(G)=L(G')$ e $G'$ não é ambígua.}

       \textit{Solução}: Utilizando os métodos vistos no curso:
       \begin{enumerate}
			  \item[1.] A partir de $G$, obtenha um AFN $M$ tal que $L(M)=L(G)$;
				\item[2.] A partir de $M$, obtenha um AFD $M'$ tal que $L(M')=L(M)$;
				\item[3.] A partir de $M'$, obtenha uma gramática redular $G'$ tal que $L(G')=L(M')$.
			 \end{enumerate}
			 Tem-se que $L(G)=L(M)=L(M')=L(G')$ e, assim como as computações do AFD $M'$ para cada palavra são
			 únicas, as derivações de $G'$ para cada palavra são únicas. Logo, $L(G)=L(G')$ e $G'$ não é
			 ambígua.
 \item {\footnotesize Construa uma gramática na forma normal de Chomsky equivalente à gramática:
       \begin{quote}
        $S \,\rightarrow\, AB \,|\, SCB$ \\
        $A \,\rightarrow\, {\tt a}A \,|\, C$ \\
        $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$ \\
        $C \,\rightarrow\, {\tt c}C \,|\, \lambda$
			 \end{quote}
       Deverão ser seguidos os passos recomendados em aula (os mesmos que são recomendados no
			 livro texto).}

       \textit{Solução}:
       \begin{enumerate}
			  \item[1.] Eliminação de variáveis anuláveis:
				
				          O conjunto de variáveis anuláveis é $\{C,A\}$. GLC obtida:
       \begin{quote}
        $S \,\rightarrow\, AB \,|\, B \,|\, SCB \,|\, SB $ \\
        $A \,\rightarrow\, {\tt a}A \,|\, {\tt a} \,|\, C$ \\
        $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$ \\
        $C \,\rightarrow\, {\tt c}C \,|\, {\tt c}$
			 \end{quote}
			  \item[2.] Eliminação de regras unitárias:
				
				         $enc(S)=\{S,B\}$; $enc(A)=\{A,C\}$; $enc(B)=\{B\}$; $enc(C)=\{C\}$. GLC obtida:
       \begin{quote}
        $S \,\rightarrow\, AB \,|\, {\tt b}B \,|\, {\tt b} \,|\, SCB \,|\, SB $ \\
        $A \,\rightarrow\, {\tt a}A \,|\, {\tt a} \,|\, {\tt c}C \,|\, {\tt c}$ \\
        $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$ \\
        $C \,\rightarrow\, {\tt c}C \,|\, {\tt c}$
			 \end{quote}
			  \item[3.] Substituição de terminais por variáveis:
				
       \begin{quote}
        $S \,\rightarrow\, AB \,|\, YB \,|\, {\tt b} \,|\, SCB \,|\, SB $ \\
        $A \,\rightarrow\, XA \,|\, {\tt a} \,|\, ZC \,|\, {\tt c}$ \\
        $B \,\rightarrow\, YB \,|\, {\tt b}$ \\
        $C \,\rightarrow\, ZC \,|\, {\tt c}$ \\
        $X \,\rightarrow\, {\tt a}$ \\
        $Y \,\rightarrow\, {\tt b}$ \\
        $Z \,\rightarrow\, {\tt c}$
			 \end{quote}
			  \item[4.] Quebra de regras:
				
       \begin{quote}
        $S \,\rightarrow\, AB \,|\, YB \,|\, {\tt b} \,|\, SR \,|\, SB $ \\
        $A \,\rightarrow\, XA \,|\, {\tt a} \,|\, ZC \,|\, {\tt c}$ \\
        $B \,\rightarrow\, YB \,|\, {\tt b}$ \\
        $C \,\rightarrow\, ZC \,|\, {\tt c}$ \\
        $X \,\rightarrow\, {\tt a}$ \\
        $Y \,\rightarrow\, {\tt b}$ \\
        $Z \,\rightarrow\, {\tt c}$ \\
        $R \,\rightarrow\, CB$
			 \end{quote}
			 \end{enumerate}

 \item {\footnotesize Seja $L=\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,n,k\geq 0, m\not=n \mbox{ ou } n\not=k\}$. 
       Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L$ é LLC.
        \item $\overline{L}$ não é LLC.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L$ é LLC, pois é gerada pela GLC:
              \begin{quote}
               $S \,\rightarrow\, XC \,|\, AY$ \\
               $X \,\rightarrow\, {\tt a}X{\tt b} \,|\, {\tt a}A \,|\, B{\tt b}$ \\
               $Y \,\rightarrow\, {\tt b}Y{\tt c} \,|\, {\tt b}B \,|\, C{\tt c}$ \\
               $A \,\rightarrow\, {\tt a}A \,|\, \lambda$ \\
               $B \,\rightarrow\, {\tt b}B \,|\, \lambda$ \\
               $C \,\rightarrow\, {\tt c}C \,|\, \lambda$
		         \end{quote}
        \item $\overline{L}$ não é LLC, pois  $\overline{L}=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\geq 0\}$.
       \end{list}     
\end{enumerate}

\end{document}
 