\documentclass[11pt, 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\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turma N\hfill {05/06/2012}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos.

\vspace*{2mm}
\begin{enumerate}
 \item Construa:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item um APD que reconheça $\{{\tt 0}^m{\tt 1}^{n}\,|\, m<n\}$;
        \item um APN que reconheça $\{{\tt 0}^m{\tt 1}^{n}\,|\, m>n\}$.
       \end{list}

 \item Construa GLCs que gerem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^n\,|\,m>n\}$.
        \item $L_2=\{{\tt b}^m{\tt c}^{n}\,|\,m<n\}$.
        \item $L_1((L_2L_1)\cup L_2^*)$.
       \end{list}

 \item Ainda sobre GLCs:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que a GLC
              \begin{quote}
               $P\,\rightarrow\, A \,|\, B$ \\
               $A\,\rightarrow\, aAa \,|\, \lambda$ \\
               $B\,\rightarrow\, bBb \,|\, \lambda$
              \end{quote} 
              \'e amb\'{\i}gua. Construa uma GLC equivalente n\~ao amb\'{\i}gua.
        \item Obtenha uma GLC na FNC equivalente a:
              \begin{tabbing}
               xxx\= \kill
                  \> $P \,\rightarrow\, ABC$ \\
                  \> $A \,\rightarrow\, {\tt a}A \,|\, BC \,|\, {\tt a}$ \\
                  \> $B \,\rightarrow\, {\tt b}B{\tt b} \,|\, C$ \\
                  \> $C \,\rightarrow\, {\tt abc} \,|\, A \,|\, \lambda$ \\
              \end{tabbing}
       \end{list}

 \item Prove que se $L$ n\~ao \'e LLC e \'e retirado um conjunto finito de palavras de $L$,
       a linguagem resultante n\~ao \'e LLC. Use isso para provar que
       \begin{quote}
        $\{{\tt a}^k{\tt b}^k{\tt c}^k\,|\, k>10^{10}\}$
       \end{quote}
       n\~ao \'e uma linguagem livre do contexto.
\end{enumerate}

\vspace*{3mm}
\hrule

\vspace*{.5mm}
\hrule
\vspace*{3mm}
\begin{itemize}
	\item APN: aut\^omato de pilha n\~ao determin\'{\i}stico.
	\item APD: aut\^omato de piliha determin\'{\i}stico.
	\item GLC: gram\'atica livro do contexto.
	\item LLC: linguagem livre do contexto.
	\item FNC: forma normal de Chomsky.
\end{itemize}
\end{document}
