\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
{\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $2^{\mbox{\underline{o}}}$ semestre de 2004 \\
Professor: Newton Jos\'e Vieira \\
{\bf Terceira Prova}/Especial \hfill 30/11/2004

\vspace*{3mm}
\noindent Cada quest\~ao vale 3 pontos.

\begin{enumerate}
 \item Para cada linguagem abaixo, construa um aut\^omato determin\'{\i}stico, se poss\'{\i}vel.
       Caso contr\'ario, construa um aut\^omato n\~ao determin\'{\i}stico.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\, n<k\}$
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\, n>k\}$
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $M$ um aut\^omato a pilha n\~ao determin\'{\i}stico que reconhece uma certa
              linguagem $L$ por estado final. Mostre como obter um aut\^omato a pilha que reconhece
              $L\cup\{\lambda\}$ por pilha vazia.
        \item Seja $M$ um aut\^omato a pilha n\~ao determin\'{\i}stico que reconhece uma certa
              linguagem $L$ por pilha vazia. Mostre como obter um aut\^omato a pilha que reconhece
              $L$ por estado final.
        \end{list}

 \item Construa gram\'aticas livre do contexto (GLC's) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{\verb+0+^n\verb+1+^k\,\,|\,\, 2n\leq k \leq 3n\}$
        \item $L_2=\{\verb+a+^n\verb+b+^k\verb+c+^m\,\,|\,\,k=2n+m\}$
        \item $(L_1\cup L_2)^2$
       \end{list}

 \item Seja a GLC $G=(\{E,D\},\{\verb+0+,\verb+1+,+\},R,E)$, onde $R$ consta das regras:
       \begin{tabbing}
        $E\,$\=$\,\rightarrow E+E\,\,|\,\, (E)\,\,|\,\, D$ \\
        $D$   \>$\,\rightarrow \verb+0+\,\,|\,\,\verb+1+$
       \end{tabbing}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}g\"ua.
        \item Construa uma GLC n\~ao amb\'{\i}gua para $L(G)$.
       \end{list}
 \item Seja a GLC $G=(\{E,D\},\{\verb+0+,\verb+1+,+\},R,E)$, onde $R$ consta das regras:
       \begin{tabbing}
        $E\,$\=$\,\rightarrow E+E\,\,|\,\, (E)\,\,|\,\, D$ \\
        $D$   \>$\,\rightarrow \verb+0+\,\,|\,\,\verb+1+$
       \end{tabbing}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma GLC $G'$ equivalente a $G$ eliminando recurs\~ao \`a esquerda.
        \item Obtenha uma GLC $G''$ equivalente a $G'$ na forma normal de Chomsky.
       \end{list}

\end{enumerate}
\end{document}
