\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\newcounter{conta3}
\begin{document} \footnotesize
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Solu\c c\~ao da Sexta Lista de Exerc\'{\i}cios}

\begin{flushleft} \large\bf
 {Aut\^omatos Finitos}
\end{flushleft}


\begin{enumerate}
 \item {\it Construa um aut\^{o}mato finito determin\'{\i}stico (AFD) para cada 
       uma das linguagens do e\-xer\-c\'{\i}\-cio 2.7.}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ que n\~{a}o
              cont\^{e}m $aa$.}
        
              $(\{q_0,q_1,q_2\},\{a,b,c\},\delta,q_0,\{q_0,q_1\})$, onde
              $\delta$ \'e dada por:
              
              \begin{tabular}{c|ccc}
               $\delta$ & $a$ & $b$ & $c$ \\ \hline
               $q_0$ & $q_1$ & $q_0$ & $q_0$ \\
               $q_1$ & $q_2$ & $q_0$ & $q_0$ \\
               $q_2$ & $q_2$ & $q_2$ & $q_2$
              \end{tabular}
              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ nos quais
              cada $b$ \'{e} seguido por pelo menos um $c$.}
              
              $(\{q_0,q_1,q_2\},\{a,b,c\},\delta,q_0,\{q_0\})$, onde
              $\delta$ \'e dada por:
              
              \begin{tabular}{c|ccc}
               $\delta$ & $a$ & $b$ & $c$ \\ \hline
               $q_0$ & $q_0$ & $q_1$ & $q_0$ \\
               $q_1$ & $q_2$ & $q_2$ & $q_0$ \\
               $q_2$ & $q_2$ & $q_2$ & $q_2$
              \end{tabular}
 
              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o
              n\'{u}mero de $a$'s \'{e} divis\'{\i}vel por 3.}
              
              $(\{q_0,q_1,q_2\},\{a,b\},\delta,q_0,\{q_0\})$, onde
              $\delta$ \'e dada por:
              
              \begin{tabular}{c|cc}
               $\delta$ & $a$ & $b$ \\ \hline
               $q_0$ & $q_1$ & $q_0$ \\
               $q_1$ & $q_2$ & $q_1$ \\
               $q_2$ & $q_0$ & $q_2$
              \end{tabular}


        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais
              cada $a$ \'{e} precedido (imediatamente) ou seguido
              (imediatamente) por $b$.}
              
              $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_0,q_2,q_3\})$,
              onde $\delta$ \'e dada por:
              
              \begin{tabular}{c|cc}
               $\delta$ & $a$ & $b$ \\ \hline
               $q_0$ & $q_1$ & $q_2$ \\
               $q_1$ & $q_4$ & $q_2$ \\
               $q_2$ & $q_3$ & $q_2$ \\
               $q_3$ & $q_1$ & $q_2$ \\
               $q_4$ & $q_4$ & $q_4$
              \end{tabular}

              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ com n\'{u}mero par de
              $a$'s e n\'{u}mero par de $b$'s.}
              
              $(\{\mbox{\it pp},\mbox{\it ip},\mbox{\it pi},\mbox{\it ii}\},
              \{a,b\},\delta,\mbox{\it pp},\{\mbox{\it pp}\})$, onde
              $\delta$ \'e dada por:
              
              \begin{tabular}{c|cc}
               $\delta$ & $a$ & $b$ \\ \hline
               {\it pp} & {\it ip} & {\it pi} \\
               {\it ip} & {\it pp} & {\it ii} \\
               {\it pi} & {\it ii} & {\it pp} \\
               {\it ii} & {\it pi} & {\it ip}
             \end{tabular}

              
        \item {\it o conjunto dos {\em strings\/} de tamanho \'{\i}mpar sobre
              $\{a,b\}$ que cont\^{e}m exatamente dois $b$'s.}
              
              $(\{\mbox{\it p0},\mbox{\it i0},\mbox{\it p1},\mbox{\it i1},
              \mbox{\it p2},\mbox{\it i2},\mbox{\it e}\},\{a,b\},\delta,
              \mbox{\it p0},\{\mbox{\it i2}\})$, onde $\delta$ \'e dada por:
              
              \begin{tabular}{c|cc}
               $\delta$ & $a$ & $b$ \\ \hline
               {\it p0} & {\it i0} & {\it i1} \\
               {\it i0} & {\it p0} & {\it p1} \\
               {\it p1} & {\it i1} & {\it p2} \\
               {\it i1} & {\it p1} & {\it i2} \\
               {\it p2} & {\it i2} & {\it e} \\
               {\it i2} & {\it p2} & {\it e} \\
               {\it e} & {\it e} & {\it e} \\
              \end{tabular}

       \end{list}


       
 \item {\it Construa um AFD para cada uma das linguagens:}
       
       \begin{tabular}{rlrlrl}
        (a) & {\boldmath $(ab)^*ba$} & (b) & {\boldmath $(ab)^*(ba)^*$} 
        \ \ \ \ \ \ &
        (c) & {\boldmath $aa(a\cup b)^+bb$} \\
        (d) & {\boldmath $((aa)^+bb)^*$} \ \ \ \ \ \ & (e) & {\boldmath $(ab^*a)^*$} \\
       \end{tabular}
       
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item {\boldmath $(ab)^*ba$}
         
               $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_3\})$,
               onde $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $q_1$ & $q_2$ \\
                $q_1$ & $q_4$ & $q_0$ \\
                $q_2$ & $q_3$ & $q_4$ \\
                $q_3$ & $q_4$ & $q_2$ \\
                $q_4$ & $q_4$ & $q_4$
               \end{tabular}

         
         \item {\boldmath $(ab)^*(ba)^*$} 

               $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_0,q_3\})$,
               onde $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $q_1$ & $q_2$ \\
                $q_1$ & $q_4$ & $q_0$ \\
                $q_2$ & $q_3$ & $q_4$ \\
                $q_3$ & $q_4$ & $q_2$ \\
                $q_4$ & $q_4$ & $q_4$
               \end{tabular}

         \item {\boldmath $aa(a\cup b)^+bb$}
         
               $(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6\},\{a,b\},\delta,q_0,
               \{q_0,q_5\})$, onde $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $q_1$ & $q_6$ \\
                $q_1$ & $q_2$ & $q_6$ \\
                $q_2$ & $q_3$ & $q_3$ \\
                $q_3$ & $q_3$ & $q_4$ \\
                $q_4$ & $q_3$ & $q_5$ \\
                $q_5$ & $q_3$ & $q_5$ \\
                $q_6$ & $q_6$ & $q_6$
               \end{tabular}

         \item {\boldmath $((aa)^+bb)^*$}
         
               $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_0\})$, onde
               $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $q_1$ & $q_4$ \\
                $q_1$ & $q_2$ & $q_4$ \\
                $q_2$ & $q_1$ & $q_3$ \\
                $q_3$ & $q_4$ & $q_0$ \\
                $q_4$ & $q_4$ & $q_4$
               \end{tabular}

         \item {\boldmath $(ab^*a)^*$}

               $(\{q_0,q_1,q_2\},\{a,b\},\delta,q_0,\{q_0\})$, onde
               $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $q_1$ & $q_2$ \\
                $q_1$ & $q_0$ & $q_1$ \\
                $q_2$ & $q_2$ & $q_2$
               \end{tabular}
          
       \end{list}
              
 \item {\it Construa um aut\^{o}mato finito n\~{a}o determin\'{\i}stico
       (AFN) para cada uma das linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              {\em substring\/} de tamanho 4 tem pelo menos um $b$.
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              {\em substring\/} de tamanho 4 tem exatamente um $b$.
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o terceiro
              s\'{\i}mbolo da direita para a esquerda \'{e} $b$.
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ que cont\^{e}m um n\'{u}mero
              par de {\em substrings\/} $ba$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              {\em substring\/} de tamanho 4 tem pelo menos um $b$.
       
              $(\{q_0,q_1,q_2,q_3\},\{a,b\},\delta,q_0,\{q_0,q_1,q_2,q_3\})$,
               onde $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $\{q_1\}$ & $\{q_0\}$ \\
                $q_1$ & $\{q_2\}$ & $\{q_0\}$ \\
                $q_2$ & $\{q_3\}$ & $\{q_0\}$ \\
                $q_3$ & $\phi$ & $\{q_0\}$
               \end{tabular}      
              
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais cada
              {\em substring\/} de tamanho 4 tem exatamente um $b$.
       
              $(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6\},\{a,b\},\delta,q_0,
              \{q_0,q_1,q_2,q_3,q_4,q_5,q_6\})$, onde $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $\{q_1\}$ & $\{q_1,q_4\}$ \\
                $q_1$ & $\{q_2\}$ & $\{q_2,q_4\}$ \\
                $q_2$ & $\{q_3\}$ & $\{q_3,q_4\}$ \\
                $q_3$ & $\phi$ & $\{q_4\}$ \\
                $q_4$ & $\{q_5\}$ & $\phi$ \\
                $q_5$ & $\{q_6\}$ & $\phi$ \\
                $q_6$ & $\{q_3\}$ & $\phi$
              \end{tabular}      
              
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o terceiro
              s\'{\i}mbolo da direita para a esquerda \'{e} $b$.
              
              $(\{q_0,q_1,q_2,q_3\},\{a,b\},\delta,q_0,\{q_3\})$, onde $\delta$
              \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $\{q_0\}$ & $\{q_0,q_1\}$ \\
                $q_1$ & $\{q_2\}$ & $\{q_2\}$ \\
                $q_2$ & $\{q_3\}$ & $\{q_3\}$ \\
                $q_3$ & $\phi$ & $\phi$
              \end{tabular}      
              
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ que cont\^{e}m um
              n\'{u}mero par de {\em substrings\/} $ba$.
              
              $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_0,q_1\})$, onde
              $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $\{q_0\}$ & $\{q_1\}$ \\
                $q_1$ & $\{q_2\}$ & $\{q_1\}$ \\
                $q_2$ & $\{q_2\}$ & $\{q_3\}$ \\
                $q_3$ & $\{q_1\}$ & $\{q_3\}$
              \end{tabular}      
              
       \end{list}  
       
 \item {\it Construa um AFD que reconhe\c{c}a o conjunto dos {\em
       strings\/} sobre $\{a,b\}$ terminados em $abba$. Construa um diagrama de
       estados de um AFN, com seis arcos, que reconhe\c{c}a a mesma linguagem.}

       AFD: $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_4\})$, onde
              $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $q_1$ & $q_0$ \\
                $q_1$ & $q_1$ & $q_2$ \\
                $q_2$ & $q_1$ & $q_3$ \\
                $q_3$ & $q_4$ & $q_0$ \\
                $q_4$ & $q_1$ & $q_2$
              \end{tabular}      
              
       AFN: $(\{q_0,q_1,q_2,q_3,q_4\},\{a,b\},\delta,q_0,\{q_4\})$, onde
              $\delta$ \'e dada por:
              
               \begin{tabular}{c|cc}
                $\delta$ & $a$ & $b$ \\ \hline
                $q_0$ & $\{q_0,q_1\}$ & $\{q_0\}$ \\
                $q_1$ & $\phi$ & $\{q_2\}$ \\
                $q_2$ & $\phi$ & $\{q_3\}$ \\
                $q_3$ & $\{q_4\}$ & $\phi$ \\
                $q_4$ & $\phi$ & $\phi$
              \end{tabular}      
       
       
 \item {\it Seja o AFN-$\lambda$ $M=(\{q_0,q_1,q_2\},
       \{a,b,c\},\delta,q_0,\{q_1,q_2\})$, sendo $\delta$ dada por:
       \begin{center}
       \begin{tabular}{c|cccc}
       $\delta$ & $a$ & $b$ & $c$ & $\lambda$ \\ \hline
       $q_0$ & $\{q_0\}$ & $\phi$ & $\{q_1\}$ & $\{q_2\}$ \\
       $q_1$ & $\phi$ & $\phi$ & $\{q_1\}$ & $\phi$ \\
       $q_2$ & $\phi$ & $\{q_1,q_2\}$ & $\phi$ & $\phi$
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma express\~{a}o regular para $L(M)$.
        \item Determine $\lambda$-{\em fecho\/}$(q_i)$ para $i=0,1,2$.
        \item D\^{e} a fun\c{c}\~{a}o de transi\c{c}\~{a}o $t$ para $M$.
        \item Construa um AFD equivalente a $M$ usando o algoritmo 6.6.3 de
              S88.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Express\~{a}o regular para $L(M)$: {\boldmath $a^*(c\cup b^+)c^*$}
        \item $\lambda$-{\em fecho\/}$(q_i)$ para $i=0,1,2$:
        
              $\lambda$-{\em fecho\/}$(q_0)=\{q_0,q_2\}$
        
              $\lambda$-{\em fecho\/}$(q_1)=\{q_1\}$
        
              $\lambda$-{\em fecho\/}$(q_2)=\{q_2\}$
       
        \item Fun\c{c}\~{a}o de transi\c{c}\~{a}o $t$ para $M$:

               \begin{tabular}{c|ccc}
                $t$ & $a$ & $b$ & $c$\\ \hline
                $q_0$ & $\{q_0,q_2\}$ & $\{q_1,q_2\}$ & $\{q_1\}$\\
                $q_1$ & $\phi$        & $\phi$        & $\{q_1\}$ \\
                $q_2$ & $\phi$        & $\{q_1,q_2\}$ & $\phi$
              \end{tabular}      
 
        \item AFD equivalente a $M$: $(\{\{q_0,q_2\},\{q_1,q_2\},\{q_1\},\phi\},
              \{a,b\},\delta',\{q_0,q_2\},\{\{q_0,q_2\},\{q_1,q_2\}, \{q_1\}\})$,
              onde $\delta'$ \'e dada por:

               \begin{tabular}{c|ccc}
                $\delta'$ & $a$ & $b$ & $c$\\ \hline
                $\{q_0,q_2\}$ & $\{q_0,q_2\}$ & $\{q_1,q_2\}$ & $\{q_1\}$ \\
                $\{q_1,q_2\}$ & $\phi$        & $\{q_1,q_2\}$ & $\{q_1\}$ \\
                $\{q_1\}$     & $\phi$        & $\phi$        & $\{q_1\}$ \\
                $\phi$        & $\phi$        & $\phi$        & $\phi$
              \end{tabular}      


       \end{list}       
       
 \item {\it Seja o AFN-$\lambda$ $M=(\{q_0,q_1,q_2\},\{a,b,c\},\delta,q_0,\{q_2\})$,
       sendo $\delta$ dada por:
       \begin{center}
       \begin{tabular}{c|cccc}
       $\delta$ & $a$ & $b$ & $c$ & $\lambda$ \\ \hline
       $q_0$ & $\{q_0\}$ & $\phi$ & $\phi$ & $\{q_1\}$ \\
       $q_1$ & $\phi$ & $\{q_1\}$ & $\phi$ & $\{q_2\}$ \\
       $q_2$ & $\phi$ & $\phi$ & $\{q_2\}$ & $\phi$
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item D\^{e} uma express\~{a}o regular para $L(M)$.
        \item Determine $\lambda$-{\em fecho\/}$(q_i)$ para $i=0,1,2$.
        \item D\^{e} a fun\c{c}\~{a}o de transi\c{c}\~{a}o $t$ para $M$.
        \item Construa um AFD equivalente a $M$ usando o algoritmo 6.6.3 de
              S88.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Express\~{a}o regular para $L(M)$: {\boldmath $a^*b^*c^*$}      
        
        \item $\lambda$-{\em fecho\/}$(q_i)$ para $i=0,1,2$:
        
              $\lambda$-{\em fecho\/}$(q_0)=\{q_0,q_1,q_2\}$
        
              $\lambda$-{\em fecho\/}$(q_1)=\{q_1,q_2\}$
        
              $\lambda$-{\em fecho\/}$(q_2)=\{q_2\}$
       
        \item Fun\c{c}\~{a}o de transi\c{c}\~{a}o $t$ para $M$:
        
               \begin{tabular}{c|ccc}
                $t$ & $a$ & $b$ & $c$\\ \hline
                $q_0$ & $\{q_0,q_1,q_2\}$ & $\{q_1,q_2\}$ & $\{q_2\}$\\
                $q_1$ & $\phi$            & $\{q_1,q_2\}$ & $\{q_2\}$ \\
                $q_2$ & $\phi$            & $\phi       $ & $\{q_2\}$
              \end{tabular}      
 
        \item AFD equivalente a $M$:
        
              $(\{\{q_0,q_1,q_2\},\{q_1,q_2\},\{q_2\},
              \phi\},\{a,b,c\},\delta',\{q_0,q_1,q_2\},\{\{q_0,q_1,q_2\},
              \{q_1,q_2\}, \{q_2\}\})$,
              onde $\delta'$ \'e dada por:

               \begin{tabular}{c|ccc}
                $\delta'$ & $a$ & $b$ & $c$\\ \hline
                $\{q_0,q_1,q_2\}$ & $\{q_0,q_1,q_2\}$ & $\{q_1,q_2\}$ & $\{q_2\}$ \\
                $\{q_1,q_2\}$ & $\phi$        & $\{q_1,q_2\}$ & $\{q_2\}$ \\
                $\{q_2\}$     & $\phi$        & $\phi$        & $\{q_2\}$ \\
                $\phi$        & $\phi$        & $\phi$        & $\phi$
              \end{tabular}      


       \end{list}
 \item {\it Fa\c{c}a uma defini\c{c}\~{a}o recursiva da fun\c{c}\~{a}o de transi\c{c}\~{a}o
       estendida $\hat{\delta}$ de um AFN-$\lambda$. O valor
       $\hat{\delta}(q_i,w)$ \'{e} o conjunto dos estados que podem ser alcan\c{c}ados
       por computa\c{c}\~{o}es que come\c{c}am no estado $q_i$ e processam completamente o
       {\em string\/} $w$.}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\hat{\delta}(q_i,\lambda)=\lambda$-{\em fecho\/}$(q_i)$
        \item para qualquer {\it string\/} $w$ e s\'{\i}mbolo $a$,
              $\hat{\delta}(q_i,wa)=\cup_{q_k\in\hat{\delta}(q_i,w)}
              \lambda$-{\em fecho\/}$(\delta(q_k,a))$
       \end{list}       
       
  \item {\it Determine uma express\~{a}o regular para as linguagens aceitas
        pelos seguintes aut\^{o}matos finitos (use a t\'{e}cnica do algoritmo
        6.8.2 de S88)}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{q_1, q_2, q_3\},\{a,b\},\delta_1,q_1, \{q_2\})$, onde
              $\delta_1$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_1$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_2$ & $q_2$ \\
         $q_2$ & $q_3$ & $q_1$ \\
         $q_3$ & $q_2$ & $q_2$
        \end{tabular}
        \end{center}
        
        \underline{Observa\c c\~ao}: a express\~ao encontrada depende da ordem
        de elimina\c c\~ao dos estados.
        
        {\boldmath $(a\cup b)(a(a\cup b)\cup b(a\cup b))^*$}
        
        \item $(\{q_1, q_2, q_3\},\{a,b\},\delta_2,q_1, \{q_1\})$, onde
              $\delta_2$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_2$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_1$ & $q_3$ \\
         $q_2$ & $q_1$ & $q_3$ \\
         $q_3$ & $q_2$ & $q_3$
        \end{tabular}
        \end{center}
        
        {\boldmath $(a\cup b(b\cup ab)^*aa)^*$}
        
        \item $(\{q_1, q_2, q_3\},\{a,b\},\delta_3,q_1, \{q_2,q_3\})$, onde
             $\delta_3$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_3$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_3$ & $q_2$ \\
         $q_2$ & $q_3$ & $q_1$ \\
         $q_3$ & $q_1$ & $q_2$
        \end{tabular}
        \end{center}
        
        {\boldmath $(aa)^*(b\cup ab)(ab\cup (b\cup aa)(aa)^*(b\cup ab))^*\cup
                    (bb)^*(a\cup ba)(ba\cup (a\cup bb)(bb)^*(a\cup ba))^*$}
        
        \item $(\{q_1, q_2, q_3,q_4,q_5\},\{a,b\},\delta_4,q_1, \{q_5\})$, onde
              $\delta_4$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_4$ & $a$ & $b$  \\ \hline
         $q_1$ & $q_2$ & $q_1$ \\
         $q_2$ & $q_2$ & $q_3$ \\
         $q_3$ & $q_4$ & $q_1$ \\
         $q_4$ & $q_5$ & $q_3$ \\
         $q_5$ & $q_5$ & $q_5$
        \end{tabular}
        \end{center}
        
        {\boldmath $(b\cup a^+b(ab)^*b)^*a^+b(ab)^*aa(a\cup b)^*$}
        
        \item $(\{q_1, q_2, q_3,q_4\},\{a,b\},\delta_5,q_1, \{q_3\})$, onde
              $\delta_5$ \'{e} dada por:
        \begin{center}
        \begin{tabular}{c|cc}
         $\delta_5$ & $a$ & $b$  \\ \hline
         $q_1$ & $\{q_2\}$ & $\{q_4\}$ \\
         $q_2$ & $\phi$ & $\{q_3,q_4\}$ \\
         $q_3$ & $\{q_3\}$ & $\{q_3\}$ \\
         $q_4$ & $\{q_2,q_4\}$ & $\phi$
        \end{tabular}
        \end{center}
        
        {\boldmath $(a\cup ba^+)(ba^+)^*b(a\cup b)^*$}
        
       \end{list}
\end{enumerate}

\end{document}
