\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{amsfonts}

\usepackage{fullpage}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Terceira Prova} --- Turma N \hfill 30/6/2015

\vspace*{2mm}
\noindent \textbf{Escolha 5 questões para fazer; cada uma valerá 5 pontos.}

%\vspace*{2mm}
\begin{enumerate}
 \item Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X$ é regular e $L$ não é LLC, então $L-X$ pode ser LLC e pode não ser LLC.
        \item Se $X$ é finita e $L$ não é uma LLC, então $L-X$ não é uma LLC.
       \end{list}

 \item Crie MTs que reconheçam $a(a+b+c)^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item por parada em estado final;
        \item por parada.
       \end{list}

 \item Faça uma MT multifita que reconheça $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=
       2(n_{\tt b}(w)+n_{\tt c}(w))\}$.

 \item Mostre que se $L$ é uma LRE e $X$ é uma LLC, então:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-X$ é LRE.
        \item $X-L$ pode ser LRE ou não.
       \end{list}

 \item Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O problema a seguir é \emph{decidível}:
				      \begin{quote}
               dada uma MT $M$, determinar se existe estado $e$ de $M$ tal que $M$ passe duas vezes por $e$
				       ao processar $\lambda$.
							\end{quote}
							\emph{Dica}: diga como alterar a MT universal para resolver tal	problema.
        \item O problema a seguir é \emph{indecidível}:
				      \begin{quote}
               dada uma MT $M$ e um estado $e$ de $M$, determinar se $M$ passa duas vezes por $e$
 				       ao processar $\lambda$.
							\end{quote}
							\emph{Dica}: reduza o problema da fita em branco a este.
       \end{list}

 \item Mostre que a linguagem a seguir é LRE: $$\{R\langle M,e\rangle \,|\, M \mbox{ passa duas vezes pelo estado } e
       \mbox{ ao processar } \lambda\}$$ \emph{Dica}: diga como alterar a MT universal para reconhecer tal
			 linguagem.
\end{enumerate}

\end{document}
