\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 08/08/2002 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turma A}

\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 dois s\'{\i}mbolos, em que o \'ultimo s\'{\i}mbolo \'e diferente
              do primeiro.
        \item $\{x\verb+0+y\verb+0+ \,\,|\,\,x,y\in\{\verb+0+,\verb+1+\}^*, x
               \mbox{ n\~ao cont\'em } \verb+00+ \mbox{ e } n_{\verb+0+}(y)
               \mbox{ \'e \'{\i}mpar}\}$.
       \end{list}

 \item Obtenha um AFD equivalente ao AFN$\lambda$:
         \begin{center}
          \begin{picture}(250,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$}}

           \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]{$b,c$}}

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

           \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(130,70){\vector(1,0){60}}
           \put(160,73){\makebox(0,0)[b]{$\lambda$}}
           \put(200,70){\oval(20,20){\makebox(0,0){4}}}
           \put(208,65){\line(1,0){10}}
           \put(218,70){\oval(10,10)[r]}
           \put(218,75){\vector(-1,0){10}}
           \put(226,70){\makebox(0,0)[l]{$c$}}
           \put(200,70){\oval(17,17)}
          \end{picture}
         \end{center}

 \item Prove que o conjunto $\{xx^R \,\,|\,\, 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_1-L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma
              linguagem regular.
        \item se $L_1$ n\~ao \'e linguagem regular e $L_2$ \'e regular, $L_1-L_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+0+ \,\,|\,\, w\in\{\verb+0+,\verb+1+\}^* \mbox{ e }
               n_{\verb+0+}(w) \mbox{ \'e impar}\}$.
        \item $\{x\verb+11+y \,\,|\,\, x,y\in\{\verb+0+,\verb+1+\}^*$, $x$ n\~ao
               cont\'em \verb+11+ e $y$ n\~ao cont\'em \verb+00+$\}$.
       \end{list}

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

\end{enumerate}

\end{document}

