\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} \hfill 20/05/2004

\vspace*{2mm}
\noindent {\bf Cada quest\~ao vale 3 pontos.}

\vspace*{1mm}
\begin{enumerate}

 \item Seja $L=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, |w|\geq 2$ e o
       \underline{pen\'ultimo} s\'{\i}mbolo de $w$ n\~ao ocorre antes$\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFN $M$ tal que $L(M)=L$. Use um m\'{\i}nimo de estados
              e transi\c c\~oes. (Dica: use 3 estados iniciais.)
        \item Modifique $M$ de tal forma que $L(M)=L\cup\{\lambda,{\tt a},{\tt b},{\tt c}\}$.
              Fa\c ca isto sem acrescentar nenhum estado e nenhuma transi\c c\~ao,
              se poss\'{\i}vel.
       \end{list}

 \item Seja o AFNE $M$ com o seguinte diagrama de estados simplificado:
       \begin{center}
       \begin{picture}(300,87)
        \put(10,65){\vector(1,0){10}}
        \put(28,65){\oval(16,16)}
        \put(28,65){\makebox(0,0)[c]{1}}
        \put(36,65){\vector(1,0){50}}
        \put(61,67){\makebox(0,0)[b]{{\tt 0}}}

        \put(94,65){\oval(16,16)}
        \put(94,65){\makebox(0,0)[c]{2}}
        \put(102,65){\vector(1,0){50}}
        \put(127,67){\makebox(0,0)[b]{{\tt 1}}}

        \put(98,71){\line(0,1){8}}
        \put(94,79){\oval(8,8)[t]}
        \put(90,79){\vector(0,-1){8}}
        \put(94,85){\makebox(0,0)[b]{{\tt 01}}}

        \put(160,65){\oval(16,16)}
        \put(160,65){\makebox(0,0)[c]{3}}
        \put(160,65){\oval(13,13)}

        \put(94,57){\vector(0,-1){40}}
        \put(96,37){\makebox(0,0)[l]{$\lambda$}}
        \put(94,9){\oval(16,16)}
        \put(94,9){\makebox(0,0)[c]{4}}
        \put(94,9){\oval(13,13)}

        \put(88,13){\line(-1,0){8}}
        \put(80,9){\oval(8,8)[l]}
        \put(80,5){\vector(1,0){8}}
        \put(74,9){\makebox(0,0)[r]{{\tt 00}}}

        \put(102,5){\line(1,0){8}}
        \put(110,9){\oval(8,8)[r]}
        \put(110,13){\vector(-1,0){8}}
        \put(116,9){\makebox(0,0)[l]{{\tt 11}}}

       \end{picture}
       \end{center}

       Utilizando os m\'etodos vistos em aula (ou na apostila):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha um AFN que reconhe\c ca $L(M)$.
        \item Obtenha um AFD equivalente a partir do AFN.
       \end{list}

 \item Determine ER's e GR's para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em um n\'umero par de {\tt ab}'s$\}$.
        \item $\overline{\{{\tt 0},{\tt 1}\}^*\{{\tt 001}\}\{{\tt 0},{\tt 1}\}^*}$.
       \end{list}

 \item Mostre que $\{{\tt a}^k{\tt b}^n\,|\,k>2n\}$ n\~ao \'e linguagem regular.

 \item Sejam $L$ uma linguagem n\~ao regular e $R$ uma linguagem regular.
       Responda se \'e verdadeiro ou falso, e justifique:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $R$ pode ser subconjunto de $L$.
        \item $L$ pode ser subconjunto de $R$.
        \item Todo subconjunto de $R$ \'e linguagem regular.
        \item $L$ \'e infinita.
        \item $L-R$ pode ser linguagem regular.
        \item $L\cup R$ n\~ao \'e linguagem regular.
       \end{list}
\end{enumerate}

\begin{flushright}
$\langle\langle$Se voc\^e tem d\'uvida com rela\c c\~ao a abreviaturas, consulte o verso.$\rangle\rangle$
\end{flushright}

\begin{description}
 \item[AFD:] Aut\^omato finito determin\'{\i}stico.
 \item[AFN:] Aut\^omato finito n\~ao determin\'{\i}stico.
 \item[AFNE:] Aut\^omato finito n\~ao determin\'{\i}stico estendido.
 \item[ER:] Express\~ao regular.
 \item[GR:] Gram\'atica regular.
\end{description}
\end{document}

