\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}

\pagestyle{empty}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} \hfill 06/11/2006

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

 \item Seja a linguagem:
       $L=\{{\tt a}^{n+k}{\tt b}^n{\tt c}^k\,|\,n,k\geq 0\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um APD que reconhe\c{c}a $L$.
        \item Construa uma GLC que gere $L$.
       \end{list}

 \item Seja a GLC $G$:
	\begin{enumerate}
	 \item[\ ]$P \,\rightarrow\, {\tt aa}A \,|\, B{\tt bb} \,|\, \lambda$
	 \item[\ ]$A \,\rightarrow\, P{\tt bb}$
	 \item[\ ]$B \,\rightarrow\, {\tt aa}P$
	\end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada por $G$?
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item \underline{Usando o m\'etodo visto no curso}, construa uma GLC
       equivalente \`a GLC a seguir sem vari\'aveis
       in\'uteis.
	\begin{enumerate}
	 \item[\ ]$P \,\rightarrow\, ABC \,|\, {\tt a}BB$
	 \item[\ ]$A \,\rightarrow\, CC$
	 \item[\ ]$B \,\rightarrow\, {\tt a}B \,|\, {\tt a}$
	 \item[\ ]$C \,\rightarrow\, {\tt a}C \,|\, CB$
	 \item[\ ]$D \,\rightarrow\, BDB \,|\, {\tt b}$
	\end{enumerate}


 \item  Seja a gram\'atica:
	\begin{enumerate}
	 \item[\ ] $S\,\rightarrow\, {\tt a}A{\tt b}B \,|\, A$
	 \item[\ ] $A\,\rightarrow\,{\tt a} AB \,|\, \lambda$
	 \item[\ ] $B\,\rightarrow\,{\tt b} BA \,|\, \lambda$
	\end{enumerate}
        \underline{Usando o m\'etodo visto no curso}, obtenha uma GLC
         equivalente na forma normal de Chomsky.

 \item Mostre que as linguagens livres do contexto n\~ao s\~ao fechadas sob
       diferen\c ca nem sob diferen\c ca sim\'etrica. Denotando diferen\c{c}a
       sim\'etrica por ``$\odot$'', $L_1\odot L_2=(L_1-L_2)\cup(L_2-L_1)$.

\end{enumerate}

\end{document}




