\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{2cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turma W/{\bf Solu\c{c}\~ao do professor} \hfill {31/3/2009}

\vspace*{2mm}
\begin{enumerate}

 \item {\footnotesize Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$, $X=\Sigma^*\{{\tt 0}\}$ e $Y=\Sigma^*\{{\tt 1}\}\Sigma^*$.
       Descreva de forma clara e precisa, em portugu\^es, as linguagens a seguir. N\~ao \'e necess\'ario
       dizer que as palavras s\~ao de {\tt 0}s e {\tt 1}s. Por exemplo:
       \begin{quote}
        $X$: conjunto das palavras que terminam com {\tt 0}.
       \end{quote}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y$.
        \item $XY$.
        \item $YX$.
        \item $X-Y$.
       \end{list}}

       {\em Solu\c{c}\~ao:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Y$: conjunto das palavras que cont\^em {\tt 1}.
        \item $XY$: conjunto das palavras que cont\^em {\tt 01}.
        \item $YX$: conjunto das palavras que cont\^em {\tt 1} e terminam com {\tt 0}.
        \item $X-Y$: conjunto das palavras sem {\tt 1}s com pelo menos um {\tt 0}.
       \end{list}

 \item {\footnotesize Sejam $A=\{{\tt 0}\}^*\{{\tt 1}\}^*$ e $P=\{x\in \{{\tt 0},{\tt 1}\}^+\,|\,x=x^R\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A$.
        \item $P$.
        \item $AP$.
        \item $A-P$.
       \end{list}}

       {\em Solu\c{c}\~ao:}

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

 \item {\footnotesize Construa AFDs que reconhe\c cam as linguagens a seguir. Apresente apenas os
       diagramas de estados (que podem ser simplificados).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a},{\tt b}\}^*-\{{\tt a},{\tt b}\}$.
        \item O conjunto das palavras de {\tt a}s e {\tt b}s que come\c{c}am com {\tt a}
              e t\^em n\'umero par de {\tt b}s.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ n\~ao cont\'em {\tt aba}$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em {\tt aa}, mas n\~ao cont\'em {\tt bb}$\}$.
       \end{list}}

       \emph{Solu\c{c}\~ao}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(60,15)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

                \node[Nmarks=ir](1)(20,10){}
                \node(2)(40,10){}
                \node[Nmarks=r](3)(60,10){}

                \drawedge[curvedepth=0](1,2){{\tt a},{\tt b}}
                \drawedge[curvedepth=0](2,3){{\tt a},{\tt b}}
                \drawloop[loopangle=0](3){{\tt a},{\tt b}} 
               \end{picture}
              } \\
 
        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(60,15)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

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

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

        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(60,15)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

                \node[Nmarks=ir](1)(20,10){}
                \node[Nmarks=r](2)(40,10){}
                \node[Nmarks=r](3)(60,10){}

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

        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(60,30)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

                \node[Nmarks=i](1)(20,25){}
                \node(2)(40,25){}
                \node[Nmarks=r](3)(60,25){}
                \node[Nmarks=r](4)(80,25){}
                \node(5)(30,10){}

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

 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $Z=\Sigma^*\{{\tt 0}\}\Sigma^*$
        \item $U=\Sigma^*\{{\tt 11}\}\Sigma^*$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $Z$ e $U$.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $Z\cup U$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $Z-U$.
       \end{list}}

       \emph{Solu\c{c}\~ao}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,20)
                \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

                \put(25,0){\makebox(0,0){AFD para $Z$}}
                \node[Nmarks=i](0)(15,12){$0$}
                \node[Nmarks=r](1)(35,12){$1$}

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

                \put(80,0){\makebox(0,0){AFD para $U$}}
                \node[Nmarks=i](0)(60,12){$0$}
                \node(1)(80,12){$1$}
                \node[Nmarks=r](2)(100,12){$2$}

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


               \end{picture}
              } \\


        \item Produto dos AFDs de $Z$ e $U$:

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

                \node[Nmarks=i](00)(30,27){$[0,0]$}
                \node(01)(50,27){$[0,1]$}
                \node(02)(70,27){$[0,2]$}
                \node(10)(30,3){$[1,0]$}
                \node(11)(50,3){$[1,1]$}
                \node(12)(70,3){$[1,2]$}

                \drawedge[curvedepth=0](00,01){{\tt 1}}
                \drawedge[curvedepth=0](00,10){{\tt 0}}
                \drawedge[curvedepth=0](01,10){{\tt 0}}
                \drawedge[curvedepth=0](01,02){{\tt 1}}
                \drawloop[loopangle=0](02){{\tt 1}}
                \drawedge[curvedepth=0](02,12){{\tt 0}}
                \drawloop[loopangle=180](10){{\tt 0}}
                \drawedge[curvedepth=4](10,11){{\tt 1}}
                \drawedge[curvedepth=4](11,10){{\tt 0}}
                \drawedge[curvedepth=0](11,12){{\tt 1}}
                \drawloop[loopangle=0](12){{\tt 0},{\tt 1}}
               \end{picture}
              } \\

        \item Estados finais para o AFD que reconhece $Z\cup U$: $\{[1,0],[1,1],[1,2],[0,2]\}$.
        \item Estados finais para o AFD que reconhece $Z-U$: $\{[1,0],[1,1]\}$.
       \end{list}
\end{enumerate}

\end{document}
