\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\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{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Quarta Lista de Exerc\'{\i}cios}

\vspace*{3mm}
\noindent \underline{Observa\c{c}\~{a}o}: Os n\'{u}meros dos exerc\'{\i}cios extra\'{\i}dos de livros
indicados no Plano de Curso est\~{a}o apresentados seguidos das iniciais dos autores
concatenadas com os dois \'{u}ltimos d\'{\i}gitos do ano da publica\c{c}\~{a}o do livro.

\setcounter{section}{8}

\section{M\'{a}quinas de Turing}
 
\begin{enumerate}
 \item (3, cap. 9 de S88) 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}
 \item (4, cap. 9 de S88) Construa uma MT com fita bi-direcional e alfabeto de
       entrada $\{a\}$ que pare se a fita contiver alguma c\'{e}lula sem branco.
 \item (6, cap. 9 de S88) 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}
 \item (11, cap. 9 de S88) Prove que toda linguagem recursivamente enumer\'{a}vel
       \'{e} aceita por uma MT com um \'{u}nico estado de aceita\c{c}\~{a}o.
 \item (4.4.2 de K95) 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.
 \item (16, cap. 9 de S88) 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.
 \item (18, cap. 9 de S88) Prove que uma linguagem $L$ \'{e} recursiva se, e somente
       se, $L$ e $\bar{L}$ s\~{a}o recursivamente enumer\'{a}veis.
 \item (5.3.4 de K95) 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.
 \item (4.1.3 de K95) 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} Bq_01B \stackrel{*}{\vdash} Bq_010B
       \stackrel{*}{\vdash} Bq_011B \stackrel{*}{\vdash} Bq_0100B
       \stackrel{*}{\vdash} \cdots\]
       Note que esta MT n\~{a}o p\'{a}ra.
\end{enumerate}

\section{A Hierarquia de Chomsky}

\begin{enumerate}
 \item (1, cap. 10 de S88) Construa gram\'{a}ticas irrestritas para gerar as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a^ib^ja^ib^j \,\,\,|\,\,\, i,j\geq 0\}$
        \item $\{a^ib^ic^idb^i \,\,\,|\,\,\, i\geq 0\}$
        \item $\{www \,\,\,|\,\,\, w\in \{a,b\}^*\}$
       \end{list}
 \item (7, cap. 10 de S88) Seja $L$ uma linguagem recursivamente enumer\'{a}vel
       sobre $\Sigma$, e $c$ um s\'{\i}mbolo terminal n\~{a}o pertencente a $\Sigma$.
       Mostre que existe uma linguagem sens\'{\i}vel ao contexto $L'$ sobre $\Sigma
       \cup\{c\}$ tal que, para todo $w\in \Sigma^*$, $w\in L$ se, e somente se,
       $wc^i\in L'$ para algum $i\geq 0$.
 \item (5.5.8 de K95) Seja {\cal C} uma classe de dispositivos de alguma
       esp\'{e}cie. Suponha que {\cal C} pode ser enumerada: $M_1$, $M_2$, \ldots.
       Suponha ainda que exista um algoritmo que, quando recebe um dispositivo
       $M$ de {\cal C} e uma entrada $w$, determina se $M$ aceita $w$. Mostre
       que nem toda linguagem recursiva sobre um alfabeto $\Sigma$ \'{e} aceita por
       algum dispositivo em {\cal C}.
 \item (12, cap. 10 de S88) Seja $u\rightarrow v$ uma regra monot\^{o}nica. Construa
       uma sequ\^{e}ncia de regras monot\^{o}nicas, cada uma com lado direito de tamanho
       2 ou menos, que defina a mesma transforma\c{c}\~{a}o que $u\rightarrow v$.
 \item (13, cap. 10 de S88) Construa uma sequ\^{e}ncia de regras sens\'{\i}veis ao
       contexto $uAv\rightarrow uwv$ que defina a mesma transforma\c{c}\~{a}o que a
       regra monot\^{o}nica $AB\rightarrow CD$. ({\em Sugest\~{a}o\/}: Uma sequ\^{e}ncia de
       3 regras, cada uma com os lados esquerdo e direito de tamanho 2, \'{e}
       suficiente.)
 \item (14, cap. 10 de S88) Use os resultados dos dois exerc\'{\i}cios anteriores
       para provar que toda linguagem sens\'{\i}vel ao contexto \'{e} gerada por uma
       gram\'{a}tica na qual cada regra tem a forma $uAv\rightarrow uwv$, onde
       $w\in (\Sigma\cup V)^+$ e $u,v\in (\Sigma\cup V)^*$.
 \item (4.4 de K95) Construa um aut\^{o}mato linear limitado que aceite a linguagem
       \[\{a^{n!} \,\,\,|\,\,\, n\geq 0\}\mbox{.}\] ({\em Sugest\~{a}o\/}: divida o {\em
       string\/} de entrada por 2, 3, 4, \ldots.)
\end{enumerate}

\section{Decidibilidade}

\begin{enumerate}
 \item (7, cap. 11 de S88) 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.
 \item (6.1.1 de K95) Mostre que se o problema da parada \'{e} decid\'{\i}vel ent\~{a}o toda
       linguagem recursivamente enumer\'{a}vel \'{e} recursiva.
 \item (9, cap. 11 de S88) 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.
 \item (10, cap. 11 de S88) 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.
 \item (11, cap. 11 de S88) 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$.
 \item (6.1.4 de K95) 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.)
 \item (15, cap. 11 de S88) 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.
 \item (6.3.1 de K95) 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$?
 \item (17, cap. 11 de S88) 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.
 \item (18, cap. 11 de S88) Prove que n\~{a}o existe algoritmo que determine se o
       complemento da linguagens de uma gram\'{a}tica livre do contexto cont\'{e}m
       um n\'{u}mero infinito de elementos.
\end{enumerate}

\end{document}
\endinput
\end
                            


