\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\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{2}^{\mbox{\underline{o}}}$ semestre de 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova}           \hfill {02/12/2008}

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

\vspace*{5mm}
\begin{enumerate}

 \item Construa uma MT que aceite a linguagem denotada pela express\~ao
       regular $01(0+1)^*$, sendo $\{{\tt 0},{\tt 1}\}$ o alfabeto da linguagem,
       assumindo como crit\'erio de reconhecimento a parada. Assim, a MT deve
       parar se, e somente se, a palavra de entrada pertencer a $L(01(0+1)^*)$.

 \item Construa uma gram\'atica que gere a linguagem $\{xa^nb^{n} \,|\, x\in \{{\tt a},{\tt b}\}^*,\, n\geq 0
       \mbox{ e }|x|=n\}$.

 \item Construa uma MT que aceite $\{xa^nb^{n} \,|\, x\in \{{\tt a},{\tt b}\}^*,\, n\geq 0
       \mbox{ e }|x|=n\}$. Pode usar mais de uma fita, n\~ao determinismo etc.

 \item Mostre que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L_1$ \'e recursivamente enumer\'avel e $L_2$ \'e recursiva, $L_1-L_2$ \'e recursivamente enumer\'avel.
        \item Se $L_1$ \'e recursiva e $L_2$ \'e recursivamente enumer\'avel, $L_1-L_2$ \'e recursivamente enumer\'avel.
       \end{list}
\end{enumerate}

\end{document}
 