\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 N \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=\{xy\in\{{\tt 0},{\tt 1}\}^*\,|\, |x|=|y| \mbox{ e } y\not=x^R\}$.
       \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 máquina de Turing \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 $\{w\overline{w}\,|\,w\in\{{\tt a},{\tt b}\}^*\}$.
       Definição recursiva de complemento:
       \begin{itemize}
        \item $\overline{\lambda}=\lambda$;
        \item $\overline{{\tt a}x}={\tt b}\overline{x}$, $\overline{{\tt b}x}={\tt a}\overline{x}$.
       \end{itemize}

 \item Na questão 9 da lista de exercícios sugeriu-se usar não determinismo para mostrar que as linguagens
       recursivamente enumeráveis são fechadas sob concatenação. Para este problema, o uso de não determinismo:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item É necessário? Justifique.
        \item É conveniente? Justifique.
       \end{list}
 \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 dos programas em Java que param é recursivamente enumerável.
        \item Se uma linguagem n\~ao \'e recursiva, então é recursivamente enumerável.
        \item A mesma m\'aquina de Turing que aceite por parada aceita também por parada em
              estado final, bastando que se faça finais todos os seus estados.
        \item Se uma linguagem $L$ é livre do contexto, então $L-\{\lambda\}$ é sensível ao contexto.
       \end{list}

\end{enumerate}


\end{document}
 
