\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{1}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} \hfill 05/06/2007

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

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

 \item Seja a linguagem:
       $L=\{w\in\{{\tt a},{\tt b}\}^*\,|\, n_{\tt a}(w)=n_{\tt b}(w)+1\}$.
       \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\, AB \,|\, BC$
	 \item[\ ]$A \,\rightarrow\, {\tt a}A \,|\, D \,|\, \lambda$
	 \item[\ ]$B \,\rightarrow\, {\tt b}B \,|\, C$
	 \item[\ ]$C \,\rightarrow\, {\tt c}C{\tt c} \,|\, \lambda$
	 \item[\ ]$D \,\rightarrow\, {\tt abc}D \,|\, P$
	\end{enumerate}
        Elimine as regras $\lambda$ de $G$, obtendo uma gram\'atica
        equivalente, por meio do m\'etodo visto no curso.

 \item Seja a GLC $H$:
       \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1}
                  \,|\, \lambda$
         \item[\ ]$A \,\rightarrow\, {\tt 0}A{\tt 0} \,|\, {\tt 0}$
       \end{enumerate}
       Obtenha GLCs equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Na forma normal de Chomsky.
        \item Na forma normal de Greibach.
       \end{list}

 \item Seja a gram\'atica $H$ da quest\~ao anterior. Obtenha um APN que
       reconhe\c{c}a $L(H)$, por meio de um dos m\'etodos vistos no curso
       para obten\c{c}\~ao de APNs a partir de GLCs.

 \item Mostre que $\{{\tt a}^k{\tt b}^m{\tt c}^n\,|\, m>k \mbox{ e } m>n\}$
       \'e livre do contexto ou que n\~ao \'e.

\end{enumerate}

\end{document}



