\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{2cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turma W \hfill {31/3/2009}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos (1 ponto extra!).

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

 \item Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$, $X=\Sigma^*\{{\tt 0}\}$ e $Y=\Sigma^*\{{\tt 1}\}\Sigma^*$.
       Descreva de forma clara e precisa, em portugu\^es, as linguagens a seguir. N\~ao \'e necess\'ario
       dizer que as palavras s\~ao de {\tt 0}s e {\tt 1}s. Por exemplo:
       \begin{quote}
        $X$: conjunto das palavras que terminam com {\tt 0}.
       \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y$.
        \item $XY$.
        \item $YX$.
        \item $X-Y$.
       \end{list}

 \item Sejam $A=\{{\tt 0}\}^*\{{\tt 1}\}^*$ e $P=\{x\in \{{\tt 0},{\tt 1}\}^+\,|\,x=x^R\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A$.
        \item $P$.
        \item $AP$.
        \item $A-P$.
       \end{list}

 \item Construa AFDs que reconhe\c cam as linguagens a seguir. Apresente apenas os
       diagramas de estados (que podem ser simplificados).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a},{\tt b}\}^*-\{{\tt a},{\tt b}\}$.
        \item O conjunto das palavras de {\tt a}s e {\tt b}s que come\c{c}am com {\tt a}
              e t\^em n\'umero par de {\tt b}s.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ n\~ao cont\'em {\tt aba}$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em {\tt aa}, mas n\~ao cont\'em {\tt bb}$\}$.
       \end{list}

 \item Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $Z=\Sigma^*\{{\tt 0}\}\Sigma^*$
        \item $U=\Sigma^*\{{\tt 11}\}\Sigma^*$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $Z$ e $U$.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $Z\cup U$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $Z-U$.
       \end{list}
\end{enumerate}

\end{document}
