\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{.5cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turmas B e E \hfill {08/10/2009}

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

\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{\textbf{Aten\c{c}\~ao}:
Nas quest\~oes 2,3 e 4 dever\~ao ser usados m\'etodos vistos em aula ou no livro-texto.
Qualquer resultado, mesmo que correto, obtido de forma \emph{ad-hoc\/} n\~ao ser\'a considerado.}}

\begin{enumerate}
 \item Construa AFNs que reconhe\c{c}am as seguintes linguagens de alfabeto $\{{\tt a},{\tt b},{\tt c}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto das palavras com, no m\'{\i}nimo, tr\^es ocorr\^encias da subpalavra {\tt abc}.
        \item Conjunto das palavras em que h\'a, no m\'{\i}nimo, duas ocorr\^encias da subpalavra {\tt abc} e
              entre duas delas h\'a um n\'umero \'{\i}mpar de s\'{\i}mbolos.
       \end{list}

 \item Seja o AFN$\lambda$ com o diagrama de estados:

       \begin{picture}(120,32)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(40,17){1}
        \node(2)(60,27){2}
        \node[Nmarks=r](3)(60,7){3}
        \node(4)(80,27){4}
        \node(5)(80,7){5}
        \node[Nmarks=r](6)(100,17){6}

        \drawedge[curvedepth=2](1,2){$\lambda$,{\tt b}}
        \drawedge(1,3){$\lambda$}
        \drawedge[curvedepth=2](2,1){{\tt a}}
        \drawedge(2,4){{\tt b}}
        \drawloop[loopangle=270](3){{\tt b}}
        \drawedge(3,5){{\tt a}}
        \drawedge(4,5){$\lambda$}
        \drawedge[curvedepth=2](5,6){{\tt a}}
        \drawedge[curvedepth=2](6,5){{\tt a}}
       \end{picture}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha o diagrama de estados de um AFN equivalente. Ao eliminar transi\c{c}\~oes sob $\lambda$,
              n\~ao crie transi\c{c}\~oes desness\'arias.
        \item Para cada $(e,s)$ tal que $s\not=\lambda$ e $|\delta(e,s)|>1$ indique o c\'alculo de $\delta'(e,s)$.
              ($\delta$ \'e a fun\c{c}\~ao de transi\c{c}\~ao do AFN$\lambda$ e $\delta'$ a do AFN obtido.)
       \end{list}

 \item Obtenha um AFD equivalente ao AFN a seguir usando o m\'etodo da constru\c{c}\~ao-de-subconjuntos:

       \begin{picture}(120,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=270](1)(40,7){1}
        \node[Nmarks=ir, iangle=270](2)(60,7){2}
        \node[Nmarks=r](3)(80,7){3}

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

 \item Obtenha uma express\~ao regular que denote a linguagem reconhecida pelo AFN da quest\~ao anterior, a
       partir do pr\'oprio AFN. \underline{Importante}: n\~ao simplifique a express\~ao.

 \item Sejam $L_1=\{{0}^n \,|\, n \mbox{ \'e um n\'umero primo}\}$ e $L_2=\{{\tt 0}^k \,|\, k\geq 99\}$. Sabe-se
       que $L_1$ n\~ao \'e regular, mas $L_2$ \'e. Para cada linguagem a seguir, mostre que ela \'e regular
       ou que n\~ao \'e:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$.
        \item $L_1\cap L_2$.
       \end{list}
\end{enumerate}

\vspace*{.5mm}
\hrule

\vspace*{.5mm}
\hrule
\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{
 AFN$\lambda$: aut\^omato finito n\~ao determin\'{\i}stico com transi\c{c}\~ao $\lambda$; \\
 AFN: aut\^omato finito n\~ao determin\'{\i}stico (sem transi\c{c}\~ao $\lambda$); \\
 AFD: aut\^omato finito determin\'{\i}stico.
}}
\end{document}

