\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova}/Solução do professor \hfill 25/06/2013

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Suponha que $L$ é uma linguagem \underline{não} livre do contexto. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X$ é finita então $L-X$ não é livre do contexto.
        \item Se $X$ é regular então $L-X$ pode ser livre do contexto, mas pode não ser.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que $X$ seja finita e que $L-X$ seja livre do contexto. Como $X\cap L$ é finita, é também
				      livre do contexto. Como as linguagens livres do contexto são fechadas sob união,
							$(L-X)\cup(X\cap L)$ é livre do contexto. Mas $(L-X)\cup(X\cap L)=L$ e $L$ não é livre do contexto.
			        Portanto, se $X$ é finita então $L-X$ não é livre do contexto.
        \item $L-\Sigma^*=\{\}$, $\Sigma^*$ é regular e $\{\}$ é livre do contexto. Por outro lado, $L-\{\}=L$ e
				      $\{\}$ é regular. Portanto, se $X$ é regular então $L-X$ pode ser livre do contexto, mas pode não ser.
       \end{list}

 \item {\footnotesize Construa uma máquina de Turing padrão que reconheça $a^*b^*$.}

       \textit{Solução}:

       Considerando $\Sigma=\{{\tt a},{\tt b}\}$:

       \begin{picture}(120,25)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(30,15){}
        \node(2)(50,15){}
        \node[Nmarks=r](3)(70,15){}

        \drawloop[loopangle=270](1){{\tt a/a D}}
        \drawedge(1,2){{\tt b/b D}}
        \drawloop[loopangle=270](2){{\tt b/b D}}
        \drawedge(2,3){{\tt $\sqcup$/$\sqcup$ D}}
       \end{picture}
			

 \item {\footnotesize Faça uma MT de duas fitas não determinística que reconheça
       $\{x{\tt b}^n{\tt c}^{|x|+n}\,|\, x\in \{{\tt a},{\tt b}\}^* \mbox{ e } n\geq 0\}$. Use
			 não determinismo para encontrar o comprimento do prefixo $x$.}

       \textit{Solução}:


       \begin{picture}(160,25)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](0)(10,15){}
        \node(1)(45,15){}
        \node(2)(80,15){}
        \node(3)(115,15){}
        \node[Nmarks=r](4)(150,15){}
        \node[Nmarks=r](5)(10,2){}

        \drawedge(0,1){\shortstack{{\tt a/a D, $\sqcup$/$\sqcup$ D} \\ {\tt b/b I, $\sqcup$/$\sqcup$ I}}}
        \drawloop[loopangle=270](1){\shortstack{{\tt a/a D, $\sqcup$/$\sqcup$ D} \\ {\tt b/b D, $\sqcup$/$\sqcup$ D}}}
        \drawedge(1,2){{\tt b/b D, $\sqcup$/$\sqcup$ D}}
        \drawloop[loopangle=270](2){{\tt b/b D, $\sqcup$/$\sqcup$ D}}
        \drawedge(2,3){{\tt c/c I, $\sqcup$/$\sqcup$ E}}
        \drawloop[loopangle=270](3){{\tt c/c D, $\sqcup$/$\sqcup$ E}}
        \drawedge(3,4){{\tt $\sqcup$/$\sqcup$ I}, {\tt $\langle$/$\langle$ I}}
        \drawedge(0,5){{\tt $\sqcup$/$\sqcup$ I}, {\tt $\sqcup$/$\sqcup$ I}}
       \end{picture}

 \item {\footnotesize Construa uma gramática irrestrita que gere $\{w{\tt c}w \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.
       Se a gramática for sensível ao contexto e tiver menos de 10 regras, ganha um ponto a mais.}

       \textit{Solução}:

       Uma gramática sensível ao contexto:
       \begin{tabbing}
			  xxxx\= $P \,\rightarrow\, {\tt a} P A \,|\, {\tt b} P B \,|\, {\tt c}$xxx\= \kill
			      \> $P \,\rightarrow\, {\tt a} P A \,|\, {\tt b} P B \,|\, {\tt c}$ \\
						\> ${\tt c} A \,\rightarrow\, {\tt ca}$ \> ${\tt c} B \,\rightarrow\, {\tt cb}$ \\
			      \> ${\tt a} A \,\rightarrow\, A {\tt a}$ \> ${\tt b} A \,\rightarrow\, A {\tt b}$ \\
			      \> ${\tt a} B \,\rightarrow\, B {\tt a}$ \> ${\tt b} B \,\rightarrow\, B {\tt b}$
			 \end{tabbing}
\newpage
 \item {\footnotesize Seja $L$ uma linguagem {\em n\~ao\/} recursiva. Mostre que:
       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item $\overline{L}$ n\~ao \'e recursiva.
        \item Se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\bf  \alph{conta})}{\usecounter{conta}}
        \item Se $\overline{L}$ fosse recursiva, $\overline{\overline{L}}=L$ seria recursiva.
        \item Suponha que $L$ é LRE e que $\overline{L}$ também é LRE. Neste caso, $L$ é recursiva.
				      Logo, como $L$ não é recursiva, se $L$ \'e LRE, ent\~ao $\overline{L}$ n\~ao \'e LRE.
       \end{list}

  \item {\footnotesize Mostre que o problema de, \emph{dada uma máquina de Turing $M$, determinar se $M$ aceita a
	      palavra {\tt 000}}, é indecidível.}

       \textit{Solução}:

       \underline{Uma solução}: O problema da parada pode ser reduzido a este produzindo-se uma máquina de Turing $M'$,
			 a partir de $M$ e $w$, que:
			 \begin{enumerate}
			  \item[1.] apaga sua entrada;
			  \item[2.] escreve a palavra $w$ na fita;
			  \item[3.] volta cabeçote para inícicio de $w$;
				\item[4.] se comporta como $M$.
       \end{enumerate}
			 Supõe-se que $M'$ reconhece por parada. Com isto, qualquer que seja a palavra de entrada $w'$ para $M'$,
			 \textbf{inclusive {\tt 000}}:
	     $$M' \mbox{ aceita } w' \mbox{ se e somente se } M \mbox{ para se sua entrada é }w\mbox{.}$$
			
       \underline{Outra solução}: Como a propriedade ${\tt 000}\in L(M)$ não é trivial, a linguagem
			 $\{R\langle M\rangle\,|\,{\tt 000}\in L(M)\}$ não é recursiva. Logo o problema de determinar se
			 ${\tt 000}\in L(M)$ é indecidível.
\end{enumerate}

\end{document}
