\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2014 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W/Solução do professor \hfill {15/4/2014}

\vspace*{2mm}
\begin{enumerate}

 \item {\footnotesize Prove que $\{{\tt a}^m{\tt b}^n\,|\, \mbox{ $m$ é um número par e $n$ é um número primo}\}$ não é uma
       linguagem regular.}

       \textit{Solução:}

       Seja $L$ a linguagem em questão e suponha que ela seja regular. Neste caso, como as linguagens regulares são fechadas
			 sob interseção, $L\cap\{b\}^*$ tem que ser regular. Mas $L\cap \{b\}^*=\{{\tt b}^n\,|\, \mbox{ $n$ é um número primo}\}$, uma
			 linguagem não regular. Contradição! Logo, $L$ não é regular.

 \item {\footnotesize Encontre expressões regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ contém um, dois ou três {\tt 0}s$\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ contém número ímpar de {\tt 0}s e par de {\tt 1}s}\}$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $1^*01^*(\lambda+01^*(\lambda+01^*))$.
        \item Um AFD para a linguagem:
				      
              \begin{picture}(40,33)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

               \node[Nmarks=i](pp)(10,25){$pp$}
               \node[Nmarks=r](ip)(30,25){$ip$}
               \node(pi)(10,5){$pi$}
               \node(ii)(30,5){$ii$}

               \drawedge[curvedepth=2](pp,ip){$0$}
               \drawedge[curvedepth=2](pp,pi){$1$}
               \drawedge[curvedepth=2](ip,pp){$0$}
               \drawedge[curvedepth=2](ip,ii){$1$}
               \drawedge[curvedepth=2](pi,ii){$0$}
               \drawedge[curvedepth=2](pi,pp){$1$}
               \drawedge[curvedepth=2](ii,pi){$0$}
               \drawedge[curvedepth=2](ii,ip){$1$}
              \end{picture}
              \begin{picture}(50,33)(0,-5)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

               \put(0,15){\makebox(0,0)[l]{Eliminando \textit{ii}:}}
               \node[Nmarks=i](pp)(40,25){$pp$}
               \node[Nmarks=r](ip)(60,25){$ip$}
               \node(pi)(40,5){$pi$}

               \drawedge[curvedepth=2](pp,ip){$0$}
               \drawedge[curvedepth=2](pp,pi){$1$}
               \drawedge[curvedepth=2](ip,pp){$0$}
               \drawedge[curvedepth=8](ip,pi){$10$}
							 \drawloop[loopangle=0](ip){\tt 11}
               \drawedge[curvedepth=2](pi,pp){$1$}
               \drawedge[curvedepth=-3](pi,ip){$01$}
							 \drawloop[loopangle=270](pi){$00$}
              \end{picture}

              \begin{picture}(50,33)(0,-5)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

               \put(0,15){\makebox(0,0)[l]{Eliminando \textit{pi}:}}
               \node[Nmarks=i](pp)(40,5){pp}
               \node[Nmarks=r](ip)(80,5){ip}

               \drawloop[loopangle=90](pp){$1(00)^*1$}
               \drawedge[curvedepth=3](pp,ip){$0+1(00)^*01$}
               \drawloop[loopangle=90](ip){$11+10(00)^*01$}
               \drawedge[curvedepth=3](ip,pp){$0+10(00)^*1$}
              \end{picture}

              Expressão regular: \\
							$(1(00)^*1)^*(0+1(00)^*01)[11+10(00)^*01+(0+10(00)^*1)(1(00)^*1)^*(0+1(00)^*01)]^*$.
       \end{list}

 \item {\footnotesize Construa gramáticas livres do contexto para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n\,|\,n>2m\}$.
        \item $\{{\tt a}^m{\tt b}^k{\tt c}^n\,|\,k>m+n\}$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, {\tt a}P{\tt bb} \,|\, B$ \\
				      $B\,\rightarrow\, {\tt b}B \,|\, {\tt b}$
        \item $P \,\rightarrow\, ABC$ \\
              $A \,\rightarrow\, {\tt a}A{\tt b} \,|\, \lambda$ \\
				      $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$ \\
				      $C\,\rightarrow\, {\tt b}C{\tt c} \,|\, \lambda$

       \end{list}


 \item {\footnotesize Seja a gramática $G$:
       \begin{enumerate}
        \item[\ ] $X \,\rightarrow\, X{\tt a}X \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ é ambígua.
        \item Construa uma gramática não ambígua equivalente $G$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Duas derivações mais à esquerda para {\tt aa}:
				      \begin{quote}
							 $X\,\Rightarrow\, X{\tt a}X\,\Rightarrow\,{\tt a}X\,\Rightarrow\,{\tt a}X{\tt a}X\,\Rightarrow\,{\tt aa}X
							   \,\Rightarrow\,{\tt aa}$ \\
							 $X\,\Rightarrow\, X{\tt a}X\,\Rightarrow\,X{\tt a}X{\tt a}X\,\Rightarrow\,{\tt a}X{\tt a}X\,\Rightarrow\,{\tt aa}X
							   \,\Rightarrow\,{\tt aa}$
							\end{quote}
        \item Uma gramática não ambígua equivalente $G$:
				      \begin{quote}
               $X \,\rightarrow\, {\tt a}X \,|\, \lambda$
							\end{quote}
       \end{list}

 \item {\footnotesize Seja a gramática $H$:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, ABP \,|\, A$
	      \item[\ ] $A\,\rightarrow\,{\tt aa}A \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\,( A{\tt b} )\,|\, {\tt a}$
	     \end{enumerate}
       Obtenha uma GLC equivalente a $H$ na forma normal de Chomsky. Siga os passos: (a) determine variáveis anuláveis;
			 (b) elimine regras $\lambda$; (c) obtenha conjuntos \textit{enc}; (d) elimine regras unitárias; (e) obtenha FNC.}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Variáveis anuláveis: $\{A,P\}$.
		    \item Sem regras $\lambda$:
				      \begin{quote}
	             $P\,\rightarrow\, ABP \,|\, BP \,|\, AB \,|\, B\,|\, A \,|\, \lambda$ \\
	             $A\,\rightarrow\,{\tt aa}A \,|\, {\tt aa}$ \\
	             $B\,\rightarrow\,( A{\tt b} )\,|\, ( {\tt b} )\,|\, {\tt a}$
 							\end{quote}
				\item $\textit{enc}(P)=\{P,A,B\}$, $\textit{enc}(A)=\{A\}$, $\textit{enc}(B)=\{B\}$.
		    \item Sem regras unitárias:
				      \begin{quote}
	             $P\,\rightarrow\, ABP \,|\, BP \,|\, AB \,|\, ( A{\tt b} )\,|\, ( {\tt b} )\,|\, {\tt a}\,|\,
							                   {\tt aa}A \,|\, {\tt aa} \,|\, \lambda$ \\
	             $A\,\rightarrow\,{\tt aa}A \,|\, {\tt aa}$ \\
	             $B\,\rightarrow\,( A{\tt b} )\,|\, ( {\tt b} )\,|\, {\tt a}$
							\end{quote}
		    \item FNC/passo 1:
				      \begin{quote}
	             $P\,\rightarrow\, ABP \,|\, BP \,|\, AB \,|\, X AG Y\,|\, X G Y\,|\, {\tt a}\,|\,
							                   FFA \,|\, FF \,|\, \lambda$ \\
	             $A\,\rightarrow\,FFA \,|\, FF$ \\
	             $B\,\rightarrow\,X AG Y\,|\, X G Y\,|\, {\tt a}$ \\
							 $F\,\rightarrow\, {\tt a}$ \\
							 $G\,\rightarrow\, {\tt b}$ \\
							 $X\,\rightarrow\, ($ \\
							 $Y\,\rightarrow\, )$
							\end{quote}
		          FNC/passo 2:
				      \begin{quote}
	             $P\,\rightarrow\, AR \,|\, BP \,|\, AB \,|\, X S\,|\, X T\,|\, {\tt a}\,|\,
							                   FU \,|\, FF \,|\, \lambda$ \\
	             $A\,\rightarrow\,FU \,|\, FF$ \\
	             $B\,\rightarrow\,X S\,|\, X T\,|\, {\tt a}$ \\
							 $R\,\rightarrow\, BP$ \\
							 $S\,\rightarrow\, AT$ \\
							 $T\,\rightarrow\, GY$ \\
							 $U\,\rightarrow\, FA$ \\
							 $F\,\rightarrow\, {\tt a}$ \\
							 $G\,\rightarrow\, {\tt b}$ \\
							 $X\,\rightarrow\, ($ \\
							 $Y\,\rightarrow\, )$
							\end{quote}
       \end{list}
\end{enumerate}

\end{document}
