\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{10mm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turmas B e E \hfill {10/9/2009}

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

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

 \item Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$, $X=\Sigma^+\{{\tt 1}\}$ e $Y=\Sigma^*\{{\tt 0}\}\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 01} ou {\tt 11}.
       \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y$.
        \item $X\cap Y$.
        \item $X-Y$.
       \end{list}

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas conjuntos finitos, opera\c c\~oes sobre conjuntos,
       concatena\c c\~ao e fecho de Kleene. Procure obter uma descri\c c\~ao bem
       concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que come\c{c}am com {\tt 0} e cont\^em pelo menos um {\tt 1}.
        \item O conjunto das palavras que cont\^em {\tt 00}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
       \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 $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 01},{\tt 10}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0}\}^*\{{\tt 0},{\tt 1}\}\{{\tt 1}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, 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 $A=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o n\'umero de {\tt 0}s em $w$ \'e par}\}$;
        \item $B=\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 $A$ e $B$.
        \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 $A\cup B$ e para
              o AFD que reconhece $A\cap B$.
       \end{list}
\end{enumerate}

\end{document}
