\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}
\begin{document}

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


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

 \item Seja a linguagem $L=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o
       \'ultimo s\'{\i}mbolo de $w$ ocorre antes no m\'aximo uma vez$\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFN que reconhe\c{c}a $L$ usando o \textit{menor
              n\'umero de estados e de transi\c c\~oes\/} que conseguir.
        \item Construa uma express\~ao regular que denote $L$. (N\~ao precisa
              ser a partir do AFN.)
       \end{list}
 
 \item Seja o AFN com o diagrama de estados a seguir:

       \begin{picture}(100,43)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(20,30){1}
        \node[Nmarks=i, iangle=180](2)(20,10){2}
        \node(3)(40,20){3}
        \node[Nmarks=r](4)(60,20){4}

        \drawedge[curvedepth=0](1,3){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt a}}
        \drawedge[curvedepth=0](3,4){{\tt b},{\tt c}}
        \drawloop[loopangle=90](1){{\tt a},{\tt b}}
        \drawloop[loopangle=270](2){{\tt a},{\tt c}}
       \end{picture}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gram\'atica regular que gere a linguagem reconhecida
              pelo AFN usando o m\'etodo visto em aula. (Antes, transforme o
              AFN em um equivalente com apenas um estado inicial.)
        \item Construa um AFD equivalente usando o m\'etodo visto em aula.
       \end{list}

 \item Seja o AFN$\lambda$ $M$:

       \begin{picture}(100,25)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(20,10){1}
        \node(2)(40,10){2}
        \node[Nmarks=r](3)(60,10){3}

        \drawedge[curvedepth=0](1,2){{\tt a},$\lambda$}
        \drawedge[curvedepth=0](2,3){{\tt a},$\lambda$}
        \drawloop[loopangle=90](1){{\tt b}}
        \drawloop[loopangle=90](2){{\tt b}}
        \drawloop[loopangle=90](3){{\tt b}}
       \end{picture}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O que \'e $f\lambda(\{1\})$?
        \item Construa um AFN $N$, equivalente a $M$, usando o m\'etodo visto
              em aula.
       \end{list}

 \item Seja a linguagem $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\eta(w) \mbox{ mod }
       3 = 1\}$. Obtenha um AFD para a mesma e, a partir dele, uma express\~ao
       regular, usando o m\'etodo visto em aula. ($\eta(w)$ \'e o n\'umero
       representado por $w$ em bin\'ario.)

 \item Utilizando o lema do bombeamento, prove que $\{xy\in\{{\tt 0},
       {\tt 1}\}^*\,|\, |x|=|y|$ e $n_{\tt 0}(x)=n_{\tt 1}(y)\}$ n\~ao \'e uma
       linguagem regular. ($n_s(w)$ \'e o n\'umero de s\'{\i}mbolos $s$ na
       palavra $w$.)
\end{enumerate}
\end{document}
