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

\begin{flushleft} \large\bf
 {Decidibilidade}
\end{flushleft}


\begin{enumerate}
 \item {\it Dada uma MT arbitr\'{a}ria $M$ e um {\em string\/} de entrada $w$,
       ir\'{a} a computa\c{c}\~{a}o de $M$ com entrada $w$ parar em menos de 100
       transi\c{c}\~{o}es? Descreva uma MT que resolva este problema de
       decis\~{a}o.}
       
       MT de 4 fitas:
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item copie $w$, da fita 1 para a fita 2;
        \item reposicione o cabe\c cote da fita 2 no in\'{\i}cio;
        \item escreva {\it en\/}$(q_0)$ na fita 3;
        \item escreva 99 na fita 4;
        \item sejam $x$ o s\'{\i}mbolo que est\'a sendo lido na fita 2, e $q_i$
              o estado codificado na fita 3; localize na fita 1 uma
              transi\c c\~ao da forma {\it en\/}$(q_i)0${\it en\/}$(x)0$
              {\it en\/}$(q_j)0${\it en\/}$(y)0${\it en\/}$(d)$; se n\~ao
              existir, pare e aceite, sen\~ao:
              \begin{enumerate}
               \item[.] substitua {\it en\/}$(q_i)$ por {\it en\/}$(q_j)$ na
                      fita 3;
               \item[.] escreva $y$ na fita 2 e mova seu cabe\c cote na
                      dire\c c\~ao $d$;
              \end{enumerate}
        \item decremente o n\'umero da fita 4;  se o n\'umero cair para 0, pare
              e rejeite; caso contr\'ario volte ao passo (5).
       \end{list}
       
 \item {\it Mostre que se o problema da parada \'{e} decid\'{\i}vel ent\~{a}o
       toda linguagem recursivamente enumer\'{a}vel \'{e} recursiva.}
       
       Seja uma linguagem recursivamente enumer\'{a}vel, reconhecida por uma MT
       $M$. A partir de $M$, pode-se construir uma MT $M'$, que
       p\'ara com a entrada $w$ se, e somente se, $M$ reconhece $w$ (ou seja, o
       problema de reconhecer se $w\in L(M)$ pode ser reduzido ao problema da
       parada): $M'$ seria como $M$, exceto que nas situa\c c\~oes em que $M$
       p\'ara em estado \underline{n\~ao final}, $M'$ entra em {\it loop\/}.
       
 \item {\it Prove que n\~{a}o existe algoritmo que determine se uma MT
       arbitr\'{a}ria ir\'{a} parar para alguma entrada. Isto \'{e}, $R(M)$
       \'{e} aceito se $M$ parar para algum {\em string\/} $w$; caso
       contr\'{a}rio, $R(M)$ \'{e} rejeitado.}
       
       Redu\c c\~ao do problema da parada a este: a MT redutora produz, a partir
       de $R(M)w$, $R(M')$ tal que:
       \begin{enumerate}
        \item[.] $M'$ apaga o conte\'udo da fita;
        \item[.] $M'$ escreve $w$ na fita, posiciona o cabe\c cote no
                 in\'{\i}cio, e vai para estado inicial de $M$;
        \item[.] $M'$ faz como $M$.
       \end{enumerate}
       
       Com isto, $M'$ p\'ara com alguma entrada se, e somente se, $M$ p\'ara com
       a entrada $w$.

 \item {\it Prove que n\~{a}o existe algoritmo que determine se uma
       MT arbitr\'{a}ria ir\'{a} parar para todos os {\em strings\/} de entrada.}
       
       O problema da parada pode ser reduzido a este exatamente da mesma forma
       que na quest\~ao anterior.
       
 \item {\it Prove que n\~{a}o existe algoritmo que receba como entrada uma MT
       $M=(Q,\Sigma,\Gamma,\delta,q_0,F)$, um estado $q_i\in Q$, e um {\em
       string\/} $w\in\Sigma^*$, e determine se a computa\c{c}\~{a}o de $M$
       com entrada $w$ entra no estado $q_i$.}
       
       Redu\c c\~ao do problema da parada a este: a MT redutora produz, a partir
       de $R(M)w$, $R(M')w\mbox{\it en}(q_k)$, onde $q_k$ \'e um novo estado
       (ou seja, n\~ao pertence a $M$), e $M'$ \'e tal que:
       \begin{enumerate}
        \item[.] para todo $(q_j,x)\in Q\times \Gamma$ tal que
               $\delta(q_j,x)\downarrow$, $\delta'(q_j,x)=\delta(q_j,x)$; e
        \item[.] para todo $(q_j,x)\in Q\times \Gamma$ tal que
               $\delta(q_j,x)\uparrow$, $\delta'(q_j,x)=[q_k,x,R]$.
       \end{enumerate}
       onde $\delta'$ \'e a fun\c c\~ao de transi\c c\~ao de $M'$.
       
       Com isto, $M'$ entra em $q_k$ com a entrada $w$ se, e somente se, $M$
       p\'ara com a entrada $w$.

 \item {\it Prove que n\~{a}o existe algoritmo que determine se $L(M)=\phi$,
       para uma MT arbitr\'{a}ria $M$.  ({\em Sugest\~{a}o\/:} reduzir o
       problema da fita em branco a este.)}
       
       Redu\c c\~ao do problema da fita em branco a este: a MT redutora produz,
       a partir de $R(M)$, $R(M')$ tal que:
       \begin{enumerate}
        \item[.] $M'$ apaga o conte\'udo da fita;
        \item[.] $M'$ faz como $M$.
       \end{enumerate}
       
       Com isto, $L(M')=\phi$ se, e somente se, $M$ n\~ao p\'ara com a entrada
       $\lambda$.

       (Observe que, no caso, se $L(M')\not=\phi$ ent\~ao $L(M')=\Sigma^*$.)
       
 \item {\it Prove que o problema da correspond\^{e}ncia de Post para
       sistemas com alfabeto de um \'{u}nico s\'{\i}mbolo \'{e} decid\'{\i}vel.}
       
       Segue um algoritmo para o problema. Sejam $[a^{n_1},a^{m_1}] \ldots
       [a^{n_k},a^{m_k}]$ os domin\'os.
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item se $n_i=m_i$, para algum $i$, ent\~ao $i$ \'e uma solu\c c\~ao;
        \item se $n_i>m_i$ para todo $i$, ou se $n_i<m_i$ para todo $i$, ent\~ao
              o problema n\~ao tem solu\c c\~ao;
        \item sejam $i$ e $j$ tais que $n_i>m_i$ e $n_j<m_j$ (que devem existir,
              caso este passo seja alcan\c cado). Uma solu\c c\~ao, envolvendo
              $x$ domin\'os $[a^{n_i},a^{m_i}]$ e $y$ domin\'os
              $[a^{n_j},a^{m_j}]$ deve ser tal que \[xn_i+yn_j=xm_i+ym_j\mbox{,}\]
              ou seja, $x(n_i-m_i)=y(m_j-n_j)$. Uma possibilidade \'e ter:
              \[x=m_j-n_j \mbox{ e } y=m_i-n_i\mbox{.}\]
       \end{list}
       
 \item {\it Sejam $G_1$ uma gram\'{a}tica regular arbitr\'{a}ria e $G_2$ uma
       gram\'{a}tica livre do contexto arbitr\'{a}ria. \'{E} decid\'{\i}vel o
       problema de determinar se $L(G_1)\cap L(G_2)=\phi$?}
       
       Este problema \'e decid\'{\i}vel, podendo ser resolvido assim: (observe que
       todas as etapas do algoritmo foram abordadas no curso):
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item obtenha um AFD $M_1$ que reconhece $L(G_1)$;
        \item obtenha um AP $M_2$ que reconhece $L(G_2)$;
        \item obtenha, a partir de $M_1$ e $M_2$, um AP $M_3$ que reconhece
              $L(M_1)\cap L(M_2)$;
        \item obtenha uma gram\'atica livre do contexto $G_3$ que gera $L(M_3)$;
        \item seja $G_3'$ uma gram\'atica na forma normal de Chomsky equivalente
              a $G_3$, e seja $n=2^{k+1}$, onde $k$ \'e o n\'umero de
              vari\'aveis de $G_3'$;
        \item se existe um {\it string\/} de tamanho no m\'aximo igual a $n$ que
              gerado por $G_3'$, ent\~ao $L(G_3')\not=\phi$ (e, portanto,
              $L(G_1)\cap L(G_2)\not=\phi$), caso contr\'ario,
              $L(G_3')=\phi$ (e, portanto, $L(G_1)\cap L(G_2)=\phi$).
       \end{list}
       Observe que todas as etapas do algoritmo foram abordadas no curso. A
       \'ultima pode ser justificada atrav\'es do {\it pumping lemma\/}.
       
 \item {\it Prove que n\~{a}o existe algoritmo que determine se a
       interse\c{c}\~{a}o das linguagens de duas gram\'{a}ticas livres do
       contexto cont\'{e}m um n\'{u}mero infinito de elementos.}
       
       O Problema da Correspond\^encia de Post (PCP) pode ser reduzido a este.
       Sejam as gram\'aticas $G_U$ e $G_V$, como mostradas no livro texto. O
       PCP tem uma solu\c c\~ao $i_1 i_2\ldots i_k$ se, e somente se,
       $u_{i_1}u_{i_2}\ldots u_{i_k}i_k\ldots i_2 i_1 \in L(G_U)\cap L(G_V)$.
       Mas, se o PCP tem a solu\c c\~ao $i_1 i_2\ldots i_k$, ent\~ao
       ele tem infinitas solu\c c\~oes $(i_1 i_2\ldots i_k)^n$, para
       $n\geq 1$. E, portanto, $(u_{i_1}u_{i_2}\ldots u_{i_k})^n(i_k\ldots i_2
       i_1)^n \in L(G_U)\cap L(G_V)$ para $n\geq 1$, e $L(G_U)\cap L(G_V)$ tem
       um n\'umero infinito de elementos. Assim:
       \[\mbox{O PCP tem solu\c c\~ao se, e somente se, } L(G_U)\cap L(G_V) \mbox{
        \'e infinito.} \]
       (Observe que $L(G_U)\cap L(G_V)$ \'e infinito ou $\phi$.)

 \item {\it Prove que n\~{a}o existe algoritmo que determine se o complemento
       da linguagem de uma gram\'{a}tica livre do contexto cont\'{e}m
       um n\'{u}mero infinito de elementos.}
       
       Aproveitando aquest\~ao anterior: $L(G_U)\cap L(G_V)$ tem um n\'umero
       infinito de elementos se, e somente se,
       $\overline{\overline{L(G_U)}\cup \overline{L(G_V)}}$ \'e infinito. Mas,
       $\overline{L(G_U)}\cup \overline{L(G_V)}$ \'e uma linguagem livre do
       contexto, como j\'a visto.
\end{enumerate}

\end{document}
