\documentclass[12pt]{report}

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

\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 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Segunda Prova} \hfill 07/08/2002 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turma M}

\vspace*{2mm}
\noindent {\bf Os itens 4(a), 4(b) e 5(a) valem 1 ponto cada um; os restantes
 valem 2 pontos cada um.}

\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 O conjunto das palavras de $\{\verb+a+,\verb+b+,\verb+c+\}^*$, de pelo menos
              um s\'{\i}mbolo, em que o \'ultimo s\'{\i}mbolo \underline{n\~ao} tenha
              ocorrido antes.
        \item $\{xy\in\{\verb+0+,\verb+1+\}^* \,\,|\,\, |x|\,\,\mbox{\em mod}\,\,
              3=1 \mbox{ e } \eta(y) \,\,\mbox{\em mod}\,\, 3=1\}$, onde $\eta(y)$
              \'e o n\'umero representado por $y$ na base 2.
       \end{list}

 \item Obtenha um AFD equivalente ao AFN$\lambda$:
         \begin{center}
          \begin{picture}(150,150)
           \put(20,110){\vector(1,0){10}}
           \put(40,110){\oval(20,20){\makebox(0,0){1}}}
           \put(45,118){\line(0,1){10}}
           \put(40,128){\oval(10,10)[t]}
           \put(35,128){\vector(0,-1){10}}
           \put(40,136){\makebox(0,0)[b]{$a,b$}}

           \put(40,100){\vector(0,-1){60}}
           \put(37,70){\makebox(0,0)[r]{$\lambda$}}

           \put(40,30){\oval(20,20){\makebox(0,0){2}}}
           \put(35,22){\line(0,-1){10}}
           \put(40,12){\oval(10,10)[b]}
           \put(45,12){\vector(0,1){10}}
           \put(40,4){\makebox(0,0)[t]{$a,c$}}

           \put(48,104){\vector(2,-1){62}}
           \put(80,91){\makebox(0,0)[b]{$b$}}

           \put(48,38){\vector(2,1){62}}
           \put(80,49){\makebox(0,0)[t]{$c$}}

           \put(120,70){\oval(20,20){\makebox(0,0){3}}}
           \put(120,70){\oval(17,17)}
          \end{picture}
         \end{center}

 \item Prove que o conjunto $\{xx \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$ n\~ao \'e
       regular.

 \item Sejam $L_1$ e $L_2$ duas linguagens. Mostre que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item se $L_1L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
              re\-gu\-lar.
        \item se $L_1$ e $L_2$ n\~ao s\~ao linguagens regulares, $L_1L_2$ n\~ao \'e
              uma linguagem regular.
       \end{list}

 \item Encontre express\~oes regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+w\verb+1+ \,\,|\,\, w\in\{\verb+0+,\verb+1+\}^* \mbox{ e }
               |w| \mbox{ \'e par}\}$.
        \item $\{w\in\{\verb+0+,\verb+1+\}^* \,\,|\,\, w$ cont\'em \verb+11+ mas n\~ao
               \verb+00+$\}$.
       \end{list}

 \item Encontre uma gram\'atica regular para a linguagem da quest\~ao 1(a).

\end{enumerate}

\end{document}

