\documentclass[11pt, a4paper]{report}

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

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

\begin{document}

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

\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ões 2(a) e 2(b) dever\~ao ser usados \textbf{m\'etodos vistos em aula ou no livro-texto}.
Não será permitido o uso de outros métodos, mesmo os que levem a soluções corretas.}}

\begin{enumerate}
 \item Construa AFNs (sem transições $\lambda$) que reconhe\c{c}am:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in \{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ contém algum símbolo repetido}\}$.
              O AFN não deve ter mais de 5 estados.
        \item $(00)^*(01+10)^*(11)^*$. O AFN não deve ter mais de 8 estados.
       \end{list}

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

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

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

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha o diagrama de estados de um AFN equivalente. Para cada $(e,s)$ tal que $|\delta'(e,s)|>1$,
              indique o c\'alculo de $\delta'(e,s)$. ($\delta'$ é a função de transição do AFN obtido.)
        \item Construa um AFD equivalente ao AFN obtido em (a).
       \end{list}

 \item Encontre expressões regulares que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o n\'umero de {\tt a}s somado
               com o de {\tt b}s em $w$ \'e par$\}$.
        \item A linguagem reconhecida por:

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

        \node[Nmarks=i](1)(40,27){1}
        \node[Nmarks=r](2)(70,27){2}
        \node(3)(55,7){3}

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

       \end{list}
 \item Seja $L=\{x{\tt 1}x^R \,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$. Para cada linguagem a seguir,
       mostre que ela \'e regular ou que n\~ao \'e:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L$.
        \item $L\{{\tt 0},{\tt 1}\}^*$.
       \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}

