\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Primeira Lista de Exercícios}/Solução do professor \hfill Data de entrega: 19/9/2017 \hfill Valor: 10 pontos

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Uma versão do \emph{problema da parada}, problema este a ser abordado no Capítulo 5, é: dado um programa (sem
       entrada), determinar se ele para. Lá no Capítulo 5 será visto que não existe algoritmo que, recebendo como
			 entrada um (texto de) programa qualquer em Java (ou em outra linguagem de programação), determine se ele para ou
			 não. Em outras palavras, o problema da parada não é computável. Sabendo disto, argumente que o problema ``dado um 
			 programa qualquer em Java, determinar se ele emitirá algum sinal sonoro'', também não é computável.}
			
			\emph{Solução}: Considere que a emissão de um sinal sonoro se dê via um certo comando \textsf{S} em Java (que comando é esse é
       irrelevante), de tal forma que um programa só possa emitir um sinal sonoro se ele contém uma ou mais ocorrências de
			 \textsf{S}. Ora, antes de uma ocorrência de \textsf{S}, pode vir \textsf{qualquer sequência de comandos}. Como determinar
			 se a execução dessa sequência de comandos para, de forma que \textsf{S} seja atingida em seguida?
			 Impossível, pois o  problema da parada não é computável!

 \item {\footnotesize Seja $\Sigma=\{{\tt 0},{\tt 1},\mbox{\tt \#}\}$. Sejam $k$ e $n$ números naturais tais que $k\leq n$.
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item Quantas palavras há na linguagem $\Sigma^k$?
        \item Quantas palavras há na linguagem $(\Sigma\cup\{\lambda\})^k$?
        \item Quantas palavras de $n$ símbolos contêm exatamente $k$ ocorrências de {\tt \#}?
        \item Quantas palavras de $n$ símbolos contêm no máximo $k$ ocorrências de {\tt \#}?
       \end{list}}

			\emph{Solução}:
			 \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada símbolo da palavra pode ser {\tt 0}, {\tt 1} ou {\tt \#} (3 opções). Logo, existem $3^k$
              palavras de $k$ símbolos.
        \item Número de palavras de zero a $k$ símbolos: $\sum_{i=0}^{k}3^i=(3^{i+1}-1)/2$.
        \item Número de posicionamentos para os $k$ {\tt \#}s: $C(n,k)$; número de sequências dos símbolos
              restantes ({\tt 0} e {\tt 1}) nas posições restantes: $2^{n-k}$. A resposta é, então, $C(n,k).2^{n-k}$.
        \item Número de palavras com zero a $k$ ocorrências de {\tt \#}: $\sum_{i=0}^{k}C(n,i).2^{n-i}$.
       \end{list}

 \item {\footnotesize Seja $\Sigma$ um alfabeto. Prove que se $x,y,w\in\Sigma^*$ e $xw=yw$, então $x=y$.}

			\emph{Solução}: Por indução sobre $|w|$. Para $w=\lambda$, se $x\lambda=y\lambda$, segue-se trivialmente que $x=y$. Seja $n\geq 0$, e
       suponha, como hipótese de indução, que para todo $w$ tal que $|w|=n$, se $xw=yw$, então $x=y$. Seja $w$ tal que $|w|=n+1$.
			 Segue-se que $w=za$, em que $z\in\Sigma^*$ e $a\in\Sigma$. Suponha que $x(za)=y(za)$. Pela associatividade da concatenação,
			 $(xz)a=(yz)a$. Para que isso seja verdade, os prefixos $xz$ e $yz$ devem ser idênticos. Neste caso, pela hipótese de
			 indução, $x=y$. Portanto, se $xw=yw$ para $|w|=n+1$, então $x=y$.

 \item {\footnotesize Sejam $\Sigma=\{\tt{0},{\tt 1}\}$, $A=\Sigma^*\{\tt{0}\}$ e $B=\{{\tt 1}\}\Sigma^*$. Descreva, em português, as
       linguagens a seguir. Não é necessário dizer que as palavras são de {\tt 0}s e {\tt 1}s. Por exemplo, $A$ é o ``conjunto
			 das palavras que terminam com {\tt 0}''.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $A\cup B$;
        \item $A\cap B$;
        \item $A-B$;
        \item $B-A$;
        \item $\overline{A}$;
        \item $AB$;
        \item $BA$.
       \end{list}}

			\emph{Solução}: 
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $A\cup B$: conjunto das palavras que começam com {\tt 1} ou terminam com {\tt 0}.
        \item $A\cap B$: conjunto das palavras que começam com {\tt 1} e terminam com {\tt 0}.
        \item $A-B$: conjunto das palavras que começam e terminam com {\tt 0}.
        \item $B-A$: conjunto das palavras que começam e terminam com {\tt 1}.
        \item $\overline{A}$: conjunto das palavras que não terminam com {\tt 0}.
        \item $AB$: conjunto das palavras que contêm {\tt 01}.
        \item $BA$: conjunto das palavras que começam com {\tt 1} e terminam com {\tt 0}.
       \end{list}

 \item {\footnotesize Sejam $A=\{\lambda,{\tt a}\}$ e $B=\{{\tt a},{\tt b}\}$. Determine $A^nB$, $AB^n$ e $A^nB^n$. Quantos elementos
       tem cada um desses conjuntos?}

			\emph{Solução}: $A^nB=\{{\tt a}^ks\,|\, 0\leq k\leq n \mbox{ e } s\in\{{\tt a},{\tt b}\}\}$ e $|A^nB|=2(n+1)$;
       $AB^n=\{sy\,|\, s\in\{\lambda,{\tt a}\}, y\in\{{\tt a},{\tt b}\}^* \mbox{ e } |y|=n\}$ e $|AB^n|=2^{n+1}$;
       $A^nB^n=\{{\tt a}^ky\,|\, 0\leq k\leq n, y\in\{{\tt a},{\tt b}\}^* \mbox{ e } |y|=n\}$ e $|A^nB^n|=(n+1)2^{n}$.


 \item {\footnotesize Descreva, em português, as seguintes linguagens sobre o alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}$;
			  \item $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\cup\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}$;
			  \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 01}\}\{{\tt 11}\}$;
			  \item $\{{\tt 01},{\tt 1}\}^*$.
			  \item $\{{\tt 1},\lambda\}(\{{\tt 0}\}\{{\tt 0}\}^*\{{\tt 1}\})^*\{{\tt 0}\}^*$;
			  \item $\{{\tt 0}\}^*\{{\tt 1}\}(\{{\tt 0}\}\cup\{{\tt 1}\}\{{\tt 0}\}^*\{{\tt 1}\})^*$.
       \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Conjunto das palavras cujo penúltimo símbolo é {\tt 1}.
        \item Conjunto das palavras que começam com {\tt 0} ou terminam com {\tt 1}.
        \item Conjunto das palavras que terminam com {\tt 0} imediatamente seguido de um número ímpar de {\tt 1}s.
        \item Conjunto das palavras em que todo {\tt 0} (caso haja algum) é seguido de {\tt 1}.
        \item Conjunto das palavras sem {\tt 1}s consecutivos.
        \item Conjunto das palavras com um número ímpar de {\tt 1}s.
       \end{list}

 \item {\footnotesize Seja $\Sigma$ o conjunto de todas as 26 letras do alfabeto e $C$ o conjunto das 21 consoantes. Seja $D$ o conjunto
       de todas as palavras de um dicionário da lingua portuguesa, e, para cada letra $l\in\Sigma$, seja
			 $P_l=\{w\in D\,|\, w \mbox{ contém a letra } l\}$. A partir de tais conjuntos, usando operações sobre conjuntos,
			 concatenações e fechos de Kleene, descreva o conjunto das palavras:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item que contêm pelo menos uma das letras A, B ou C;
			  \item que contêm as letras A e B, mas não C;
			  \item que não contêm A nem B;
			  \item que começam com a letra A;
			  \item que começam com a letra A e contêm pelo menos uma consoante;
			  \item que contêm a subpalavra RR.
			 \end{list}}

       \emph{Solução}: \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $P_{\mbox{A}}\cup P_{\mbox{B}}\cup P_{\mbox{C}}$;
			  \item $(P_{\mbox{A}}\cap P_{\mbox{B}})-P_{\mbox{C}}$;
			  \item $D-(P_{\mbox{A}}\cup P_{\mbox{B}})$;
			  \item $(\{\mbox{A}\}\Sigma^*)\cap D$;
			  \item $(\{\mbox{A}\}\Sigma^*C\Sigma^*)\cap D$;
			  \item $(\Sigma^*\{\mbox{RR}\}\Sigma^*)\cap D$.
			 \end{list}

 \item {\footnotesize Sejam $A$, $B$ e $C$ linguagens sobre um alfabeto $\Sigma$. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $A(B\cup C)=(AB)\cup(AC)$;
        \item nem sempre $A(B\cap C)=(AB)\cap(AC)$.
       \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $A(B\cup C)\subseteq (AB)\cup(AC)$

              Seja $w\in\Sigma^*$ tal que $w\in A(B\cup C)$. Então existem $x$ e $y$
              tais que $w=xy$, $x\in A$ e $y\in B\cup C$. No caso em que $y\in B$,
              segue-se que $xy\in AB$ e no caso em que $y\in C$, segue-se que
              $xy\in AC$. Logo, $xy=w\in (AB)\cup(AC)$.

              $(AB)\cup(AC)\subseteq A(B\cup C)$

              Seja $w\in\Sigma^*$ tal que $w\in (AB)\cup (AC)$. Então $w\in AB$ ou
              $w\in AC$. No primeiro caso, existem $x$ e $y$
              tais que $w=xy$, $x\in A$ e $y\in B$. Como $y\in B\cup D$ para qualquer
              linguagem $D$, segue-se que $xy=w\in A(B\cup C)$.  No caso em que $w\in AC$,
              existem $x$ e $y$ tais que $w=xy$, $x\in A$ e $y\in C$. Como $y\in D\cup C$
              para qualquer linguagem $D$, segue-se que $xy=w\in A(B\cup C)$. Conclui-se,
              portanto, que $w\in A(B\cup C)$.
        \item Contra-exemplo: $A=\{\lambda,a\}$, $B=\{b\}$, $C=\{ab\}$.
       \end{list}

 \item {\footnotesize Prove que não existe $x\in\{{\tt 0},{\tt 1}\}^*$ tal que ${\tt 0}x=x{\tt 1}$.}

       \emph{Solução}: Será mostrado que para todo $x\in\{{\tt 0},{\tt 1}\}^*$ ${\tt 0}x\not=x{\tt 1}$ por indução sobre $|x|$.
	     Para $x=\lambda$, tem-se: ${\tt 0}\lambda={\tt 0}\not={\tt 1}=\lambda{\tt 1}$. Seja $n\geq 0$ e suponha, como
	     hipótese de indução, que ${\tt 0}x\not=x{\tt 1}$ para qualquer $x$ tal que $|x|=n$. Dada uma palavra qualquer
			 $w$ tal que $|w|=n+1$, tem-se que existe um símbolo $s\in\{{\tt 0},{\tt 1}\}$ tal que $w=xs$ e $|x|=n$.
			 Dois casos: \\
			 \textit{Caso 1}: $s={\tt 0}$. Tem-se: ${\tt 0}w={\tt 0}(x{\tt 0})$. Mas ${\tt 0}x{\tt 0}\not=x{\tt 01}$, pois
			 diferem no último símbolo. Logo, ${\tt 0}(x{\tt 0})\not=(x{\tt 0}){\tt 1}$ e, portanto, ${\tt 0}w\not=w{\tt 1}$. \\
			 \textit{Caso 2}: $s={\tt 1}$. Tem-se: ${\tt 0}w={\tt 0}(x{\tt 1})=({\tt 0}x){\tt 1}$. Pela hipótese de indução,
			 ${\tt 0}x\not=x{\tt 1}$ e, portanto, $({\tt 0}x){\tt 1}\not=(x{\tt 1}){\tt 1}$. Como $(x{\tt 1}){\tt 1}=w{\tt 1}$,
			 segue-se que ${\tt 0}w\not=w{\tt 1}$.


 \item {\footnotesize Seja a gramática $G=(\{A,B\},\{{\tt a},{\tt b}\},R,A)$ em que $R$ é cons\-ti\-tuí\-do pelas quatro regras:
       \begin{enumerate}
        \item[\ \ \ ] $A\rightarrow {\tt a} A \,|\, B$
        \item[\ \ \ ] $B\rightarrow {\tt b} B \,|\, \lambda$
      \end{enumerate}
      Apresente um esquema de derivação que mostre como derivar qualquer palavra de $L(G)$. Expresse o que é $L(G)$ de forma
			bem concisa.}

       \emph{Solução}: \begin{tabbing}
        xxx\= $A$ \=$\stackrel{k}{\Rightarrow} {\tt a}^n{\tt b}^kB$ \ \ \=  \kill
           \> $A$\>$\stackrel{n}{\Rightarrow} {\tt a}^nA$          \>(regra $A\rightarrow {\tt a}A$ $n$ vezes, $n\geq 0$) \\
           \>    \>$\Rightarrow {\tt a}^nB$                        \>(regra $A\rightarrow B$) \\
           \>    \>$\stackrel{k}{\Rightarrow} {\tt a}^n{\tt b}^kB$ \>(regra $B\rightarrow {\tt b}B$ $k$ vezes, $k\geq 0$) \\
           \>    \>$\Rightarrow {\tt a}^n{\tt b}^k$                \>(regra $B\rightarrow \lambda$)
       \end{tabbing}
       $L(G)=\{{\tt a}\}^*\{{\tt b}\}^*$.

 \item {\footnotesize Construa gramáticas para as seguintes linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\{11\}$;
			  \item $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$;
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o número de {\tt a}s em $w$ é par}\}$;
        \item $\{{\tt a}^n{\tt b}^n\,|\, n\in{\bf N}\}$;
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w=w^R\}$.
       \end{list}
       Para as duas últimas, determine o número de passos para gerar uma palavra de $n$ símbolos.}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
         \item \begin{enumerate}
                \item[\ ] $P \,\rightarrow\, {\tt 0}X {\tt 11}$
                \item[\ ] $X \,\rightarrow\, {\tt 0}X \,|\, {\tt 1}X \,|\, \lambda$
               \end{enumerate}
         \item \begin{enumerate}
                \item[\ ] $P \,\rightarrow\, AXA$
                \item[\ ] $A \,\rightarrow\, {\tt 0} \,|\, \lambda$
                \item[\ ] $X \,\rightarrow\, {\tt 11}X \,|\, \lambda$
               \end{enumerate}
         \item \begin{enumerate}
                \item[\ ] $P \,\rightarrow\, {\tt a}I \,|\, {\tt b}P \,|\, \lambda$
                \item[\ ] $I \,\rightarrow\, {\tt a}P \,|\, {\tt b}I$
               \end{enumerate}

         \item \begin{enumerate}
                \item[\ ] $X \,\rightarrow\, {\tt a}X{\tt b} \,|\, \lambda$
               \end{enumerate}

         \item \begin{enumerate}
                \item[\ ] $X \,\rightarrow\, {\tt a}X{\tt a} \,|\, {\tt b}X{\tt b}
                           \,|\, \lambda \,|\, {\tt a} \,|\, {\tt b}$
               \end{enumerate}
        \end{list}

 \item {\footnotesize Diga que linguagens são geradas pelas gramáticas:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $G_1=(\{A\},\{{\tt 0},{\tt 1}\},R_1,A)$, sendo $R_1$ constituído de:
              \begin{quote}
			         $A\,\rightarrow\, {\tt 0} A \,|\, A{\tt 0} \,|\, {\tt 1}$
		      	  \end{quote}
        \item $G_2=(\{B\},\{{\tt 0},{\tt 1}\},R_2,B)$, sendo $R_2$ constituído de:
              \begin{quote}
			         $B\,\rightarrow\, {\tt 0}B{\tt 00} \,|\, {\tt 1}$
			        \end{quote}
        \item $G_3=(\{S,A,B\},\{{\tt 0},{\tt 1}\},R_3,S)$, sendo $R_3$ constituído de:
              \begin{quote}
			         $S\,\rightarrow\, AA \,|\, B$ \\
			         $A\,\rightarrow\, {\tt 0} A \,|\, A{\tt 0} \,|\, {\tt 1}$\\
			         $B\,\rightarrow\, {\tt 0}B{\tt 00} \,|\, {\tt 1}$
			        \end{quote}
       \end{list}}

       \emph{Solução}: \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{0\}^*\{1\}\{0\}^*$
        \item $\{0^n10^{2n}\,|\, n\geq 0\}$
        \item $\{0\}^*\{1\}\{0\}^*\{1\}\{0\}^*\cup\{0^n1^{2n}\,|\, n\geq 0\}$
       \end{list}

 \item {\footnotesize Identifique as linguagens geradas pelas gramáticas:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $G_1=(\{P,X\},\{{\tt a},{\tt b}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt a} X \,|\, {\tt b} P \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \end{enumerate}

        \item $G_2=(\{P,A\},\{{\tt a},{\tt b}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:]  $P\,\rightarrow\,{\tt a}P{\tt a}\,|\, A$
               \item[\ ]      $A\,\rightarrow\,{\tt b}A \,|\, {\tt b}$
              \end{enumerate}

        \item $G_3=(\{A,B\},\{{\tt 0},{\tt 1}\},R_3,A)$.
              \begin{enumerate}
               \item[$R_3$:]  $A\,\rightarrow\,{\tt 0}A\,|\, B$
               \item[\ ]      $B\,\rightarrow\,B{\tt 1} \,|\, {\tt 01}$
              \end{enumerate}

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

        \item $G_5=(\{P,X\},\{{\tt a},{\tt b}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:]  $P\,\rightarrow\,{\tt aa} P \,|\, X {\tt b} \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \end{enumerate}
       \end{list}}

       \emph{Solução}: \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G_1)=\{{\tt aa},{\tt b}\}^*$.
        \item $L(G_2)=\{{\tt a}^n{\tt b}^k{\tt a}^n\,|\, n\geq 0 \mbox{ e } k\geq 1\}$.
				\item $L(G_3)=\{{\tt 0}\}^*\{{\tt 01}\}\{{\tt 1}\}^*$.
        \item $L(G_4)=\{{\tt a}^n{\tt b}^k\,|\, n\geq k\}$.
        \item $L(G_5)=\{{\tt a}^{k+2n}{\tt b}^k\,|\, n,k\geq 0\}$.
       \end{list}

 \item {\footnotesize Sejam os PDs:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item determinar se um número natural $n$, para $1\leq n\leq 200$, é um número primo;
        \item dada uma equação do segundo grau de coeficientes $a$, $b$ e $c$, determinar se suas raízes são ambas reais,
				      se cada um dos coeficientes é um número natural entre 10 e 20 (exclusive);
        \item dada uma equação do segundo grau de coeficientes $a$, $b$ e $c$, determinar se suas raízes são ambas reais,
				      se seus coeficientes podem ser números reais quaisquer;
        \item dada uma fórmula da lógica de predicados, determinar se ela é válida;
        \item dados dois conjuntos finitos, determinar se eles são disjuntos;
        \item determinar se uma árvore $A$ tem altura menor ou igual a $n$;
        \item determinar se uma palavra $w$ é palíndromo, se $w\in\{{\tt 0},{\tt 1}\}^*$.
       \end{list}
       Dizer quantos parâmetros e quantas instâncias tem cada um.}

       \emph{Solução}: \begin{list}{\bf\alph{conta})}{\usecounter{conta}}
        \item 1 parâmetro, 200 instâncias;
        \item 3 parâmetros, $9^3=729$ instâncias.
        \item 3 parãmetros, conjunto infinito de instâncias;
        \item 1 parâmetro, conjunto infinito de instâncias.
        \item 2 parâmetros, conjunto infinito de instâncias.
        \item 2 parâmetros, conjunto infinito de instâncias;
        \item 1 parâmetro, conjunto infinito de instâncias.
       \end{list}

 \item {\footnotesize Diz-se que um PD $P$ é \emph{redutível} a um PD $Q$, se existe um algoritmo $\mathcal{R}$ que, recebendo $x$ como entrada,
       produz um resultado $y$ tal que a resposta a $P$ para a entrada $x$ é idêntica ou complementar\footnote{\noindent \ A
			 resposta complementar a \emph{sim} é \emph{não}, e a \emph{não} é \emph{sim}.} à resposta a $Q$ para a entrada $y$,
			 qualquer que seja a entrada $x$. Diz-se, com isso, que o algoritmo $\mathcal{R}$ pode ser usado para \emph{reduzir} o
			 problema $P$ ao problema $Q$.

       Seja $D$ um PD decidível e $I$ um PD indecidível. O que se pode dizer de um PD $X$, com relação à sua decidibilidade, se:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $D$ é redutível a $X$?
        \item $X$ é redutível a $D$?
        \item $I$ é redutível a $X$?
        \item $X$ é redutível a $I$?
       \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Nada se pode dizer. $X$ pode ser decidível ou não.
        \item $X$ é decidível: para qualquer entrada $x$ (para $X$), o algoritmo ${\cal R}$
              produz uma saída $y$, a partir da qual um algoritmo para $D$ obtém
              a resposta para $x$.
        \item $X$ é indecidível: pelo item anteriror, se $X$ fosse decidível, $I$ seria decidível.
        \item Nada se pode dizer. $X$ pode ser decidível ou não.
       \end{list}

 \item {\footnotesize Faça um diagrama de estados, similar àquele do quebra-cabeça LCR, para o problema dos missionários 
				 e canibais:
         \begin{quote}
           Três missionários e três canibais devem atravessar um rio. Para isso, dispõem de uma canoa que pode transportar
					 no máximo duas pessoas de cada vez. Durante a travessia, se o número de canibais for maior que o de missionários
					 em qualquer uma das margens, os canibais comem os missionários. Determinar um plano para travessia em que nenhum
					 missionário seja devorado.
         \end{quote}}

       \emph{Solução}: Cada estado será uma palavra $mcl$, onde $m\in\{0,1,2,3\}$ é o número de missionários do lado esquerdo, $c\in\{0,1,2,3\}$
       é o número de canibais do lado esquerdo, e $l\in\{o,d\}$ é o lado em que está a canoa ($o$: origem; $d$: destino). Cada
			 transição  terá um um rótulo da forma $ij$, onde $1\leq i+j\leq 2$, sendo que $i$ é o número de missionários e $j$ é o
			 número de canibais viajando na canoa. O diagrama de estados está mostrado na figura a seguir. Nele, cada aresta
			 $(v_1,r,v_2)$ representa duas transições: de $v_1$ para $v_2$ e de $v_2$ para $v_1$, ambas com rótulo $r$.

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

               \node[Nmarks=i](33o)(20,50){$33o$}
               \node(22d)(40,60){$22d$}
               \node(31d)(40,40){$31d$}
               \node(32o)(60,50){$32o$}
               \node(32d)(20,35){$32d$}

               \node(30d)(80,50){$30d$}
               \node(31o)(100,50){$31o$}
               \node(11d)(120,50){$11d$}

               \node(22o)(135,35){$22o$}

               \node(02d)(120,20){$02d$}
               \node(03o)(100,20){$03o$}
               \node(01d)(80,20){$01d$}
               \node(11o)(60,30){$11o$}
               \node(02o)(60,10){$02o$}

               \node[Nmarks=r](00d)(40,20){$00d$}
               \node(01o)(20,20){$01o$}

               \drawedge[curvedepth=0, AHnb=0, ELside=r](33o,32d){{\tt 01}}
               \drawedge[curvedepth=0, AHnb=0](33o,22d){{\tt 11}}
               \drawedge[curvedepth=0, AHnb=0, ELside=r](33o,31d){{\tt 02}}
               \drawedge[curvedepth=0, AHnb=0](22d,32o){{\tt 10}}
               \drawedge[curvedepth=0, AHnb=0, ELside=r](31d,32o){{\tt 01}}

               \drawedge[curvedepth=0, AHnb=0](32o,30d){{\tt 02}}
               \drawedge[curvedepth=0, AHnb=0](30d,31o){{\tt 01}}
               \drawedge[curvedepth=0, AHnb=0](31o,11d){{\tt 20}}

               \drawedge[curvedepth=0, AHnb=0](11d,22o){{\tt 11}}

               \drawedge[curvedepth=0, AHnb=0](22o,02d){{\tt 20}}
               \drawedge[curvedepth=0, AHnb=0](02d,03o){{\tt 01}}
               \drawedge[curvedepth=0, AHnb=0](03o,01d){{\tt 02}}
               \drawedge[curvedepth=0, AHnb=0](11o,01d){{\tt 10}}
               \drawedge[curvedepth=0, AHnb=0](02o,01d){{\tt 01}}

               \drawedge[curvedepth=0, AHnb=0](00d,11o){{\tt 11}}
               \drawedge[curvedepth=0, AHnb=0](00d,02o){{\tt 02}}
               \drawedge[curvedepth=0, AHnb=0](01o,00d){{\tt 01}}
            \end{picture}
           } \\


 \item {\footnotesize Faça um diagrama de estados, usando a ideia apresentada na Seção 2.1.2, para uma máquina que determine se uma 
       sequência ternária (com dígitos 0, 1 e 2) é divisível por 4.}

       \emph{Solução}:\

 \mbox{\setlength{\unitlength}{1mm}
  \begin{picture}(80,40)(-15,0)\small
   \gasset{Nw=5, Nh=5, Nmr=5, loopdiam=6, ELdist=0.5, fillgray=0.9}

   \node[Nmarks=i](i)(5,20){i}
   \node[Nmarks=r](0)(20,20){0}
   \node(1)(35,30){1}
   \node(2)(35,10){2}
   \node(3)(50,20){3}

   \drawedge[curvedepth=0](i,0){0}
   \drawedge[curvedepth=5](i,1){1}
   \drawedge[curvedepth=-5,ELside=r](i,2){2}
   \drawedge[curvedepth=2](0,1){1}
   \drawloop[loopangle=270](0){0}
   \drawedge[curvedepth=2](0,1){1}
   \drawedge[curvedepth=2](0,2){2}
   \drawloop[loopangle=90](1){2}
   \drawedge[curvedepth=2](1,0){1}
   \drawedge[curvedepth=2](1,3){0}
   \drawloop[loopangle=270](2){0}
   \drawedge[curvedepth=2](2,3){1}
   \drawedge[curvedepth=2](2,0){2}
   \drawloop[loopangle=0](3){2}
   \drawedge[curvedepth=2](3,1){0}
   \drawedge[curvedepth=2](3,2){1}
  \end{picture}
 }


 \item {\footnotesize Construa um diagrama de estados para uma máquina de Mealy que, dada uma sequência de moedas de 25 e 50 centavos e de
       1 real, forneça uma lata de refrigerante quando a sequência totalizar 1 real ou mais. A cada moeda inserida deverá
			 corresponder uma de duas saídas: {\tt 0}, se uma lata não pode ser (ainda) liberada, ou {\tt 1}, se uma lata deve
			 ser liberada. Um exemplo de entrada e saída correspondente:
       \begin{quote}
			 \begin{tabular}{rcccccccc}
				entrada:  & 50& 25& 50& 100& 25& 50& 25& $\cdots$ \\
				  saída:  & 0& 0& 1& 1& 0& 1& 0& $\cdots$
			 \end{tabular}
       \end{quote}}


       \emph{Solução}:\

 \mbox{\setlength{\unitlength}{1mm}
  \begin{picture}(80,40)\small
   \gasset{Nw=6, Nh=6, Nmr=4, loopdiam=6, ELdist=0.5, fillgray=0.9}

   \node[Nmarks=i](0)(20,30){0}
   \node(50)(20,10){50}
   \node(25)(60,30){25}
   \node(75)(60,10){75}

   \drawedge[curvedepth=0](0,25){25/0}
   \drawedge[curvedepth=3](0,50){50/0}
   \drawloop[loopangle=90](0){100/1}
   \drawedge[curvedepth=0,ELpos=60](25,50){25/0}
   \drawedge[curvedepth=3](25,75){50/0}
   \drawloop[loopangle=0](25){100/1}
   \drawedge[curvedepth=0,ELside=r](50,75){25/0}
   \drawedge[curvedepth=3](50,0){50/1}
   \drawloop[loopangle=180](50){100/1}
   \drawedge[curvedepth=0, ELside=r,ELpos=60](75,0){25/1}
   \drawedge[curvedepth=3](75,25){50/1}
   \drawloop[loopangle=270](75){100/1}
  \end{picture}
 }

 \item {\footnotesize Construa AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{\lambda,{\tt 0}\}^2$;
        \item $\{\lambda,{\tt 0},{\tt 1}\}^2\{{\tt 1}\}^*$;
        \item $\{{011},{1}\}^*$.
        \item $\{{\tt 0},{\tt 1}\}^*-\{{\tt 0},{\tt 1},{\tt 00},{\tt 11}\}$;
        \item $\{{\tt 01}\}^*\{{\tt 10}\}^*$;
        \item $\{{00},{1}\}^*\{{0},{11}\}^*$.
       \end{list}}
			
       \emph{Solução}:\begin{list}{\alph{conta})}{\usecounter{conta}}
        \item \

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

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

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

        \item \

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

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

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

       \item \

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

               \node[Nmarks=ir](2)(20,5){2}
               \node(0)(40,5){0}
               \node(1)(60,5){1}

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

       \item \  

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=ir](i)(20,12){}
               \node(1)(35,19){}
               \node(2)(35,5){}
               \node(3)(50,12){}
               \node[Nmarks=r](4)(65,12){}

               \drawedge[curvedepth=0](i,1){{\tt 0}}
               \drawedge[curvedepth=0, ELside=r](i,2){{\tt 1}}
               \drawedge[curvedepth=0](1,3){{\tt 0}}
               \drawedge[curvedepth=0,ELside=r](2,3){{\tt 1}}
               \drawedge[curvedepth=6](1,4){{\tt 1}}
               \drawedge[curvedepth=0](3,4){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=-6,ELside=r](2,4){{\tt 0}}
               \drawloop[loopangle=0](4){{\tt 0},{\tt 1}}
              \end{picture}
             } \\

       \item \

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

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

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

              \end{picture}
             } \\

       \item \ 
			
			  \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,10)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=ir](A)(20,5){}
          \node[Nmarks=r](B)(40,5){}
          \node(C)(60,5){}
          \node[Nmarks=r](D)(80,5){D}

          \drawedge[curvedepth=3](A,B){{\tt 0}}
          \drawloop[loopangle=90](A){{\tt 1}}
          \drawedge[curvedepth=3](B,A){{\tt 0}}
          \drawedge[curvedepth=0](B,C){{\tt 1}}
          \drawedge[curvedepth=3](C,D){{\tt 1}}
          \drawedge[curvedepth=3](D,C){{\tt 1}}
          \drawloop[loopangle=90](D){{\tt 0}}
         \end{picture}
        }
      \end{list}


 \item {\footnotesize Faça AFDs que reconheçam as linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{{\tt a}^m{\tt b}^n\,|\, m+n\geq 2\}$;
        \item $\{{\tt a}^m{\tt b}^n\,|\, m+n \mbox{ é par}\}$;
        \item $\{{\tt a}^m{\tt b}^n\,|\, m+n \mbox{ mod } 3 = 0\}$;
        \item $\{{\tt a}^n{\tt b}^n\,|\, n \leq 3\}$.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\leq 2 \mbox{ e } n \geq m+2\}$.
       \end{list}}

       \emph{Solução}:\begin{list}{\alph{conta})}{\usecounter{conta}}
        \item \

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

               \node[Nmarks=i](i)(20,15){}
               \node(1)(35,25){}
               \node[Nmarks=r](2)(55,25){}
               \node(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=0](1,4){\tt b}
							 \drawloop[loopangle=0](2){\tt a}
               \drawedge[curvedepth=0](2,4){\tt b}
               \drawedge[curvedepth=0](3,4){\tt b}
							 \drawloop[loopangle=0](4){\tt b}
              \end{picture}
             } \\
       \item \

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

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

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

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

               \node[Nmarks=ir](0)(20,15){0}
               \node(1)(35,25){1}
               \node(2)(35,8){2}
               \node(2l)(50,25){$2'$}
               \node[Nmarks=r](0l)(50,8){$0'$}
               \node(1l)(65,15){$1'$}

               \drawedge[curvedepth=0](0,1){\tt a}
               \drawedge[curvedepth=-15,ELside=r](0,1l){\tt b}
               \drawedge[curvedepth=0](1,2){\tt a}
               \drawedge[curvedepth=0](1,2l){\tt b}
               \drawedge[curvedepth=0](2,0){\tt a}
               \drawedge[curvedepth=0](2,0l){\tt b}
               \drawedge[curvedepth=0,ELside=r](0l,1l){\tt b}
               \drawedge[curvedepth=0,ELside=r](1l,2l){\tt b}
               \drawedge[curvedepth=0,ELside=r](2l,0l){\tt b}
              \end{picture}
             } \\
        \item \ 

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

               \node[Nmarks=ir](1)(20,20){}
               \node(2)(35,20){}
               \node(3)(50,20){}
               \node(4)(65,20){}
               \node[Nmarks=r](5)(35,5){}
               \node(6)(50,5){}
               \node(7)(65,5){}

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

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

               \node[Nmarks=i](1)(20,15){}
               \node(2)(35,15){}
               \node(3)(50,15){}
               \node(4)(65,15){}
               \node(5)(80,15){}
               \node(6)(95,15){}
               \node[Nmarks=r](7)(110,15){}

               \drawedge[curvedepth=0](1,2){\tt a}
               \drawedge[curvedepth=-10,ELside=r](1,6){\tt b}
               \drawedge[curvedepth=0](2,3){\tt a}
               \drawedge[curvedepth=-5,ELside=r](2,5){\tt b}
               \drawedge[curvedepth=0](3,4){\tt b}
               \drawedge[curvedepth=0](4,5){\tt b}
               \drawedge[curvedepth=0](5,6){\tt b}
               \drawedge[curvedepth=0](6,7){\tt b}
               \drawloop[loopangle=0](7){\tt b}
              \end{picture}
             }
       \end{list}

 \item {\footnotesize Prove que $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$, em que $\delta$ é a função de transição de
       um AFD, $e$ é um estado e $x$ e $y$ são palavras.}

       \emph{Solução}: Por indução sobre $|x|$. Para $x=\lambda$, $\hat{\delta}(e,\lambda y)=
       \hat{\delta}(\hat{\delta}(e,\lambda),y)$, pela definição de $\hat{\delta}$. Suponha,
       como hipótese de indução, que $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$
       para palavras $x$ de tamanho $n$, $n\geq 0$. Para palavras de tamanho $n+1$, $az$, onde $a$
       é um símbolo do alfabeto e $z$ uma palavra de tamanho $n$, tem-se:
       \begin{tabbing}
        $\hat{\delta}(e,azy)$\=$=\hat{\delta}(\hat{\delta}(\delta(e,a),z),y)$ \= xxx \kill
        $\hat{\delta}(e,azy)$\>$=\hat{\delta}(\delta(e,a),zy)$ \> pela definição de $\hat{\delta}$\\
                             \>$=\hat{\delta}(\hat{\delta}(\delta(e,a),z),y)$ \> pela hip\a'otese de 
                                  indução\\
                             \>$=\hat{\delta}(\hat{\delta}(e,az),y)$ \> pela definição de
                                  $\hat{\delta}$.
       \end{tabbing}


 \item {\footnotesize Dado um AFD $M$ e um conjunto $X$ de estados de erro em $M$, apresente em detalhes como seria um AFD $M'$,
			 equivalente a $M$, obtido pela substituição de todos os estados de $X$ em $M$ por um único estado de erro.}

       \emph{Solução}: Seja um AFD $M=(E,\Sigma,\delta,i,F)$  e um conjunto de estados de erro $X\subseteq E$. Seja $\textsf{x}\not\in E$
       e $M'=((E-X)\cup\{\textsf{x}\},\Sigma,\delta',i',F)$ em que $i'=i$, se $i\not\in X$, e $i'=\textsf{x}$ se $i\in X$,
			 e $\delta'$ é tal que
			 \begin{itemize}
				\item $\delta'(e,a)=\delta(e,a)$ se $\delta(e,a)\not\in X$,
			  \item $\delta'(e,a)=\textsf{x}$ se $\delta(e,a)\in X$, e
			  \item $\delta'(\textsf{x},a)=\textsf{x}$ para todo $a\in\Sigma$.
			 \end{itemize}
			 Segue-se que $L(M')=L(M)$. Assim, em particular, o conjunto de todos os estados de erro pode ser reduzido a um só.

 \item {\footnotesize Seja o AFD com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(100,40)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(10,20){1}
          \node(2)(30,30){2}
          \node(3)(30,10){3}
          \node[Nmarks=r](4)(50,30){4}
          \node(5)(50,10){5}
          \node[Nmarks=r](6)(70,30){6}
          \node(7)(70,10){7}
          \node(8)(90,20){8}

          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
          \drawedge[curvedepth=2](2,1){{\tt 0}}
          \drawedge[curvedepth=0](2,3){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](3,4){{\tt 0}}
          \drawloop[loopangle=270](3){{\tt 1}}
          \drawedge[curvedepth=0](4,5){{\tt 0}}
          \drawedge[curvedepth=0](4,6){{\tt 1}}
          \drawloop[loopangle=270](5){{\tt 0}}
          \drawedge[curvedepth=2](5,7){{\tt 1}}
          \drawedge[curvedepth=0](6,7){{\tt 0}}
          \drawloop[loopangle=90](6){{\tt 1}}
          \drawedge[curvedepth=2](7,5){{\tt 0}}
          \drawloop[loopangle=270](7){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](8,6){{\tt 0}}
          \drawedge[curvedepth=0](8,7){{\tt 1}}
         \end{picture}
        }
       \end{center}
      \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
       \item Obtenha o diagrama de estados de um AFD mínimo equivalente.
       \item Que linguagem é reconhecida pelo AFD em questão?
      \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Evolução das partições do conjunto de estados após eliminação do estado 8:
             \begin{quote}
              $S_0$: $\{1,2,3,5,7\}$ $\{4,6\}$; \\
              $S_1$: $\{1,2,5,7\}$ $\{3\}$ $\{4,6\}$; \\
              $S_2$: $\{1,2\}$ $\{5,7\}$ $\{3\}$ $\{4,6\}$; \\
              $S_3$: $\{1,2\}$ $\{5,7\}$ $\{3\}$ $\{4,6\}$.
             \end{quote}
             Diagrama do AFD mínimo:
 
              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(90,17)
              \gasset{Nw=8, Nh=6, Nmr=7, loopdiam=5}

              \node[Nmarks=i](1)(10,5){$12$}
              \node(2)(32,5){$3$}
              \node[Nmarks=r](3)(54,5){$46$}
              \node(4)(76,5){$57$}

              \drawloop[loopangle=90](1){{\tt 0}}
              \drawedge[curvedepth=0](1,2){{\tt 1}}
              \drawloop[loopangle=90](2){{\tt 1}}
              \drawedge[curvedepth=0](2,3){{\tt 0}}
              \drawloop[loopangle=90](3){{\tt 1}}
              \drawedge[curvedepth=0](3,4){{\tt 0}}
              \drawloop[loopangle=90](4){{\tt 0},{\tt 1}}
             \end{picture}
             }
        \item Linguagem: $\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*$.
       \end{list}


\item {\footnotesize Utilizando produto de autômatos, determine AFDs que re\-co\-nhe\-çam
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
          \item a união e
          \item a interseção
         \end{list}
         das linguagens $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 1}(w)\mbox{ mod } 3\not=0\}$ e
					              $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,|w| \mbox{ mod } 3=0\}$.}

       \emph{Solução}: O produto tem estados $E=\{0,1,2\}\times\{0,1,2\}$, em que cada estado $(i,j)$, é atingido quando
      a palavra de entrada $w$ for tal que $n_{\tt 1}(w)\mbox{ mod } 3 =i$ e $|w|\mbox{ mod } 3 =j$. O estado
			inicial é $(0,0)$ e a função de transição é dada por:
       \begin{itemize}
        \item $\delta((i,j),{\tt 0})=(i, (j+1)\mbox{ mod } 3)$; e
        \item $\delta((i,j),{\tt 1})=((i+1)\mbox{ mod } 3,(j+1)\mbox{ mod } 3)$.
       \end{itemize}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
          \item Estados finais para união: $(0,0),(1,0),(1,1),(1,2),(2,0),(2,1)(2,2)$.
          \item Estados finais para interseção: $(1,0),(2,0)$.
         \end{list}

 \item {\footnotesize Sejam
       \begin{itemize}\setlength{\parsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L_1=\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$;
        \item $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém }{\tt 00}\}$.
       \end{itemize}
       Construa autômatos finitos determinísticos que reconheçam:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $L_1$.
        \item $L_2$.
        \item $L_1-L_2$. Para isto, faça o produto dos autômatos que reconhecem $L_1$ e $\overline{L_2}$.
       \end{list}}

       \emph{Solução}:  \item \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}

                \node[Nmarks=i, iangle=180](A)(25,10){A}
                \node[Nmarks=r](B)(45,10){B}

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

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

                \node[Nmarks=ir, iangle=180](1)(25,10){1}
                \node[Nmarks=r](2)(45,10){2}
                \node(3)(65,10){3}

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

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

                \node[Nmarks=i, iangle=180](A1)(25,25){A1}
                \node(B1)(25,10){B1}
                \node(A2)(45,25){A2}
                \node(B2)(45,10){B2}
                \node(A3)(65,25){A3}
                \node[Nmarks=r](B3)(65,10){B3}

                \drawedge[curvedepth=0](A1,A2){{\tt 0}}
                \drawedge[curvedepth=0](A1,B1){{\tt 1}}
                \drawedge[curvedepth=0](A2,A3){{\tt 0}}
                \drawedge[curvedepth=-1,ELside=r](A2,B1){{\tt 1}}
                \drawloop[loopangle=270](B1){{\tt 1}}
                \drawedge[curvedepth=3](B1,B2){{\tt 0}}
                \drawedge[curvedepth=0](B2,B3){{\tt 0}}
                \drawedge[curvedepth=3](B2,B1){{\tt 1}}
                \drawloop[loopangle=270](B3){{\tt 0},{\tt 1}}
                \drawedge[curvedepth=0](A3,B3){{\tt 1}}
                \drawloop[loopangle=90](A3){{\tt 0}}
               \end{picture}
              }

       \end{list}

\item {\footnotesize Sim ou não? Por quê?
      \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
       \item Existe linguagem infinita que pode ser reconhecida por um AFD de apenas um estado.
       \item Existe linguagem finita que pode ser reconhecida por um AFD de, no mínimo, um trilhão de estados.
       \item Se uma linguagem pode ser reconhecida por um AFD, qualquer subconjunto dela também pode.
       \item Se uma linguagem não pode ser reconhecida por um AFD e ela é subconjunto de $L$, então $L$ também não
			       pode ser reconhecida por um AFD.
       \item Se um AFD $M$ reconhece uma palavra cujo número símbolos é igual ao número de estados de $M$, então $L(M)$
			       é infinita.
       \item Supondo que existam AFDs que reconheçam as linguagens $A$, $B$ e $C$, então existirá AFD que reconhece
			       $A-(B-C)$.
      \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Sim. O AFD $(\{i\},\{{\tt 0}\},\delta,i,\{i\})$ tal que $\delta(i,{\tt 0})=i$
             reconhece $\{{\tt 0}\}^*$.
       \item Sim. O número de estados de um AFD que reconhece uma linguagem finita deve ter no
             mínimo o tamanho da maior palavra reconhecida mais 1. Por exemplo, se uma
             palavra tiver $999.999.999.999$ símbolos, o AFD terá no mínimo
             1 trilhão de estados.
       \item Não. $\{{\tt 0}\}^*\{{\tt 1}\}^*$ pode ser reconhecida, e $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$ não pode.
       \item Não. Valem os exemplos do item anterior. Observe que as afirmativas são logicamente equivalentes.
       \item Sim. Seja $k$ o número de estados de $M$. Se $M$ reconhece uma palavra $w$ de $k$ símbolos, o caminho
			       percorrido no diagrama de estados de $M$ tem $k+1$ estados. Assim, algum estado é repetido no caminho,
						 o que implica que o caminho tem um ciclo. Isto, por sua vez, implica que $w$ é da forma $xyz$,
             em que $y$ é a subpalavra consumida no ciclo. Como o ciclo pode ser percorrido quantas vezes se queira,
						 tem-se que $xy^iz\in L(M)$ para todo $i\in\mbox{\bf N}$. Logo, $L(M)$ é infinita.
       \item Sim. Observe que $A-(B-C)=A\cap\overline{B-C}=A\cap\overline{B\cap\overline{C}}=A\cap(\overline{B}\cup C)$.
			       Como existe AFD para $B$, existe AFD para $\overline{B}$. Como existem AFDs para $\overline{B}$ e para
             $C$, existe AFD para $\overline{B}\cup C$. Finalmente, como existem AFDs para $A$ e para
						 $\overline{B}\cup C$, existe AFD para $A\cap(\overline{B}\cup C)$. Conclusão: existe AFD para $A-(B-C)$.
      \end{list}

 \item {\footnotesize Construa AFNs para as seguintes linguagens sobre $\{{\tt a},{\tt b},{\tt c}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item o conjunto das palavras com, no mínimo, três ocorrências de {\tt abc};
        \item o conjunto das palavras com, no mínimo, três ocor\-rên\-cias de {\tt a}s ou três ocor\-rên\-cias de {\tt b}s ou
				      três de {\tt c}s;
        \item o conjunto das palavras com sufixo {\tt abc} ou {\tt bca};
        \item o conjunto das palavras em que existem duas ocorrências de {\tt abc} com um número ímpar de símbolos entre elas;
        \item o conjunto das palavras em que o último símbolo seja idêntico ao primeiro;
        \item o conjunto das palavras em que o último símbolo seja diferente do primeiro;
        \item o conjunto das palavras em que o último símbolo tenha ocorrido antes;
        \item o conjunto das palavras em que o último símbolo tenha ocorrido antes no máximo uma vez;
        \item o conjunto das palavras em que o último símbolo não tenha ocorrido antes;
        \item o conjunto das palavras com um único {\tt a} ou um único {\tt b} ou um único {\tt c}. 
      \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item \ 
				
              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,15)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

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

        \item \ 

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,45)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,20){1}
               \node(2a)(35,35){2a}
               \node(2b)(35,20){2b}
               \node(2c)(35,5){2c}
               \node(3a)(55,35){3a}
               \node(3b)(55,20){3b}
               \node(3c)(55,5){3c}
               \node[Nmarks=r](4)(70,20){4}

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

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

               \node[Nmarks=i](1)(20,5){1}
               \node[Nmarks=r](2)(50,5){2}

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

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

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

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

        \item \ 

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,45)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,20){1}
               \node(2a)(40,35){2a}
               \node(2b)(40,20){2b}
               \node(2c)(40,5){2c}
               \node[Nmarks=r](3)(60,20){3}

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

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,45)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,20){1}
               \node(2a)(40,35){2a}
               \node(2b)(40,20){2b}
               \node(2c)(40,5){2c}
               \node[Nmarks=r](3)(60,20){3}

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

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,45)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,20){1}
               \node(2a)(40,35){2a}
               \node(2b)(40,20){2b}
               \node(2c)(40,5){2c}
               \node[Nmarks=r](3)(60,20){3}

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

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,45)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i, iangle=220](1a)(20,35){1a}
               \node[Nmarks=i, iangle=220](1b)(20,20){1b}
               \node[Nmarks=i, iangle=220](1c)(20,5){1c}
               \node[Nmarks=i, iangle=220](2a)(40,35){2a}
               \node[Nmarks=i, iangle=220](2b)(40,20){2b}
               \node[Nmarks=i, iangle=220](2c)(40,5){2c}
               \node[Nmarks=r](3)(60,20){3}

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

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,45)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1a)(20,35){1a}
               \node[Nmarks=i](1b)(20,20){1b}
               \node[Nmarks=i](1c)(20,5){1c}
               \node[Nmarks=r](2)(40,20){2}

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

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

               \node[Nmarks=i](1)(20,5){}
               \node[Nmarks=r](2)(40,5){}
               \node[Nmarks=i](3)(60,5){}
               \node[Nmarks=r](4)(80,5){}
               \node[Nmarks=i](5)(100,5){}
               \node[Nmarks=r](6)(120,5){}

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

 \item \label{e1afn2ei} {\footnotesize Mostre que para todo AFN existe um AFN equivalente com um único estado inicial, para
       isto indicando um mínimo de alterações no AFN original. Exemplifique com o AFN da Figura~\ref{fafn2ei}.
       \begin{figure}
        \begin{center} \setlength{\unitlength}{1mm}
         \begin{picture}(100,20)
          \gasset{Nw=6, Nh=6, Nmr=3, % fillcolor=Gray,
					        fillgray=0.9, loopdiam=4}
          \node[Nmarks=ir, iangle=270](1)(20,10){1}
          \node(2)(40,10){2}
          \node[Nmarks=i, iangle=270](3)(60,10){3}
          \node[Nmarks=r](4)(80,10){4}

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

        \caption{\label{fafn2ei} AFN para Exercícios \ref{e1afn2ei} e \ref{ec2efun}.}
       \end{figure}}

       \emph{Solução}: Seja um AFN $M=(E,\Sigma,\delta,I,F)$. Um AFN com único estado inicial que reconhece $L(M)$ seria
       $M'=(E\cup\{i\},\Sigma,\delta',i,F')$, onde $i$ é um estado que não pertence a $E$ e:
        \begin{itemize}
         \item $F'=F$ se $I\cap F=\emptyset$; caso contrário, $F'=F\cup\{i\}$;
         \item $\delta'(e,a)=\delta(e,a)$ para todo $(e,a)\in E\times \Sigma$;
         \item $\delta'(i,a)=\bigcup_{e\in I}\delta(e,a)$ para todo $a\in\Sigma$.
        \end{itemize}
       Exemplo:
        \begin{center} \setlength{\unitlength}{1mm}
         \begin{picture}(100,25)
          \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
					        fillgray=0.9, loopdiam=4}
          \node[Nmarks=r](1)(20,20){1}
          \node(2)(40,20){2}
          \node(3)(60,20){3}
          \node[Nmarks=r](4)(80,20){4}
          \node[Nmarks=ir, iangle=270](i)(50,5){$i$}

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

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

 \item {\footnotesize Mostre que para todo AFN existe um AFN equivalente com um único estado final.
       Exemplifique com o AFN da Figura~\ref{fafn2ei}.}

       \label{ec2efun}

       \emph{Solução}: Seja um AFN $M=(E,\Sigma,\delta,I,F)$. Um AFN com único estado
       final que reconhece $L(M)$ seria $M'=(E\cup\{f\},\Sigma,\delta',I',\{f\})$, onde
       $f$ é um estado que não pertence a $E$ e:
       \begin{itemize}
        \item $I'=I$ se $I\cap F=\emptyset$; caso contrário, $I'=I\cup\{f\}$;
        \item $\delta'(e,a)=\delta(e,a)$ se $\delta(e,a)\cap F=\emptyset$;
              caso contrário, $\delta'(e,a)=\delta(e,a)\cup\{f\}$;
       \end{itemize}
       Exemplo:
        \begin{center} \setlength{\unitlength}{1mm}
         \begin{picture}(100,25)
          \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
					        fillgray=0.9, loopdiam=4}
          \node[Nmarks=i,iangle=135](1)(20,20){1}
          \node(2)(40,20){2}
          \node[Nmarks=i,iangle=135](3)(60,20){3}
          \node[Nmarks=r](4)(80,20){4}
          \node[Nmarks=ir, iangle=270](f)(50,5){$f$}

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

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

 \item {\footnotesize Mostre que existe linguagem regular que não pode ser reconhecida por AFN que tenha apenas um
       estado inicial \textbf{e} um estado final.}

       \emph{Solução}: Para reconhecer $\{\lambda,{\tt a}\}$, um AFN de um único estado inicial tem que ter no mínimo dois
       estados finais. Por exemplo: 
				
              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,10)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

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

	   Para a mesma linguagem, um AFN de um único estado final tem que ter no mínimo dois estados
		 iniciais. Por exemplo: 

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

               \node[Nmarks=i](1)(20,5){}
               \node[Nmarks=ir,iangle=0](2)(40,5){}

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


 \item {\footnotesize Mostre que toda linguagem regular que não contenha a palavra $\lambda$ pode ser reconhecida por
       AFN que tenha apenas um estado inicial \textbf{e} um estado final.}

       \emph{Solução}: Sendo $(E,\Sigma,\delta,I,F)$ um AFN que reconhece uma linguagem sem a palavra vazia, então
       $I\cap F=\emptyset$. Um AFN equivalente de um único estado inicial e um único estado final seria
			 $(E\cup\{i,f\},\Sigma,\delta',\{i\},\{f\})$ em que $i\not\in E$, $f\not\in E$ e $\delta'$ é assim
			 definida:
			 \begin{itemize}
			  \item $\delta'(i,a)=\cup_{e\in I}\delta(e,a)$ para todo $a\in\Sigma$ (como $I\cap F=\emptyset$,
				       $i$ não é estado final);
			  \item se $\delta(e,a)\not\in F$ então $\delta'(e,a)=\delta(e,a)$, para todo $(e,a)
				      \in E\times\Sigma$; e
			  \item se $\delta(e,a)\in F$ então $\delta'(e,a)=\delta(e,a)\cup\{f\}$, para todo $(e,a)
				      \in E\times\Sigma$ (como $I\cap F=\emptyset$, $f$ não é estado inicial).
			 \end{itemize}

 \item \label{edeafnpafd} {\footnotesize Sejam os AFNs com os diagramas de estados da Figura~\ref{fdeafnpafd}.
       \begin{figure}[t]
       \begin{center}
       \begin{picture}(65,45)
        \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}

        \put(30,0){\makebox(0,0){\textbf{(a) AFN 1.}}}
        \node[Nmarks=i, iangle=180](1)(10,25){1}
        \node(2)(25,35){2}
        \node(3)(25,15){3}
        \node[Nmarks=r](4)(40,25){4}
        \node[Nmarks=i, iangle=0](5)(55,25){5}

        \drawedge(1,2){\tt 0}
        \drawedge(1,3){\tt 1}
        \drawloop[loopangle=90](2){{\tt 0},{\tt 1}}
        \drawedge(2,4){\tt 1}
        \drawloop[loopangle=270](3){{\tt 0},{\tt 1}}
        \drawedge(3,4){\tt 0}
        \drawedge(5,4){\tt 0}
       \end{picture}
       \begin{picture}(65,45)
        \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}

        \put(30,0){\makebox(0,0){\textbf{(b) AFN 2.}}}
        \node[Nmarks=i, iangle=180](1)(10,25){1}
        \node(2)(25,35){2}
        \node[Nmarks=i, iangle=225](3)(25,15){3}
        \node[Nmarks=ir, iangle=0](4)(40,25){4}

        \drawloop[loopangle=90](1){{\tt 0},{\tt 1}}
        \drawedge(1,2){\tt 0}
        \drawedge(1,3){\tt 1}
        \drawedge(2,4){\tt 1}
        \drawedge(3,4){{\tt 0},{\tt 1}}
       \end{picture}
       \begin{picture}(65,50)
        \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}

        \put(30,0){\makebox(0,0){\textbf{(c) AFN 3.}}}
        \node[Nmarks=i, iangle=180](1)(10,35){1}
        \node(2)(25,35){2}
        \node[Nmarks=i, iangle=180](3)(25,15){3}
        \node[Nmarks=i, iangle=70](4)(40,25){4}
        \node[Nmarks=ir, iangle=0](5)(55,25){5}

        \drawedge(1,2){${\tt 1}$}
        \drawloop[loopangle=90](2){{\tt 0},{\tt 1}}
        \drawedge(2,4){${\tt 1}$}
        \drawedge[ELside=r](3,4){${\tt 0},{\tt 1}$}
        \drawedge(4,5){${\tt 0},{\tt 1}$}
       \end{picture}
       \begin{picture}(65,50)
        \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(10,35){1}
        \node[Nmarks=i, iangle=180](2)(10,15){2}
        \node(3)(25,25){3}
        \node[Nmarks=r](4)(40,25){4}

        \put(30,0){\makebox(0,0){\textbf{(d) AFN 4.}}}
        \drawedge[curvedepth=0](1,3){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt a}}
        \drawedge[curvedepth=0](3,4){{\tt b},{\tt c}}
        \drawloop[loopangle=90](1){{\tt a},{\tt b}}
        \drawloop[loopangle=270](2){{\tt a},{\tt c}}
       \end{picture}
       \end{center}

        \caption{\label{fdeafnpafd} AFNs para Exercício \ref{edeafnpafd}.}
       \end{figure}
       Obtenha AFDs equivalentes aos AFNs utilizando o método de construção de subconjuntos.}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Para o AFN 1:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(65,40)
                \gasset{Nw=8, Nh=6, Nmr=7, %fillcolor=Gray,
								        fillgray=0.9, loopdiam=4}

                \node[Nmarks=i, iangle=180](15)(10,20){15}
                \node[Nmarks=r](24)(25,30){24}
                \node(3)(25,10){3}
                \node(2)(40,30){2}
                \node[Nmarks=r](34)(40,10){34}

                \drawedge(15,24){\tt 0}
                \drawedge(15,3){\tt 1}
                \drawloop[loopangle=90](24){\tt 1}
                \drawedge[curvedepth=3](24,2){\tt 0}
                \drawloop[loopangle=270](3){\tt 1}
                \drawedge[curvedepth=3](3,34){\tt 0}
                \drawloop[loopangle=90](2){\tt 0}
                \drawedge[curvedepth=3](2,24){\tt 1}
                \drawloop[loopangle=270](34){\tt 0}
                \drawedge[curvedepth=3](34,3){\tt 1}
               \end{picture}
							}
        \item Para o AFN 2:

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,15)
               \gasset{Nw=9, Nh=6, Nmr=7.5, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=ir](134)(20,5){134}
               \node[Nmarks=r](124)(40,7){124}
               \node(12)(60,5){12}

               \drawloop[loopangle=90](134){\tt 1}
               \drawedge[curvedepth=3](134,124){\tt 0}
               \drawedge[curvedepth=3](124,134){\tt 1}
               \drawedge[curvedepth=0](124,12){\tt 0}
               \drawloop[loopangle=90](12){\tt 0}
               \drawedge[curvedepth=8](12,134){\tt 1}
              \end{picture}
             }

       \item Para o AFN 3:
			
       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(80,30)\setlength{\unitlength}{1mm}
         \gasset{Nw=10, Nh=6, Nmr=8, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=r](5)(20,15){5}
         \node[Nmarks=r](45)(40,15){45}
         \node[Nmarks=ir,iangle=90](1345)(60,15){1345}
         \node[Nmarks=r](245)(80,15){245}
         \node[Nmarks=r](25)(100,15){25}
         \node(2)(115,25){2}
         \node(24)(115,5){24}

         \drawedge[curvedepth=0](45,5){{\tt 0},{\tt 1}}
         \drawedge[curvedepth=0](1345,45){\tt 0}
         \drawedge[curvedepth=0](1345,245){\tt 1}
         \drawloop[loopangle=0,loopangle=90](245){\tt 1}
         \drawedge[curvedepth=0](245,25){\tt 0}
         \drawedge[curvedepth=0](25,2){\tt 0}
         \drawedge[curvedepth=2](25,24){\tt 1}
         \drawloop[loopangle=0](2){\tt 0}
         \drawedge[curvedepth=0](2,24){\tt 1}
         \drawedge[curvedepth=2](24,25){\tt 0}
         \drawedge[curvedepth=8](24,245){\tt 1}
        \end{picture}
			 }
       \item Para o AFN 4:

       \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(100,45)
        \gasset{Nw=8, Nh=6, Nmr=4, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](12)(20,25){12}
        \node(1)(40,40){1}
        \node(123)(40,25){123}
        \node(2)(40,10){2}
        \node[Nmarks=r](14)(60,32.5){14}
        \node[Nmarks=r](24)(60,17.5){24}
        \node(13)(80,32.5){13}
        \node(23)(80,17.5){23}
        \node[Nmarks=r](4)(100,25){4}

        \drawedge[curvedepth=0](12,1){{\tt b}}
        \drawedge[curvedepth=0](12,123){{\tt a}}
        \drawedge[curvedepth=0](12,2){{\tt c}}
        \drawloop[loopangle=90](1){{\tt b}}
        \drawedge[curvedepth=7](1,13){{\tt a}}
        \drawloop[loopangle=90](123){{\tt a}}
        \drawedge[curvedepth=0](123,14){{\tt b}}
        \drawedge[curvedepth=0](123,24){{\tt c}}
        \drawloop[loopangle=90](2){{\tt c}}
        \drawedge[curvedepth=-7,ELside=r](2,23){{\tt a}}
        \drawedge[curvedepth=0,ELside=r](14,1){{\tt b}}
        \drawedge[curvedepth=3](14,13){{\tt a}}
        \drawedge[curvedepth=0](24,2){{\tt c}}
        \drawedge[curvedepth=3](24,23){{\tt a}}
        \drawloop[loopangle=90](13){{\tt a}}
        \drawedge[curvedepth=3](13,14){{\tt b}}
        \drawedge[curvedepth=0](13,4){{\tt c}}
        \drawloop[loopangle=270](23){{\tt a}}
        \drawedge[curvedepth=3](23,24){{\tt c}}
        \drawedge[curvedepth=0](23,4){{\tt b}}
       \end{picture}
       }
       \end{list}

 \item {\footnotesize Construa um AFN de 3 estados que reconheça $\{{\tt a}\}^*\{{\tt b}\}\cup\{{\tt b}\}^*\{{\tt a}\}$. Em seguida,
       obtenha um AFD equivalente pelo método da construção de subconjuntos.}

       \emph{Solução}: \ 

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(55,40)\setlength{\unitlength}{1mm}
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \put(10,15){\makebox(0,0){AFN:}}
         \node[Nmarks=i](1)(30,25){1}
         \node[Nmarks=i](2)(30,5){2}
         \node[Nmarks=r](3)(45,15){3}

         \drawloop[loopangle=45](1){\tt a}
         \drawedge[curvedepth=0](1,3){\tt b}
         \drawloop[loopangle=315](2){\tt b}
         \drawedge[curvedepth=0](2,3){\tt a}
        \end{picture}
        \begin{picture}(80,40)\setlength{\unitlength}{1mm}
         \gasset{Nw=7, Nh=6, Nmr=6.5, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \put(13,15){\makebox(0,0){AFD:}}
         \node[Nmarks=i](12)(30,15){12}
         \node[Nmarks=r](13)(40,25){13}
         \node[Nmarks=r](23)(40,5){23}
         \node[Nmarks=r](3)(50,15){3}
         \node(1)(60,25){1}
         \node(2)(60,5){2}

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


 \item {\footnotesize Seja o AFN$\lambda$ $M=(\{0,1,2\},\{{\tt a},{\tt b},{\tt c}\},\delta,\{0\},\{2\})$,
       sendo $\delta$ dada por:
       \begin{center}
        \begin{tabular}{c|cccc}
         $\delta$ & {\tt a} & {\tt b} & {\tt c} & $\lambda$ \\ \hline
         $0$ & $\{0\}$ & $\emptyset$ & $\emptyset$ & $\{1\}$ \\
         $1$ & $\emptyset$ & $\{1\}$ & $\emptyset$ & $\{2\}$ \\
         $2$ & $\emptyset$ & $\emptyset$ & $\{2\}$ & $\emptyset$
        \end{tabular}
       \end{center}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Determine $f\!\lambda(e)$ para $e=0, 1, 2$.
        \item Determine um AFN $M'$ equivalente a $M$, usando a técnica para eliminação de transições $\lambda$.
        \item Determine um AFD equivalente a $M'$, usando o método de construção de subconjuntos.
       \end{list}}

       \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $f\!\lambda(0)=\{0,1,2\}$; $f\!\lambda(1)=\{1,2\}$; $f\!\lambda(2)=\{2\}$. 
        \item AFN $M'=(\{0,1,2\},\{{\tt a},{\tt b},{\tt c}\},\delta',\{0,1,2\},\{2\})$, sendo
              $\delta'$ dada por:
              \begin{center}
               \begin{tabular}{c|ccc}
                $\delta'$ & {\tt a} & {\tt b} & {\tt c} \\ \hline
                $0$ & $\{0,1,2\}$ & $\emptyset$ & $\emptyset$  \\
                $1$ & $\emptyset$ & $\{1,2\}$ & $\emptyset$ \\
                $2$ & $\emptyset$ & $\emptyset$ & $\{2\}$
               \end{tabular}
              \end{center}

        \item AFD $M''=(\{012,12,2,\emptyset\},\{{\tt a},{\tt b},{\tt c}\},\delta'',012,\{012,12,2\})$, sendo
              $\delta''$ dada por:
              \begin{center}
               \begin{tabular}{c|ccc}
                $\delta''$ & {\tt a} & {\tt b} & {\tt c} \\ \hline
                $012$ & $012$ & $12$ & $2$  \\
                $12$ & $\emptyset$ & $12$ & $2$ \\
                $2$ & $\emptyset$ & $\emptyset$ & $2$ \\
                $\emptyset$ & $\emptyset$ & $\emptyset$ & $\emptyset$
               \end{tabular}
              \end{center}
       \end{list}

 \item {\footnotesize Sejam $L_1=\{1,01\}^+$ e $L_2=\{0,10\}^*$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Construa AFNs (AFDs sem estados de erro) que reconheçam $L_1$ e $L_2$.
				\item Obtenha um AFN$\lambda$ que reconheça $L_1L_2$ usando transição $\lambda$, como exemplificado
			        no Exemplo 37 da Seção 2.3.
				\item Obtenha um AFN equivalente usando a técnica para eliminação de transições $\lambda$.
				\item Obtenha um AFD equivalente pelo método da construção de subconjuntos.
       \end{list}}

     \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item AFNs para $L_1$ e $L_2$, respectivamente:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(50,25)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,15){1}
               \node(2)(30,8){2}
               \node[Nmarks=r](3)(40,15){3}

               \drawedge[curvedepth=-2,ELside=r](1,2){\tt 0}
               \drawedge[curvedepth=3](1,3){\tt 1}
               \drawedge[curvedepth=2](2,3){\tt 1}
               \drawloop[loopangle=90](3){\tt 1}
               \drawedge[curvedepth=2](3,2){\tt 0}
               \end{picture}
               \begin{picture}(60,25)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=ir](4)(20,15){4}
               \node(5)(35,15){5}

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

                \item  AFN$\lambda$ para $L_1L_2$:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(100,25)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,15){1}
               \node(2)(30,8){2}
               \node(3)(40,15){3}

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

               \node[Nmarks=r](4)(65,15){4}
               \node(5)(80,15){5}

               \drawloop[loopangle=90](4){\tt 0}
               \drawedge[curvedepth=3](4,5){\tt 1}
               \drawedge[curvedepth=3](5,4){\tt 0}
               \drawedge[curvedepth=0](3,4){$\lambda$}
               \end{picture}
                      }
                \item AFN para $L_1L_2$:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(60,35)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,25){1}
               \node(2)(30,18){2}
               \node(3)(40,25){3}

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

               \node[Nmarks=r](4)(50,10){4}
               \node(5)(65,10){5}

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

               \drawedge[curvedepth=-12,ELside=r](1,4){\tt 1}
               \drawedge[curvedepth=-4](2,4){\tt 1}
               \drawedge[curvedepth=0,ELside=r](3,4){\tt 1}
               \end{picture}
                      }
                \item AFD para $L_1L_2$:

              \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(60,35)\setlength{\unitlength}{1mm}
               \gasset{Nw=8, Nh=6, Nmr=7, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=i](1)(20,25){1}
               \node(2)(30,18){2}
               \node[Nmarks=r](34)(40,25){34}
               \node[Nmarks=r](24)(55,25){24}
               \node[Nmarks=r](345)(47.5,10){345}
               \node[Nmarks=r](4)(75,25){4}
               \node(5)(90,25){5}

               \drawedge[curvedepth=-2](1,2){\tt 0}
               \drawedge[curvedepth=3](1,34){\tt 1}
               \drawedge[curvedepth=-2,ELside=r](2,34){\tt 1}
               \drawedge[curvedepth=0](34,24){\tt 0}
               \drawedge[curvedepth=0,ELside=r](34,345){\tt 1}
               \drawloop[loopangle=270](345){\tt 1}
               \drawedge[curvedepth=3](345,24){\tt 0}
               \drawedge[curvedepth=3](24,345){\tt 1}
               \drawedge[curvedepth=0](24,4){\tt 0}
               \drawloop[loopangle=270](4){\tt 0}
               \drawedge[curvedepth=3](4,5){\tt 1}
               \drawedge[curvedepth=3](5,4){\tt 0}
               \end{picture}
                      }
       \end{list}

 \item {\footnotesize Espelhando-se nos Exemplos 37 a 40 da Seção 2.3 construa, a partir de AFN$\lambda$s, AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
				\item $\{{\tt a}\}\{\lambda,{\tt a},{\tt b}\}^2\{{\tt b}\}$;
        \item $\{{\tt a}\}^*(\{{\tt b}\}^*\cup\{{\tt c}\}^*)\{{\tt a}\}^*$;
        \item $\{{\tt aa}\}^*\{{\tt bb}\}^*\{{\tt cc}\}^*$.
       \end{list}}

     \emph{Solução}: \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item \ 

      \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(120,15)
        \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFN$\lambda$:}}
        \node[Nmarks=i](1)(20,5){1}
        \node(2)(40,5){2}
        \node(3)(60,5){3}
        \node(4)(80,5){4}
        \node[Nmarks=r](5)(100,5){5}

        \drawedge[curvedepth=0](1,2){\tt a}
        \drawedge[curvedepth=0](2,3){$\lambda$,{\tt a},{\tt b}}
        \drawedge[curvedepth=0](3,4){$\lambda$,{\tt a},{\tt b}}
        \drawedge[curvedepth=0](4,5){\tt b}
       \end{picture}
      }

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

        \put(0,20){\makebox(0,0)[l]{AFN:}}
        \node[Nmarks=i](1)(20,5){1}
        \node(2)(40,5){2}
        \node(3)(60,5){3}
        \node(4)(80,5){4}
        \node[Nmarks=r](5)(100,5){5}

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

      \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(60,40)
        \gasset{Nw=8, Nh=6, Nmr=7, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFD:}}
        \node[Nmarks=i](1)(20,25){1}
        \node(234)(40,25){234}
        \node(34)(60,25){34}
        \node(4)(80,25){4}
        \node[Nmarks=r](345)(40,5){345}
        \node[Nmarks=r](45)(60,5){45}
        \node[Nmarks=r](5)(80,5){5}

        \drawedge[curvedepth=0](1,234){\tt a}
        \drawedge[curvedepth=0](234,34){\tt a}
        \drawedge[curvedepth=0](34,4){\tt a}
        \drawedge[curvedepth=0](234,345){\tt b}
        \drawedge[curvedepth=0,ELpos=30](34,45){\tt b}
        \drawedge[curvedepth=0](4,5){\tt b}
        \drawedge[curvedepth=0](345,45){\tt b}
        \drawedge[curvedepth=0,ELpos=40](345,4){\tt a}
        \drawedge[curvedepth=0](45,5){\tt b}
       \end{picture}
			}

        \item \ 

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

        \put(0,20){\makebox(0,0)[l]{AFN$\lambda$:}}
        \node[Nmarks=i](1)(20,20){1}
        \node(2)(35,30){2}
        \node(3)(35,10){3}
        \node[Nmarks=r](4)(50,20){4}

        \drawloop[loopangle=90](1){\tt a}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawedge[curvedepth=0, ELside=r](1,3){$\lambda$}
        \drawloop[loopangle=90](2){\tt b}
        \drawedge[curvedepth=0](2,4){$\lambda$}
        \drawloop[loopangle=270](3){\tt c}
        \drawedge[curvedepth=0, ELside=r](3,4){$\lambda$}
        \drawloop[loopangle=90](4){\tt a}
       \end{picture}
       \begin{picture}(60,40)
        \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFN:}}
        \node[Nmarks=i](1)(20,20){1}
        \node[Nmarks=i, iangle=135](2)(35,30){2}
        \node[Nmarks=i, iangle=315](3)(35,10){3}
        \node[Nmarks=ir, iangle=0](4)(50,20){4}

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

      \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(60,42)
        \gasset{Nw=10, Nh=6, Nmr=8, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFD:}}
        \node[Nmarks=ir](1234)(22,20){1234}
        \node[Nmarks=r](24)(37,30){24}
        \node[Nmarks=r](34)(37,10){34}
        \node[Nmarks=r](4)(52,20){4}

        \drawloop[loopangle=90](1234){\tt a}
        \drawedge[curvedepth=0](1234,24){\tt b}
        \drawedge[curvedepth=0, ELside=r](1234,34){\tt c}
        \drawloop[loopangle=90](24){\tt b}
        \drawedge[curvedepth=0](24,4){\tt a}
        \drawloop[loopangle=270](34){\tt c}
        \drawedge[curvedepth=0, ELside=r](34,4){\tt a}
        \drawloop[loopangle=90](4){\tt a}
       \end{picture}
			}

        \item \ 

      \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(70,30)
        \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFN$\lambda$:}}
        \node[Nmarks=i](1)(20,25){1}
        \node(1l)(20,5){$1'$}
        \node(2)(40,25){2}
        \node(2l)(40,5){$2'$}
        \node[Nmarks=r](3)(60,25){3}
        \node(3l)(60,5){$3'$}

        \drawedge[curvedepth=3](1,1l){\tt a}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawedge[curvedepth=3](1l,1){\tt a}
        \drawedge[curvedepth=3](2,2l){\tt b}
        \drawedge[curvedepth=0](2,3){$\lambda$}
        \drawedge[curvedepth=3](2l,2){\tt b}
        \drawedge[curvedepth=3](3,3l){\tt c}
        \drawedge[curvedepth=3](3l,3){\tt c}
       \end{picture}
       \begin{picture}(60,30)
        \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFN:}}
        \node[Nmarks=i,iangle=135](1)(20,25){1}
        \node(1l)(20,5){$1'$}
        \node[Nmarks=i,iangle=135](2)(40,25){2}
        \node(2l)(40,5){$2'$}
        \node[Nmarks=ir,iangle=135](3)(60,25){3}
        \node(3l)(60,5){$3'$}

        \drawedge[curvedepth=3](1,1l){\tt a}
        \drawedge[curvedepth=3](1l,1){\tt a}
        \drawedge[curvedepth=0](1l,2){\tt a}
        \drawedge[curvedepth=-14,ELside=r](1l,3){\tt a}
        \drawedge[curvedepth=3](2,2l){\tt b}
        \drawedge[curvedepth=3](2l,2){\tt b}
        \drawedge[curvedepth=0](2l,3){\tt b}
        \drawedge[curvedepth=3](3,3l){\tt c}
        \drawedge[curvedepth=3](3l,3){\tt c}
       \end{picture}
       }

      \mbox{\setlength{\unitlength}{1mm}
       \begin{picture}(60,42)
        \gasset{Nw=10, Nh=6, Nmr=8, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFD:}}
        \node[Nmarks=ir,iangle=270](123)(40,15){123}
        \node(1l)(20,15){$1'$}
        \node(2l)(60,25){$2'$}
        \node(3l)(60,5){$3'$}
        \node[Nmarks=r](23)(80,25){23}
        \node[Nmarks=r](3)(80,5){3}

        \drawedge[curvedepth=3](123,1l){\tt a}
        \drawedge[curvedepth=0](123,2l){\tt b}
        \drawedge[curvedepth=0, ELside=r](123,3l){\tt c}
        \drawedge[curvedepth=3](1l,123){\tt a}
        \drawedge[curvedepth=3](2l,23){\tt b}
        \drawedge[curvedepth=3](3l,3){\tt c}
        \drawedge[curvedepth=3](23,2l){\tt b}
        \drawedge[curvedepth=0](23,3l){\tt c}
        \drawedge[curvedepth=3](3,3l){\tt c}
       \end{picture}
			}
			 \end{list}
\end{enumerate}
\end{document}