\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{10mm}
\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}/Turmas Z e F \hfill {08/3/2010}

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

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

 \item Seja $\Sigma=\{{\tt 0},{\tt 1},{\tt \#}\}$. Sejam $k$ e $n$ números naturais tais que $k\leq n$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantas palavras há na linguagem $\Sigma^k$?
        \item Quantas palavras há na linguagem $(\Sigma\cup\{\lambda\})^k$?
        \item Quantas palavras de $n$ símbolos contêm exatamente $k$ ocorrências do símbolo {\tt \#}?
        \item Quantas palavras de $n$ símbolos contêm no máximo $k$ ocorrências do símbolo {\tt \#}?
       \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 com no mínimo um símbolo.
        \item O conjunto das palavras em que toda ocorrência de {\tt 0} é precedida de {\tt 1}.
        \item O conjunto das palavras que cont\^em um número ímpar de {\tt 0}s seguido por um número par de {\tt 1}s.
              Ou seja, cada palavra é da forma ${\tt 0}^i{\tt 1}^p$, em que $i$ é ímpar e $p$ é par.
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^2$.
        \item $\{ww^R\,|\,w\in\{{\tt 0},{\tt 1}\}^*\}$.
       \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},{\tt aa},{\tt bb}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ tem tamanho par e tem no mínimo uma ocorrência de {\tt a}$\}$.
        \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 $X=\Sigma^*\{{\tt 1}\}$
        \item $Y=\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 $X$ e $Y$. O que reconhece $X$ deve ter
              dois estados e o que reconhece $Y$ deve ter três estados.
        \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}
