\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} \hfill 28/04/2005

\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:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, |w|\geq 2$ e o \'ultimo
               s\'{\i}mbolo de $w$ tenha ocorrido antes$\}$.
        \item $\{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}$\}$.
       \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 p (inicial de $M_2$). Em seguida, obtenha um AFN
              equivalente pela elimina\c c\~ao da transi\c c\~ao sob $\lambda$
              usando o m\'etodo visto em aula (que \'e o da apostila).
       \end{list}

 \item Mostre que $\{{\tt 0}^{n^2}y\,|\, y\in\{{\tt 1}\}^*\}$ n\~ao \'e regular (ou que \'e).

 \item Encontre express\~oes regulares que denotem as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(M_1)$, onde $M_1$ \'e o AFN da quest\~ao 2.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \eta(w) \mbox{ mod } 3 = 2\}$, onde
              $\eta(w)$ \'e o n\'umero representado por $w$ na base 2.
       \end{list}

 \item Diga se est\'a certo ou errado, justificando sua resposta:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'e uma linguagem finita, existe uma express\~ao regular
              que denota $L$.
        \item O lema do bombeamento pode ser utilizado para provar que uma linguagem
              \'e regular.
        \item As linguagens regulares s\~ao fechados sob interse\c c\~ao.
        \item Se $L$ \'e uma linguagem regular e $L\subset L'$, $L'$ pode ser
              ou n\~ao ser regular.
       \end{list}
       A resposta para cada item ser\'a considerada correta se, e somente se,
       a justificativa estiver correta.
\end{enumerate}

\end{document}

