\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\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{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova} -- Turma D\hfill {11/10/2012}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:}  as 4 primeiras valem 5 pontos cada uma, e a última 4 pontos.

\vspace*{2mm}
\begin{enumerate}
 \item Sejam $\Sigma=\{{\tt a},{\tt b}\}$,  $A=\{{\tt a}\}\Sigma^+$ e $B=\Sigma^*\{{\tt b}\}$.
       Descreva uma condição necessária e suficiente para que uma palavra de $\Sigma^*$ pertença a:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $AA$
        \item $A\cap B$
        \item $A-B$
       \end{list}

 \item Seja a gramática $G=(\{P,A\},\{{\tt a},{\tt b}\},R,P)$.
       \begin{enumerate}
        \item[$R$:] $P\,\rightarrow\,{\tt a}P{\tt a}\,|\, A$
        \item[\ ]   $A\,\rightarrow\,{\tt b}A{\tt b} \,|\, \lambda$
       \end{enumerate}
       Descreva $L(G)$.

 \item Construa uma gramática que gere $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt ab}
       nem {\tt bc}}\}$.

 \item Construa um AFD que reconheça $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt ab}
       nem {\tt bc}}\}$.

 \item Responda às perguntinhas, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\lambda$ pode ser símbolo de um alfabeto?
        \item Todo AFD tem estado de erro (a partir do qual não se alcança estado final). Certo ou errado?
       \end{list}

\end{enumerate}

\end{document}
