\documentclass[12pt, a4paper]{report}
 
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Segunda Prova} \hfill 17/05/01

\begin{enumerate}
 \item (2,5 pontos) Construa um AFN\footnote{Aut\^omato finito n\~ao determin\'{\i}stico.} que reconhe\c ca a
       linguagem: \[\{x\verb+1+y\verb+1+z \,\,|\,\, x,y,z\in\{\verb+0+,\verb+1+\}^* \mbox{ e 
       $|x|$, $|y|$ e $|z|$ s\~ao \'{\i}mpares}\}\mbox{.}\]

 \item (6 pontos) Seja o AFN $M=(\{a,b,c,d\},\{\verb+0+,\verb+1+\},\delta,\{a\},\{d\})$, onde $\delta$ \'e
       dada por:
       \begin{center}
        \begin{tabular}{c|cc}
         $\delta$ & \verb+0+ & \verb+1+ \\ \hline
         $a$ & $\{b\}$ & $\{b\}$ \\
         $b$ & $\{a\}$ & $\{a,c\}$ \\
         $c$ & $\{a,d\}$ & $\{d\}$ \\
         $d$ & $\{\}$ & $\{\}$ \\
        \end{tabular}
       \end{center}
       Utilizando os m\'etodos vistos no curso:
       \begin{enumerate}
        \item[(a)] Obtenha, a partir de $M$, uma gram\'atica regular que gere $L(M)$.
        \item[(b)] Obtenha, a partir de $M$, uma express\~ao regular que denote $L(M)$.
        \item[(c)] Transforme $M$ em um AFD\footnote{Aut\^omato finito determin\'{\i}stico.}
                   equivalente a $M$.
       \end{enumerate}

 \item (2 pontos) Seja o AFN$\lambda$\footnote{Aut\^omato finito n\~ao determin\'{\i}stico com
        transi\c c\~ao $\lambda$.}
       $M=(\{0,1,2\},\{\verb+a+,\verb+b+,\verb+c+\},\delta,\{0\},\{2\})$, onde $\delta$ \'e
       dada por:
       \begin{center}
        \begin{tabular}{c|cccc}
         $\delta$ & \verb+a+ & \verb+b+ & \verb+c+ & $\lambda$\\ \hline
         $0$ & $\{0\}$ & $\{1\}$ & $\{\}$  & $\{\}$ \\
         $1$ & $\{\}$  & $\{\}$  & $\{2\}$ & $\{0\}$ \\
         $2$ & $\{\}$  & $\{\}$  & $\{1\}$ & $\{\}$ \\
        \end{tabular}
       \end{center}
       Construa um AFN equivalente.

 \item (4 pontos) Para cada express\~ao regular abaixo, obtenha uma gram\'atica regular que gere
       a linguagem denotada por ela.
       \begin{enumerate}
        \item[(a)] $(1+011)^*$
        \item[(b)] $(01)^*(10)^*$
       \end{enumerate}

 \item (2,5 pontos) Prove que a linguagem $\{\verb+a+^n\verb+b+^k\,\,|\,\,n\not=k\}$ n\~ao \'e linguagem regular.

\end{enumerate}

\end{document}
 
