\documentclass[12pt,a4paper]{report}

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

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

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Solução do professor

\begin{enumerate}
 \item {\footnotesize Sejam $A=\{\lambda,{\tt 0}\}$, $B=\{{\tt 0},{\tt 11}\}$ e $C=\{{\tt 00},{\tt 1}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Calcule $AAB$.
				\item Quantas palavras há na linguagem $A^k$, sendo $k\in\mathbb{N}$?
				\item Dê, em português, uma condição necessária e suficiente para que uma palavra pertença a
				      $\{{\tt 00}\}^*\cap B^*$.
        \item Descreva $B^*\cap C^*$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $AAB=\{{\tt 0},{\tt 11},{\tt 00},{\tt 011},{\tt 000},{\tt 0011}\}$.
				\item $A^k=\{{\tt 0}^0,{\tt 0}^1,\ldots,{\tt 0}^k\}$ tem $k+1$ palavras.
				\item Uma palavra pertence a $\{{\tt 00}\}^*\cap B^*$ sse ela só tem {\tt 0}s e tem número par
				      de {\tt 0}s.
        \item $B^*\cap C^*=\{{\tt 00},{\tt 11}\}^*$.
       \end{list}

  \item {\footnotesize Obtenha gramáticas para as linguagens:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\{{\tt 0}\}^*\{{\tt 1}\}^+$;
         \item $\{xyx^R\,|\, x\in\{{\tt a},{\tt b}\}^* \mbox{ e } y\in\{{\tt cc}\}^*\}$.
        \end{list}}

       \textit{Solução}:

        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $P \,\rightarrow\, {\tt 0}P \,|\, {\tt 1}R$ \\
               $R \,\rightarrow\, {\tt 1}R \,|\, \lambda$
         \item $P \,\rightarrow\, {\tt a}P{\tt a} \,|\, {\tt b}P{\tt b} \,|\, C$ \\
               $C \,\rightarrow\, {\tt c}C{\tt c} \,|\, \lambda$
        \end{list}

 \item {\footnotesize Construa AFDs que reconheçam as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 11}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o último símbolo de $w$ é idêntico ao primeiro}\}$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \  

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,10)(10,0)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

               \node[Nmarks=ir](1)(20,5){1}
               \node(2)(35,5){2}
               \node(3)(50,5){3}

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

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,34)(10,0)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, filllgray=0.9, loopdiam=4}

               \node[Nmarks=i](i)(20,17){}
               \node[Nmarks=r](1)(35,24){}
               \node[Nmarks=r](2)(35,10){}
               \node(3)(50,24){}
               \node(4)(50,10){}

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

 \item {\footnotesize Sejam $B=\{{\tt 0},{\tt 11}\}$ e $C=\{{\tt 00},{\tt 1}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFD que reconheça $\overline{C^*}$. \textit{Dica}: faça antes um AFD para $C^*$.
        \item Construa um AFD que reconheça $B^*-C^*$. \textit{Dica}: utilize produto de autômatos.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \  

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,10)(10,0)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

               \node[Nmarks=i](1)(20,5){1}
               \node[Nmarks=r](2)(35,5){2}
               \node[Nmarks=r](3)(50,5){3}

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

        \item Fazendo o produto do AFD de 3(a) com o de 4(a), obtenho:  

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,34)(10,0)\setlength{\unitlength}{1mm}
               \gasset{Nw=7, Nh=6, Nmr=3.5, filllgray=0.9, loopdiam=4}

               \node[Nmarks=i](11)(20,17){11}
               \node[Nmarks=r](12)(35,28){12}
               \node(21)(35,6){21}
               \node(23)(50,28){23}
               \node(32)(50,6){32}
               \node[Nmarks=r](13)(65,28){13}
               \node(31)(65,6){31}
               \node(33)(57.5,17){33}

               \drawedge[curvedepth=2](11,12){\tt 0}
               \drawedge[curvedepth=2](11,21){\tt 1}
               \drawedge[curvedepth=2](12,11){\tt 0}
               \drawedge[curvedepth=0](12,23){\tt 1}
               \drawedge[curvedepth=2](21,11){\tt 1}
               \drawedge[curvedepth=0](21,32){\tt 0}
               \drawedge[curvedepth=2](23,13){\tt 1}
               \drawedge[curvedepth=0,ELside=r](23,33){\tt 0}
               \drawedge[curvedepth=2](32,31){\tt 0}
               \drawedge[curvedepth=0](32,33){\tt 1}
               \drawloop[loopangle=0](13){\tt 0}
               \drawedge[curvedepth=2](13,23){\tt 1}
               \drawloop[loopangle=0](31){\tt 1}
               \drawedge[curvedepth=2](31,32){\tt 0}
               \drawloop[loopangle=0](33){{\tt 0},{\tt 1}}
              \end{picture}
             }
       \end{list}

 \item {\footnotesize Sobre AFNs:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFN que reconheça $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ contém apenas um {\tt a} ou apenas um {\tt b} ou apenas um {\tt c}}\}$. Basta o diagrama de estados.
        \item Usando o método visto no curso, construa um AFD equivalente ao AFN:

              \begin{picture}(120,15)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

               \node[Nmarks=i, iangle=180](1)(15,5){1}
               \node[Nmarks=ir, iangle=90](3)(35,5){3}
               \node[Nmarks=i, iangle=0](2)(55,5){2}

               \drawedge[curvedepth=0](1,3){\tt a}
               \drawedge[curvedepth=3](2,3){\tt b}
               \drawedge[curvedepth=3](3,2){\tt a}

              \end{picture}
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \  

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,10)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, filllgray=0.9, loopdiam=4}

               \node[Nmarks=i](1)(15,5){}
               \node[Nmarks=r](2)(30,5){}

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

               \node[Nmarks=i](1)(55,5){}
               \node[Nmarks=r](2)(70,5){}

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

               \node[Nmarks=i](1)(95,5){}
               \node[Nmarks=r](2)(110,5){}

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

        \item Diagrama de estados simplificado:

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,34)(10,0)\setlength{\unitlength}{1mm}
               \gasset{Nw=9, Nh=6, Nmr=4, filllgray=0.9, loopdiam=4}

               \node[Nmarks=ir](123)(20,17){123}
               \node[Nmarks=r](23)(35,28){23}
               \node[Nmarks=r](3)(35,6){3}
               \node(2)(50,17){2}

               \drawedge[curvedepth=0](123,23){\tt a}
               \drawedge[curvedepth=0](123,3){\tt b}
               \drawedge[curvedepth=0](23,2){\tt a}
               \drawedge[curvedepth=0](23,3){\tt b}
               \drawedge[curvedepth=2](2,3){\tt b}
               \drawedge[curvedepth=2](3,2){\tt a}
              \end{picture}
             }
       \end{list}
\item {\footnotesize Construa um AFN equivalente ao AFN$\lambda$ a seguir usando o método visto  em aula.

      \begin{picture}(120,15)\setlength{\unitlength}{1mm}
       \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

       \node[Nmarks=r](B)(20,5){B}
       \node[Nmarks=i, iangle=270](A)(40,5){A}
       \node[Nmarks=r](C)(60,5){C}

       \drawloop[loopangle=90](B){\tt b}
       \drawedge[curvedepth=0,ELside=r](A,B){$\lambda$}
       \drawloop[loopangle=90](A){\tt a}
       \drawedge[curvedepth=0](A,C){$\lambda$}
       \drawloop[loopangle=90](C){\tt c}
      \end{picture}}

       \textit{Solução}:

      \begin{picture}(120,15)\setlength{\unitlength}{1mm}
       \gasset{Nw=6, Nh=6, Nmr=3, filllgray=0.9, loopdiam=4}

       \node[Nmarks=ir, iangle=270](B)(20,5){B}
       \node[Nmarks=i, iangle=270](A)(40,5){A}
       \node[Nmarks=ir, iangle=270](C)(60,5){C}

       \drawloop[loopangle=90](B){\tt b}
       \drawedge[curvedepth=0,ELside=r](A,B){\tt a}
       \drawloop[loopangle=90](A){\tt a}
       \drawedge[curvedepth=0](A,C){\tt a}
       \drawloop[loopangle=90](C){\tt c}
      \end{picture}


\end{enumerate}
\end{document}
