\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/Solução doprofessor \hfill {20/12/2012}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize 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}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Variáveis encadeadas: $\mbox{enc}(P)=\{P,A,B,C\}$, $\mbox{enc}(A)=\{A,B,C\}$, $\mbox{enc}(B)=\{B\}$,
				      $\mbox{enc}(C)=\{C\}$. Com isto, a gramática fica assim:							
					    \begin{enumerate}
	             \item[\ ] $P\,\rightarrow\, BC \,|\,  {\tt b}B \,|\, {\tt b} \,|\, {\tt c}C \,|\, {\tt c}$
	             \item[\ ] $A\,\rightarrow\, {\tt b}B \,|\, {\tt b} \,|\, {\tt c}C \,|\, {\tt c}$
	             \item[\ ] $B\,\rightarrow\,{\tt b}B \,|\, {\tt b}$
	             \item[\ ] $C\,\rightarrow\, {\tt c}C \,|\, {\tt c}$
	            \end{enumerate}

        \item Aplicando-se o método de detecção de variáveis inúteis obtém-se inicialmente $V'=\{P,A,B,C\}$ e
				      depois $V''=\{P,B,C\}$, e portanto $A$ é inútil.
       \end{list}

 \item {\footnotesize 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}}

       \textit{Solução:}

        \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item É falsa. Contra-exemplo: $L=\{{\tt 0}\}^*$ e $X=\{0\}^*-\{{\tt 0}^n\,|\, n \mbox{ é primo}\}$, pois
				       aí $L-X=\{{\tt 0}^n\,|\, n \mbox{ é primo}\}$, que não é LLC.
         \item É falsa. Contra-exemplo: $X=L$, pois aí $L-X=\emptyset$, que é LLC.
        \end{list}

 \item {\footnotesize 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}}

       \textit{Solução:} MT de duas fitas não determinística (cada símbolo lido apenas uma vez):

       \begin{picture}(120,30)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](X)(10,10){}
        \node(A)(46,10){}
        \node(B)(82,10){}
        \node[Nmarks=r](C)(118,10){}

        \drawedge[curvedepth=0](X,A){a/a D, $\sqcup$/a D}
				\put(28,7){\makebox(0,0){b/b D, $\sqcup$/b D}}
        \drawloop[loopangle=90](A){b/b D, $\sqcup$/b D}
				\put(46,24){\makebox(0,0){a/a D, $\sqcup$/a D}}
        \drawedge[curvedepth=0](A,B){a/a I, $\sqcup$/$\sqcup$ E}
				\put(64,7){\makebox(0,0){b/b I, $\sqcup$/$\sqcup$ E}}
        \drawloop[loopangle=90](B){b/b D, b/b E}
				\put(82,24){\makebox(0,0){a/a D, a/a E}}
        \drawedge[curvedepth=0](B,C){$\sqcup$/$\sqcup$ I, $\langle$/$\langle$ D}
       \end{picture}

 \item {\footnotesize 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.}

       \textit{Solução:} Uma gramática sensível ao contexto:

					    \begin{enumerate}
	             \item[\ ] $P\,\rightarrow\, {\tt a}PB{\tt a} \,|\,  {\tt aba}$
	             \item[\ ] ${\tt a}B\,\rightarrow\, B{\tt a}$
	             \item[\ ] ${\tt b}B\,\rightarrow\, {\tt bb}$
	            \end{enumerate}

 \item {\footnotesize 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}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Se $L$ não for livre do contexto, $\overline{L}$ pode ser livre do contexto?
        \item Sim. Sendo $L$ sensível ao contexto, é recursiva; e a classe das recursivas é fechada sob complementação.
        \item Sim. Existe linguagem recursivamente enumerável não recursiva. Seja $\overline{L}$ uma linguagem dessas.
				      Com isto, $L$ não é recursivamente enumerável; logo, $L$ não é recursiva. Assim, existe $L$ não
							recursiva cujo complemento é 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?

       \textit{Solução:} $$\mbox{PD é decidível se e somente se }\{p\in \mbox{PD}\,|\, \mbox{ a resposta a } p
			       \mbox{ é \emph{sim}}\} \mbox{ é recursiva.}$$


\end{enumerate}

\end{document}
