\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{.5cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W \hfill {17/06/2010}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 3 pontos cada uma, exceto as questões 4 e 5, que valem 2 pontos cada uma.

\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 um APD que reconhe\c{c}a $\{{\tt a}^{n}{\tt b}^{n}{\tt abc}\,|\,n\geq 0\}$.

 \item Faça uma GLC que gere $\{{\tt a}^i{\tt b}^n{\tt c}^j\,|\,n > i+j\}$.

 \item Seja a gram\'atica $G$:
       \begin{enumerate}
	      \item[\ ] $E \,\rightarrow\, E {\tt +} T \,|\, T$
	      \item[\ ] $T \,\rightarrow\, T {\tt *} F \,|\, F$
	      \item[\ ] $F \,\rightarrow\, {\tt a} \,|\, {\tt (} E {\tt )}$
       \end{enumerate}
       Obtenha uma GLC na forma normal de Chomsky equivalente a $G$.

 \item Sejam $L_1=\{ww^R \,|\, w\in \{{\tt 0},{\tt 1}\}^+\}$ e
             $L_2=\{w\in \{{\tt 0},{\tt 1}\}^+\,|\,w=w^R\}$. Construa uma GLC que gere $((L_1L_1)^*L_2)^*$.

 \item Obtenha um APN que aceite $L(G)$ a partir das regras da gramática $G$ da questão 3.

 \item Mostre que \textit{sim} ou que \textit{n\~ao} ou que \textit{às vezes sim e às vezes não}:
       $L_1\cup \overline{L_2}$ é LLC se
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1$ é LLC e $L_2$ é regular.
        \item $L_1$ é regular e $L_2$ é LLC.
        \item $L_1$ não é LLC e $L_2$ é regular.
       \end{list}
\end{enumerate}

\vspace*{3mm}
\hrule

\vspace*{.5mm}
\hrule
\vspace*{3mm}
\begin{itemize}
	\item APD: aut\^omato de pilha determin\'{\i}stico;
	\item APN: aut\^omato de pilha não determin\'{\i}stico;
	\item GLC: gram\'atica livre do contexto.
	\item LLC: linguagem livre do contexto.
\end{itemize}
\end{document}
