\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\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 W\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 $AB$
        \item $BB$
        \item $B-A$
       \end{list}

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

 \item Construa uma gramática que gere $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$.

 \item Construa um AFD que reconheça $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$.

 \item Responda às perguntinhas, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $\Sigma$ é um alfabeto, o conjunto potência de $\Sigma^*$ \'e:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item o conjunto de todas as palavras no alfabeto $\Sigma$; ou
               \item o conjunto de todas as linguagens de alfabeto $\Sigma$; ou
               \item não é conjunto?
              \end{list}
        \item Se uma variável aparece em uma única regra de uma gramática ela é inútil. Certo ou errado?
       \end{list}

\end{enumerate}

\end{document}
