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

\vspace*{2mm}
\begin{enumerate}
 \item {footnotesize Seja a gram\'atica livre do contexto:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, B P A  \,|\,  A$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\,B{\tt ba} \,|\, \lambda$
	     \end{enumerate}
       Usando os métodos vistos no curso, construa uma gramática equivalente que satisfaça:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A única regra $\lambda$, se houver, é $P\,\rightarrow\,\lambda$, sendo $P$ o símbolo de partida;
        \item A gramática não contém regras de cadeias (regras unitárias).
       \end{list}}

       \textit{Solução:}

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

 \item {footnotesize Prove que as seguintes afirmativas são ou não verdadeiras:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X\subseteq L$ e $L$ é uma LLC, então $X$ é uma LLC.
        \item Se $X\subseteq L$ e $L$ não é uma uma LLC, então $X$ não é uma LLC.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É falsa. Contra-exemplo: $L=\Sigma^*$ e $X=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\, n\geq 0\}$.
        \item É falsa. Contra-exemplo: $X=\emptyset$.
       \end{list}

 \item {footnotesize Faça uma MT de qualquer tipo (uma ou mais fitas, determinística ou não) que reconheça
       $\{ww\,|\,\in\{{\tt a},{\tt b}\}^*\}$.}

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

       \begin{picture}(160,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(C)(118,10){}
        \node[Nmarks=r](D)(150,10){}

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

 \item {footnotesize Construa uma gramática irrestrita que gere $\{ww \,|\, w\in\{{\tt a},{\tt b}\}^+\}$.
       Se ela for sensível ao contexto, vale um ponto extra.}

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

					    \begin{enumerate}
	             \item[\ ] $P\,\rightarrow\, {\tt a}PA \,|\,  {\tt b}PB \,|\, X{\tt a} \,|\, Y{\tt b}$
	             \item[\ ] ${\tt a}A\,\rightarrow\, A{\tt a}$
	             \item[\ ] ${\tt b}A\,\rightarrow\, A{\tt b}$
	             \item[\ ] ${\tt a}B\,\rightarrow\, B{\tt a}$
	             \item[\ ] ${\tt b}B\,\rightarrow\, B{\tt b}$
	             \item[\ ] $XA\,\rightarrow\, X{\tt a}$
	             \item[\ ] $XB\,\rightarrow\, X{\tt b}$
	             \item[\ ] $YA\,\rightarrow\, Y{\tt a}$
	             \item[\ ] $YB\,\rightarrow\, Y{\tt b}$
	             \item[\ ] $X\,\rightarrow\, {\tt a}$
	             \item[\ ] $Y\,\rightarrow\, {\tt b}$
	            \end{enumerate}

 \item {footnotesize Responda, justificando:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Se $L_1$ e $L_2$ forem livres do contexto, $L_1\cup\overline{L_2}$ pode ser livre do contexto? Pode não ser
%				      livre do contexto?
        \item Se $L_1$ e $L_2$ são sensíveis ao contexto, $L_1\cup L_2$ é sensível ao contexto?
        \item Se $L$ não for recursivamente enumerável, $\overline{L}$ pode ser recursivamente enumerável?
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sim. Se $G_1=(V_1,\Sigma_1,R_1,P_1)$ gera $L_1$, $G_2=(V_2,\Sigma_2,R_2,P_2)$ gera $L_2$ e (sem
				      perda de generalidade) $V_1\cap V_2=\emptyset$, então $(V_1\cup V_2,\Sigma_1\cup\Sigma_2,R_1\cup R_2\cup
							\{P\rightarrow P_1,P\rightarrow P_2\},P)$, em que $P\not\in V_1\cup V_2$, gera $L_1\cup L_2$.
							 Sendo $G_1$ e $G_2$ sensíveis ao contexto, então $G_3$ também é.
        \item Sim. Como existe linguagem recursivamentre enumerável não recursiva, seja $\overline{L}$ uma delas.
				      Neste caso, $L$ não é 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}
