\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 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Segunda Prova} \hfill 16/01/2003 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turmas T 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\{0,1\}^*\,|\, \mbox{ o segundo s\'{\i}mbolo de $w$ \'e
                                    igual ao \'ultimo}\}$
        \item $\{xyx\in\{0,1\}^*\,|\, |x|=2\}$
       \end{list}

 \item Seja o 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]{$a$}}

           \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}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^e o fecho $\lambda$ de cada estado.
        \item Construa o AFN equivalente usando o m\'etodo visto em aula.
        \item Apartir do AFN obtenha o AFD usando o m\'etodo visto em aula.
       \end{list}
 \item Prove que o conjunto $\{x1^n \,\,|\,\, x\in\{0,1\}^* \mbox{ e } |x|<n\}$
       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$ e $L_2$ s\~ao linguagens regulares, ent\~ao $L_1-L_2$
              \'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 e gram\'aticas regulares para as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{0,1\}^* \,\,|\,\,$  as posi\c c\~oes \'{\i}mpares
              de $w$ cont\^em 1's e as pares cont\^em 0's$\}$. Exemplos:
              $\lambda$, 1, 10, 101, 1010, etc.
        \item $L(M)$, onde $M$ \'e o AFN da quest\~ao 1(a).
       \end{list}

\end{enumerate}

\end{document}

