\documentclass[12pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2011 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Quarta Prova} - Turma W \hfill 28/06/2011

\vspace*{4mm}

\noindent {As 3 primeiras quest\~oes valem 4 pontos e as duas últimas 2 pontos cada uma.}

\vspace*{1mm}
\begin{enumerate}
 \item Seja a linguagem: $L=\{x\overline{x^R}\,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$. Definição recursiva de complemento:
       \begin{itemize}
        \item $\overline{\lambda}=\lambda$;
        \item $\overline{{\tt 0}x}={\tt 1}\overline{x}$, $\overline{{\tt 1}x}={\tt 0}\overline{x}$.
       \end{itemize}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Responda cada item sem justificar (diga apenas SIM ou NÃO):
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $L$ é regular?
               \item $L$ é livre do contexto?
               \item $L$ é sensível ao contexto?
               \item $L$ é recursiva?
              \end{list}
        \item Faça uma MT \underline{padrão} que aceite $L$.
       \end{list}

 \item Construa o diagrama de estados de uma MT de duas fitas que reconhe\c ca a linguagem $L$ da questão anterior.
       Ela deverá:
       \begin{itemize}
        \item usar a segunda fita para cópia da primeira ou segunda metade da palavra de entrada;
        \item dar apenas uma (se usar não determinismo) ou duas (se for determinística) passadas sobre a palavra
              de entrada.  
       \end{itemize}

 \item Construa uma gram\'atica irrestrita que gere $\{{\tt a}^n{\tt b}^n{\tt a}^n\,|\,n\geq 0\}$.

 \item Na questão 8 da lista de exercícios, pede-se para mostrar que ``se uma linguagem não é recursiva, então
       ao acrescentar um conjunto finito de palavras a ela, o resultado ainda é uma linguagem não recursiva''.
       Explique por que isto acontece.

 \item Responda SIM (correto) ou NÃO (incorreto). Para cada resposta certa voc\^e ganha meio ponto
       e para cada resposta errada perde meio ponto:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item O conjunto de todos os programas em Java é recursivo.
        \item Se uma linguagem é recursiva, mas não é recursivamente enumerável, então seu complemento não é
              recursivamente enumerável.
        \item Uma máquina de Turing que aceite por parada pode reconhecer linguagem não recursiva.
        \item Qualquer linguagem recursivamente enumerável pode ser gerada por uma gramática irrestrita.
       \end{list}

\end{enumerate}


\end{document}
 
