\documentclass[12pt, a4paper]{report}
\newcounter{conta}
\pagestyle{empty}
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Terceira Prova} \hfill 27/03/02

\vspace*{.5cm}
{\bf $\Rightarrow$ Cada quest\~ao vale 3 pontos.}

\begin{enumerate}
 \item Construa um aut\^omato com pilha determin\'{\i}stico, se poss\'{\i}vel, que
       reconhe\c ca a linguagem: \[\{x\#y\,\,|\,\,x,y\in\{\verb+0+,\verb+1+\}^* \mbox{ e }
       n_{\verb+0+}(x)=n_{\verb+1+}(y) \}\mbox{,}\]
       onde $n_a(w)$ \'e a quantidade de s\'{\i}mbolos $a$ na palavra $w$. Se
       n\~ao for poss\'{\i}vel, construa um n\~ao determin\'{\i}stico.

 \item Descreva um m\'etodo que, dado um aut\^omato com pilha $M$ que re\-co\-nhe\-ce uma
       linguagem \underline{por pilha vazia}, obt\'em um aut\^omato com pilha que re\-co\-nhe\-ce
       a mesma linguagem \underline{por estado final}.

 \item Seja a gram\'atica $G=(\{P,A\},\{\verb+a+,\verb+b+,\verb+c+,\verb|+|\},R,P)$,
       onde $R$ consta das regras:
       \begin{enumerate}
        \item[\ ] $P\,\,\rightarrow\,\,\verb|a+| P \,\,|\,\, A$
        \item[\ ] $A\,\,\rightarrow\,\, P\verb|+b| \,\,|\,\, \verb|c|$
       \end{enumerate}
       Qual \'e a linguagem gerada por $G$? Mostre que $G$ \'e amb\'{\i}g\"ua usando a
       {\em menor\/} palavra poss\'{\i}vel. Construa uma gram\'atica livre do contexto
       equivalente a $G$ n\~ao amb\'{\i}g\"ua.

 \item Descreva um m\'etodo para eliminar todas as vari\'aveis in\'uteis de uma
       gram\'atica livre do contexto.

 \item Construa uma gram\'atica sem regras $\lambda$ e sem regras unit\'arias equivalente
       \`a gram\'atica $(\{P,A,B,C,D\},\{\verb+a+,\verb+b+,\verb+d+\},R,P)$, onde $R$
       consta das regras:
       \begin{enumerate}
        \item[\ ] $P\,\,\rightarrow\,\, A B \verb|a| C$
        \item[\ ] $A\,\,\rightarrow\,\, B C$
        \item[\ ] $B\,\,\rightarrow\,\, \verb|b| \,\,|\,\, \lambda$
        \item[\ ] $C\,\,\rightarrow\,\, D \,\,|\,\, \lambda$
        \item[\ ] $D\,\,\rightarrow\,\, \verb|d|$
       \end{enumerate}

\end{enumerate}
\end{document}