\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 2005 \\
Professor: Newton Jos\'{e} Vieira \\
{\bf Terceira Lista de Exerc\'{\i}cios} \hfill Entrega: at\'e 21/11/05

{\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 some 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 1101}$, ap\'os o
       processamento, seu conte\'udo ser\'a $\langle \underline{{\tt 1}}{\tt 0010}$.

 \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 come\c cam com {\tt 0}.
        \item O conjunto das palavras que n\~ao come\c cam com {\tt 0}.
      \end{list}

 \item Escreva MT's que reconhe\c cam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^m{\tt d}^n\,|\,m,n\in\mbox{\bf N}\}$.
        \item $\{xyx^Ry^R\,\,|\,\,x,y\in\{{\tt 0},{\tt 1}\}^*\}$.
        \item $\{{\tt a}^{n^2}\,|\,n\in\mbox{\bf N}\}$.
        \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 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 $\{R\langle M\rangle\,|\,$a MT $M$ p\'ara se a entrada \'e $\lambda\}$
       \'e LRE.

 \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 de $n$ ou menos s\'{\i}mbolos.
        \item Dada uma MT $M$ e uma palavra $w$, determinar se $M$ escreve
              algum s\'{\i}mbolo diferente do branco, ao processar $w$.
        \item Dada uma MT $M$ e uma palavra $w$, determinar se $M$ l\^e
              algum branco ao processar $w$.
        \item Dada uma MT $M$, determinar se $|L(M)|>1$.
       \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 $a$ 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)=\emptyset$.
       \end{list}

 \item Mostre que os seguinte problemas s\~ao ou n\~ao decid\'{\i}veis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dadas duas GLCs $G_1$ e $G_2$, determinar se $L(G_1)\cap L(G_2)$ \'e finito.
        \item Dado um AP $M$, determinar se $\overline{L(M)}$ \'e finito.
        \item Dadas uma GR $G_R$ e uma GLC $G_L$, determinar se $L(G_R)\cap L(G_L)=\emptyset$.
        \item Dadas uma GR $G_R$ e uma GLC $G_L$, determinar se $L(G_R)\subseteq L(G_L)$.
       \end{list}

 \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}