\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 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} \hfill 19/10/2004

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

 \item Construa um AFN (sem transi\c c\~oes $\lambda$) que reconhe\c ca a
       linguagem $X_1X_2$, onde:
       \begin{itemize}
        \item $X_1=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ o n\'umero de {\tt 1}'s
               em $w$ \'e \'{\i}mpar$\}$ e
        \item $X_2$ \'e a linguagem denotada pela ER $1(0+1)(0+1)$.
       \end{itemize}
       Mostre apenas seu diagrama de estados. Em seguida, obtenha, a partir do
       diagrama de estados, uma gram\'atica regular que gere $X_1X_2$.

 \item Seja o AFN $M=(\{A,B,C\},\{{\tt a},{\tt b}\},\delta, \{A,B\},\{A,B,C\})$,
       onde $\delta$ \'e dada por:
       \begin{center}
        \begin{tabular}{c|cc}
         $\delta$ & {\tt a} & {\tt b} \\ \hline
              $A$ & $\{A\}$ & $\{C\}$ \\
              $B$ & $\{C\}$ & $\{B\}$ \\
              $C$ & $\{\}$ & $\{\}$
       \end{tabular}
       \end{center}
       Determine um AFD equivalente a $M$ utilizando o m\'etodo visto em aula.

 \item Seja um AFN$\lambda$ com o seguinte diagrama de estados:

       \begin{center}
       \begin{picture}(140,120)
        \put(10,90){\vector(1,0){10}}
        \put(30,90){\oval(20,20)}
        \put(30,90){\makebox(0,0){A}}
        \put(35,98){\line(0,1){10}}
        \put(30,108){\oval(10,10)[t]}
        \put(25,108){\vector(0,-1){10}}
        \put(30,116){\makebox(0,0)[b]{\tt a}}
        \put(40,90){\vector(1,0){50}}
        \put(65,93){\makebox(0,0)[b]{$\lambda$}}

        \put(30,80){\vector(0,-1){40}}
        \put(27,60){\makebox(0,0)[r]{$\lambda$}}
        \put(30,30){\oval(20,20)}
        \put(30,30){\makebox(0,0){C}}
        \put(22,35){\line(-1,0){10}}
        \put(12,30){\oval(10,10)[l]}
        \put(12,25){\vector(1,0){10}}
        \put(4,30){\makebox(0,0)[r]{\tt c}}
        \put(40,30){\vector(1,0){50}}
        \put(65,27){\makebox(0,0)[t]{$\lambda$}}

        \put(100,90){\oval(20,20)}
        \put(100,90){\makebox(0,0){B}}
        \put(108,95){\line(1,0){10}}
        \put(118,90){\oval(10,10)[r]}
        \put(118,85){\vector(-1,0){10}}
        \put(126,90){\makebox(0,0)[l]{\tt b}}
        \put(100,80){\vector(0,-1){40}}
        \put(103,60){\makebox(0,0)[l]{$\lambda$}}

        \put(100,30){\oval(20,20)}
        \put(100,30){\oval(17,17)}
        \put(105,22){\line(0,-1){10}}
        \put(100,12){\oval(10,10)[b]}
        \put(95,12){\vector(0,1){10}}
        \put(100,4){\makebox(0,0)[t]{\tt d}}
        \put(100,30){\makebox(0,0){D}}

       \end{picture}
       \end{center}
       Encontre um AFN equivalente utilizando o m\'etodo de remo\c c\~ao de
       transi\c c\~oes $\lambda$ visto em aula. (Pode usar outro m\'etodo geral,
       desde que voce o explicite.)

 \item Obtenha ER's que denotem as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ {\tt 1}'s s\'o podem ocorrer
               nas posi\c c\~oes \'{\i}mpares de $w\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \eta(w) \mbox{ mod } 3 = 1\}$. \\
              ($\eta(w)$ \'e o n\'umero representado por $w$ na base 2.)
       \end{list}

 \item Mostre, usando o lema do bombeamento, que $\{{\tt 0}^nx{\tt 0}^n\,|\,
       x\in\{{\tt 0},{\tt 1}\}^*\mbox{ e }|x|=n\}$ n\~ao \'e uma linguagem regular.

 \end{enumerate}

\end{document}

