\documentclass[11pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}

%\usepackage{gastex}
%\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens} \hfill  $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton José Vieira \\
{\bf Terceira Lista de Exercícios} \hfill Entrega: até 26/11/2013

\vspace*{3mm}
\noindent \textbf{Obs:} Para quem entregar as soluções até o dia da prova às 9:25h, esta lista valerá 14 pontos (dos 34 da terceira prova).

\vspace*{3mm}
{\bf Todas as MTs referidas nesta lista podem conter qualquer incremento (várias fitas, não determinismo, etc.),
a menos que se diga o contrário.}
\begin{enumerate}
 \item Construa uma MT que some dois números naturais em notação binária. Por exemplo, se o conteúdo inicial da fita
       de entrada for $\langle \underline{{\tt 1}}{\tt 01}\sqcup{\tt 1101}$, após o processamento, seu conteúdo será
			 $\langle \underline{{\tt 1}}{\tt 0010}$. Se usar outra(s) fita(s), seu(s) conteúdo(s) ao final
       do processamento não será(ão) importante(s).

 \item Construa MTs, com o menor número de transições possível, que  reconheçam \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çam com {\tt 0}.
        \item O conjunto das palavras que não começam com {\tt 0}.
      \end{list}

 \item Escreva MTs que reconheçam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n{\tt a}^m{\tt b}^n\,|\,m,n\in\mbox{\bf N}\}$.
        \item $\{{\tt a}^{n^2}\,|\,n\in\mbox{\bf N}\}$.
        \item $\{{\tt 0}^n\,|\, \mbox{$n$ não é primo}\}$.
       \end{list}

 \item Construa uma gramática irrestrita que gere
       $\{{\tt a}^m{\tt b}^n{\tt a}^m{\tt b}^n\,|\,m,n\in\mbox{\bf N}\}$.

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

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

 \item Mostre que $\{R\langle M\rangle\,|\,M \mbox{ é MT e } {\tt 0} \in L(M)\}$ é LRE.

 \item Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT $M$ e uma palavra $w$, determinar se $M$ escreve algum símbolo diferente do branco
				      ao processar $w$.
        \item Dada uma MT $M$ e uma palavra $w$, determinar se $M$ lê algum branco ao processar $w$.
       \end{list}

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

 \item Mostre que os seguinte problemas são ou não decidí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)$ é finito.
        \item Dado um AP $M$, determinar se $\overline{L(M)}$ é 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}

\end{enumerate}

\end{document}