\documentclass[11pt,a4paper]{book}

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

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\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 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova} \hfill 26/11/2008

\vspace*{3mm}
\begin{flushleft}
Valor de cada quest\~ao: 4 pontos as tr\^es primeiras; 6 pontos a \'ultima.
\end{flushleft}

\begin{enumerate}

 \item Construa uma m\'aquina de Turing n\~ao determin\'{\i}stica de duas fitas que reconhe\c{c}a:
       \[\{{\tt 0}^nxx^R\,|\, n\geq 0,\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=n\}\mbox{.}\]
       O cabe\c{c}ote da \textit{fita de entrada\/} s\'o poder\'a se movimentar para a \textit{direita\/}
       (ou seja, a m\'aquina dever\'a dar uma \'unica passada sobre a palavra de entrada).

 \item Fa\c{c}a uma gram\'atica irrestrita que gere:
       \[\{{\tt a}^nx{\tt b}^n\,|\, n\geq 0,\, x\in\{{\tt a},{\tt b}\}^* \mbox{ e } |x|=n\}\mbox{.}\]

 \item Sejam $R$ uma linguagem recursiva e $L$ uma linguagem recursivamente enumer\'avel. Para os
       dois casos a seguir, mostre que a linguagem \'e (necessariamente) recursivamente enumer\'avel ou
       que ela pode n\~ao ser recursivamente enumer\'avel:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-R$.
        \item $R-L$.
       \end{list}
 \item Mostre que os seguintes problemas s\~ao decid\'{\i}veis ou n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dadas uma gram\'atica livre do contexto $G_1$ e uma gram\'atica regular $G_2$,
              determinar se $L(G_2)\subseteq L(G_1)$.
        \item Dadas uma gram\'atica livre do contexto $G_1$ e uma gram\'atica regular $G_2$,
              determinar se $L(G_1)\subseteq L(G_2)$.
        \item Dada uma m\'aquina de Turing $M$, determinar se $L(M)$ \'e linguagem regular.
       \end{list}
\end{enumerate}

\end{document}