\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\vspace*{2cm}
\noindent {\it Fundamentos da Teoria da Computação}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turma W \hfill {08/3/2010}

\vspace*{1mm}
\noindent \textbf{Duração:} 1 hora e 35 minutos. \\
\noindent \textbf{Valores:} 1 ponto cada item.

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

 \item Seja $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantas palavras sobre $\Sigma$ existem com exatamente $n$ símbolos?
        \item Quantas palavras sobre $\Sigma$ existem com no máximo $n$ símbolos?
        \item Quantas subpalavras contém uma palavra de $n$ símbolos, \underline{no mínimo}?
        \item Quantas subpalavras contém uma palavra de $n$ símbolos, \underline{no máximo}?
       \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 iniciadas com {\tt 0} e de tamanho ímpar.
        \item O conjunto das palavras em que cada ocorrência de {\tt 0} é seguida de pelo menos dois
              {\tt 1}s consecutivos.
        \item O conjunto das palavras que cont\^em um número par de {\tt 0}s (e qualquer número de {\tt 1}s).
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 010}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w=w^R\}$.
       \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 aba}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em pelo menos um {\tt a} e cont\'em número par de {\tt b}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ n\~ao cont\'em {\tt ab} nem {\tt bc}$\}$.
       \end{list}

 \item Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $X=\{{\tt 1}\}\Sigma^*$
        \item $Y=\Sigma^*\{{\tt 11}\}$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $X$ e $Y$. Eles devem três estados cada um.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs.
        \item Diga quais s\~ao os estados finais para os AFDs que reconhecem $X\cap Y$ e $X\cup Y$.
       \end{list}
\end{enumerate}

\end{document}
