\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

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

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 3 pontos.

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

\item Construa um AFN que reconhe\c{c}a a linguagem a seguir usando o
      \textit{menor n\'umero de estados e de transi\c c\~oes\/} que conseguir:
      \[\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, \mbox{ o \'ultimo
      s\'{\i}mbolo de $w$ ocorre antes um n\'umero \'{\i}mpar de
      vezes}\}\mbox{.}\] Observe que o n\'umero \textbf{total} de
      ocorr\^encias do \'ultimo s\'{\i}mbolo \'e par. Suponha tamb\'em que
      $\lambda$ n\~ao \'e palavra da linguagem em quest\~ao.

 \item Seja o AFNE com o diagrama de estados:

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

        \drawedge[curvedepth=0](1,3){$\lambda$}
        \drawedge[curvedepth=3](2,4){{\tt bb},{\tt cc}}
        \drawedge[curvedepth=3](4,2){{\tt a}}
        \drawedge[curvedepth=0](4,3){$\lambda$}
        \drawloop[loopangle=90](1){{\tt aa}}
        \drawloop[loopangle=90](3){{\tt ab},{\tt ac}}
       \end{picture}

       Obtenha, em seq\"u\^encia, \underline{usando os m\'etodos vistos em
       aula}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um AFN$\lambda$ equivalente.
        \item Um AFN equivalente.
       \end{list}

 \item Seja o AFN com o diagrama de estados:

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

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe o diagrama de estados de um AFN equivalente com
              apenas um estado inicial.
        \item Desenhe o diagrama de estados de um AFN equivalente com
              apenas um estado final.
       \end{list}
       No item (a), o AFN pode ter v\'arios estados finais e no item (b)
       o AFN pode ter v\'arios estados iniciais.

 \item Para a linguagem reconhecida pelo AFN da quest\~ao anterior:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gram\'atica regular que a gere.
        \item Obtenha uma express\~ao regular que a denote.
       \end{list}
       Dever\~ao ser usados os m\'etodos de obten\c{c}\~ao de gram\'atica
       regular e de express\~ao regular a partir de aut\^omatos finitos
       vistos em aula.

 \item Prove que $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)\not=
       n_{\tt c}(w)\}$ n\~ao \'e uma linguagem regular. ($n_s(w)$ \'e o
       n\'umero de s\'{\i}mbolos $s$ na palavra $w$.)
\end{enumerate}


\noindent \textbf{Extra.} Prove que \textit{se um AFD $M$ de $k$ estados
n\~ao reconhece palavras de $k$ a $2k-1$ s\'{\i}mbolos, ent\~ao $L(M)$ \'e
finita}, e ganhe dois pontos extra! Como toda demonstra\c{c}\~ao digna do
nome, ela deve ser escrita \textit{em portugu\^es}, de cabo a rabo.

\end{document}
