\documentclass[11pt,a4paper]{book}

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

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\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}/DINTER
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova} \hfill 19/11/2010

\vspace*{3mm}
\begin{flushleft}
Valor de cada quest\~ao: 4 pontos, exceto a última, que vale 2 pontos.
\end{flushleft}

\begin{enumerate}

 \item Construa uma m\'aquina de Turing n\~ao determin\'{\i}stica de duas fitas que reconhe\c{c}a:
       \[\{x{\tt 1}^n \,|\, n\geq 0,\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=n\}\mbox{.}\]
       O cabe\c{c}ote da \textit{fita de entrada\/} (fita 1) s\'o poder\'a se movimentar para a \textit{direita\/}
       (ou seja, a m\'aquina dever\'a dar uma \'unica passada sobre a palavra de entrada).

 \item Fa\c{c}a uma gram\'atica irrestrita que gere:
       \[\{x{\tt 1}x \,|\, n\geq 0,\, x\in\{{\tt 0} \mbox{ e } {\tt 1}\}^*\}\mbox{.}\]
       Se a gramática for sensível ao contexto, você ganha um ponto a mais.

 \item Sejam $R$ uma linguagem recursiva e $L$ uma linguagem recursivamente enumer\'avel. Para os
       casos a seguir, diga se a linguagem \'e (1) \underline{necessariamente} recursivamente
       enumer\'avel, (2) \underline{necessariamente} não recursivamente enumer\'avel, ou (3) nem uma
       coisa nem outra (ou seja, pode ser recursivamente enumerável e pode não ser). Justifique suas
       respostas (resposta sem justificativa válida será desconsiderada).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\Sigma^*-R$.
        \item $\Sigma^*-L$.
        \item $L-R$.
        \item $R-L$.
       \end{list}

 \item Mostre para cada um dos seguintes problemas, se ele é decid\'{\i}vel ou n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma máquina de Turing $M$ e um número natural $n$, determinar se $M$
              reconhece alguma palavra de $n$ símbolos.
        \item Dada uma máquina de Turing $M$ e uma palavra $w$, determinar se, ao processar $w$, $M$ passa
              por algum estado mais de uma vez.
       \end{list}

 \item No contexto do Teorema de Rice, o que é uma propriedade trivial de LREs? Enuncie o Teorema de Rice
       e dê dois exemplos de aplicação dele.

\end{enumerate}

\end{document}