\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova} \hfill 23/10/2003

\vspace*{10mm}
\noindent {\bf As quest\~oes 1, 2 e 3 valem 3 pontos cada uma; a quest\~ao
4 vale 4,5 pontos; e a quest\~ao 5 vale 1,5 pontos.}

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

 \item Responda sem provar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Qual \'e o n\'umero de subpalavras de uma palavra de tamanho $n$?
        \item Em que situa\c c\~oes $L^*$ \'e finita?
        \item Em que situa\c c\~oes $L^*=L^+$?
       \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, concatena\c c\~ao,
       fecho de Kleene, etc.) as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com prefixo {\tt 01}.
        \item O conjunto das palavras com 0 (zero) a 5 s\'{\i}mbolos.
        \item O conjunto das palavras de tamanho \'{\i}mpar com pelo menos um {\tt 0}.
       \end{list}

 \item Sobre gram\'aticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada pela gram\'atica $G$ definida a seguir?

              $G=(\{X\},\{{\tt 0},{\tt 1}\},R,X)$.
               \begin{enumerate}
                \item[$R$:] $X\,\rightarrow\,{\tt 0} X {\tt 0}\,|\, {\tt 1}X{\tt 1}\,|\,
                                   \lambda$
               \end{enumerate}
        \item Obtenha uma gram\'atica que gere $\{{\tt 0}^m{\tt 1}^n\,|\,m>n\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\lambda,{\tt a},{\tt aa}\}\{{\tt bb}\}\{{\tt a},{\tt b}\}^*$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ que n\~ao t\^em
              {\tt 000} como sufixo.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho \'{\i}mpar
              com duas (e apenas duas) ocorr\^encias de {\tt 1}.
       \end{list}

 \item Explique: n\~ao existe AFD que reconhe\c ca $\{x{\tt 1}y\,|\,x,y\in\{{\tt 0},{\tt 1}\}^*
       \mbox{ e } |x|=|y|\}$.

\end{enumerate}

\end{document}
