\documentclass[11pt,a4paper]{book}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{4mm}
\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 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova} \hfill 02/12/2009

\begin{flushleft}
Valores das quest\~oes 1 e 2: 3 pontos; quest\~ao 3: 6 pontos; quest\~oes 4, 5 e 6: 2 pontos.
\end{flushleft}

\begin{enumerate}
 \item Fa\c ca uma MT n\~ao determin\'{\i}stica de duas fitas que implemente o seguinte algoritmo n\~ao
       determin\'{\i}stico para determinar se um n\'umero dado como entrada \textbf{n\~ao \'e} primo:
       \begin{enumerate} \em
        \item[1.] selecione (n\~ao deterministicamente) um n\'umero maior ou igual a 2 e menor do que o
                  dado como entrada (na fita 1) e escreva-o na fita 2;
        \item[2.] verifique se o n\'umero dado como entrada \'e divis\'{\i}vel pelo da fita 2; \\
                  se for, aceite; se n\~ao for, rejeite.
       \end{enumerate}

 \item Fa\c{c}a uma gram\'atica que gere $\{w\overline{w}\,|\, w\in\{{\tt 0},{\tt 1}\}^*\}$, em que $\overline{w}$
       \'e assim definida, recursivamente:
       \begin{enumerate}
        \item[(i)] $\overline{\lambda}=\lambda$; \ \ \ \ 
              (ii) $\overline{{\tt 0}y}={\tt 1}\overline{y}$ e $\overline{{\tt 1}y}={\tt 0}\overline{y}$ para
                   $y\in\{{\tt 0},{\tt 1}\}^*$.
       \end{enumerate}

 \item Sejam as seguintes classes de linguagens, \emph{da mais restrita para a menos restrita}:
       \begin{enumerate}
        \item[i.] regular (mais restrita);
        \item[ii.] livre do contexto;
        \item[iii.] recursiva; e
        \item[iv.] recursivamente enumer\'avel (menos restrita).
       \end{enumerate}
       Dada uma linguagem $L$ qual \'e a classe \emph{mais restrita} a que, \emph{necessariamente},
       pertence $\overline{L}$ para cada caso a seguir? Justifique cada resposta.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L$ \'e regular;
        \item $L$ \'e livre do contexto;
        \item $L$ \'e recursiva;
        \item $L$ \'e recursivamente enumer\'avel.
       \end{list}

 \item Mostrar que o problema ``\emph{dados uma m\'aquina $M$ e uma express\~ao regular $r$, determinar se
        $L(M)\subseteq L(r)$}''
       \'e decid\'{\i}vel nos casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $M$ \'e um aut\^omato finito; \ \ \ \ (b) $M$ \'e um aut\^omato de pilha.
       \end{list}

 \item Mostrar que o problema ``\emph{dada uma express\~ao regular $r$ e um aut\^omato de pilha $M$, determinar se
        $L(r)\subseteq L(M)$}'' \'e indecid\'{\i}vel.

 \item Mostrar que o problema ``\emph{dada uma m\'aquina de Turing $M$ e um estado $e$, determinar se
        $M$ atinge o estado $e$ se a palavra de entrada for $\lambda$}'' \'e indecid\'{\i}vel.
\end{enumerate}

\end{document}
