\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}/Turmas F e N/{\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=\{{\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 $XY$.
        \item $YX$.
        \item $X\cap Y$.
        \item $X-Y$.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $XY$: conjunto das palavras que cont\^em {\tt 01}.
        \item $YX$: conjunto das palavras que come\c{c}am com {\tt 1} e terminam com {\tt 0}.
        \item $X\cap Y$: conjunto das palavras que come\c{c}am com {\tt 1} e terminam com {\tt 0}.
        \item $X-Y$: conjunto das palavras que come\c{c}am e terminam com {\tt 0}.
       \end{list}

 \item {\footnotesize Sejam $A=\{{\tt 0}\}^*\{{\tt 0},{\tt 1}\}\{{\tt 1}\}^*$ e $B=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A$.
        \item $B$.
        \item $AB$.
        \item $B^*$.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\,\rightarrow\, {\tt 0}A \,|\, A{\tt 1} \,|\, {\tt 0} \,|\, {\tt 1}$
        \item $B\,\rightarrow\, {\tt 0}B{\tt 1} \,|\, \lambda$
        \item $C\,\rightarrow\, AB$ \\
              $A\,\rightarrow\, {\tt 0}A \,|\, A{\tt 1} \,|\, {\tt 0} \,|\, {\tt 1}$ \\
              $B\,\rightarrow\, {\tt 0}B{\tt 1} \,|\, \lambda$
        \item $D\,\rightarrow\, BD \,|\, \lambda$ \\
              $B\,\rightarrow\, {\tt 0}B{\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}\}^*-\{\lambda,{\tt a}\}$.
        \item $\{{\tt a},{\tt b}\}^*\{{\tt bb}\}\{{\tt a},{\tt b}\}^*$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ tem n\'umero par de {\tt a}s e \'{\i}mpar de {c}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ n\~ao cont\'em tr\^es s\'{\i}mbolos consecutivos id\^enticos$\}$.
       \end{list}}

       {\em 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=i](1)(20,10){}
                \node(2)(40,10){}
                \node[Nmarks=r](3)(60,10){}

                \drawedge[curvedepth=0](1,2){{\tt a}}
                \drawedge[curvedepth=0](2,3){{\tt a},{\tt b}}
                \drawedge[curvedepth=-6, ELside=r](1,3){{\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(2)(40,10){}
                \node[Nmarks=r](3)(60,10){}

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

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

                \node[Nmarks=i](pp)(20,30){$pp$}
                \node(ip)(40,30){$ip$}
                \node[Nmarks=r](pi)(20,10){$pi$}
                \node(ii)(40,10){$ii$}

                \drawloop[loopangle=90](pp){{\tt b}}
                \drawloop[loopangle=0](ip){{\tt b}}
                \drawloop[loopangle=270](ii){{\tt b}}
                \drawloop[loopangle=180](pi){{\tt b}}

                \drawedge[curvedepth=4](pp,ip){{\tt a}}
                \drawedge[curvedepth=4](pp,pi){{\tt c}}
                \drawedge[curvedepth=4](ip,pp){{\tt a}}
                \drawedge[curvedepth=4](ip,ii){{\tt c}}
                \drawedge[curvedepth=4](pi,ii){{\tt a}}
                \drawedge[curvedepth=4](pi,pp){{\tt c}}
                \drawedge[curvedepth=4](ii,pi){{\tt a}}
                \drawedge[curvedepth=4](ii,ip){{\tt c}} 
               \end{picture}
              } \\


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

               \node[Nmarks=ir](i)(20,15){}
               \node[Nmarks=r](1)(35,25){}
               \node[Nmarks=r](2)(55,25){}
               \node[Nmarks=r](3)(35,5){}
               \node[Nmarks=r](4)(55,5){}

               \drawedge[curvedepth=0](i,1){{\tt a}}
               \drawedge[curvedepth=0, ELside=r](i,3){{\tt b}}
               \drawedge[curvedepth=0](1,2){{\tt a}}
               \drawedge[curvedepth=4](1,3){{\tt b}}
               \drawedge[curvedepth=0,ELpos=30](2,3){{\tt b}}
               \drawedge[curvedepth=4](3,1){{\tt a}}
               \drawedge[curvedepth=0](3,4){{\tt b}}
               \drawedge[curvedepth=0, ELside=r, ELpos=30](4,1){{\tt a}}
              \end{picture}
             } \\
       \end{list}

 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $I_0=\{w\in\Sigma^* \,|\, \mbox{ o n\'umero de {\tt 0}s em $w$ \'e \'{\i}mpar}\}$
        \item $I_1=\{w\in\Sigma^* \,|\, \mbox{ o n\'umero de {\tt 1}s em $w$ \'e \'{\i}mpar}\}$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $I_0$ e $I_1$.
        \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 $I_0\cup I_1$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $I_0-I_1$.
       \end{list}}

       {\em 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(30,0){\makebox(0,0){AFD para $I_0$}}
                \node[Nmarks=i](p)(20,15){$p$}
                \node[Nmarks=r](i)(40,15){$i$}

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

                \put(90,0){\makebox(0,0){AFD para $I_1$}}
                \node[Nmarks=i](p)(80,15){$p$}
                \node[Nmarks=r](i)(100,15){$i$}

                \drawloop[loopangle=90](p){{\tt 0}} 
                \drawedge[curvedepth=4](p,i){{\tt 1}}
                \drawedge[curvedepth=4](i,p){{\tt 1}}
                \drawloop[loopangle=90](i){{\tt 0}} 
               \end{picture}
              } \\

        \item  Produto dos AFDs de $I_0$ e $I_1$:
        
              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,35)
                \gasset{Nw=10, Nh=6, Nmr=3, loopdiam=6, fillgray=0.9}

                \node[Nmarks=i](pp)(40,28){$[p,p]$}
                \node(ip)(70,28){$[i,p]$}
                \node(pi)(40,3){$[p,i]$}
                \node(ii)(70,3){$[i,i]$}

                \drawedge[curvedepth=4](pp,ip){{\tt 0}}
                \drawedge[curvedepth=4](pp,pi){{\tt 1}} 
                \drawedge[curvedepth=4](ip,pp){{\tt 0}} 
                \drawedge[curvedepth=4](ip,ii){{\tt 1}} 
                \drawedge[curvedepth=4](pi,pp){{\tt 1}} 
                \drawedge[curvedepth=4](pi,ii){{\tt 0}} 
                \drawedge[curvedepth=4](ii,ip){{\tt 1}} 
                \drawedge[curvedepth=4](ii,pi){{\tt 0}} 
               \end{picture}
              } \\

        \item Estados finais para o AFD que reconhece $I_0\cup I_1$: $\{[p,i], [i,p], [i,i]\}$
        \item Estados finais para o AFD que reconhece $I_0-I_1$: $\{[i,p]\}$.
       \end{list}
\end{enumerate}

\end{document}
