\documentclass[12pt, a4paper]{report}
\newcounter{conta}
\pagestyle{empty}
\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 2002 \\ 
Professor: Newton Jos\'{e} Vieira

\noindent {\bf Quarta Prova} \hfill 13/03/03

\vspace*{2mm}

\noindent{\bf Cada quest\~ao vale 3 pontos.}
\vspace*{1mm}
\begin{enumerate}

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

 \item Construa uma gram\'atica irrestrita que gere a linguagem
       \[\{a^nb^{2n}c^{3n} \,\,\,|\,\,\, n\geq 0\}\mbox{.}\]

 \item Construa uma m\'aquina de Turing para a linguagem dos par\^enteses balanceados.
       Use qualquer modelo de m\'aquina de Turing (com v\'arias fitas, n\~ao determinismo,
       etc.).

       A linguagem dos par\^enteses balanceados \'e aquela gerada pela gram\'atica que tem
       as regras:
       \begin{enumerate}
        \item[\ ] $P\rightarrow (P) \,|\, PP \,|\, \lambda$
       \end{enumerate}

 \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 di\-fe\-ren\-\c ca.
       \end{list}

 \item Sejam $L_1$ e $L_2$ linguagens recursivamente enumer\'aveis. Explique
       como poderia ser constru\'{\i}da uma MT para reconhecer $L_1L_2$.
       Podem ser usadas v\'arias fitas, n\~ao determinismo, etc.
\end{enumerate}

\end{document}
 
