\documentclass[12pt]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{3cm}

\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 Segunda Prova} \hfill 03/07/2003 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turmas B e G}

\vspace*{1mm}

\noindent {\bf Cada quest\~ao vale 3 pontos.}
\vspace*{1mm}
\begin{enumerate}

 \item Construa AFN's para as seguintes linguagens, com o {\em menor n\'umero
       de estados\/} poss\'{\i}vel e {\em um \'unico\/} estado final:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{a,b,c\}^*\,|\, |w|\geq 2$ e o primeiro s\'{\i}mbolo
               de $w$ \'e diferente do \'ultimo$\}$.
        \item $\{xay\,|\, x,y\in\{a,b,c\}^* \mbox{ e $y$ tem n\'umero par
               de $b$'s}\}$ (lembre-se: 0 \'e par).
       \end{list}

 \item Sejam os seguintes aut\^omatos finitos:
       \begin{center}
        \begin{picture}(185,48)
         \put(0,15){\makebox(0,0)[r]{\boldmath $M_1$:}}
         \put(10,15){\vector(1,0){10}}
         \put(30,15){\oval(20,20)}
         \put(30,15){\makebox(0,0){a}}
         \put(35,25){\line(0,1){10}}
         \put(30,35){\oval(10,10)[t]}
         \put(25,35){\vector(0,-1){10}}
         \put(30,43){\makebox(0,0)[b]{0,1}}
         \put(40,15){\vector(1,0){60}}
         \put(70,23){\makebox(0,0)[b]{0}}


         \put(110,15){\oval(20,20)}
         \put(110,15){\oval(17,17)}
         \put(110,15){\makebox(0,0){b}}
         \put(115,25){\line(0,1){10}}
         \put(110,35){\oval(10,10)[t]}
         \put(105,35){\vector(0,-1){10}}
         \put(110,43){\makebox(0,0)[b]{0}}

         \put(120,20){\vector(1,0){59}}
         \put(150,23){\makebox(0,0)[b]{1}}
         \put(180,10){\vector(-1,0){59}}
         \put(150,7){\makebox(0,0)[t]{1}}

         \put(190,15){\oval(20,20)}
         \put(190,15){\makebox(0,0){c}}
         \put(195,25){\line(0,1){10}}
         \put(190,35){\oval(10,10)[t]}
         \put(185,35){\vector(0,-1){10}}
         \put(190,43){\makebox(0,0)[b]{0}}
        \end{picture}
       \end{center}
       \begin{center}
        \begin{picture}(185,48)
         \put(0,15){\makebox(0,0)[r]{\boldmath $M_2$:}}
         \put(10,15){\vector(1,0){10}}
         \put(30,15){\oval(20,20)}
         \put(30,15){\makebox(0,0){p}}
         \put(35,25){\line(0,1){10}}
         \put(30,35){\oval(10,10)[t]}
         \put(25,35){\vector(0,-1){10}}
         \put(30,43){\makebox(0,0)[b]{0}}

         \put(40,20){\vector(1,0){59}}
         \put(70,23){\makebox(0,0)[b]{1}}
         \put(100,10){\vector(-1,0){59}}
         \put(70,7){\makebox(0,0)[t]{1}}

         \put(110,15){\oval(20,20)}
         \put(110,15){\oval(17,17)}
         \put(110,15){\makebox(0,0){q}}
         \put(115,25){\line(0,1){10}}
         \put(110,35){\oval(10,10)[t]}
         \put(105,35){\vector(0,-1){10}}
         \put(110,43){\makebox(0,0)[b]{0}}
        \end{picture}
       \end{center}

        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha um AFD equivalente ao AFN $M_1$ usando o m\'etodo
              visto em aula (que \'e o da apostila).
        \item Construa um AFN com transi\c c\~ao $\lambda$ que reconhe\c ca
              $L(M_1)L(M_2)$, a partir de $M_1$ e $M_2$, pela coloca\c c\~ao
              de uma transi\c c\~ao sob $\lambda$ do estado $b$ (final de $M_1$)
              para o estado $q$ (inicial de $M_2$). Em seguida, obtenha um AFN
              equivalente pela elimina\c c\~ao da transi\c c\~ao sob $\lambda$.
       \end{list}

 \item Mostre que $\{xy\in\{0,1\}^* \,|\, n_0(x)<n_1(y)\}$ n\~ao \'e regular (ou que \'e).

 \item Determine AFN's que reconhe\c cam as linguagens que as seguintes express\~oes
       regulares denotam:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(bab)^*(aa+b)^*$
        \item $(aa+b)^*(bab)^*$
       \end{list}

 \item Encontre express\~oes regulares e gram\'aticas regulares para as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras em $\{0,1\}^*$ que n\~ao cont\^em $001$.
        \item $L(M_1)$, onde $M_1$ \'e o AFN da quest\~ao 2.
       \end{list}

\end{enumerate}

\end{document}

