\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012\\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: até 28/06/2012 antes da prova

\vspace*{2mm}
\noindent \textbf{\underline{Importante}:}
\begin{quote}
 \textbf{Questões ilegíveis não serão corrigidas (nota zero).\\
 Quem copiar ou deixar copiar uma questão terá nota zero na lista. \\
 Locais de recebimento: salas 3018, 4010 e 4023 ou em sala de aula. \\
 Após a 4a prova começa o primeiro dia de atraso.}
\end{quote}

\begin{enumerate}
 \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 $\{wxwx\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 Construa uma gram\'atica sens\'{\i}vel ao contexto que reconheça $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^+\}$.

 \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 Seja $\Sigma=\{{\tt 0},{\tt 1}\}$. Considerando que o conjunto de todas as MTs de alfabeto de entrada
       $\Sigma$ \'e enumer\'avel, mostre que existe uma linguagem, subconjunto de $\Sigma^*$, que n\~ao \'e LRE.
       Para isso, use o argumento da diagonaliza\c c\~ao de Cantor (veja a p\'agina 25 do livro-texto).

 \item Um problema de decisão $PD$ tem solução se para cada instância $p\in PD$ existe uma MT que, recebendo $p$ como
       entrada, determina a resposta correta para $p$. Que relação existe entre decidibilidade (de problemas de decisão)
       e classes de linguagens reconhecíveis por MTs?
\end{enumerate}

\end{document}
