\documentclass[11pt, a4paper]{report}

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

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Solu\c{c}\~ao do professor \hfill {31/8/2010}

\begin{enumerate}

 \item {\footnotesize Sejam $\Sigma=\{{\tt}0,{\tt 1}\}$, $X=\Sigma^*\{{\tt 0}\}\Sigma^*$ e $Y=\Sigma^*\{{\tt 1}\}$.
       Descreva, de forma concisa, uma condi\c{c}\~ao necess\'aria e suficiente para que uma
       palavra perten\c{c}a a:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $XY$.
        \item $X\cap Y$.
        \item $Y-X$.
        \item $Y^+$.
       \end{list}}

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

      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cont\'em {\tt 0} e seu \'ultimo s\'{\i}mbolo \'e {\tt 1}.
        \item Idem.
        \item Tem no m\'{\i}nimo um s\'{\i}mbolo e cont\'em apenas {\tt 1}s.
        \item Seu \'ultimo s\'{\i}mbolo \'e {\tt 1}.
       \end{list}

 \item {\footnotesize Seja $Z=\{{\tt 0}\}^*\{{\tt 1}\}^*$ e $W=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 1\}$.
       Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $Z$.
        \item $W$.
        \item $ZW$.
        \item $\{wxw^R\,|\, w\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } x\in Z\}$.
       \end{list}}

       \emph{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 1} \,|\, {\tt 01}$
        \item $X\,\rightarrow\, AB$ \\
              $A\,\rightarrow\, {\tt 0}A \,|\, A{\tt 1} \,|\, \lambda$ \\
              $B\,\rightarrow\, {\tt 0}B{\tt 1} \,|\, \lambda$
        \item $P\,\rightarrow\, {\tt 0}P{\tt 0} \,|\, {\tt 1}P{\tt 1} \,|\, A$ \\
              $A\,\rightarrow\, {\tt 0}A \,|\, A{\tt 1} \,|\, \lambda$
       \end{list}
 
 \item {\footnotesize Sejam $\Sigma=\{{\tt}0,{\tt 1}\}$, $X=\Sigma^*\{{\tt 0}\}\Sigma^*$ e $Y=\Sigma^*\{{\tt 1}\}$.
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de dois AFDs $M_X$ e $M_Y$ tais que $L(M_X)=X$ e $L(M_Y)=Y$.
        \item Obtenha o diagrama de estados para o produto de $M_X$ e $M_Y$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $X\cap Y$.
        \item Diga quais s\~ao os estados finais para o AFD que reconhece $Y-X$.
       \end{list}}

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

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

        \put(10,10){\makebox(0,0){$M_X$:}}
        \node[Nmarks=i, iangle=180](1)(25,10){1}
        \node[Nmarks=r](2)(45,10){2}

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

%------------------
        \put(75,10){\makebox(0,0){$M_Y$:}}
        \node[Nmarks=i, iangle=180](1)(90,10){1}
        \node[Nmarks=r](2)(110,10){2}

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

       \end{picture}
}

        \item  \ 
        
              \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,35)
        \gasset{Nw=10, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \node[Nmarks=i, iangle=180](11)(30,30){[1,1]}
        \node(21)(60,30){[2,1]}
        \node(12)(30,10){[1,2]}
        \node(22)(60,10){[2,2]}

        \drawedge[curvedepth=0](11,21){{\tt 0}}
        \drawedge[curvedepth=0](11,12){{\tt 1}}
        \drawloop[loopangle=90](21){{\tt 0}}
        \drawedge[curvedepth=4](21,22){{\tt 1}}
        \drawloop[loopangle=180](12){{\tt 1}}
        \drawedge[curvedepth=0](12,21){{\tt 0}}
        \drawloop[loopangle=0](22){{\tt 1}}
        \drawedge[curvedepth=4](22,21){{\tt 0}}

       \end{picture}
}

        \item Estados finais para o AFD que reconhece $X\cap Y$: [2,2].
        \item Estados finais para o AFD que reconhece $Y-X$: [1,2].
       \end{list}

 \item {\footnotesize Seja $L=\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ se $|w|>0$, o primeiro e o \'ultimo
       s\'{\i}mbolos de $w$ s\~ao id\^enticos}\}$.
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Apresente o diagrama de estados de um AFD que reconhe\c{c}a $L$.
        \item Expresse $L$ usando apenas subconjuntos finitos de $\{{\tt a},{\tt b}\}^*$ e opera\c{c}\~oes
              dentre: uni\~ao, interse\c{c}\~ao, concatena\c{c}\~ao e fecho de Kleene.
       \end{list}}


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

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

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

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

               \drawloop[loopangle=270](3){{\tt b}}
               \drawedge[curvedepth=4](3,4){{\tt a}}
               \drawloop[loopangle=270](4){{\tt a}}
              \drawedge[curvedepth=4](4,3){{\tt b}}
              \end{picture}
             }
        \item $\{{\tt a},{\tt b}\}\cup\{{\tt a}\}\{{\tt a},{\tt b}\}^*\{{\tt a}\}\cup\{{\tt b}\}\{{\tt a},{\tt b}\}^*\{{\tt b}\}$
       \end{list}
\end{enumerate}

\end{document}
