\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\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{1}^{\mbox{\underline{o}}}$ semestre de 2011 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W \hfill {10/05/2011}

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

%\vspace*{2mm}
%\noindent\framebox{\parbox{15.6cm}{\textbf{Aten\c{c}\~ao}: Em todas as quest\~oes 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. Assim, \'e importante que explicite os passos executados em cada solu\c{c}\~ao apresentada.}}

\begin{enumerate}
 \item Construa diagramas de estado para AFNs que reconhe\c{c}am as linguagens a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto das palavras em $\{{\tt 0},{\tt 1}\}^*$ que tenham dois {\tt 1}s separados por um
              número ímpar de símbolos.
        \item $(00+11)^*(0+\lambda)(1+01)^*$.
       \end{list}

 \item Seja o AFN com o diagrama de estados (note os 4 estados iniciais):

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

        \node[Nmarks=i, iangle=180](1)(40,25){1}
        \node(2)(60,25){2}
        \node[Nmarks=i, iangle=180](3)(60,5){3}
        \node[Nmarks=i, iangle=70](4)(80,15){4}
        \node[Nmarks=ir, iangle=0](5)(100,15){5}

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

       Obtenha um AFD equivalente ao AFN utilizando o m\'etodo visto (\textit{subset construction}); use
       como nome de cada estado do AFD o conjunto dos estados do qual foi derivado.

 \item Obtenha uma express\~ao regular que denote a linguagem reconhecida pelo AFN:

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

        \drawloop[loopangle=90](1){{\tt 1}}
        \drawedge[curvedepth=2](1,2){{\tt 0}}
        \drawedge[curvedepth=0, ELside=r](1,3){{\tt 0}}
        \drawloop[loopangle=90](2){{\tt 1}}
        \drawedge[curvedepth=2](2,1){{\tt 0}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt 1}}
        \drawloop[loopangle=180](3){{\tt 0}}
        \drawedge[curvedepth=2](3,4){{\tt 1}}
        \drawloop[loopangle=0](4){{\tt 0}}
        \drawedge[curvedepth=2](4,3){{\tt 1}}
       \end{picture}
       
 \item Diga, justificando de forma sucinta, se está certa ou errada cada afirmativa a seguir.
       Não será aceita resposta sem justificativa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dado um AFN$\lambda$ qualquer, é possível obter um AFN equivalente com exatamente
              o mesmo número de estados.
        \item Dado um AFN qualquer, é possível obter um AFD equivalente com no máximo o dobro de estados.
        \item Se uma linguagem satisfaz o lema do bombeamento visto em aula, então ela é uma linguagem regular.
        \item $\{{\tt 0}\}^*\{{\tt 0}^n\,|\,\mbox{ $n$ é primo}\}$ é uma linguagem regular.
       \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}
