\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage{amsfonts}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Lista de Exercícios} \\
\noindent \emph{Data de entrega}: até 16:40h de 28/6/2016

\vspace*{3mm}
\begin{enumerate}
 \item Prove que a linguagem $\{{\tt a}^{n^2}\,|\,n\in\mathbb{N}\}$ não é LLC.

  \item Sejam \[L_1=\{{\tt a}^n{\tt b}^n \,|\, n\geq 0\} \mbox{ e } L_2=\{w\in\{{\tt a},{\tt b}\}^*
        \,|\, |w| \mbox{ é múltiplo de 5}\}\mbox{.}\] Mostre, para cada linguagem a seguir, que ela é
        ou não  uma LLC:
      	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	       \item $\overline{L_1}$;
	       \item $L_1\cap L_2$;
	       \item $L_1\cap \overline{L_2}$.
	      \end{list}

 \item Prove que se $X$ é finita então as seguintes afirmativas são verdadeiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ é uma LLC, então $L-X$ é uma LLC.
        \item Se $L$ não é uma LLC, então $L-X$ não é uma LLC.
       \end{list}

 \item Faça uma MT com alfabeto de entrada $\{{\tt 0}\}$ que, recebendo como entrada uma palavra
       $w$, concatena $w$ imediatamente à sua direita e retorna o cabeçote para o início.
       Por exemplo, se a configuração inicial for $[i,\langle\underline{{\tt 0}}{\tt 0}]$,
       a configuração final deverá ser $[i,\langle\underline{{\tt 0}}{\tt 000}]$.

 \item Construa uma MT padrão que reconheça $\{w\in\{{\tt a},{\tt b}\}\,|\, n_{\tt a}(w)=n_{\tt b}(w)\}$.

 \item Faça uma MT multifita que reconheça $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=
       n_{\tt b}(w)+n_{\tt c}(w)\}$.

 \item Faça uma MT não determinística de duas fitas que reconheça $\{wxw\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$.
       O não determinismo deve ser usado para ``adivinhar'' o momento em termina o primeiro terço da palavra de
			 entrada.

 \item Construa uma gramática irrestrita que gere $\{ww^Rw \,|\, w\in\{{\tt 0},{\tt 1}\}^*\}$.

 \item Construa uma gramática sensível ao contexto que gere $\{w{\tt c}w \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.

 \item Mostre que se $L$ é uma linguagem \emph{não} recursiva, então:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X$ é finita, então $L\cup X$ não é recursiva.
        \item se $X$ é regular, então $L\cup X$ pode ser recursiva ou não.
       \end{list}

 \item Mostre que se $L$ é uma LRE e $X$ é uma linguagem regular, então:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-X$ é LRE.
        \item $X-L$ pode ser LRE ou não.
       \end{list}

 \item Mostre que as LREs são fechadas  sob concatenação por meio de MTs. {\em Dica}: Use duas fitas e não
       determinismo.

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

 \item Mostre que se o problema da parada fosse decidível, então \mbox{toda LRE seria recursiva}.

 \item Para cada PD a seguir, mostre que o mesmo é decidível ou indecidível:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT $M$, determinar se $M$ vai mover o cabeçote para a esquerda alguma vez, para
				      a entrada $\lambda$.
        \item Dados uma MT $M$ e uma palavra $w$, determinar se existe estado $e$ tal que $M$ passe duas
				      vezes por $e$ ao processar $w$.
        \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 Dados uma MT $M$ e um símbolo $a$ de $M$, determinar se a computação de $M$
              para a entrada $\lambda$ escreve $a$ na fita em algum momento.
       \end{list}

\end{enumerate}

\end{document}
