\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{amsfonts}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Primeira Prova} --- Turma N \hfill 7/4/2015

\noindent Cada questão vale 4 pontos.

%\vspace*{2mm}
\begin{enumerate}
 \item Descreva as linguagens a seguir, todas de alfabeto $\{{\tt 0},{\tt 1}\}$, usando apenas \textit{conjuntos finitos}
       e operações de \textit{união}, \textit{interseção}, \textit{concatenação} e \textit{fecho de Kleene}.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com número par de símbolos.
        \item O conjunto das palavras com no máximo três {\tt 0}s.
        \item O conjunto das palavras que contêm no mínimo um {\tt 0} e no mínimo um {\tt 1}.
        \item O conjunto das palavras que não contêm {\tt 01} como prefixo.
       \end{list}

 \item Obtenha gramáticas para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}$.
        \item O conjunto das palavras no alfabeto $\{{\tt 0},{\tt 1}\}$ com número par de símbolos.
        \item $\{{\tt 0}^{2n}{\tt 1}^{3n}\,|\, n\in\mathbb{\bf N}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w=w^R\}$.
       \end{list}

 \item Obtenha AFDs para as linguagens dos ítens (c) e (d) da questão 1.

 \item Seja o AFN com o diagrama de estados a seguir:
       \begin{center}
       \begin{picture}(70,35)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,25){1}
        \node[Nmarks=i](2)(20,5){2}
        \node[Nmarks=r](3)(40,15){3}

        \drawloop[loopangle=90](1){\tt 0}
        \drawedge[curvedepth=0](1,3){\tt 1}
        \drawloop[loopangle=270](2){\tt 1}
        \drawedge[curvedepth=0, ELside=r](2,3){\tt 0}
       \end{picture}
       \end{center}
       Apresente o diagrama de estados completo de um AFD equivalente usando o método visto em aula
			 (\textit{subset construction}).

 \item Seguem diagramas de estado incompletos de dois AFDs, um que reconhece $X=\{{\tt 0}\}^*\{{\tt 1}\}$ e outro que
       reconhece $Y=\{{\tt 1}\}^*\{{\tt 0}\}$:
       \begin{center}
       \begin{picture}(120,10)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,0){1}
        \node[Nmarks=r](2)(40,0){2}

        \node[Nmarks=i](3)(70,0){1}
        \node[Nmarks=r](4)(90,0){2}

        \drawloop[loopangle=90](1){\tt 0}
        \drawedge[curvedepth=0](1,2){\tt 1}
        \drawloop[loopangle=90](3){\tt 1}
        \drawedge[curvedepth=0](3,4){\tt 0}
       \end{picture}
       \end{center}
       Faça o produto dos dois (não esquecendo estados de erro) e aponte que estados seriam finais para o reconhecimento de:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X\cap Y$. \hspace{1cm} (b) $X\cup Y$. \hspace{1cm} (c) $X-Y$.
       \end{list}

 \item Seja o AFN$\lambda$ com o diagrama de estados a seguir:
       \begin{center}
       \begin{picture}(90,10)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,0){1}
        \node(2)(40,0){2}
        \node[Nmarks=r](3)(60,0){3}

        \drawloop[loopangle=90](1){\tt a}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawloop[loopangle=90](2){\tt b}
        \drawedge[curvedepth=0](2,3){$\lambda$}
        \drawloop[loopangle=90](3){\tt c}
       \end{picture}
       \end{center}
       Construa um AFN equivalente usando o método visto em aula. Comece exibindo $f\lambda(e)$ para cada estado $e$.
\end{enumerate}

\end{document}
