\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 Nona Lista de Exerc\'{\i}cios}

\noindent \underline{Observa\c c\~ao}: As fun\c c\~oes de transi\c c\~ao desta
lista n\~ao foram conferidas ap\'os a digita\c c\~ao; assim, pode haver erros de
digita\c c\~ao.

\begin{flushleft} \large\bf
 {M\'{a}quinas de Turing}
\end{flushleft}

 
\begin{enumerate}
 \item {\it Construa uma m\'{a}quina de Turing (MT) com alfabeto de entrada
       $\{a,b\}$ para realizar cada uma das opera\c{c}\~{o}es abaixo. Note que
       o cabe\c{c}ote deve estar na posi\c{c}\~{a}o zero, no estado $q_f$,
       quando a computa\c{c}\~{a}o terminar.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Deslocar o {\em string\/} de entrada uma c\'{e}lula para a direita:
              $q_0BuB \stackrel{*}{\vdash} q_fBBuB$.
        \item Concatenar uma c\'{o}pia do reverso do {\em string\/} de entrada \`{a}
              direita do mesmo: $q_0BuB \stackrel{*}{\vdash} q_fBuu^RB$.
        \item Inserir um branco entre cada par de s\'{\i}mbolos de entrada. Exemplo:
              $q_0abaB \stackrel{*}{\vdash} q_fBaBbBaB$.
        \item Eliminar todos os $b$'s da entrada. Exemplo: $q_0babaababB
              \stackrel{*}{\vdash} q_fBaaaaB$.
       \end{list}}
       
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item MT para $q_0BuB \stackrel{*}{\vdash} q_2BBuB$: $(\{q_0,q_1,q_2,
              q_3,q_4,q_5\},\{a,b\},\{a,b,B\},\delta,q_0)$, onde $\delta$ \'e
              dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,a)=[q_1,a,R]$ &
               $\delta(q_1,b)=[q_1,b,R]$ \\
               $\delta(q_1,B)=[q_2,B,L]$ & $\delta(q_2,a)=[q_3,B,R]$ &
               $\delta(q_2,b)=[q_4,B,R]$ \\
               $\delta(q_3,B)=[q_5,a,L]$ & $\delta(q_4,B)=[q_5,b,L]$ &
               $\delta(q_5,B)=[q_2,B,L]$
              \end{tabular}
        
        \item MT para $q_0BuB \stackrel{*}{\vdash} q_2Buu^RB$: $(\{q_0,q_1,q_2,
              q_3,q_4\},\{a,b\},\{a,b,X,Y,B\},\delta,q_0)$, onde $\delta$ \'e
              dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,a)=[q_1,X,R]$ &
               $\delta(q_1,b)=[q_1,Y,R]$ \\
               $\delta(q_1,B)=[q_2,B,L]$ & $\delta(q_2,a)=[q_2,a,L]$ &
               $\delta(q_2,b)=[q_2,b,L]$ \\
               $\delta(q_2,X)=[q_3,a,R]$ & $\delta(q_2,Y)=[q_4,b,R]$ &
               $\delta(q_3,a)=[q_3,a,R]$ \\
               $\delta(q_3,b)=[q_3,b,R]$ & $\delta(q_3,B)=[q_2,a,L]$ &
               $\delta(q_4,a)=[q_4,a,R]$ \\
               $\delta(q_4,b)=[q_4,b,R]$ & $\delta(q_4,B)=[q_2,b,L]$ \\
              \end{tabular}

        
        \item MT para inserir um branco entre cada par de s\'{\i}mbolos de
              entrada:
              
              $(\{q_i \,\,|\,\, 0\leq i\leq 11\},\{a,b\},
              \{a,b,X,Y,\#,B\},\delta,q_0)$, onde $\delta$ \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,a)=[q_1,a,R]$ &
               $\delta(q_1,b)=[q_1,b,R]$ \\
               $\delta(q_1,B)=[q_2,B,L]$ & $\delta(q_2,X)=[q_2,X,L]$ &
               $\delta(q_2,Y)=[q_2,Y,L]$ \\
               $\delta(q_2,\#)=[q_2,\#,L]$ & $\delta(q_2,a)=[q_3,X,R]$ &
               $\delta(q_2,b)=[q_3,Y,R]$ \\
               $\delta(q_3,X)=[q_3,X,R]$ & $\delta(q_3,Y)=[q_3,Y,R]$ &
               $\delta(q_3,\#)=[q_3,\#,R]$ \\
               $\delta(q_3,B)=[q_2,\#,L]$ & $\delta(q_2,B)=[q_4,B,R]$ &
               $\delta(q_4,X)=[q_4,X,R]$ \\
               $\delta(q_4,Y)=[q_4,Y,R]$ & $\delta(q_4,\#)=[q_5,\#,L]$ &
               $\delta(q_5,\#)=[q_5,\#,L]$ \\
               $\delta(q_5,X)=[q_6,\#,R]$ & $\delta(q_5,Y)=[q_9,\#,R]$ &
               $\delta(q_5,\#)=[q_5,\#,L]$ \\
               $\delta(q_6,\#)=[q_6,\#,R]$ & $\delta(q_6,a)=[q_7,a,L]$ &
               $\delta(q_6,b)=[q_7,b,L]$ \\
               $\delta(q_6,B)=[q_7,B,L]$ & $\delta(q_7,\#)=[q_8,B,L]$ &
               $\delta(q_8,\#)=[q_5,a,L]$ \\
               $\delta(q_9,\#)=[q_9,\#,R]$ & $\delta(q_9,a)=[q_{10},a,L]$ &
               $\delta(q_9,b)=[q_{10},b,L]$ \\
               $\delta(q_9,B)=[q_{10},B,L]$ & $\delta(q_{10},\#)=[q_{11},B,L]$ &
               $\delta(q_{11},\#)=[q_5,b,L]$
              \end{tabular}
        
        \item MT para eliminar todos os $b$'s da entrada: $(\{q_0,q_1,q_2,
              q_3,q_4,q_5\},\{a,b\},\{a,b,B\},\delta,q_0)$, onde $\delta$ \'e
              dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,a)=[q_1,a,R]$ &
               $\delta(q_1,b)=[q_1,b,R]$ \\
               $\delta(q_1,B)=[q_2,B,L]$ & $\delta(q_2,b)=[q_2,B,L]$ &
               $\delta(q_2,a)=[q_3,a,L]$ \\
               $\delta(q_3,a)=[q_3,a,L]$ & $\delta(q_3,b)=[q_4,a,R]$ &
               $\delta(q_4,a)=[q_4,a,R]$ \\
               $\delta(q_4,B)=[q_5,B,L]$ & $\delta(q_5,a)=[q_3,B,L]$
              \end{tabular}

       \end{list}

 \item {\it Construa uma MT com fita bi-direcional e alfabeto de entrada
       $\{a\}$ que pare se a fita contiver alguma c\'{e}lula sem branco.}

       Uma MT seria: $(\{q_0,q_1\},\{a\},\{a,X,B\},\delta,q_0)$, onde $\delta$
       \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,X)=[q_0,X,L]$ & $\delta(q_0,B)=[q_1,X,R]$ &
               $\delta(q_1,X)=[q_1,X,R]$ \\
               $\delta(q_1,B)=[q_0,X,L]$ \\
              \end{tabular}

       
 \item {\it Construa uma MT com alfabeto de entrada $\{a,b\}$ que
       aceite as seguintes linguagens por estado final:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^i \,\,\,|\,\,\, i\geq 0\}$
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j>0\}$
        \item conjunto dos {\em strings\/} com mesmo n\'{u}mero de $a$'s e
              $b$'s.
        \item $\{ww^R \,\,\,|\,\,\, w\in\{a,b\}^*\}$
       \end{list}}
       
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^i \,\,\,|\,\,\, i\geq 0\}$
        
              $(\{q_0,q_1,q_2,q_3,q_4,q_5\},\{a,b\},\{a,b,B\},\delta,q_0,
              \{q_5\})$, onde $\delta$ \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,B)=[q_5,B,L]$ &
               $\delta(q_1,a)=[q_2,b,R]$ \\
               $\delta(q_2,a)=[q_2,a,R]$ & $\delta(q_2,b)=[q_2,b,R]$ &
               $\delta(q_2,B)=[q_3,B,L]$ \\
               $\delta(q_3,b)=[q_4,B,L]$ & $\delta(q_4,a)=[q_4,a,L]$ &
               $\delta(q_4,b)=[q_4,b,L]$ \\
               $\delta(q_4,B)=[q_1,B,R]$ \\
              \end{tabular}

        
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j>0\}$
        
              $(\{q_i \,\,|\,\, 1\leq i\leq 10\},\{a,b\},\{a,b,X,B\},\delta,q_0,
              \{q_{10}\})$, onde $\delta$ \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,a)=[q_2,B,R]$ &
               $\delta(q_2,a)=[q_2,a,R]$ \\
               $\delta(q_2,b)=[q_3,b,R]$ & $\delta(q_3,b)=[q_3,b,R]$ &
               $\delta(q_3,X)=[q_3,X,R]$ \\
               $\delta(q_3,a)=[q_4,X,L]$ & $\delta(q_4,X)=[q_4,X,L]$ &
               $\delta(q_4,b)=[q_4,b,L]$ \\
               $\delta(q_4,B)=[q_5,B,R]$ & $\delta(q_5,b)=[q_6,B,R]$ &
               $\delta(q_6,b)=[q_6,b,R]$ \\
               $\delta(q_6,X)=[q_6,X,R]$ & $\delta(q_6,b)=[q_7,X,L]$ &
               $\delta(q_7,X)=[q_7,X,L]$ \\
               $\delta(q_7,b)=[q_8,X,R]$ & $\delta(q_7,B)=[q_9,B,R]$ &
               $\delta(q_8,X)=[q_8,X,R]$ \\
               $\delta(q_8,b)=[q_7,X,L]$ & $\delta(q_9,X)=[q_9,B,R]$ &
               $\delta(q_9,B)=[q_{10},B,R]$
              \end{tabular}
        
        
        \item conjunto dos {\em strings\/} com mesmo n\'{u}mero de $a$'s e
              $b$'s.
              
              $(\{q_0,q_1,q_2,q_3,q_4,q_5\},\{a,b\},\{a,b,X,B\},\delta,q_0,
              \{q_5\})$, onde $\delta$ \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,X)=[q_1,B,R]$ &
               $\delta(q_1,a)=[q_2,B,R]$ \\
               $\delta(q_1,b)=[q_3,B,R]$ & $\delta(q_1,B)=[q_5,B,L]$ &
               $\delta(q_2,a)=[q_2,a,R]$ \\
               $\delta(q_2,X)=[q_2,X,R]$ & $\delta(q_2,b)=[q_4,X,L]$ &
               $\delta(q_3,b)=[q_3,b,R]$ \\
               $\delta(q_3,X)=[q_3,X,R]$ & $\delta(q_3,a)=[q_4,X,L]$ &
               $\delta(q_4,a)=[q_4,a,L]$ \\
               $\delta(q_4,b)=[q_4,b,L]$ & $\delta(q_4,X)=[q_4,X,L]$ &
               $\delta(q_4,B)=[q_1,B,R]$
              \end{tabular}

              
        \item $\{ww^R \,\,\,|\,\,\, w\in\{a,b\}^*\}$
        
              $(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6\},\{a,b\},\{a,b,B\},\delta,q_0,
              \{q_1\})$, onde $\delta$ \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_1,a)=[q_2,B,R]$ &
               $\delta(q_1,b)=[q_4,B,R]$ \\
               $\delta(q_2,a)=[q_2,a,R]$ & $\delta(q_2,b)=[q_2,b,R]$ &
               $\delta(q_2,B)=[q_3,B,L]$ \\
               $\delta(q_3,a)=[q_6,B,L]$ & $\delta(q_4,a)=[q_4,a,R]$ &
               $\delta(q_4,b)=[q_4,b,R]$ \\
               $\delta(q_4,B)=[q_5,B,L]$ & $\delta(q_5,b)=[q_6,B,L]$ &
               $\delta(q_6,a)=[q_6,a,L]$ \\
               $\delta(q_6,b)=[q_6,b,L]$ & $\delta(q_6,B)=[q_1,B,R]$
              \end{tabular}
        
       \end{list}
 \item {\it Prove que toda linguagem recursivamente enumer\'{a}vel
       \'{e} aceita por uma MT com um \'{u}nico estado de aceita\c{c}\~{a}o.}
       
       Seja uma MT $M=(Q,\Sigma,\Gamma,\delta,q_0,F)$ que aceita uma linguagem
       recursivamente enumer\'{a}vel $L(M)$. Caso $F$ n\~ao seja unit\'ario,
       uma MT equivalente a $M$ com um \'unico estado de aceita\c{c}\~{a}o seria
       $M'=(Q\cup \{p\},\Sigma,\Gamma,\delta',q_0,\{p\})$, onde $p\not\in Q$ e
       $\delta'$ \'e igual a $\delta$, acrescida de uma transi\c c\~ao da forma
       $\delta'(q_i,a)=p$ para cada par $(q_i,a)\in F\times \Gamma$ tal que
       $\delta(q_i,a)\uparrow$. 
       
 \item {\it Construa uma MT de 3 trilhas que subtraia o n\'{u}mero bin\'{a}rio
       na sua segunda trilha do n\'{u}mero bin\'{a}rio na sua primeira trilha e
       deposite o resultado na terceira trilha.}
       
       Sup\~oe-se que os n\'umeros est\~ao alinhados \`a direita e \`a esquerda
       (neste caso, com eventuais zeros \`a esquerda). Uma MT \'e
       $(\{q_0,q_1,q_2,q_3\},\{0,1\},\{0,1,B\},\delta,q_0,)$, onde $\delta$ \'e
       dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,[B,B,B])=[q_1,[B,B,B],R]$ &
                $\delta(q_1,[0,0,B])=[q_1,[0,0,B],R]$ &
                $\delta(q_1,[0,1,B])=[q_1,[0,1,B],R]$ \\
               $\delta(q_1,[1,0,B])=[q_1,[1,0,B],R]$ &
                $\delta(q_1,[1,1,B])=[q_1,[1,1,B],R]$ &
                $\delta(q_1,[B,B,B])=[q_2,[B,B,B],L]$ \\
               $\delta(q_2,[0,0,B])=[q_2,[0,0,0],L]$ &
                $\delta(q_2,[1,0,B])=[q_2,[1,0,1],L]$ &
                $\delta(q_2,[1,1,B])=[q_2,[1,1,0],L]$ \\
               $\delta(q_2,[0,1,B])=[q_3,[0,1,1],L]$ &
                $\delta(q_3,[0,0,B])=[q_3,[0,0,1],L]$ &
                $\delta(q_3,[0,1,B])=[q_3,[0,1,0],L]$ \\
               $\delta(q_3,[1,1,B])=[q_3,[1,1,1],L]$ &
                $\delta(q_3,[1,0,B])=[q_2,[1,0,0],L]$
              \end{tabular}
     
 \item {\it Construa uma MT n\~{a}o determin\'{\i}stica de 2 fitas que aceite os
       {\em strings\/} de tamanho \'{\i}mpar sobre $\{a,b,c\}$ com um $c$ na
       posi\c{c}\~{a}o do meio. Toda computa\c{c}\~{a}o com entrada $w$ deve
       terminar ap\'{o}s, no m\'{a}ximo, $|w|+1$ transi\c{c}\~{o}es.}
       
       $(\{q_0,q_1,q_2\},\{0,1\},\{0,1,X,B\},\delta,q_0,\{q_2\})$, onde
       $\delta$ \'e dada por:
              
              \begin{tabular}{lll}
               $\delta(q_0,B,B)=[q_1,(B,R),(B,R)]$ &
                $\delta(q_1,a,B)=[q_1,(a,R),(X,R)]$ &
                $\delta(q_1,b,B)=[q_1,(b,R),(X,R)]$ \\
               $\delta(q_1,c,B)=[q_1,(c,R),(X,R)]$ &
                $\delta(q_1,c,B)=[q_2,(c,R),(B,L)]$ &
                $\delta(q_2,a,X)=[q_2,(a,R),(B,L)]$ \\
               $\delta(q_2,b,X)=[q_2,(b,R),(B,L)]$ &
                $\delta(q_2,c,X)=[q_2,(c,R),(B,L)]$
              \end{tabular}

 \item {\it Prove que uma linguagem $L$ \'{e} recursiva se, e somente
       se, $L$ e $\overline{L}$ s\~{a}o recursivamente enumer\'{a}veis.}
       
       $(\rightarrow)$ Se $L$ \'e recursiva, $\overline{L}$ tamb\'em \'e (as
       linguagens recursivas s\~ao fechadas sob complementa\c c\~ao). Como
       toda linguagem recursiva \'e recursivamente enumer\'avel, segue-se que
       $L$ e $\overline{L}$ s\~{a}o recursivamente enumer\'{a}veis.

       $(\leftarrow)$ Se $L$ e $\overline{L}$ s\~{a}o recursivamente
       enumer\'{a}veis, existem m\'aquinas de Turing $M_1$ que reconhece $L$ e
       $M_2$ que reconhece $\overline{L}$. Pode-se construir uma m\'aquina de
       Turing $M_3$ que reconhece $L$, e que {\it sempre p\'ara\/} (mostrando
       assim, que $L$ \'e recursiva), com duas fitas, n\~ao determin\'{\i}stica;
       $M_3$ faz o seguinte:
       \begin{list}{\arabic{conta2}.}{\usecounter{conta2}}
        \item copia a entrada da fita 1 para a fita 2;
        \item transfere o controle (n\~ao deterministicamente) para $M_1$ na
              fita 1 ou $M_2$ na fita 2.
        \item na situa\c c\~ao em que $M_1$ p\'ara, $M_3$ p\'ara e aceita o
              {\it string\/} se, e somente se, $M_1$ aceita;
        \item na situa\c c\~ao em que $M_2$ p\'ara, $M_3$ p\'ara e aceita o
              {\it string\/} se, e somente se, $M_2$ n\~ao aceita.
       \end{list}
       Para qualquer {\it string\/} $w$, uma das m\'aquinas, $M_1$ ou $M_2$,
       seguramente p\'ara; neste caso, por constru\c c\~ao, $M_3$ tamb\'em
       p\'ara.
       
 \item {\it Suponha que $L_1, L_2, \ldots, L_n$ s\~{a}o linguagens que formam
       uma parti\c{c}\~{a}o de $\Sigma^*$. Se todas estas linguagens s\~{a}o
       recursivamente enumer\'{a}veis, mostre que elas t\^{e}m que ser
       recursivas.}

       Isto \'e um corol\'ario da proposi\c c\~ao da quest\~ao anterior. Observe
       que $\overline{L_1}=\cup_{i=2}^{n}L_i$ e $\cup_{i=2}^{n}L_i$ \'e
       linguagem recursivamente enumer\'avel (pois linguagens recursivamente
       enumer\'aveis s\~ao fechadas sob uni\~ao). Logo $L_1$ \'e recursiva,
       pela proposi\c c\~ao da quest\~ao anterior. Assim, sucessivamente, para
       $L_2, \ldots, L_n$.
       
 \item {\it  Construa uma m\'{a}quina de Turing que enumere todos os inteiros
       bin\'{a}rios (em ordem num\'{e}rica), quando submetido o {\em string\/}
       de entrada $0$. Ou seja, a MT deve se comportar assim: \[Bq_00B
       \stackrel{*}{\vdash} q_0B1B \stackrel{*}{\vdash} q_0B10B
       \stackrel{*}{\vdash} q_0B11B \stackrel{*}{\vdash} q_0B100B
       \stackrel{*}{\vdash} \cdots\]
       Note que esta MT n\~{a}o p\'{a}ra.}
       
       $(\{q_0,q_1,q_2,q_3,q_4,q_5,q_6,q_7,q_8,q_9\},\{0,1\},\{0,1,B\},\delta,
       q_0)$, onde $\delta$ \'e dada por:
              
       \begin{tabular}{lll}
        $\delta(q_0,B)=[q_1,B,R]$ & $\delta(q_0,0)=[q_0,0,L]$ &
               $\delta(q_0,1)=[q_0,1,L]$ \\
               $\delta(q_1,0)=[q_1,0,R]$ & $\delta(q_1,1)=[q_1,1,R]$ &
               $\delta(q_1,B)=[q_2,B,L]$ \\
               $\delta(q_2,0)=[q_0,1,L]$ & $\delta(q_2,1)=[q_3,0,L]$ &
               $\delta(q_3,0)=[q_0,1,L]$ \\
               $\delta(q_3,1)=[q_3,0,L]$ & $\delta(q_3,B)=[q_4,B,R]$ &
               $\delta(q_4,0)=[q_4,0,R]$ \\
               $\delta(q_4,1)=[q_4,1,R]$ & $\delta(q_4,B)=[q_5,B,L]$ &
               $\delta(q_5,0)=[q_6,B,R]$ \\
               $\delta(q_5,1)=[q_7,B,R]$ & $\delta(q_6,B)=[q_8,0,L]$ &
               $\delta(q_7,B)=[q_8,1,L]$ \\
               $\delta(q_8,B)=[q_5,B,L]$ & $\delta(q_5,B)=[q_9,B,R]$ &
               $\delta(q_9,B)=[q_0,1,L]$
              \end{tabular}
\end{enumerate}

\end{document}
