\documentclass[12pt, a4paper]{report}

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

\newcounter{conta}

\begin{document}
\pagestyle{empty}

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

\vspace*{3mm}
\noindent Cada quest\~ao vale 3 pontos.
\begin{enumerate}
 \item Fa\c ca um AFN que reconhe\c ca a linguagem: \[\{w\in\{{\tt 0},{\tt 1}\}^*
       \,|\, |w|> 0 \mbox{ e o \'ultimo s\'{\i}mbolo de $w$ ocorre um n\'umero
       \'{\i}mpar de vezes}\}\mbox{.}\]
       Se conseguir um AFN de, no m\'aximo, 5 estados, ganha 1 ponto extra.

 \item Prove que $\{{\tt 0}^n{\tt 1}{\tt 0}^n\,|\, n\geq 0\}$ \'e uma
       linguagem regular ou n\~ao regular.

 \item Fa\c ca um AFD que reconhe\c ca a linguagem: \[L=\{w\in\{{\tt a},{\tt b},
       {\tt c}\}^*\,|\, \mbox{ o resto da divis\~ao do n\'umero de {\tt a}s em $w$ por
       3 \'e 1}\}\mbox{.}\]
       Em seguida, obtenha uma express\~ao regular que denote $L$ utilizando o
       m\'etodo do livro texto ou visto em aula.

 \item Sejam as ERs:
       \begin{itemize}
        \item $r_1=(0+1)^*(01+10)(0+1)^*$
        \item $r_2=1(0+1)^*1$
       \end{itemize}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Construa um AFD $M_1$ que reconhe\c ca $L(r_1)$ com apenas um estado final.
        \item Construa um AFD $M_2$ que reconhe\c ca $L(r_2)$.
        \item Obtenha um AFN$\lambda$ $M_3$ que reconhe\c ca $L(M_1)L(M_2)$
              utilizando os estados de $M_1$ e $M_2$ e introduzindo uma
              transi\c c\~ao sob $\lambda$ do estado final de $M_1$ para o estado
              inicial de $M_2$.
        \item Ao eliminar a transi\c c\~ao sob $\lambda$ de $M_3$ para transform\'a-lo
              em um AFN equivalente, que transi\c c\~oes devem ser
              acrescentadas? Como fica o AFN?
       \end{list}

 \item Seja a gram\'atica regular $G$:
       \begin{enumerate}
        \item[\ ] $P\,\rightarrow{\tt a}A\,|\,{\tt b}B\,|\,{\tt c}C$
        \item[\ ] $A\,\rightarrow{\tt a}A\,|\,{\tt b}A\,|\,{\tt c}A
                    \,|\,{\tt a}$
        \item[\ ] $B\,\rightarrow{\tt a}B\,|\,{\tt b}B\,|\,{\tt c}B
                    \,|\,{\tt b}$
        \item[\ ] $C\,\rightarrow{\tt a}C\,|\,{\tt b}C\,|\,{\tt c}C
                    \,|\,{\tt c}$
       \end{enumerate}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item A partir de $G$, pelo m\'etodo visto em aula ou no livro, construa
              um AFN que reconhe\c ca $L(G)$.
        \item Que linguagem \'e $L(G)$?
       \end{list}
\end{enumerate}

\end{document}
