\documentclass[12pt]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
\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
    $1^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova} \hfill {\bf Dura\c c\~ao: 1h30m}

\vspace*{2mm}
\noindent {\bf No final do enunciado de cada item est\'a o valor do mesmo
entre par\^enteses.}

\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 come\c cam com \verb+0+ e terminam com \verb+1+. (1)
        \item O conjunto das palavras que t\^em \verb+01+ como subpalavra. (1)
        \item O conjunto das palavras que t\^em \verb+00+ ou \verb+11+ como sufixo. (1)
        \end{list}

 \item Seja a seguinte defini\c c\~ao {\em recursiva\/} da linguagem $L$:
       \begin{itemize}
        \item $\{a,b\}\subset L$;
        \item se $x\in L$, ent\~ao $axa\in L$ e $bxb\in L$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Descreva, em portugu\^es, a linguagem $L$. (1)
        \item Construa uma gram\'atica que gere $L$. (1)
       \end{list}

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

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Toda linguagem finita pode ser reconhecida por AFD. (0,5)
        \item Existe linguagem infinita que n\~ao pode ser reconhecida por AFD. (0,5)
        \item Dado um AFD $M$, existe um AFD $M'$ que reconhece
              $\Sigma^*-L(M)$, onde $\Sigma$ \'e o alfabeto de $L(M)$, e tal
              AFD n\~ao precisa ter mais estados que $M$. (1)
        \item Dados dois AFD's $M_1$ e $M_2$, existe um AFD $M_3$ que reconhece
              $L(M_1)-L(M_2)$ que cont\'em no m\'aximo $n_1\times n_2$ estados,
              onde $n_1$ \'e o n\'umero de estados de $M_1$ e $n_2$ \'e o n\'umero
              de estados de $M_2$. (1)
       \end{list}

\end{enumerate}
\end{document}
