\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{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova/Solu\c c\~ao do professor} \hfill 28/04/2005

\begin{enumerate}
 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFN para $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, |w|\geq 2$ e
              o \'ultimo s\'{\i}mbolo de $w$ tenha ocorrido antes$\}$:
              \begin{center}
              \begin{picture}(300,105)
               \put(10,70){\vector(1,-1){12}}
               \put(30,50){\oval(20,20)}
               \put(22,55){\line(-1,0){5}}
               \put(17,50){\oval(10,10)[l]}
               \put(17,45){\vector(1,0){5}}
               \put(10,50){\makebox(0,0)[r]{{\tt a},{\tt b},{\tt c}}}

               \put(30,60){\line(0,1){30}}
               \put(35,90){\oval(10,10)[tl]}
               \put(35,95){\vector(1,0){50}}
               \put(28,75){\makebox(0,0)[r]{{\tt a}}}
               \put(95,95){\oval(20,20)}
               \put(100,103){\line(0,1){5}}
               \put(95,108){\oval(10,10)[t]}
               \put(90,108){\vector(0,-1){5}}
               \put(95,115){\makebox(0,0)[b]{{\tt a},{\tt b},{\tt c}}}

               \put(105,95){\line(1,0){50}}
               \put(155,90){\oval(10,10)[tr]}
               \put(160,90){\vector(0,-1){30}}
               \put(162,75){\makebox(0,0)[l]{{\tt a}}}

               \put(40,50){\vector(1,0){45}}
               \put(60,52){\makebox(0,0)[b]{{\tt b}}}
               \put(95,50){\oval(20,20)}
               \put(100,58){\line(0,1){5}}
               \put(95,63){\oval(10,10)[t]}
               \put(90,63){\vector(0,-1){5}}
               \put(95,70){\makebox(0,0)[b]{{\tt a},{\tt b},{\tt c}}}

               \put(105,50){\vector(1,0){45}}
               \put(130,52){\makebox(0,0)[b]{{\tt b}}}
               \put(160,50){\oval(20,20)}
               \put(160,50){\oval(17,17)}

               \put(30,40){\line(0,-1){30}}
               \put(35,10){\oval(10,10)[bl]}
               \put(35,5){\vector(1,0){50}}
               \put(28,25){\makebox(0,0)[r]{{\tt c}}}
               \put(95,5){\oval(20,20)}
               \put(100,13){\line(0,1){5}}
               \put(95,18){\oval(10,10)[t]}
               \put(90,18){\vector(0,-1){5}}
               \put(95,25){\makebox(0,0)[b]{{\tt a},{\tt b},{\tt c}}}

               \put(105,5){\line(1,0){50}}
               \put(155,10){\oval(10,10)[br]}
               \put(160,10){\vector(0,1){30}}
               \put(162,25){\makebox(0,0)[l]{{\tt c}}}

              \end{picture}
              \end{center}
        \item AFN para  $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, |w|\geq 1$ e $w$ tenha
              um \'unico {\tt a} ou um \'unico {\tt b} ou um \'unico {\tt c}$\}$:
              \begin{center}
              \begin{picture}(400,55)
               \put(10,20){\vector(1,0){10}}
               \put(30,20){\oval(20,20)}
               \put(35,28){\line(0,1){5}}
               \put(30,33){\oval(10,10)[t]}
               \put(25,33){\vector(0,-1){5}}
               \put(30,40){\makebox(0,0)[b]{{\tt b},{\tt c}}}

               \put(40,20){\vector(1,0){30}}
               \put(55,22){\makebox(0,0)[b]{{\tt a}}}
               \put(80,20){\oval(20,20)}
               \put(80,20){\oval(17,17)}
               \put(85,28){\line(0,1){5}}
               \put(80,33){\oval(10,10)[t]}
               \put(75,33){\vector(0,-1){5}}
               \put(80,40){\makebox(0,0)[b]{{\tt b},{\tt c}}}

               \put(130,20){\vector(1,0){10}}
               \put(150,20){\oval(20,20)}
               \put(155,28){\line(0,1){5}}
               \put(150,33){\oval(10,10)[t]}
               \put(145,33){\vector(0,-1){5}}
               \put(150,40){\makebox(0,0)[b]{{\tt a},{\tt c}}}

               \put(160,20){\vector(1,0){30}}
               \put(175,22){\makebox(0,0)[b]{{\tt b}}}
               \put(200,20){\oval(20,20)}
               \put(200,20){\oval(17,17)}
               \put(205,28){\line(0,1){5}}
               \put(200,33){\oval(10,10)[t]}
               \put(195,33){\vector(0,-1){5}}
               \put(200,40){\makebox(0,0)[b]{{\tt a},{\tt c}}}

               \put(250,20){\vector(1,0){10}}
               \put(270,20){\oval(20,20)}
               \put(275,28){\line(0,1){5}}
               \put(270,33){\oval(10,10)[t]}
               \put(265,33){\vector(0,-1){5}}
               \put(270,40){\makebox(0,0)[b]{{\tt a},{\tt b}}}

               \put(280,20){\vector(1,0){30}}
               \put(295,22){\makebox(0,0)[b]{{\tt c}}}
               \put(320,20){\oval(20,20)}
               \put(320,20){\oval(17,17)}
               \put(325,28){\line(0,1){5}}
               \put(320,33){\oval(10,10)[t]}
               \put(315,33){\vector(0,-1){5}}
               \put(320,40){\makebox(0,0)[b]{{\tt a},{\tt b}}}


              \end{picture}
              \end{center}
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O AFD equivalente ao AFN:
       \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}
       usando o m\'etodo visto em aula (que \'e o da apostila) tem o seguinte
       diagrama de estados:
       \begin{center}
        \begin{picture}(400,48)
         \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]{1}}
         \put(40,15){\vector(1,0){60}}
         \put(70,23){\makebox(0,0)[b]{0}}


         \put(120,15){\oval(40,20)}
         \put(120,15){\oval(37,17)}
         \put(120,15){\makebox(0,0){$\{a,b\}$}}
         \put(125,25){\line(0,1){10}}
         \put(120,35){\oval(10,10)[t]}
         \put(115,35){\vector(0,-1){10}}
         \put(120,43){\makebox(0,0)[b]{0}}

         \put(140,20){\vector(1,0){59}}
         \put(170,23){\makebox(0,0)[b]{1}}
         \put(200,10){\vector(-1,0){59}}
         \put(170,7){\makebox(0,0)[t]{1}}

         \put(220,15){\oval(40,20)}
         \put(220,15){\makebox(0,0){$\{a,c\}$}}
         \put(240,15){\vector(1,0){60}}
         \put(270,18){\makebox(0,0)[b]{0}}

         \put(325,15){\oval(50,20)}
         \put(325,15){\oval(47,17)}
         \put(325,15){\makebox(0,0){$\{a,b,c\}$}}
         \put(330,25){\line(0,1){10}}
         \put(325,35){\oval(10,10)[t]}
         \put(320,35){\vector(0,-1){10}}
         \put(325,43){\makebox(0,0)[b]{0,1}}

        \end{picture}
        \end{center}
         \item O AFN que reconhece $L(M_1)L(M_2)$, obtido pela elimina\c c\~ao
               da transi\c c\~ao sob $\lambda$ usando o m\'etodo visto em aula
               (que \'e o da apostila) \'e
               \[(\{{\tt a},{\tt b},{\tt c},{\tt p},{\tt q}\},\{{\tt 0},{\tt 1}\},
                 \delta,\{{\tt a}\},\{{\tt q}\})\]
               onde $\delta$ \'e dada por:
               \begin{enumerate} \item[\ ]
               \begin{tabular}{c|cc}
                $\delta$ & {\tt 0} & {\tt 1} \\ \hline
                {\tt a} & $\{{\tt a},{\tt b},{\tt p}\}$ & $\{{\tt a}\}$ \\
                {\tt b} & $\{{\tt b},{\tt p}\}$ & $\{{\tt c}\}$ \\
                {\tt c} & $\{{\tt c}\}$ & $\{{\tt b},{\tt p}\}$ \\
                {\tt p} & $\{{\tt p}\}$ & $\{{\tt q}\}$ \\
                {\tt q} & $\{{\tt q}\}$ & $\{{\tt p}\}$ \\
               \end{tabular}
               \end{enumerate}
       \end{list}
 
 \item Seja $L=\{{\tt 0}^{n^2}y\,|\, y\in\{{\tt 1}\}^*\}$.

       Suponha que $L$ \'e regular. Seja $k$ a constante do lema do bombeamento, e
       seja $z={\tt 0}^{k^2}$. Como $z\in L$ e $|z|\geq k$, o lema diz que existem $u$, $v$ e
       $w$ tais que $z=uvw$, $|v|>0$, $|uv|\leq k$ e $uv^iw\in L$ para
       todo $i\geq 0$. Sejam, ent\~ao, $u$, $v$ e $w$ tais que $z=uvw$,
       $|v|>0$ e $|uv|\leq k$. Tem-se: $uv^2w={\tt 0}^{k^2+|v|}$. Como
       $|v|>0$, $k^2+|v|>k^2$, e como $|uv|\leq k$, $|v|\leq k$ e, portanto,
       $k^2+|v|\leq k^2+k<k^2+2k+1=(k+1)^2$. Como $k^2<k^2+|v|<(k+1)^2$,
       $k^2+|v|$ n\~ao \'e um quadrado perfeito e, portanto, $uv^2w\not\in L$,
       contrariando o lema. Logo, $L$ n\~ao \'e regular.

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item ER para $L(M_1)$: $(0+1)^*0(0+10^*1)^*$.
        \item ER para $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \eta(w) \mbox{ mod } 3 = 2\}$:
              $(0+11)^*10(1+00+01(0+11)^*10)^*$.
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \underline{Certo}: se $L$ \'e uma linguagem finita, existe uma express\~ao regular
              que denota $L$. Toda linguagem finita \'e regular, e para toda linguagem regular
              existe uma express\~ao regular.
        \item \underline{Errado}: o lema do bombeamento pode ser utilizado para provar que uma linguagem
              \'e regular. Se uma linguagem \'e regular, ela satisfaz a afirmativa
              explicitada no lema. Mas a rec\'{\i}proca n\~ao vale, ou seja, se tal afirmativa
              for satisfeita por uma linguagem, ela pode ser regular ou n\~ao.
        \item \underline{Certo}: as linguagens regulares s\~ao fechados sob interse\c c\~ao.
              Dados dois AFDs quaisquer, $M_1$ e $M_2$, \'e poss\'{\i}vel obter um AFD para
              $L(M_1)\cap L(M_2)$ (a partir do ``produto'').
        \item \underline{Certo}: se $L$ \'e uma linguagem regular e $L\subset L'$, $L'$ pode ser
              ou n\~ao ser regular. Por exemplo, $\emptyset$ \'e subconjunto de qualquer linguagem,
              seja ela regular ou n\~ao.
       \end{list}
\end{enumerate}

\end{document}

