\documentclass[12pt]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{3cm}

\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Departamento de Ci\^encia da Computa\c c\~ao \hfill ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill
                            $1^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Terceira Prova} \hfill 31/07/2003 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turmas B e G}

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

\vspace*{1mm}
\begin{enumerate}
 \item Construa um aut\^omato com pilha determin\'{\i}stico que reconhe\c ca a
       linguagem $\{\verb+a+^n\verb+b+^{2n}\verb+c+^{2k} \,\,|\,\, n,k\geq 0\}$, se for
       poss\'{\i}vel construir; se n\~ao for poss\'{\i}vel, explique porque.

 \item Construa um aut\^omato com pilha que reconhe\c ca, e uma gram\'atica
       livre do contexto (GLC) que gere $\{\verb+0+^{m}\verb+1+^n\verb+0+ \,\,|\,\, m>n\}$.

 \item Dadas duas GLC's $G_1$ e $G_2$, como seriam obtidas GLC's para re\-co\-nhe\-cer:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(L(G_1)\cup L(G_2))^2$?
        \item $(L(G_1)\cup L(G_2))^*$?
       \end{list}

 \item Seja a gram\'atica $G=(\{P,A,B\},\{\verb+a+,\verb+b+\},R,P)$,
       onde $R$ consta das regras:
      \begin{enumerate}
       \item[\ \ ] $P\,\,\rightarrow\,\, AB\,\,|\,\,\lambda$
       \item[\ \ ] $A\,\,\rightarrow\,\, aAb\,\,|\,\,\lambda$
       \item[\ \ ] $B\,\,\rightarrow\,\, \verb+b+B\verb+a+\,\,|\,\,\lambda$
      \end{enumerate}
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item Que linguagem $G$ gera?
       \item Remova a ambiguidade de $G$ modificando-a o m\'{\i}nimo poss\'{\i}vel.
      \end{list}

 \item Obtenha uma GLC equivalente \`a GLC $G$ da quest\~ao anterior sem regras
       $\lambda$ e sem regras unit\'arias.
\end{enumerate}

\end{document}
 
