\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 D\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:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, A  \,|\,  BC$
	      \item[\ ] $A\,\rightarrow\, B \,|\, C$
	      \item[\ ] $B\,\rightarrow\,{\tt b}B \,|\, {\tt b}$
	      \item[\ ] $C\,\rightarrow\, {\tt c}C \,|\, {\tt c}$
	     \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Use o método visto no curso para criar uma gramática equivalente sem regras unitárias (regras de cadeias).
        \item Mostre que a gramática criada contém símbolos inúteis (um ou mais).
       \end{list}

 \item Prove que as seguintes afirmativas s\~{a}o ou n\~ao verdadeiras, considerando
       que $X$ é uma linguagem qualquer:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma LLC, ent\~{a}o $L-X$ \'{e} uma LLC.
        \item Se $L$ n\~{a}o \'{e} uma LLC, ent\~{a}o $L-X$ n\~{a}o \'{e} uma LLC.
       \end{list}

 \item Faça uma MT de duas fitas que reconheça $\{ww^R\,|\,\in\{{\tt a},{\tt b}\}^*\}$, tal que
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item cada símbolo da palavra de entrada pode ser lido no máximo duas vezes;
        \item a MT pode ser determinística ou não determinística;
       \end{list}

 \item Construa uma gramática irrestrita que gere $\{{\tt a}^{n}{\tt b}^n{\tt a}^n \,|\, n\geq 1\}$. Se ela for
       sensível ao contexto, vale um ponto a mais.

 \item Responda, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Se $L$ não for livre do contexto, $\overline{L}$ pode ser livre do contexto?
        \item Se $L$ for sensível ao contexto, $\overline{L}$ é recursiva?
        \item Se $L$ não for recursiva, $\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}
