\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 Terceira Prova} -- Turma N\hfill {27/5/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 $L-X$ é uma LLC.
        \item Se $L$ não é uma LLC, então $L-X$ não é uma LLC.
       \end{list}

 \item Crie MTs padrão, cada uma com uma única transição, que reconheçam $a^+$:
       \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 $\{xww^R\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$. Pode usar várias fitas e
       não determinismo.

 \item Construa uma gramática que gere $\{{\tt 0}^{n}{\tt 1}^n{\tt 0}^n \,|\, n\geq 1\}$.

 \item Seja $L$ uma linguagem \emph{não} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L\cup F$ não é recursiva, se $F$ é finita.
        \item Se $\overline{L}$ é LRE, então $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)$ é uma linguagem regular.
        \item Dados uma MT $M$ e um símbolo $a$ de fita de $M$, determinar se a computação de $M$
              para a entrada $\lambda$ escreve $a$ na fita em algum momento.
       \end{list}
\end{enumerate}

\end{document}
