\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}/Turmas F e N \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=\{{\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 $XY$.
        \item $YX$.
        \item $X\cap Y$.
        \item $X-Y$.
       \end{list}

 \item Sejam $A=\{{\tt 0}\}^*\{{\tt 0},{\tt 1}\}\{{\tt 1}\}^*$ e $B=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A$.
        \item $B$.
        \item $AB$.
        \item $B^*$.
       \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}\}^*-\{\lambda,{\tt a}\}$.
        \item $\{{\tt a},{\tt b}\}^*\{{\tt bb}\}\{{\tt a},{\tt b}\}^*$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ tem n\'umero par de {\tt a}s e \'{\i}mpar de {c}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ n\~ao cont\'em tr\^es s\'{\i}mbolos consecutivos id\^enticos$\}$.
       \end{list}

 \item Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $I_0=\{w\in\Sigma^* \,|\, \mbox{ o n\'umero de {\tt 0}s em $w$ \'e \'{\i}mpar}\}$
        \item $I_1=\{w\in\Sigma^* \,|\, \mbox{ o n\'umero de {\tt 1}s em $w$ \'e \'{\i}mpar}\}$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $I_0$ e $I_1$.
        \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 $I_0\cup I_1$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $I_0-I_1$.
       \end{list}
\end{enumerate}

\end{document}
