\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 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turma W \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 Construa
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item um APD que reconhe\c{c}a $\{{\tt 0}^n{\tt 1}^{2n}{\tt 0}^{k}{\tt 2}\,|\, n,k\geq 0\}$; e
        \item um APN que reconhe\c{c}a $\{{\tt 0}^n{\tt 1}^{2n}{\tt 0}^{k}\,|\, n,k\geq 0\}$.
       \end{list}

 \item Construa GLCs para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt 0}^m{\tt 1}^{m+n}{\tt 0}^{n}\,|\,m,n\geq 0\}$.
        \item $L_2=\{{\tt 0}^m{\tt 1}^{n}{\tt 0}^{m+n}\,|\,m,n\geq 0\}$.
        \item $L_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\, {\tt a}P \,|\, {\tt a}P{\tt b}P \,|\, \lambda$
              \end{quote} 
              \'e amb\'{\i}gua.
        \item Construa uma GLC sem regras $\lambda$ e sem regras unit\'arias equivalente a:
              \begin{tabbing}
               xxx\= \kill
                  \> $P \,\rightarrow\, A \,|\, BC$ \\
                  \> $A \,\rightarrow\, B \,|\, C$ \\
                  \> $B \,\rightarrow\, {\tt b}B{\tt b} \,|\, \lambda$ \\
                  \> $C \,\rightarrow\, {\tt ab}C \,|\, {\tt c}$ \\
              \end{tabbing}
       \end{list}

 \item Prove que se $L$ \'e LLC e $R$ regular, $L-R$ \'e LLC. Use isso para mostrar que
       \begin{quote}
        $\{{\tt a}^n\,|\, n \mbox{ \'e n\'umero par ou primo}\}$
       \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 pilha determin\'{\i}stico;
	\item GLC: gram\'atica livre do contexto.
	\item LLC: linguagem livre do contexto.
\end{itemize}
\end{document}
