\documentclass[12pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\usepackage{latexsym}
\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 2011 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova}  \hfill 29/11/2011

\vspace*{2mm}
\noindent Pesos das questões:

\vspace*{2mm}
%\begin{tabular}[t]{|r|c|c|c|c|c|}\hline
% \textit{questão:} & 1 & 2 & 3 & 4 & 5 \\ \hline
% \textit{peso:} & 3 & 3 & 4 & 4 & 4 \\ \hline
%\end{tabular}
\begin{tabular}[t]{rccccc}
 \textit{questão:} & 1 & 2 & 3 & 4 & 5 \\
 \textit{peso:} & 3 & 3 & 4 & 4 & 4 \\
\end{tabular}

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

 \item Construa uma máquina de Turing que reconheça $\{{\tt 0}^{2^n}\,|\, n\geq 0\}$. \emph{Dica}: Apague a metade
       da palavra de entrada, iterativamente, até atingir a palavra {\tt 0}.

 \item Construa uma gramática que gere $\{{\tt 0}^n{\tt 1}^k{\tt 0}^n\,|\, 0\leq n\leq k\}$.

 \item Seja uma m\'aquina de Turing padr\~ao $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$.
       Suponha que exista um trecho de uma gram\'atica $G$ que gere qualquer forma sentencial
       do tipo $\langle i w \sqcup\rangle$, em que $w\in\Sigma^*$, sendo $\langle$, $i$,
       $\sqcup$ e $\rangle$ vari\'aveis da gram\'atica. Construa um conjunto de regras
       para adicionar a $G$ de tal forma que \[\langle i w \sqcup\rangle\stackrel{*}{\Rightarrow}
       \lambda \mbox{ se e somente se $M$ para se a entrada é $w$.}\]

 \item Mostre que \'e decid\'{\i}vel ou que n\~ao \'e: \textit{dada uma máquina de Turing $M$, verificar se}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \textit{$L(M)$ é recursiva}.
        \item \textit{a computação de $M$ percorre uma transição da forma $\delta(e,a)=[e,b,d]$ (um laço)
              em algum momento, quando a fita é iniciada em branco}.
       \end{list}

 \item Mostre que \'e decid\'{\i}vel ou que n\~ao \'e: \textit{dadas uma gramática livro do contexto $G$ e uma gramática regular $H$, determine se}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(H)\subseteq L(G)$.
        \item $L(G)=L(H)$.
       \end{list}
\end{enumerate}

\end{document}
