\documentclass[11pt, a4paper]{report}

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

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Lista de Exercícios Preparatória para a Terceira Prova}

\vspace*{3mm}
\begin{enumerate}
 \item Prove que as seguintes afirmativas s\~{a}o ou n\~ao verdadeiras, considerando
       os casos em que (i) $X$ \'e finita e (ii) $X$ \'e regular.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma LLC, ent\~{a}o $L-X$ \'{e} uma LLC.
        \item Se $L$ n\~{a}o \'{e} uma LLC, ent\~{a}o $L-X$ n\~{a}o \'{e} uma LLC.
       \end{list}

 \item Crie MTs padrão que reconhe\c cam as seguintes linguagens de alfabeto $\{{\tt a},{\tt b},{\tt c}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item ${\tt a}^*$.
        \item $\{{\tt a}^n{\tt b}^n\,|\, n\geq 0\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^{m+n}\,|\, m,n\geq 0\}$.
       \end{list}

 \item Faça uma MT de duas fitas que reconheça $\{{\tt a}^m{\tt b}^n{\tt c}^{m+n}\,|\, m,n\geq 0\}$.

 \item Fa\c ca uma MT que reconhe\c ca a linguagem $\{wxw\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item de duas fitas determin\'{\i}stica;
        \item de duas fitas n\~ao determin\'{\i}stica.
       \end{list}

 \item Construa gram\'aticas irrestritas que gerem:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^{m}{\tt b}^n{\tt a}^{m}{\tt b}^n \,|\, m,n\geq 0\}$.
        \item $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.
       \end{list}

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $L\cup F$ n\~ao \'e recursiva, se $F$ \'e finita.
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

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

 \item Mostre que a linguagem $\{R\langle M,w\rangle\,\,|\,\,$ existe estado $e$ tal que $M$
       passe duas vezes por $e$ ao processar $w\}$ \'e recursiva.

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

 \item Mostre que se o problema da parada fosse decid\'{\i}vel, ent\~ao \mbox{toda LRE seria recursiva}.

 \item Mostre que é decidível: dada uma MT $M$, determinar se $M$ vai mover o cabe\c cote para a esquerda 
       alguma vez, para a entrada $\lambda$.

 \item Para cada PD a seguir, mostre que o mesmo \'e indecid\'{\i}vel:
       \begin{list}{\bf \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.
       \end{list}

\end{enumerate}

\end{document}
