\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{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turma D \hfill {22/11/2012}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} A segunda questão vale 3 pontos; as restantes, 5 pontos cada uma.

\vspace*{2mm}
\begin{enumerate}
 \item Construa AFNs que reconheçam:
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item $L_1=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ não contém } {\tt abc}\}$, com 3 estados;
			  \item $L_2=\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\geq 2 \mbox{ e o primeiro e o último símbolos de $w$ são idênticos}\}$,
				      com 4 estados.
			 \end{list}

 \item Como construir um AFN$\lambda$ que reconheça $L_1L_2$ a partir de AFNs que reconheçam $L_1$ e $L_2$? Exemplifique
       com os AFNs obtidos na questão anterior.

 \item Encontre expressões regulares que denotem as linguagem $L_1$ e $L_2$ da primeira questão.

 \item Seja $L=\{{\tt a}^n{\tt b}^i{\tt c}^j\,|\,n > i+j\}$.
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Construa uma GLC que reconheça $L$.
				\item Construa uma GLC que gere $(LL)^*L$.
			  \item Construa um APN que reconheça $L$.
			 \end{list}

 \item Seja a GLC
       \begin{quote}
			  \item $G$: $A \,\rightarrow\, AA \,|\, {\tt 01} \,|\, {\tt 1}$
			 \end{quote}
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
			  \item Mostre que $G$ é ambígua apresentando duas árvores de derivação para a menor palavra para a qual existam
			        duas árvores de derivação.
			  \item Construa duas GLCs equivalentes a $G$, ambas não ambíguas.
			 \end{list}
\end{enumerate}

\vspace*{3mm}
\hrule

\vspace*{.5mm}
\hrule
\vspace*{3mm}
\begin{itemize}
	\item AFN: autômato finito não determinístico;
	\item AFN$\lambda$: autômato finito com transição $\lambda$;
	\item APN: aut\^omato de pilha não determin\'{\i}stico;
	\item GLC: gram\'atica livre do contexto.
\end{itemize}
\end{document}

