\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2001 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Quarta Prova} \hfill 05/07/2001

\vspace*{2mm}
\noindent{\bf Valores das quest\~oes:} A primeira vale 1 ponto e as restantes 4 pontos cada uma. {\em Escolha apenas 4 dentre as \'ultimas 5 quest\~oes.}

\vspace*{2mm}
\begin{enumerate}
 \item Suponha que um procedimento de decis\~ao $P$ seja programado mediante uma m\'aquina de Turing $M$,
       de forma que $w\in L(M)$ se, e somente se, $w$ representa uma inst\^ancia de $P$ para a qual a
       reposta \'e {\em sim\/}. Que caracter\'{\i}stica $L(M)$ deve ter para que $P$ seja considerado um
       problema decid\'{\i}vel (ou seja, que tenha solu\c c\~ao)?

 \item Seja $n_a(w)$ o n\'umero de s\'{\i}mbolos $a$ da palavra $w$. Assim, por exemplo: $n_0(001010)=4$,
       $n_1(001010)=2$.
       Mostre que a linguagem \[\{w\in\{a,b,c\}^*\,\,|\,\, n_a(w)=n^2 \mbox{ para algum $n$ e }
       n_b(w)=n_c(w)\}\] n\~ao \'e uma linguagem livre do contexto.

 \item Construa uma m\'aquina de Turing para a linguagem dos par\^enteses balanceados. Use qualquer
       modelo de m\'aquina de Turing (com v\'arias fitas, n\~ao determinismo, etc.).

       A linguagem dos par\^enteses balanceados \'e aquela gerada pela gram\'atica que tem as regras:
       \begin{enumerate}
        \item[\ ] $P\rightarrow (P) \,|\, PP \,|\, \lambda$
       \end{enumerate}

 \item Mostre que qualquer linguagem recursivamente enumer\'avel pode ser reco\-nhe\-cida por uma m\'aquina de
       Turing padr\~ao com um \'unico estado final.

 \item Construa uma gram\'atica irrestrita que gere a linguagem \[\{ww^Rw^R\,\,|\,\, w\in\{a,b\}^*\}\mbox{.}\]

 \item Sejam $L$ uma linguagem recursivamente enumer\'avel e $R$ uma linguagem recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-R$ \'e recursivamente enumer\'avel.
        \item $L-R$ pode n\~ao ser recursiva.
        \item $R-L$ pode n\~ao ser recursivamente enumer\'avel.
       \end{list}

\end{enumerate}
\end{document}
