\documentclass[12pt, 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ção} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2014 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova} -- Turma W/Solução de professor\hfill {15/4/2014}

\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Prove que as seguintes afirmativas são ou não verdadeiras, considerando os casos em que (i) $X$ é finita
       e (ii) $X$ é regular.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ é uma LLC, então $X-L$ é uma LLC.
        \item Se $L-X$ não é uma LLC, então $L$ não é uma LLC.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A primeira é \emph{verdadeira} e a segunda é \emph{falsa}: \\
				      (i) Como $X$ é finita, $X-L$ é finita e, portanto, é uma LLC. \\
							(ii) Se $\Sigma$ é o alfabeto de $L$, mesmo
							$L$ sendo LLC, $\Sigma^*-L=\overline{L}$ pode não ser, visto que a classe das LLCs não é fechada sob
							complementação; e $\Sigma^*$ é regular. Assim, se $L$ é uma LCC, $X-L$ pode não ser LLC.
        \item  Ambas são \emph{verdadeiras}: \\
				      (i) Pela contrapositiva. Suponha que $L$ seja LLC. Então, como $X$ é regular, $\overline{X}$ é regular. Portanto,
							$L\cap \overline{X}$ é LLC. Como $L\cap \overline{X}=L-X$, conclui-se que se $L-X$ não é uma LLC, então $L$ não é
							uma LLC. \\
							(ii) A mesma argumentação que em (i).
       \end{list}
 \item {\footnotesize Crie MTs padrão com uma única transição que reconheçam $(a+b)^+$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Por parada.
        \item Por estado final.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
				
				      \begin{picture}(160,1)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

               \node[Nmarks=i, iangle=180](0)(10,5){}
               \drawloop[loopangle=45](0){\tt $\sqcup$/$\sqcup$ D}
              \end{picture}
        \item \ 
				
				      \begin{picture}(160,6)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

               \node[Nmarks=i, iangle=180](0)(10,5){}
               \node[Nmarks=r](1)(30,5){}
               \drawedge(0,1){\shortstack{{\tt a/a D} \\ {\tt b/b D}}}
              \end{picture} (duas transições é o mínimo)
       \end{list}

 \item {\footnotesize Faça uma MT que reconheça a linguagem $\{ww^Rx\in\{{\tt a},{\tt b}\}^*\,|\, |x|=|w|\}$. Pode usar várias
       fitas e não determinismo.}

       \emph{Solução}:

       MT não determinística de duas fitas:

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

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

 \item {\footnotesize Construa uma gramática que gere $\{ww^R{\tt c}^{|w|} \,|\, w\in\{{\tt a},{\tt b}\}^*\}$.}

       \emph{Solução}:

       \begin{quote}
			  $P \,\rightarrow\, {\tt a}PA{\tt c} \,|\, {\tt b}PB{\tt c} \,|\, \lambda$ \\
				${\tt c}A \,\rightarrow\, A{\tt c}$ \\
				${\tt c}B \,\rightarrow\, B{\tt c}$ \\
			  ${\tt a}A \,\rightarrow\, {\tt aa}$ \\
			  ${\tt b}A \,\rightarrow\, {\tt ba}$ \\
			  ${\tt a}B \,\rightarrow\, {\tt ab}$ \\
			  ${\tt b}B \,\rightarrow\, {\tt bb}$
			 \end{quote}

 \item {\footnotesize Seja $L$ uma linguagem \emph{não} recursiva. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-F$ não é recursiva, se $F$ é finita.
        \item Se $L$ é LRE, então $\overline{L}$ não é LRE.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que $F$ seja finita. Se $L-F$ fosse recursiva, então $(L-F)\cup(F\cap L)$ seria recursiva. Mas
				      $(L-F)\cup(F\cap L)=L$, e $L$ não é recursiva! Portanto, se $F$ é finita, então $L-F$ não é recursiva.
        \item Suponha que $L$ é LRE. Neste caso, se $\overline{L}$ fosse LRE, então $L$ seria recursiva. Mas $L$
				      não é recursiva. Logo, se $\overline{L}$ é LRE, então $L$ não é LRE.
       \end{list}

 \item {\footnotesize Mostre que são \emph{indecidíveis} os problemas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT $M$, determinar se $|L(M)|=2$.
        \item Dados uma MT $M$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada $\lambda$
				      atinge o estado $e$.
       \end{list}}
       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A propriedade de ter duas palavras é \emph{não trivial}: existem LREs que têm duas palavras e outras que
				      têm menos ou mais de duas. Logo, pelo teorema de Rice, o problema é indecidível.
        \item O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de uma MT $M$, uma MT $M'$ e um
				      estado $k$ tais que:
							\begin{itemize}
							 \item $k$ é um estado diferente de todos os utilizados por $M$; e
							 \item $M'$ é como $M$, exceto que, para todo par $(e,s)$ tal que $\delta(e,s)$ é indefinido em $M$,
							       em $M'$ tem-se a transição $\delta'(e,s)=[k,a,D]$.
							\end{itemize}
							Com isto, $M$ para se iniciada com a fita em branco sse a computação de $M'$ para a entrada $\lambda$
							atinge o estado $k$.
       \end{list}
\end{enumerate}

\end{document}
