\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

%\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turma W\hfill {20/12/2012}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 40 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 4 pontos, exceto a última, que vale 3 pontos.

\vspace*{2mm}
\begin{enumerate}
 \item Seja a gram\'atica livre do contexto:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, B P A  \,|\,  A$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\,B{\tt ba} \,|\, \lambda$
	     \end{enumerate}
       Usando os métodos vistos no curso, construa uma gramática equivalente que satisfaça:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A única regra $\lambda$, se houver, é $P\,\rightarrow\,\lambda$, sendo $P$ o símbolo de partida;
        \item A gramática não contém regras de cadeias (regras unitárias).
       \end{list}

 \item Prove que as seguintes afirmativas são ou não verdadeiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X\subseteq L$ e $L$ é uma LLC, então $X$ é uma LLC.
        \item Se $X\subseteq L$ e $L$ não é uma uma LLC, então $X$ não é uma LLC.
       \end{list}

 \item Faça uma MT de qualquer tipo (uma ou mais fitas, determinística ou não) que reconheça
       $\{ww\,|\,\in\{{\tt a},{\tt b}\}^*\}$.

 \item Construa uma gramática irrestrita que gere $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^+\}$. Se ela for sensível ao
       contexto, vale um ponto extra.

 \item Responda, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Se $L_1$ e $L_2$ forem livres do contexto, $L_1\cup\overline{L_2}$ pode ser livre do contexto? Pode não ser
%				      livre do contexto?
        \item Se $L_1$ e $L_2$ são sensíveis ao contexto, $L_1\cup L_2$ é sensível ao contexto?
        \item Se $L$ não for recursivamente enumerável, $\overline{L}$ pode ser recursivamente enumerável?
       \end{list}

 \item Um problema de decisão $PD$ tem solução se para cada instância $p\in PD$ existe uma MT que, recebendo $p$ como
       entrada, determina a resposta correta para $p$. Que relação existe entre decidibilidade (de problemas de decisão)
       e classes de linguagens reconhecíveis por MTs?


\end{enumerate}

\end{document}
