\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

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

\pagestyle{empty}
\newcounter{conta}

\begin{document}
\selectlanguage{portuguese}
\setlength{\unitlength}{1mm}

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

\begin{enumerate}

 \item Sejam $\Sigma=\{{\tt a},{\tt b}\}$,  $A=(\Sigma\Sigma)^*$ e $B=\{{\tt a}\}\Sigma^9$.
       Para cada uma das linguagens abaixo, d\^e uma propriedade necess\'aria
       e suficiente para que uma palavra perten\c ca \`a mesma. N\~ao precisa
       dizer que a palavra deve conter apenas {\tt a}s e {\tt b}s (fica
       impl\'{\i}cito).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $B\cap B^R$.
        \item $B-A$.
        \item $B^+$.
       \end{list}
       Exemplo: uma propriedade necess\'aria e suficiente para que uma palavra
       perten\c{c}a a $A-B$ \'e: tem n\'umero par de s\'{\i}mbolos, mas se tem
       10 s\'{\i}mbolos, come\c{c}a com {\tt b}.

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

        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Tem 10 s\'{\i}mbolos e come\c{c}a e termina com {\tt a}.
        \item Falso ($B-A=\emptyset$).
        \item Tem tamanho $10n$, para $n\geq 1$, e tem {\tt a} nas
              posi\c{c}\~oes $10n+1$ para $n\geq 0$.
       \end{list}

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas conjuntos finitos, opera\c c\~oes sobre conjuntos,
       concatena\c c\~ao e fecho de Kleene. Procure obter uma descri\c c\~ao bem
       concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que cont\^em {\tt 00}, mas n\~ao {\tt 11}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras com n\'umero par de {\tt 0}s.
       \end{list}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*-
               \{{\tt 0},{\tt 1}\}^*\{{\tt 11}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0},{\tt 1}\}^*-
               \{{\tt 0},{\tt 1}\}^*\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*$. \\
              Outra resposta: $\{{\tt 1},{\tt 01}\}^*\{\lambda,{\tt 0}\}$.
        \item $(\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\})\{{\tt 1}\}^*$.
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 11}\}^*\{{\tt 0}\}\{{\tt 00}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt \#}\}^*\,|\,$ {\tt 0}'s em $w$ nunca s\~ao seguidos de
              {\tt 1}s e {\tt 1}s nunca s\~ao seguidos de {\tt 0}s$\}$. (Ou seja, seq\"u\^encias
              de {\tt 0}s e de {\tt 1}s s\~ao separadas por um ou mais ${\tt \#}$s.)
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\geq n\}$.
       \end{list}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{enumerate}
               \item[\ ] $X\rightarrow {\tt 11}X \,|\, X{\tt 00} \,|\, {\tt 0}$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\rightarrow {\tt \#}P \,|\, {\tt 0}Z \,|\, {\tt 1}U \,|\, \lambda$
               \item[\ ] $Z\rightarrow {\tt 0}Z \,|\, {\tt \#}P \,|\, \lambda$
               \item[\ ] $U\rightarrow {\tt 1}U \,|\, {\tt \#}P \,|\, \lambda$
              \end{enumerate}
        \item \begin{enumerate}
               \item[\ ] $P\rightarrow {\tt a}P{\tt b} \,|\, {\tt a}P \,|\, \lambda$
              \end{enumerate}

       \end{list}


 \item Construa AFDs que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}^*\{{ \tt 10}\}^*\{11\}^+$.
        \item A linguagem da quest\~ao 3(b).
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ o primeiro s\'{\i}mbolo de
               $w$ \'e igual ao \'ultimo ou ent\~ao $w=\lambda\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \eta(w)\, \mbox{\em mod\/}\, 3=1\}$.
              ($\eta(w)$ \'e o n\'umero representado por $w$ em bin\'ario.)
       \end{list}

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

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

              \begin{picture}(60,33)\scriptsize
               \gasset{Nw=6, Nh=6, Nmr=3}
               \node[Nmarks=i](1)(10,30){$1$}
               \node(1L)(10,10){$1'$}
               \node(2)(30,30){$2$}
               \node(2L)(30,10){$2'$}
               \node[Nmarks=r](3)(50,30){$3$}
               \node(3L)(50,10){$3'$}

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

              \end{picture}
              \begin{picture}(53,33)(-10,0)\scriptsize
               \gasset{Nw=6, Nh=6, Nmr=3}

               \put(-5,34){\normalsize (b)}
               \node[Nmarks=ir](P)(10,30){$i$}
               \node[Nmarks=r](Z)(10,10){$0$}
               \node[Nmarks=r](U)(30,30){$1$}

               \drawedge[curvedepth=4](P,Z){{\tt 0}}
               \drawedge[curvedepth=4](P,U){{\tt 1}}
               \drawedge[curvedepth=4](Z,P){{\tt \#}}
               \drawedge[curvedepth=4](U,P){{\tt \#}}

               \drawloop[loopangle=90, ELside=l](P){{\tt \#}}
               \drawloop[loopangle=270, ELside=l](Z){{\tt 0}}
               \drawloop[loopangle=90, ELside=l](U){{\tt 1}}

            \end{picture}
        \item[(c)] \ 

              \begin{picture}(53,40)\scriptsize
               \gasset{Nw=6, Nh=6, Nmr=3}
               \node[Nmarks=ir](P)(10,20){$i$}
               \node[Nmarks=r](Z)(20,30){$0$}
               \node[Nmarks=r](U)(20,10){$1$}
               \node(ZL)(40,30){$0'$}
               \node(UL)(40,10){$1'$}

               \drawedge[curvedepth=0](P,Z){{\tt 0}}
               \drawedge[curvedepth=0](P,U){{\tt 1}}
               \drawedge[curvedepth=4](Z,ZL){{\tt 1}}
               \drawedge[curvedepth=4](U,UL){{\tt 0}}
               \drawedge[curvedepth=4](ZL,Z){{\tt 0}}
               \drawedge[curvedepth=4](UL,U){{\tt 1}}

               \drawloop[loopangle=90, ELside=l](Z){{\tt 0}}
               \drawloop[loopangle=90, ELside=l](ZL){{\tt 1}}
               \drawloop[loopangle=270, ELside=l](U){{\tt 1}}
               \drawloop[loopangle=270, ELside=l](UL){{\tt 0}}

            \end{picture}
              \begin{picture}(23,40)(-10,0)\scriptsize
               \gasset{Nw=6, Nh=6, Nmr=3}

               \put(-5,34){\normalsize (d)}
               \node[Nmarks=i](Z)(10,20){$0$}
               \node[Nmarks=r](U)(30,20){$1$}
               \node(D)(50,20){$2$}

               \drawedge[curvedepth=4](Z,U){{\tt 1}}
               \drawedge[curvedepth=4](U,Z){{\tt 1}}
               \drawedge[curvedepth=4](U,D){{\tt 0}}
               \drawedge[curvedepth=4](D,U){{\tt 0}}

               \drawloop[loopangle=90, ELside=l](Z){{\tt 0}}
               \drawloop[loopangle=90, ELside=l](D){{\tt 1}}

            \end{picture}
       \end{list}
 \item Dados dois AFDs $M_1=(E_1,\Sigma,\delta_1,i_1,F_1)$ e
       $M_2=(E_2,\Sigma,\delta_2,i_2,F_2)$, explique como obter AFDs que
       reconhe\c{c}am as linguagens a seguir.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(M_1)\cup L(M_2)$.
        \item $L(M_1)-L(M_2)$.
       \end{list}
       Para cada um dos casos, sendo o AFD $(E_3,\Sigma,\delta_3,i_3,F_3)$,
       basta dizer o que s\~ao: $E_3$, $\delta_3$, $i_3$, e $F_3$.


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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $E_3=E_1\times E_2$, $\delta_3([e_1,e_2],a)=[\delta_1(e_1,a),
              \delta_2(e_2,a)]$ para todo $a\in\Sigma$, $i_3=[i_1,i_2]$,
               e $F_3=F_1\times E_2\cup E_1\times F_2$.
        \item $E_3=E_1\times E_2$, $\delta_3([e_1,e_2],a)=[\delta_1(e_1,a),
              \delta_2(e_2,a)]$ para todo $a\in\Sigma$, $i_3=[i_1,i_2]$,
               e $F_3=F_1\times (E_2-F_2)$.
       \end{list}

\end{enumerate}

\end{document}
