\documentclass[12pt]{report}

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

\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 2004 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Terceira Prova} \hfill {\bf Dura\c c\~ao: 1h:30m}

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

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

 \item Construa um APD que reconhe\c ca $\{{\tt a}^{2n}({\tt bc})^n\}
        \,|\, n\geq 0\}$.

 \item Construa um APN que reconhe\c ca $\{{\tt a}^m{\tt b}^n{\tt c}^k\}
        \,|\, m+n<k\}$.

 \item Construa GLC's que gerem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}} 
        \item $\{{\tt 0}^m{\tt 1}^n \,|\,\, 2n\leq m\leq 3n\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k \,|\, m+n<k\}$.
       \end{list}

 \item Dadas duas GLC's $G_1$ e $G_2$, sem vari\'aveis em comum, como seriam
       obtidas GLC's para re\-co\-nhe\-cer:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G_1)\cup L(G_2)$?
        \item $L(G_1)L(G_2)$?
        \item $L(G_1)^*$?
       \end{list}
       Nos 3 casos, se $G_1$ e $G_2$ n\~ao s\~ao amb\'{\i}g\"uas, a gram\'atica
       resultante pode ser amb\'{\i}g\"ua ou n\~ao? Justifique.

 \item Resolva \underline{usando os m\'etodos vistos em aula}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}} 
        \item Elimine regras $\lambda$ de:
              \begin{enumerate}
               \item[\ ] $X\,\rightarrow\, A B$
               \item[\ ] $A\,\rightarrow\, {\tt a} A \,|\, \lambda$
               \item[\ ] $B\,\rightarrow\, {\tt a} B {\tt b} \,|\, \lambda$
              \end{enumerate}

        \item Elimine regras unit\'arias de:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A \,|\, B$
               \item[\ ] $A\,\rightarrow\, {\tt a} A \,|\, B$
               \item[\ ] $B\,\rightarrow\, {\tt a} B {\tt b} \,|\, {\tt b}$
              \end{enumerate}

        \item Elimine recurs\~ao \`a esquerda de:
              \begin{enumerate}
               \item[\ ] $S\,\rightarrow\, {\tt a} S {\tt b} \,|\, S S \,|\, \lambda$
              \end{enumerate}
       \end{list}
\end{enumerate}

\end{document}
