\documentclass[11pt, a4paper]{report}

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

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

\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 Solu\c{c}\~ao da primeira lista de exerc\'{\i}cios}

\begin{enumerate}
 \item {\footnotesize Sobre conjuntos enumer\' aveis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que o conjunto de n\'umeros inteiros \'{\i}mpares \' e enumer\'avel.
        \item Prove que o conjunto $\{{\tt 0}\}^*$ \' e enumer\'avel.
        \item Prove que o conjunto ${\cal P}(\{{\tt 0}\}^*)$ n\~ao \'e enumer\'avel.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Uma fun\c{c}\~ao bijetora dos naturais para os inteiros
              \'{\i}mpares seria $f$ tal que $f(n)=n+1$, se $n$ \'e par, e $f(n)=-n$,
              se $n$  \'e \'{\i}mpar.
        \item Uma fun\c{c}\~ao bijetora dos naturais para o conjunto $\{{\tt 0}\}^*$
              seria $g$ tal que $g(n)={\tt 0}^n$.
        \item Suponha que o conjunto ${\cal P}(\{{\tt 0}\}^*)$ seja enumer\'avel.
              Seja, ent\~ao, uma enumera\c{c}\~ao $C_0,C_1,C_2,\ldots$ dos conjuntos
              em ${\cal P}(\{{\tt 0}\}^*)$. Definamos o conjunto $X$ da seguinte
              forma: \[\mbox{para todo } n\in\mbox{\bf N}: {\tt a}^n \in X
              \mbox{ se, e somente se, } {\tt a}^n\not\in C_n\mbox{.}\]
              Se a enumera\c{c}\~ao existe mesmo, ent\~ao $X$ deve ser algum
              conjunto da seq\"u\^encia; seja, ent\~ao $X=C_k$. Segue-se que
              ${\tt a}^k \in C_k$ se, e somente se, ${\tt a}^k\not\in C_k$, o que
              \'e contradit\'orio! Conclui-se que ${\cal P}(\{{\tt 0}\}^*)$
              n\~ao \'e enumer\'avel.
       \end{list} 

 \item {\footnotesize Fa\c ca defini\c c\~oes recursivas tradicionais (sem uso de gram\'atica)
       para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^*$
        \item $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w$ n\~ao cont\'em {\tt 00} nem {\tt 11}$\}$
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{enumerate}
               \item[a)] $\lambda\in L$;
               \item[b)] se $x\in L$, ent\~ao ${\tt 0}x\in L$ e $x{\tt 1}\in L$.
              \end{enumerate}
        \item \begin{enumerate}
               \item[a)] $\lambda\in L$;
               \item[b)] se $x\in L$, ent\~ao ${\tt 0}x{\tt 1}\in L$.
              \end{enumerate}
        \item \begin{enumerate}
               \item[a)] $\lambda,{\tt 0},{\tt 1}\in L$;
               \item[b)] se $x{\tt 0}\in L$, ent\~ao $x{\tt 01}\in L$; \\
                    se $x{\tt 1}\in L$, ent\~ao $x{\tt 10}\in L$.
              \end{enumerate}
       \end{list}

 \item {\footnotesize Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$,  $A=\Sigma^5$ e $B=\{{\tt 0}\}\Sigma^*$.
       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 0}s e {\tt 1}s (fica
       impl\'{\i}cito).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cap B$.
        \item $AB$.
        \item $B-A$.
        \item $A^*$.
        \item $B^+$.
        \item $A^*\cap B^*$.
       \end{list}
       Exemplo: uma propriedade necess\'aria e suficiente para que uma palavra
       perten\c{c}a a $A-B$ \'e: come\c{c}a com {\tt 1} e tem 5 s\'{\i}mbolos.}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Come\c{c}a com {\tt 0} e tem 5 s\'{\i}mbolos.
        \item Tem pelo menos 6 s\'{\i}mbolos e o sexto \'e {\tt 0}.
        \item Come\c{c}a com {\tt 0} e n\~ao tem 5 s\'{\i}mbolos.
        \item Tem tamanho m\'ultiplo de 5.
        \item Come\c{c}a com {\tt 0}.
        \item Come\c{c}a com {\tt 0} (se n\~ao for $\lambda$) e tem tamanho m\'ultiplo de 5.
       \end{list}

 \item {\footnotesize 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 da forma ${\tt 0}^m{\tt 1}^n$, em que $m$ \'e par
              e $n$ \'e \'{\i}mpar.
        \item O conjunto das palavras em que entre cada par de {\tt 0}s
              h\'a uma subpalavra ${\tt 1}^n$, sendo $n$ par.
              Observe que antes do primeiro {\tt 0} ou ap\'os o \'ultimo
              {\tt 0} pode ocorrer um n\'umero \'{\i}mpar de {\tt 1}s, \textit{se a palavra
              tiver {\tt 0}s}.
        \item O conjunto das palavras que cont\^em {\tt 00} ou {\tt 11} ou ambas.
        \item O conjunto das palavras que cont\^em {\tt 00} ou {\tt 11}, mas n\~ao ambas.
        \item O conjunto das palavras que cont\^em {\tt 00} e {\tt 11}.
        \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}, nem {\tt 11}.
        \item O conjunto das palavras de tamanho par que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras com tamanho m\'ultiplo de 3.
        \item O conjunto das palavras nas quais o n\'umero de {\tt 1}'s \'e m\'ultiplo
              de 3.
        \item O conjunto das palavras nas quais o n\'umero de {\tt 1}'s \'e m\'ultiplo
              de 3, exceto aquelas com um n\'umero par de s\'{\i}mbolos.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 00}\}^*\{{\tt 1}\}\{{\tt 11}\}^*$.
        \item $\{{\tt 1}\}^*(\{{\tt 0}\}\{{\tt 11}\}^*)^*\{\lambda,{\tt 1}\}$.
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00},{\tt 11}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00},{\tt 11}\}\{{\tt 0},{\tt 1}\}^*-
               (\{{\tt 0},{\tt 1}\}^*\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*\cap
               \{{\tt 0},{\tt 1}\}^*\{{\tt 11}\}\{{\tt 0},{\tt 1}\}^*)$.
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*\cap
               \{{\tt 0},{\tt 1}\}^*\{{\tt 11}\}\{{\tt 0},{\tt 1}\}^*$.
        \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 11}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $(\{{\tt 0},{\tt 1}\}^2)^*-\{{\tt 0},{\tt 1}\}^*\{{\tt 00}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $(\{{\tt 0},{\tt 1}\}^3)^*$.
        \item $(\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\})^*
               \{{\tt 0}\}^*$.
        \item $(\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\})^*
               \{{\tt 0}\}^*-(\{{\tt 0},{\tt 1}\}^2)^*$.
       \end{list}

 \item {\footnotesize Identifique as linguagens que s\~ao geradas pelas gram\'aticas a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{P,Z\},\{{\tt 0},{\tt 1}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt 0}P{\tt 1} \,|\, Z$
               \item[\ ]      $Z\,\rightarrow\,{\tt 0}Z\,|\, {\tt 0}$
              \end{enumerate}

        \item $G_2=(\{P,Z,U\},\{{\tt 0},{\tt 1}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:]  $P\,\rightarrow\,{\tt 0}P{\tt 1} \,|\, Z \,|\, U$
               \item[\ ]      $Z\,\rightarrow\,{\tt 0}Z\,|\, {\tt 0}$
               \item[\ ]      $U\,\rightarrow\,U{\tt 1}\,|\, {\tt 1}$
              \end{enumerate}

        \item $G_3=(\{S,X\},\{{\tt 0},{\tt 1}\},R_3,S)$.
              \begin{enumerate}
               \item[$R_2$:] $S\,\rightarrow\,{\tt 00} S \,|\, {\tt 1}X\,|\, \lambda$
               \item[\ ]     $X\,\rightarrow\,{\tt 00} X \,|\,{\tt 1}S $
              \end{enumerate}

        \item $G_4=(\{P,X\},\{{\tt a},{\tt b},{\tt c}\},R_4,P)$.
              \begin{enumerate}
               \item[$R_4$:] $P\,\rightarrow\,{\tt a} P {\tt a} \,|\, X$
               \item[\ ]   $X\,\rightarrow\, {\tt b} X {\tt c} \,|\, X {\tt c} \,|\, \lambda$
              \end{enumerate}

        \item $G_5=(\{P,A,B,F\},\{{\tt a},{\tt b}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:] $P\,\rightarrow\,{\tt a}AP \,|\,{\tt b}BP\,|\,F$ 
               \item[\ ]  $A{\tt a}\,\rightarrow\,{\tt a}A$
               \item[\ ]  $A{\tt b}\,\rightarrow\,{\tt b}A$
               \item[\ ]  $B{\tt a}\,\rightarrow\,{\tt a}B$
               \item[\ ]  $B{\tt b}\,\rightarrow\,{\tt b}B$
               \item[\ ]  $AF\,\rightarrow\,F{\tt a}$
               \item[\ ]  $BF\,\rightarrow\,F{\tt b}$
               \item[\ ]  $F\,\rightarrow\,\lambda$
              \end{enumerate}

        \item $G_6=(\{P\},\{{\tt 0},{\tt 1}\},R_6,P)$.
              \begin{enumerate}
               \item[$R_6$:] $P\,\rightarrow\,{\tt 0} P {\tt 1}\,|\,\lambda$
               \item[\ ]     ${\tt 01}\,\rightarrow\,{\tt 10}$
              \end{enumerate}

       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G_1)=\{{\tt 0}^k{\tt 1}^n\,|\,k>n\}$.

        \item $L(G_2)=\{{\tt 0}^k{\tt 1}^n\,|\,k\not=n\}$.

        \item $L(G_3)=\{{\tt 00}\}^*(\{{\tt 1}\}\{{\tt 00}\}^*\{{\tt 1}\}\{{\tt 00}\}^*)^*$.

        \item $L(G_4)=\{{\tt a}^n{\tt b}^i{\tt c}^j{\tt a}^n\,|\,n\geq 0 \mbox{ e } i<j\}$.

        \item $L(G_5)=\{xx\,|\,x\in\{{\tt a},{\tt b}\}^*\}$.

        \item $L(G_5)=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\mbox{ em $w$, o n\'umero de {\tt 0}s
               \'e igual ao de {\tt 1}s}\}$.

       \end{list}

 \item {\footnotesize Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}\{{\tt 11}\}^*\{{\tt 0}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt \#}\}^*\,|\, \mbox{ toda seq\"u\^encia de
               {\tt 0}'s em $w$ vem entre dois {\tt \#}s}\}$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho par
              com pelo menos dois {\tt 1}s.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\not=n\}$.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\,{\tt 0} A {\tt 0}$
               \item[\ ] $A\,\rightarrow\,{\tt 11}A\,|\,\lambda$
              \end{enumerate}

        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\,{\tt 1} P\,|\, {\tt \#}P\,|\,\lambda\,|\,{\tt \#0}Z$
               \item[\ ] $Z\,\rightarrow\,{\tt 0}Z\,|\,{\tt \#0}Z\,|\,{\tt \#}P$
              \end{enumerate}

        \item \begin{enumerate}
               \item[\ ] $P_0\,\rightarrow\,{\tt 0}I_0 \,|\, {\tt 1}I_1$
               \item[\ ] $I_0\,\rightarrow\,{\tt 0}P_0 \,|\, {\tt 1}P_1$
               \item[\ ] $P_1\,\rightarrow\,{\tt 0}I_1 \,|\, {\tt 1}I_2$
               \item[\ ] $I_1\,\rightarrow\,{\tt 0}P_1 \,|\, {\tt 1}P_2$
               \item[\ ] $P_2\,\rightarrow\,{\tt 0}I_2 \,|\, {\tt 1}I_2\,|\,\lambda$
               \item[\ ] $I_2\,\rightarrow\,{\tt 0}P_2 \,|\, {\tt 1}P_2$
              \end{enumerate}

        \item \begin{enumerate}
               \item[\ ] $P\,\rightarrow\,{\tt a} P {\tt b} \,|\, A \,|\, B$
               \item[\ ] $A\,\rightarrow\,{\tt a}A\,|\,{\tt a}$
               \item[\ ] $B\,\rightarrow\,{\tt b}B\,|\,{\tt b}$
              \end{enumerate}

       \end{list}

 \item {\footnotesize Construa aut\^omatos finitos determin\'{\i}sticos (AFDs) que reconhe\c cam
       as linguagens da quest\~ao 3. Apresente apenas os diagramas de estados.}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
              
              \begin{picture}(120,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,10){}
               \node(2)(30,10){}
               \node(3)(50,10){}
               \node(4)(70,10){}
               \node(5)(90,10){}
               \node[Nmarks=r](6)(110,10){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0](2,3){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](4,5){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](5,6){{\tt 0},{\tt 1}}
              \end{picture}
        \item \ 

              \begin{picture}(140,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,10){}
               \node(2)(30,10){}
               \node(3)(50,10){}
               \node(4)(70,10){}
               \node(5)(90,10){}
               \node(6)(110,10){}
               \node[Nmarks=r](7)(130,10){}

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

               \drawloop[loopangle=0, ELside=l](7){{\tt 0},{\tt 1}}
              \end{picture}
        \item \ 

              \begin{picture}(140,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,10){}
               \node[Nmarks=r](2)(30,10){}
               \node[Nmarks=r](3)(50,10){}
               \node[Nmarks=r](4)(70,10){}
               \node[Nmarks=r](5)(90,10){}
               \node(6)(110,10){}
               \node[Nmarks=r](7)(130,10){}

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

               \drawloop[loopangle=0, ELside=l](7){{\tt 0},{\tt 1}}
              \end{picture}
        \item \ 

              \begin{picture}(140,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93,
                       ELside=r}
               \node[Nmarks=ir, iangle=180](1)(10,10){}
               \node(2)(30,10){}
               \node(3)(50,10){}
               \node(4)(70,10){}
               \node(5)(90,10){}

               \drawedge[curvedepth=0](1,2){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](2,3){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](4,5){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=-10](5,1){{\tt 0},{\tt 1}}
              \end{picture}
        \item \ 

              \begin{picture}(140,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,10){}
               \node[Nmarks=r](2)(30,10){}

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

               \drawloop[loopangle=0, ELside=l](2){{\tt 0},{\tt 1}}
              \end{picture}

        \item \ 

              \begin{picture}(140,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93,
                       ELside=r}
               \node[Nmarks=ir, iangle=180](1)(10,10){}
               \node(2)(30,10){}
               \node(3)(50,10){}
               \node(4)(70,10){}
               \node(5)(90,10){}
               \node[Nmarks=r](6)(110,10){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0](2,3){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](4,5){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](5,6){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=-10](6,2){{\tt 0},{\tt 1}}
              \end{picture}
       \end{list}

 \item {\footnotesize Construa aut\^omatos finitos determin\'{\i}sticos (AFDs) que reconhe\c cam
       as linguagens da quest\~ao 4. Apresente apenas os diagramas de estados.}
       {\em Solu\c{c}\~ao:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,30){}
               \node(2)(40,30){}
               \node[Nmarks=r](3)(10,10){}
               \node(4)(40,10){}

               \drawedge[curvedepth=4](1,2){{\tt 0}}
               \drawedge[curvedepth=4](2,1){{\tt 0}}
               \drawedge[curvedepth=0](1,3){{\tt 1}}
               \drawedge[curvedepth=4](3,4){{\tt 1}}
               \drawedge[curvedepth=4](4,3){{\tt 1}}
              \end{picture}
        \item \ 
              
              \begin{picture}(120,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,10){}
               \node[Nmarks=r](2)(40,10){}
               \node[Nmarks=r](3)(70,10){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=4](2,3){{\tt 1}}
               \drawedge[curvedepth=4](3,2){{\tt 1}}
               \drawloop[loopangle=90](1){{\tt 1}}
               \drawloop[loopangle=90](2){{\tt 0}}
              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,30){}
               \node(2)(40,30){}
               \node[Nmarks=r](3)(40,10){}
               \node(4)(10,10){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0](2,3){{\tt 0}}
               \drawedge[curvedepth=0](4,3){{\tt 1}}
               \drawedge[curvedepth=0](1,4){{\tt 1}}
               \drawedge[curvedepth=3](2,4){{\tt 1}}
               \drawedge[curvedepth=3](4,2){{\tt 0}}
               \drawloop[loopangle=0](3){{\tt 0},{\tt 1}}
              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,20){}
               \node(2)(30,30){}
               \node(3)(30,10){}
               \node[Nmarks=r](4)(50,30){}
               \node[Nmarks=r](5)(70,30){}
               \node[Nmarks=r](6)(50,10){}
               \node[Nmarks=r](7)(70,10){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,20){}
               \node(2)(30,30){}
               \node(3)(30,10){}
               \node(4)(50,30){}
               \node(5)(70,30){}
               \node(6)(50,10){}
               \node(7)(70,10){}
               \node[Nmarks=r](8)(90,20){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0](1,3){{\tt 1}}
               \drawedge[curvedepth=3](2,3){{\tt 1}}
               \drawedge[curvedepth=3](3,2){{\tt 0}}
               \drawedge[curvedepth=0](2,4){{\tt 0}}
               \drawedge[curvedepth=0](3,6){{\tt 1}}
               \drawloop[loopangle=90](4){{\tt 0}}
               \drawloop[loopangle=90](6){{\tt 1}}
               \drawedge[curvedepth=4](4,5){{\tt 1}}
               \drawedge[curvedepth=4](5,4){{\tt 0}}
               \drawedge[curvedepth=4](6,7){{\tt 0}}
               \drawedge[curvedepth=4](7,6){{\tt 1}}
               \drawedge[curvedepth=0](5,8){{\tt 1}}
               \drawedge[curvedepth=0](7,8){{\tt 0}}
               \drawloop[loopangle=0](8){{\tt 0},{\tt 1}}

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,20){}
               \node(2)(30,30){}
               \node(3)(30,10){}
               \node[Nmarks=r](4)(50,30){}
               \node[Nmarks=r](5)(70,30){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,20){}
               \node[Nmarks=r](2)(30,30){}
               \node[Nmarks=r](3)(30,10){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,30){}
               \node(2)(40,30){}
               \node(3)(10,10){}
               \node[Nmarks=r](4)(40,10){}

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

        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,20){}
               \node(2)(30,30){}
               \node(3)(30,10){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,20){}
               \node(2)(30,30){}
               \node(3)(30,10){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=7, Nh=5, Nmr=3, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](zp)(10,30){0p}
               \node(ui)(30,30){1i}
               \node(dp)(50,10){2p}
               \node[Nmarks=r](zi)(10,10){0i}
               \node(up)(30,10){1p}
               \node(di)(50,30){2i}

               \drawedge[curvedepth=0](zp,ui){{\tt 1}}
               \drawedge[ELpos=25, curvedepth=0](ui,dp){{\tt 1}}
               \drawedge[curvedepth=0](zi,up){{\tt 1}}
               \drawedge[ELpos=25, curvedepth=0, ELside=r](up,di){{\tt 1}}

               \drawedge[curvedepth=4](zp,zi){{\tt 0}}
               \drawedge[curvedepth=4](zi,zp){{\tt 0}}
               \drawedge[curvedepth=4](ui,up){{\tt 0}}
               \drawedge[curvedepth=4](up,ui){{\tt 0}}
               \drawedge[curvedepth=4](dp,di){{\tt 0}}
               \drawedge[curvedepth=4](di,dp){{\tt 0}}

               \drawedge[ELside=r, curvedepth=-6](di,zp){{\tt 1}}
               \drawedge[curvedepth=6](dp,zi){{\tt 1}}

              \end{picture}
       \end{list}

 \item {\footnotesize Construa AFDs que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ toda posi\c c\~ao par
              de $w$ cont\'em {\tt 1}}\}$.
        \item $\{{\tt 01}\}^*\{{ \tt 10}\}^*$.
        \item $(\{{\tt 1}\}\cup\{{\tt 0}\}\{{\tt 0},{\tt 1}\})\{{\tt 0},{\tt 1}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o pen\'ultimo s\'{\i}mbolo
              de $w$ \'e {\tt 1}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt 000}
                 nem {\tt 111}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ em $w$ o s\'{\i}mbolo da
               posi\c{c}\~ao $2i$ \'e diferente daquele na posi\c{c}\~ao $2i+2$
               para cada $i\geq 1\}$. Exemplos de palavras nesta linguagem: qualquer
               palavra com menos de 4 s\'{\i}mbolos, as 4 palavras da forma {\tt a0b1},
               onde a e b podem ser {\tt 0} ou {\tt 1}, as 4 palavras da forma
               {\tt a1b0} etc.
       \end{list}}

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

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
              
              \begin{picture}(120,20)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,10){}
               \node[Nmarks=r](2)(30,10){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,30){}
               \node(2)(40,30){}
               \node(3)(10,10){}
               \node[Nmarks=r](4)(40,10){}

               \drawedge[curvedepth=4](1,2){{\tt 0}}
               \drawedge[curvedepth=4](2,1){{\tt 1}}
               \drawedge[curvedepth=0](1,3){{\tt 1}}
               \drawedge[curvedepth=4](3,4){{\tt 0}}
               \drawedge[curvedepth=4](4,3){{\tt 1}}
              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](1)(10,20){}
               \node[Nmarks=r](2)(30,30){}
               \node(3)(30,10){}

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

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=7, Nh=5, Nmr=3, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](0)(10,30){00}
               \node(1)(40,30){01}
               \node[Nmarks=r](3)(40,10){11}
               \node[Nmarks=r](2)(10,10){10}

               \drawedge[curvedepth=0](0,1){{\tt 1}}
               \drawedge[curvedepth=0](1,3){{\tt 1}}
               \drawedge[curvedepth=0](3,2){{\tt 0}}
               \drawedge[curvedepth=0](2,0){{\tt 0}}
               \drawedge[curvedepth=3](1,2){{\tt 0}}
               \drawedge[curvedepth=3](2,1){{\tt 1}}
               \drawloop[loopangle=90](0){{\tt 0}}
               \drawloop[loopangle=0](3){{\tt 1}}
              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](1)(10,20){}
               \node[Nmarks=r](2)(30,30){}
               \node[Nmarks=r](3)(30,10){}
               \node[Nmarks=r](4)(50,30){}
               \node[Nmarks=r](5)(50,10){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
               \drawedge[curvedepth=3](3,2){{\tt 0}}
               \drawedge[curvedepth=3](2,3){{\tt 1}}
               \drawedge[curvedepth=0](2,4){{\tt 0}}
               \drawedge[curvedepth=0,ELside=r](3,5){{\tt 1}}
               \drawedge[ELpos=25, ELside=r, curvedepth=0](5,2){{\tt 0}}
               \drawedge[ELpos=25, curvedepth=0](4,3){{\tt 1}}

              \end{picture}
        \item \ 
              
              \begin{picture}(120,40)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](0)(10,20){}
               \node[Nmarks=ir, iangle=180](1)(30,20){}
               \node[Nmarks=r](2)(50,30){}
               \node[Nmarks=r](3)(50,10){}
               \node[Nmarks=r](4)(40,20){}
               \node[Nmarks=r](5)(60,20){}

               \drawedge[curvedepth=0](0,1){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=5](1,2){{\tt 0}}
               \drawedge[curvedepth=-5, ELside=r](1,3){{\tt 1}}
               \drawedge[curvedepth=0](2,5){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](5,3){{\tt 1}}
               \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=0](4,2){{\tt 0}}

              \end{picture}
       \end{list}


 \item {\footnotesize Fa\c ca AFD's que reconhe\c cam: $X=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|$ \'e
       par$\}$. e $Y=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$
       n\~ao cont\'em {\tt 11}$\}$. Bastam apenas os diagramas
       de estados. Em seguida, obtenha o produto dos dois AFD's e explicite
       que estados finais ele deve ter para reconhecer:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X\cap Y$.
        \item $X\cup Y$.
        \item $X-Y$.
       \end{list}}

       {\em Solu\c{c}\~ao:}
              
              \begin{picture}(60,30)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](p)(10,10){p}
               \node(i)(30,10){i}

               \drawedge[curvedepth=3](p,i){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=3](i,p){{\tt 0},{\tt 1}}

               \put(0,25){AFD para $X$:}
              \end{picture}
              \begin{picture}(120,30)
               \gasset{Nw=5, Nh=5, Nmr=2.5, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=ir, iangle=180](0)(10,10){0}
               \node[Nmarks=r](1)(30,10){1}
               \node(2)(50,10){2}

               \drawedge[curvedepth=3](0,1){{\tt 1}}
               \drawedge[curvedepth=3](1,0){{\tt 0}}
               \drawedge[curvedepth=0](1,2){{\tt 1}}
               \drawloop[loopangle=90](0){{\tt 0}}
               \drawloop[loopangle=90](2){{\tt 0},{\tt 1}}
               \put(0,25){AFD para $Y$:}

              \end{picture}

              Produto:

              \begin{picture}(120,40)
               \gasset{Nw=7, Nh=5, Nmr=3, fillcolor=Gray, fillgray=0.93}
               \node[Nmarks=i, iangle=180](p0)(10,30){p0}
               \node(i1)(30,30){i1}
               \node(p2)(50,30){p2}
               \node(i0)(10,10){i0}
               \node(p1)(30,10){p1}
               \node(i2)(50,10){i2}

               \drawedge[curvedepth=4](p0,i1){{\tt 1}}
               \drawedge[curvedepth=4](i1,p0){{\tt 0}}
               \drawedge[curvedepth=0](i1,p2){{\tt 1}}
               \drawedge[curvedepth=4](p2,i2){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=4](i2,p2){{\tt 0},{\tt 1}}

               \drawedge[curvedepth=4](p0,i0){{\tt 0}}
               \drawedge[curvedepth=4](i0,p0){{\tt 0}}
               \drawedge[curvedepth=4](i0,p1){{\tt 1}}
               \drawedge[curvedepth=4](p1,i0){{\tt 0}}
               \drawedge[curvedepth=0](p1,i2){{\tt 1}}

              \end{picture}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X\cap Y$: $F=\{\mbox{p0},\mbox{p1}\}$.
        \item $X\cup Y$: $F=\{\mbox{p0},\mbox{p1},\mbox{p2},\mbox{i0},\mbox{i1}\}$.
        \item $X-Y$: $F=\{\mbox{p2}\}$.
       \end{list}
         
\end{enumerate}

\end{document}
