\documentclass[12pt, a4paper]{report}
\newcounter{conta}
\pagestyle{empty}
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Segunda Prova} \hfill 20/02/02

{\bf $\Rightarrow$ Cada quest\~ao vale 3 pontos.}

\begin{enumerate}
 \item Construa um AFN\footnote{Aut\^omato finito n\~ao determin\'{\i}stico.} que
       reconhe\c ca a linguagem: \[\{x\verb+1+y \,\,|\,\, x,y\in\{\verb+0+,\verb+1+\}^*
       \mbox{ e } \eta(y)\,\mbox{\em mod\/}\,3 = 1\}\mbox{.}\]
       onde $\eta(y)$ \'e o n\'umero representado por $y$ na base 2 e {\em mod\/} \'e o
       operador ``resto da divis\~ao''.


 \item Seja o AFN$\lambda$\footnote{Aut\^omato finito n\~ao determin\'{\i}stico com
        transi\c c\~ao $\lambda$.}
       $M=(\{1,2,3,4,5\},\{\verb+0+,\verb+1+\},\delta,\{1\},\{5\})$, onde $\delta$ \'e
       dada por:
       \begin{center}
        \begin{tabular}{c|ccc}
         $\delta$ & \verb+0+ & \verb+1+ & $\lambda$\\ \hline
         $1$ & $\{2,3\}$ & $\{\}$    & $\{3\}$ \\
         $2$ & $\{1\}$   & $\{1\}$   & $\{\}$  \\
         $3$ & $\{\}$    & $\{4,5\}$ & $\{\}$  \\
         $4$ & $\{\}$    & $\{3\}$   & $\{\}$  \\
         $5$ & $\{\}$    & $\{\}$    & $\{\}$ 
        \end{tabular}
       \end{center}
       \begin{enumerate}
        \item[(a)] Construa um AFN $M'$ equivalente a $M$.
        \item[(b)] Obtenha um AFD\footnote{Aut\^omato finito determin\'{\i}stico.} equivalente
                   a $M'$.
       \end{enumerate}

 \item Encontre express\~oes e gram\'aticas regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w|>1 \mbox{ e $w$ cont\'em } \verb+1+\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, \verb+0+'s
               \mbox{ n\~ao ocorrem em posi\c c\~oes \'{\i}mpares}\}$
       \end{list}

 \item Mostre que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A interse\c c\~ao de duas linguagens n\~ao regulares pode ser uma linguagem regular.
        \item Se $L_1$ e $L_2$ s\~ao linguagens regulares, $L_1-L_2$ \'e regular.
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k\,\,|\,\, m=n+k\}$ \'e linguagem regular.
       \end{list}


 \item Obtenha um AFD para o conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que n\~ao
       cont\^em \verb+00+ e que t\^em tamanho par. A partir dele, construa uma express\~ao
       regular para a mesma linguagem. (Considere 0 par.)

\end{enumerate}
\end{document}