\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} \hfill 25/06/2013

\vspace*{4mm}
As primeiras 5 questões valem 4 pontos cada uma; a última, 3 pontos.
\vspace*{3mm}
\begin{enumerate}
 \item Suponha que $L$ é uma linguagem \underline{não} livre do contexto. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X$ é finita então $L-X$ não é livre do contexto.
        \item Se $X$ é regular ent\~{a}o $L-X$ pode ser livre do contexto, mas pode não ser.
       \end{list}

 \item Construa uma máquina de Turing padrão que reconheça $a^*b^*$.

 \item Faça uma MT de duas fitas não determinística que reconheça
       $\{x{\tt b}^n{\tt c}^{|x|+n}\,|\, x\in \{{\tt a},{\tt b}\}^* \mbox{ e } n\geq 0\}$. Use
			 não determinismo para encontrar o comprimento do prefixo $x$.

 \item Construa uma gramática irrestrita que gere $\{w{\tt c}w \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.
       Se a gramática for sensível ao contexto e tiver menos de 10 regras, ganha um ponto a mais.

 \item Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

  \item Mostre que o problema de, \emph{dada uma máquina de Turing $M$, determinar se $M$ aceita a
	      palavra {\tt 000}}, é indecidível.

\end{enumerate}

\end{document}
