\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\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 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turmas N e G\hfill {16/06/2009}

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

\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{\textbf{Aten\c{c}\~ao}:
Em todas as quest\~oes dever\~ao ser usados m\'etodos vistos em aula ou no livro-texto.
Qualquer resultado, mesmo que correto, obtido de forma \emph{ad-hoc\/} n\~ao ser\'a considerado.
Assim, \'e importante que explicite os passos executados em cada solu\c{c}\~ao apresentada.}}

\begin{enumerate}
 \item Sejam $L_1=\{{\tt 0}^n{\tt 1}^{2n}\,|\, n\geq 0\}$ e $L_2=\{{\tt 0}^{2n}{\tt 1}^{n}\,|\, n\geq 0\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um APD que reconhe\c{c}a $L_1$ e outro que reconhe\c{c}a $L_2$.
        \item Construa um APN que reconhe\c{c}a $L_1\cup L_2$.
       \end{list}

 \item Construa GLCs para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt 0}^k{\tt 1}^n\,|\,k=n \mbox{ ou } k=2n\}$.
        \item $L_2=\{{\tt 1}^n{\tt 0}^{k}\,|\,k>2n\}$.
        \item $L_1(L_2^*)$.
       \end{list}

 \item Ainda sobre GLCs:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que a GLC
              \begin{quote}
               $P\,\rightarrow\, {\tt a}P \,|\, {\tt a}P{\tt b} \,|\, \lambda$
              \end{quote} 
              \'e amb\'{\i}gua. Construa uma GLC equivalente n\~ao amb\'{\i}gua.
        \item Construa uma GLC sem regras $\lambda$ equivalente \`a gram\'atica:
              \begin{tabbing}
               xxx\= \kill
                  \> $P \,\rightarrow\, ABC \,|\, CBA$ \\
                  \> $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^{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.
\end{itemize}
\end{document}
