\documentclass[12pt, a4paper]{report}
\newcounter{conta}
\pagestyle{empty}
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}

\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG \\
{\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Quarta Prova} \hfill 17/04/02

\vspace*{.5cm}
{\bf $\Rightarrow$ Cada quest\~ao vale 3 pontos.}

\begin{enumerate}

 \item Seja a gram\'atica $G=(\{E,Z\},\{\verb+a+,\verb|+|,\verb+(+,\verb+)+\},R,E)$,
       onde $R$ consta das regras:
       \begin{enumerate}
        \item[\ ] $E \,\,\rightarrow\,\, \verb+(+ E \verb+)+ \,\,|\,\, \verb+a+ \,\,|\,\,
                                         \verb+(+ E \verb+)+ Z \,\,|\,\, \verb+a+ Z$
        \item[\ ] $Z \,\,\rightarrow\,\, \verb|+| E \,\,|\,\, \verb|+| E Z$
       \end{enumerate}
       Obtenha um AP que reconhe\c ca $L(G)$ usando o m\'etodo apresentado no curso.
       (Isto \'e, obtenha uma GLC equivalente a $G$ na FNG, etc\ldots)

 \item Mostre que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X\subseteq L$ e $L$ \'e uma LLC, $X$ tamb\'em \'e uma LLC.
        \item As linguagens livres do contexto s\~ao fechadas sob diferen\c ca.
       \end{list}

 \item Construa uma MT (padr\~ao) que aceite a linguagem denotada pela express\~ao
       regular $(00)^+$, sendo $\{\verb+0+,\verb+1+\}$ o alfabeto da linguagem,
       usando um n\'umero m\'{\i}nimo de transi\c c\~oes.

 \item Construa uma MT (de qualquer um dos tipos vistos no curso, inclusive
       combinados) que reconhe\c ca:
       \[\{ww^Rz\,\,|\,\, w,z\in\{\verb+a+,\verb+b+\}^* \mbox{ e }
         |w|\geq |z|\}\mbox{.}\]
       Restri\c c\~oes: (1) passar sobre a entrada apenas uma vez, e (2) especificar
       o menor n\'umero poss\'{\i}vel de transi\c c\~oes.

 \item Mostre que sim ou que n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item As linguagens recursivas s\~ao fechadas sob diferen\c ca.
        \item As linguagens recursivamente enumer\'aveis s\~ao fechadas
              sob diferen\c ca.
       \end{list}

\end{enumerate}

\end{document}
