\documentclass[12pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\addtolength{\topmargin}{1cm}

\newcounter{conta}
\hyphenation{pro-ble-mas re-gu-lar re-gu-la-res}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens} \hfill
 $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
Professor: Newton Jos\'{e} Vieira \\
{\bf Terceira Lista de Exerc\'{\i}cios} \hfill Entrega: at\'e 09/11/04

{\bf Todas as MT's referidas nesta lista podem conter qualquer incremento
(v\'arias fitas, n\~ao determinismo, etc.), a menos que se diga o contr\'ario.}
\begin{enumerate}

 \item Construa uma MT padr\~ao que gere todos os n\'umeros naturais em nota\c c\~ao
       bin\'aria. A MT n\~ao deve parar nunca. Ela deve gerar {\tt 0}, depois {\tt 1}, depois
       {\tt 10}, etc., separados por branco, indefinidamente. A fita dever\'a ficar assim:
       \[\langle{\tt 0}\sqcup{\tt 1}\sqcup{\tt 10}\sqcup{\tt 11}\sqcup{\tt 100}
         \sqcup{\tt 101}\sqcup{\tt 110}\sqcup\cdots\]

 \item Construa uma MT que multiplique dois n\'umeros naturais em nota\c c\~ao
       bin\'aria. Por exemplo, se o conte\'udo inicial da fita de entrada for
       $\langle \underline{{\tt 1}}{\tt 01}\sqcup{\tt 110}$, ap\'os o
       processamento, seu conte\'udo ser\'a $\langle \underline{{\tt 1}}{\tt 1110}$.

 \item Construa MT's, com o menor n\'umero de transi\c c\~oes poss\'{\i}vel, que
       reconhe\c cam \underline{por parada} as seguintes linguagens de alfabeto
       $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que cont\^em {\tt 00}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
      \end{list}

 \item Escreva MT's que reconhe\c cam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{k_0}{\tt 1}{\tt 0}^{k_1}{\tt 1}\ldots{\tt 0}^{k_n}{\tt 1}
               \,|\,n\in\mbox{\bf N} \mbox{ e } 0<k_0<k_1<\cdots<k_n\}$.
        \item $\{xyx^Ry^R\,\,|\,\,x,y\in\{{\tt 0},{\tt 1}\}^*\}$.
        \item $\{{\tt 0}^n\,\,|\,\, \mbox{$n$ n\~ao \'e primo}\}$.
       \end{list}

 \item Mostre que para toda gram\'atica irrestrita existe uma equivalente na
       qual cada regra tem o lado direito maior ou igual ao lado esquerdo ou
       \'e regra $\lambda$.

 \item Seja $L$ uma LRE de alfabeto $\Sigma$, e $\#$ um s\'{\i}mbolo n\~ao
       pertencente a $\Sigma$. Mostre que existe uma LSC $L'$ de alfabeto
       $\Sigma\cup\{\#\}$ tal que, para todo $w\in \Sigma^*$:
       \[w\in L \mbox{ se, e somente se, } w\#^k\in L' \mbox{ para algum
       $k\geq 0$.}\]

 \item Sejam $L$ uma LRE e $R$ uma linguagem recursiva. Mostre:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-R$ \'e uma LRE.
        \item $L-R$ pode n\~ao ser recursiva.
        \item $R-L$ pode n\~ao ser uma LRE.
        \item $R-L$ pode ser regular.
       \end{list}

 \item Mostre que este \'e decid\'{\i}vel: {\em Dada uma MT $M$, determinar
       se $M$ escreve algum s\'{\i}mbolo diferente do branco, para a entrada
       $\lambda$\/}.

 \item Mostre que \'e decid\'{\i}vel ou que n\~ao \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT $M$ e um n\'umero natural $n$, determinar se $M$
              reconhece alguma palavra executando $n$ ou menos transi\c c\~oes.
        \item Dada uma MT $M$ e um n\'umero natural $n$, determinar se $M$
              reconhece alguma palavra de $n$ ou menos s\'{\i}mbolos.
        \item Dada uma MT $M$ e um n\'umero natural $n$, determinar se $M$
              avan\c ca o cabe\c cote para al\'em da $n$-\'esima c\'elula
              (a primeira \'e aquela com o s\'{\i}mbolo ``$\langle$'').
       \end{list}

 \item Para cada PD abaixo, mostre que o mesmo \'e indecid\'{\i}vel:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dados uma MT $M$, uma palavra $w$ e um estado $e$ de $M$,
              determinar se a computa\c c\~ao de $M$ para a entrada $w$ atinge
              o estado $e$.
        \item Dada uma MT $M$, determinar se a computa\c c\~ao de $M$
              para a entrada $\lambda$ ``volta'' ao estado inicial de $M$.
        \item Dados uma MT $M$ e um s\'{\i}mbolo $a$ de $M$, determinar se a
              computa\c c\~ao de $M$ para a entrada $\lambda$ escreve $a$ na
              fita em algum momento.
        \item Dados uma MT $M$ e uma express\~ao regular $r$, determinar se
              $L(M)\cap L(r)\not=\emptyset$.
       \end{list}

 \item Construa as gram\'aticas $G_x$ e $G_y$, como definidas na Se\c c\~ao
       5.6 da apostila, correspondentes ao SCP $(\{{\tt 0},{\tt 1}\},P)$,
       onde $P$ consta dos pares
       $({\tt 01},{\tt 011}),({\tt 001},{\tt 01}),({\tt 10},{\tt 00})$.

 \item Construa uma gram\'atica para a linguagem $\overline{L(G_x)}$, onde
       $G_x$ \'e a GLC definida na Se\c c\~ao 5.6 da apostila.

 \item Mostre que o seguinte problema n\~ao \'e decid\'{\i}vel: dadas duas
       GLC's $G_1$ e $G_2$, determinar se $L(G_1)\cap L(G_2)$ \'e finito.

 \item Mostre que o seguinte problema n\~ao \'e decid\'{\i}vel: dada uma GLC
       $G$, determinar se $\overline{L(G)}$ \'e finito.

 \item Mostre que o seguinte problema \'e ou n\~ao decid\'{\i}vel: dadas uma
       GR $G_R$ e uma GLC $G_L$, determinar se $L(G_R)\cap L(G_L)=\emptyset$.

 \item Mostre que s\~ao indecid\'{\i}veis os problemas de determinar, dadas
       duas GLC's $G_1$ e $G_2$, que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G_1)=L(G_2)$
        \item $L(G_1)\subseteq L(G_2)$
       \end{list}
\end{enumerate}

\end{document}