\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 2003
 
\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 28/01/04

{\bf Todas as MT's referidas nesta lista podem conter qualquer incremento
(v\'arias fitas, n\~ao determinismo, etc.).}
\begin{enumerate}
 \item Construa uma MT com alfabeto de entrada $\{{\tt a}\}$ que, recebendo como
       entrada uma palavra $w$, concatena $w$ imediatamente \`a sua direita e
       retorna o cabe\c cote para o in\'{\i}cio. Por exemplo, se a configura\c c\~ao
       inicial for $[i,\langle\underline{{\tt a}}{\tt aa}]$,
       a configura\c c\~ao final deve ser $[i,\langle\underline{{\tt a}}{\tt aaaaa}]$.

 \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 reconhe\c ca a linguagem denotada pela ER $a(a+b)^*$,
       assumindo que o alfabeto \'e $\{{\tt a},{\tt b}\}$. Procure obter uma MT
       com um n\'umero m\'{\i}nimo de estados e de transi\c c\~oes.

 \item Construa uma MT e uma gram\'atica para a linguagem
       $\{{\tt a}^n{\tt b}^k{\tt a}^n{\tt b}^k\,\,|\,\, n,k\geq 0\}$.

 \item Seja a linguagem dos par\^enteses balanceados, que \'e gerada pela gram\'atica
       $(\{P\},\{{\tt (},{\tt )}\},R,P)$, onde $R$ consta das regras:
       \begin{enumerate}
        \item[\ ] $P\,\,\rightarrow\,\, \lambda \,\,|\,\, {\tt (} P {\tt )} \,\,|\,\, P P$
       \end{enumerate}
       Construa uma MT que reconhe\c ca tal linguagem.

 \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 $\{xww^Ry\,\,|\,\,x,y,w\in\{{\tt 0},{\tt 1}\}^+ \mbox{ e } |x|>|w|>|y|\}$.
        \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.
       \end{list}

 \item Seja $\{L_1,L_2,\ldots,L_n\}$, $n\geq 2$, uma parti\c c\~ao de $\Sigma^*$, onde
       $\Sigma$ \'e um alfabeto. Mostre que se cada $L_i$ \'e uma LRE, ent\~ao cada $L_i$
       \'e uma linguagem recursiva.

 \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 $(\{{\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}