\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Departamento de Ci\^encia da Computa\c c\~ao \hfill ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill
    $2^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova} \hfill {\bf Dura\c c\~ao: 1h40m}

\vspace*{2mm}
\noindent {\bf Cada item das quest\~oes 1 a 3 vale 1,5 pontos. Cada item da
\'ultima quest\~ao vale 1 ponto.}

\vspace*{1mm}
\begin{enumerate}
 \item Expresse as linguagens a seguir utilizando opera\c c\~oes sobre conjuntos
       finitos de palavras de $\{\verb+0+,\verb+1+\}^*$. Considere o alfabeto
       como sendo $\{\verb+0+,\verb+1+\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que t\^em n\'umero par de s\'{\i}mbolos.
        \item O conjunto das palavras que t\^em \verb+00+ como sufixo.
        \item O conjunto das palavras em que todo \verb+0+ \'e seguido de dois
              \verb+1+'s consecutivos.
              Exemplos: $\lambda$, \verb+1+, \verb+1011111+, \verb+11011101111+.
        \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Fa\c ca uma defini\c c\~ao recursiva da linguagem constitu\'{\i}da
              das palavras em $\{\verb+0+,\verb+1+\}^*$ que n\~ao cont\^em \verb+00+
              nem \verb+11+. Exemplos: $\lambda$, \verb+0+, \verb+1+, \verb+01+,
              \verb+10+,\verb+010+,\verb+101+.
        \item Construa uma gram\'atica que gere tal linguagem
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\lambda,\verb+0+\}^2$
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ de tamanho
                \'{\i}mpar que contenham pelo menos um \verb+1+.
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w| \mbox{ mod } 3=0 
                \mbox{ e o n\'umero de } \verb+0+\mbox{'s em } w \mbox{ \'e par}\}$
         \end{list}

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe linguagem infinita que pode ser reconhecida por um AFD
              de apenas 1 estado.
        \item Existe linguagem finita que s\'o pode ser reconhecida por um AFD de,
              no m\'{\i}nimo, 1 trilh\~ao de estados.
        \item Existe AFD que reconhece $\{\verb+0+^n\verb+1+^n\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$.
        \item Existe AFD que reconhece $\{\verb+0+^n\verb+0+^n\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$.
       \end{list}

\end{enumerate}
\end{document}
