\documentclass[11pt,a4paper]{book}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Prova Suplementar} \hfill {\bf Dura\c{c}\~ao: 90 minutos} \hfill 10/12/2007

\vspace*{5mm}
\noindent A \'ultima quest\~ao vale 7 pontos e as restantes 5 pontos.

\vspace*{3mm}
\begin{enumerate}
 \item Seja a defini\c c\~ao recursiva de {\em reverso\/} de uma palavra sobre $\Sigma$:
       \begin{itemize}
        \item $\lambda^R=\lambda$;
        \item se $x\in\Sigma^*$ e $a\in\Sigma$ ent\~ao $(xa)^R=ax^R$.
       \end{itemize}
       Prove, por indu\c{c}\~ao, que $(xy)^R=y^Rx^R$.
      
 \item Mostre que sim ou que n\~ao: para todo AFN existe um equivalente com
       um \'unico estado final.

 \item Mostre que se $L$ \'e uma linguagem n\~ao regular, ent\~ao a elimina\c{c}\~ao de
       um conjunto finito de palavras da mesma n\~ao \'e suficiente para torn\'a-la regular.

 \item Construa uma gram\'atica livre do contexto para $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m+n>k\}$.

 \item Para cada problema, mostre que ele \'e ou que n\~ao \'e decid\'{\i}vel:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Determinar se uma MT, ao iniciar com a fita em branco, chega a ler o s\'{\i}mbolo de
              in\'{\i}cio, $\langle$, em algum momento. 
        \item Determinar se uma gram\'atica regular \'e amb\'{\i}gua.
       \end{list}

\end{enumerate}

\end{document}