\documentclass[12pt, 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ção} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2014 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W\hfill {15/4/2014}

\vspace*{1mm}
\noindent \textbf{Duração:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada questão:} a segunda questão vale 3 pontos e as restantes 4 pontos cada uma.

\vspace*{2mm}
\begin{enumerate}
 \item Prove que as seguintes afirmativas são ou não verdadeiras, considerando os casos em que (i) $X$ é finita
       e (ii) $X$ é regular.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ é uma LLC, então $X-L$ é uma LLC.
        \item Se $L-X$ não é uma LLC, então $L$ não é uma LLC.
       \end{list}

 \item Crie MTs padrão com uma única transição que reconheçam $(a+b)^+$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Por parada.
        \item Por estado final.
       \end{list}

 \item Faça uma MT que reconheça a linguagem  $\{ww^Rx\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$. Pode usar várias fitas e
       não determinismo.

 \item Construa uma gramática que gere $\{ww^R{\tt c}^{|w|} \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.

 \item Seja $L$ uma linguagem \emph{não} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-F$ não é recursiva, se $F$ é finita.
        \item Se $L$ é LRE, então $\overline{L}$ não é LRE.
       \end{list}

 \item Mostre que são \emph{indecidíveis} os problemas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT $M$, determinar se $|L(M)|=2$.
        \item Dados uma MT $M$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada $\lambda$
				      atinge o estado $e$.
       \end{list}

\end{enumerate}

\end{document}
