
\documentclass[12pt,a4paper]{report}

%=================================================================
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\textwidth}{1.5cm}
%=================================================================
 
\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
 
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: \parbox[t]{14cm}{Newton Jos\'{e} Vieira \\
                     e-mail: nvieira@dcc.ufmg.br}
 
\noindent {\bf Terceira Lista de Exerc\'{\i}cios} \hfill Entrega: at\'e 24/02/03

\begin{enumerate}
 \item Construa uma MT que, recebendo como entrada um n\'umero na nota\c c\~ao
       bin\'aria, some 1 ao mesmo e retorne o cabe\c cote para a posi\c c\~ao
       inicial. Se a palavra de entrada for $\lambda$, a MT dever\'a escrever
       \verb+0+.

 \item Construa uma MT para a linguagem
       $\{\verb+a+^n\verb+b+^n\verb+c+^n\,\,|\,\, n\geq 0\}$.

 \item Construa uma MT que reconhe\c ca a linguagem:
       \[\{\verb+0+^{k_0}\verb+1+\verb+0+^{k_1}\verb+1+
       \ldots\verb+0+^{k_n}\verb+1+\,\,|\,\,n\in\mbox{\bf N} \mbox{ e }
       0<k_0<k_1<\cdots<k_n\}\mbox{.}\]
       Use uma fita s\'o para assegurar a restri\c c\~ao
       $0<k_0<k_1<\cdots<k_n$.

 \item Escreva uma MT n\~ao determin\'{\i}stica de duas fitas que reconhe\c ca
       a linguagem
       \[\{xx^Ry\,\,|\,\,x,y\in\{\verb+0+,\verb+1+\}^* \mbox{ e } |x|>|y|\}
       \mbox{.}\]

 \item Seja uma MT que, em cada transi\c c\~ao, s\'o pode escrever um
       s\'{\i}mbolo ou mover o cabe\c cote, mas n\~ao ambos. Fa\c ca uma
       defini\c c\~ao formal deste tipo de m\'aquina. Depois
       mostre que tais m\'aquinas reconhecem exatamente as LRE's.

 \item Construa uma gram\'atica que gere a linguagem
       $\{\verb+0+^n\verb+1+^k\verb+0+^n\verb+1+^k\,\,|\,\, n,k\geq 0\}$.

 \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.
       \end{list}

 \item Mostre que a linguagem
       $\{R\langle M\rangle\,\,|\,\, \lambda\in L(M)\}$ \'e LRE.

 \item Mostre que este PD \'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 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 $(\{\verb+0+,\verb+1+\},P)$,
       onde $P$ consta dos pares
       $(\verb+01+,\verb+011+),(\verb+001+,\verb+01+),(\verb+10+,\verb+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}