\documentclass[11pt, a4paper]{report}

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

\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 2014 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Primeira Prova} --- Turma N \hfill 11/3/2014

\noindent Cada questão vale 4,5 pontos, exceto a terceira, que vale 6 pontos.

\vspace*{3mm}
\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 que contêm pelo menos um {\tt 0} e um {\tt 1}.
        \item O conjunto das palavras de $\{{\tt 0}\}^*\{{\tt 1}\}^*$ de comprimento par.
       \end{list}
 \item Diga que linguagens são geradas pelas gramáticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{A\},\{{\tt 0},{\tt 1}\},R_1,A)$, sendo $R_1$ constituído de:
              \begin{quote}
			         $A\,\rightarrow\, {\tt 0} A \,|\, A{\tt 0} \,|\, {\tt 1}$
		      	  \end{quote}
        \item $G_2=(\{B\},\{{\tt 0},{\tt 1}\},R_2,B)$, sendo $R_2$ constituído de:
              \begin{quote}
			         $B\,\rightarrow\, {\tt 0}B{\tt 00} \,|\, {\tt 1}$
			        \end{quote}
        \item $G_3=(\{S,A,B\},\{{\tt 0},{\tt 1}\},R_3,S)$, sendo $R_3$ constituído de:
              \begin{quote}
			         $S\,\rightarrow\, AA \,|\, B$ \\
			         $A\,\rightarrow\, {\tt 0} A \,|\, A{\tt 0} \,|\, {\tt 1}$\\
			         $B\,\rightarrow\, {\tt 0}B{\tt 00} \,|\, {\tt 1}$
			        \end{quote}
       \end{list}
 \item Obtenha AFDs para as linguagens da questão 1.
 \item Seja o AFN com o diagrama de estados a seguir:

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

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

       Construa um AFD equivalente usando o método visto em aula (\textit{subset construction}).
 \item Seja o AFN$\lambda$ com o diagrama de estados a seguir:

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

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

       Construa um AFN equivalente usando o método visto em aula.
\end{enumerate}

\end{document}
