\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\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 Prova} -- Turma N\hfill {28/06/2012}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 3 pontos.

\vspace*{2mm}
\begin{enumerate}
 \item Fa\c ca uma MT de duas fitas que reconheça $\{{\tt a}^m{\tt b}^n\,|\, m>n\geq 0\}$. Use duas fitas.

 \item Crie uma MT padrão que reconheça $\{x{\tt a}^n{\tt b}^n\,|\, n\geq 0, |x|=n,\, x\in\{{\tt a},\, {\tt b}\}^*\}$.
       Use duas fitas e não determinismo.

 \item Construa uma gramática irrestrita que gere
       $\{x{\tt a}^n{\tt b}^n\,|\, n\geq 0, |x|=n,\, x\in\{{\tt a},\, {\tt b}\}^*\}$.

 \item Mostre que sim ou que não:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item se $L_1$ é LRE e $L_2$ é recursiva, então $L_1-L_2$ é LRE.
        \item se $L_1$ é recursiva e $L_2$ é LRE, então $L_1-L_2$ é LRE.
       \end{list}

 \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}
