\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{amsfonts}

\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Terceira Prova} --- Turma N/Solução do professor \hfill 30/6/2015

%\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $X$ é regular e $L$ não é LLC, então $L-X$ pode ser LLC e pode não ser LLC.
        \item Se $X$ é finita e $L$ não é uma LLC, então $L-X$ não é uma LLC.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que $L$ não é LLC. $\Sigma^*$ e $\emptyset$ são regulares, $L-\Sigma^*=\emptyset$, que é LLC,
				      e $L-\emptyset=L$, que não é LLC.
        \item Suponha que $X$ é finita e $L$ não é uma LLC. Se $L-X$ fosse LLC, então $(L-X)\cup(L\cap X)$ teria que ser
				      LLC, pois as LLCs são fechadas sob união e $L\cap X$ é finita e, logo, LLC. Mas $(L-X)\cup(L\cap X)=L$, que
							não é LLC. Portanto, $L-X$ não pode ser LLC se $X$ for finita e $L$ não for LLC.
       \end{list}

 \item {\footnotesize Crie MTs que reconheçam $a(a+b+c)^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item por parada em estado final;
        \item por parada.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(70,1)
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

                \node[Nmarks=i](1)(20,0){}
                \node[Nmarks=r](2)(40,0){}

                \drawedge[curvedepth=0](1,2){\tt a/a E}
               \end{picture}
              } \\
        \item \ 
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(70,8)
                \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

                \node[Nmarks=i](1)(20,0){}

                \drawloop[loopangle=0](1){\shortstack{{\tt $\sqcup$/$\sqcup$ E} \\ {\tt b/b E} \\ {\tt c/c E} \\
								                                       {\tt $\langle$/$\langle$ D}}}
               \end{picture}
              } \\
       \end{list}

 \item {\footnotesize Faça uma MT multifita que reconheça $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=
       2(n_{\tt b}(w)+n_{\tt c}(w))\}$.}

       \emph{Solução}: \ 
				
       \mbox{\setlength{\unitlength}{1mm}\footnotesize
        \begin{picture}(110,30)
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](1)(20,10){}
         \node(2)(65,10){}
         \node(2x)(110,10){}
         \node[Nmarks=r](3)(30,0){}

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

 \item {\footnotesize Mostre que se $L$ é uma LRE e $X$ é uma LLC, então:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-X$ é LRE.
        \item $X-L$ pode ser LRE ou não.
       \end{list}}

       \emph{Solução}: \ 

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Como $X$ é LLC, é também recursiva. Como linguagens recursivas são fechadas sob complemento,
				      $\overline{X}$ é recursiva; portanto, é LRE. Como LREs são fechadas sob interseção, $L\cap\overline{X}=
							L-X$ é LRE.
        \item Se $X=\emptyset$, $X-L=\emptyset$; logo, é LRE. Se $X=\Sigma^*$, $X-L$ é o complemento de $L$. Como
				      as LREs não são fechadas sob complemento, o complemento de $L$ pode não ser LRE.
       \end{list}

 \item {\footnotesize Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O problema a seguir é \emph{decidível}:
				      \begin{quote}
               dada uma MT $M$, determinar se existe estado $e$ de $M$ tal que $M$ passe duas vezes por $e$
				       ao processar $\lambda$.
							\end{quote}
							\emph{Dica}: diga como alterar a MT universal para resolver tal	problema.
        \item O problema a seguir é \emph{indecidível}:
				      \begin{quote}
               dada uma MT $M$ e um estado $e$ de $M$, determinar se $M$ passa duas vezes por $e$
 				       ao processar $\lambda$.
							\end{quote}
							\emph{Dica}: reduza o problema da fita em branco a este.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Considere a MT universal que receba como entrada $R\langle M,\lambda\rangle$. Adicione uma nova fita a ela
				      e inicialize a mesma com o estado inicial de $M$. Após simular uma transição de $M$, verificar se o
							próximo estado já ocorre na fita nova; se ocorrer, ir para estado de aceitação; se não ocorrer adicioná-lo
							na fita 4 e prosseguir. Note que a máquina sempre para, pois o conjunto de estados de $M$ é finito.
        \item A redução do problema da fita em branco pode ser feita a este da seguinte forma: a partir de
				      $R\langle M\rangle$ é produzida $R\langle M',s\rangle$ tal que $s$ é um estado diferente de todos os
							de $M$ e $M'$ difere de $M$ apenas em que:
							\begin{enumerate}
               \item[1.] para todo par $(e,a)$ de $M$ para o qual $\delta(e,a)$ é indefinido, $M'$ transita para o estado
							       $s$;
							 \item[2.] no estado $s$, para qualquer símbolo de fita, $M'$ transita para $s$ (um laço).
							\end{enumerate}
							Com isto, $M$ para se sua entrada é $\lambda$ sse $M'$ passa duas vezes por $s$ ao processar $\lambda$, o que
							confirma a redução.
       \end{list}

 \item {\footnotesize Mostre que a linguagem a seguir é LRE: $$\{R\langle M,e\rangle \,|\, M \mbox{ passa duas vezes pelo estado } e
       \mbox{ ao processar } \lambda\}$$ \emph{Dica}: diga como alterar a MT universal para reconhecer tal
			 linguagem.}

       \emph{Solução}:

       Considere uma MT universal que receba como entrada $R\langle M,e\rangle$, e considere a fita de $M$ como estando
			 em branco. Adicione uma nova fita a ela e inicialize a mesma com o estado inicial de $M$. Após simular uma
			 transição de $M$, verificar se o próximo estado é o estado $e$; se for, verificar se ele já ocorre na fita nova;
			 se ocorrer, ir para estado de aceitação. Se o próximo estado não for $e$ ou se ele for a primeira ocorrência de $e$,
			 adicioná-lo à fita 4 e prosseguir.
 \end{enumerate}
\end{document}
