\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\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 $2^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Segunda Prova} \hfill 25/11/2003 \hfill {\bf Dura\c c\~ao: 1h 50min}

\vspace*{2mm}
\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 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 tenha
              ocorrido antes.
        \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.
       \end{list}

 \item Sejam as linguagens $L_1$ e $L_2$ denotadas, respectivamente, por
       $(00)^*1^*$ e $(01^+)^*$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa AFD's que reconhe\c cam $L_1$ e $L_2$.
        \item Utilize transi\c c\~oes $\lambda$ para obter um AFN$\lambda$
              que reconhe\c ca $L_1$$L_2$.
        \item Elimine as transi\c c\~oes $\lambda$ para obter um AFN equivalente.
       \end{list}

 \item Seja o AFD $M=(\{1,2,3,4\},\{{\tt 0},{\tt 1}\},\delta,1,\{1,3\})$, onde
       $\delta$ \'e dada por:
       \begin{center}
       \begin{tabular}{c|cc}
        $\delta$ & {\tt 0} & {\tt 1} \\ \hline
               1 & 1 & 2 \\
               2 & 3 & 2 \\
               3 & 4 & 2 \\
               4 & 4 & 4 \\
      \end{tabular}
      \end{center}
      Obtenha uma express\~ao regular que denote $L(M)$ usando o m\'etodo visto
      em aula (o mesmo da apostila). Em seguida, procure simplificar ao m\'aximo
      a express\~ao, de forma que ela tenha um m\'{\i}nimo de termos.

 \item Encontre express\~oes regulares para as seguintes linguagens:
       \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 tenha
              ocorrido antes.
        \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 Mostre que a linguagem $L=\{xy\in\{\verb+0+,\verb+1+\}^*\,|\,
       |x|=|y| \mbox{ e } x=\overline{y}\}$ n\~ao \'e regular. ($\overline{w}$ \'e
       o resultado de trocar {\tt 0} por {\tt 1} e {\tt 1} por {\tt 0} em $w$. Exemplo:
       $\overline{01100}=10011$.)

\end{enumerate}

\end{document}


