\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/Solução do professor \hfill 7/4/2015

%\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize 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}}

       \textit{\underline{Solução}}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{{\tt 0},{\tt 1}\}^2)^*$
        \item $\{{\tt 1}\}^*(\{\lambda,{\tt 0}\}\{{\tt 1}\}^*)^3$
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 01},{\tt 10}\}\{{\tt 0},{\tt 1}\}^*$
        \item $\{\lambda,{\tt 0}\}\cup\{{\tt 1},{\tt 00}\}\{{\tt 0},{\tt 1}\}^*$
       \end{list}

 \item {\footnotesize 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}}

       \textit{\underline{Solução}}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, {\tt 0}X{\tt 1}$ \\
				      $X \,\rightarrow\, {\tt 0}X \,|\, {\tt 1}X \,|\, \lambda$
        \item $P \,\rightarrow\, B B P \,|\, \lambda$ \\
				      $B \,\rightarrow\, {\tt 0} \,|\, {\tt 1}$
        \item $A \,\rightarrow {\tt 00}A{\tt 111} \,|\, \lambda$
        \item $P \,\rightarrow\, {\tt 0}P{\tt 0} \,|\, {\tt 1}P{\tt 1} \,|\, \lambda \,|\, {\tt 0} \,|\, {\tt 1}$
       \end{list}

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

       \textit{\underline{Solução}}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item[(c)] \
			
       \begin{picture}(90,32)
        \gasset{Nw=6, Nh=6, Nmr=3, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](1)(20,15){}
        \node(2)(40,25){}
        \node(3)(40,5){}
        \node[Nmarks=r](4)(60,15){}

        \drawedge[curvedepth=0](1,2){\tt 0}
        \drawedge[curvedepth=0,ELside=r](1,3){\tt 1}
        \drawloop[loopangle=90](2){\tt 0}
        \drawedge[curvedepth=0](2,4){\tt 1}
        \drawloop[loopangle=270](3){\tt 1}
        \drawedge[curvedepth=0, ELside=r](3,4){\tt 0}
        \drawloop[loopangle=0](4){{\tt 0},{\tt 1}}
       \end{picture}
       \item[(d)] \
			
       \begin{picture}(70,25)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir](1)(20,25){}
        \node[Nmarks=r](2)(20,5){}
        \node[Nmarks=r](3)(40,15){}

        \drawedge[curvedepth=0](1,2){\tt 0}
        \drawedge[curvedepth=0](1,3){\tt 1}
        \drawloop[loopangle=0](3){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=0](2,3){\tt 0}
       \end{picture}
       \end{list}
 
 \item {\footnotesize 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}).}

       \textit{\underline{Solução}}:

       \begin{picture}(90,32)
        \gasset{Nw=8, Nh=6, Nmr=7, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](12)(20,15){12}
        \node[Nmarks=r](13)(30,25){13}
        \node[Nmarks=r](23)(30,5){23}
        \node[Nmarks=r](3)(40,15){3}
        \node(1)(48,28){1}
        \node(2)(48,2){2}
        \node(e)(60,15){$\emptyset$}

        \drawedge[curvedepth=0](12,13){\tt 0}
        \drawedge[curvedepth=0,ELside=r](12,23){\tt 1}
        \drawedge[curvedepth=0](13,1){\tt 0}
        \drawedge[curvedepth=0](13,3){\tt 1}
        \drawedge[curvedepth=0,ELside=r](23,2){\tt 1}
        \drawedge[curvedepth=0,ELside=r](23,3){\tt 0}
        \drawloop[loopangle=0](1){\tt 0}
        \drawedge[curvedepth=0](1,3){\tt 1}
        \drawloop[loopangle=0](2){\tt 1}
        \drawedge[curvedepth=0, ELside=r](2,3){\tt 0}
       \drawedge[curvedepth=0](3,e){{\tt 0},{\tt 1}}
        \drawloop[loopangle=0](e){{\tt 0},{\tt 1}}
       \end{picture}

 \item {\footnotesize 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}}

       \textit{\underline{Solução}}:

       \begin{picture}(90,37)
        \gasset{Nw=8, Nh=6, Nmr=7, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i](11)(20,19){11}
        \node(12)(30,29){12}
        \node(21)(30,9){21}
        \node(1e)(48,36){1e}
        \node(e2)(55,14){e2}
        \node(2e)(55,24){2e}
        \node(e1)(48,2){e1}
        \node(ee)(70,19){ee}
        \node(22)(70,36){22}

        \drawedge[curvedepth=0](11,12){\tt 0}
        \drawedge[curvedepth=0,ELside=r](11,21){\tt 1}
        \drawedge[curvedepth=0](12,1e){\tt 0}
        \drawedge[curvedepth=0](12,2e){\tt 1}
        \drawedge[curvedepth=0](1e,2e){\tt 1}
        \drawloop[loopangle=0](1e){\tt 0}
        \drawedge[curvedepth=0](2e,ee){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=0](21,e2){\tt 0}
        \drawedge[curvedepth=0,ELside=r](21,e1){\tt 1}
        \drawedge[curvedepth=0,ELside=r](e1,e2){\tt 0}
        \drawloop[loopangle=0](e1){\tt 1}
        \drawedge[curvedepth=0,ELside=r](e2,ee){{\tt 0},{\tt 1}}
        \drawloop[loopangle=0](ee){{\tt 0},{\tt 1}}
        \drawedge[curvedepth=0](22,ee){{\tt 0},{\tt 1}}
       \end{picture}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item 22. \hspace{1cm} (b) 21, 22, 2e, 12, e2. \hspace{1cm} (c) 21, 2e.
       \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$.

       \textit{\underline{Solução}}:

       $f\lambda(1)=\{1,2,3\}$,  $f\lambda(2)=\{2,3\}$,  $f\lambda(3)=\{3\}$.

       \begin{picture}(90,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillgray=0.9, loopdiam=4, iangle=270}
        \node[Nmarks=i](1)(20,5){1}
        \node[Nmarks=i](2)(40,0){2}
        \node[Nmarks=ir](3)(60,5){3}

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

\end{document}
