\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 Terceira Prova} -- Turma N/Solução do professor \hfill {27/5/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 $L-X$ é uma LLC.
        \item Se $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 Ambas são verdadeiras: \\
				      (i) Como $X$ é finita, é regular e, como a classe das linguagens regulares é fechada sob complementação,
							$\overline{X}$ é regular. Como a interseção de uma LLC com uma linguagem regular é LLC, segue-se que se
							$L$ é LLC, então $L\cap\overline{X}=L-X$ é LLC. \\
							(ii) Como a interseção de uma LLC com uma linguagem regular é LLC, segue-se que se $L$ é LLC, então
							$L\cap\overline{X}=L-X$ é LLC.
        \item A primeira é verdadeira e a segunda falsa: \\
				      (i) Suponha que $L-X$ seja uma LLC. Como a classe das LLCs é fechada sob união, $(L-X)\cup(L\cap X)$ deve então
							ser LLC, pois $L\cap X$, sendo finita, é LLC. Mas $(L-X)\cup(L\cap X)=L$. Logo, se  $L$ não é LLC, então $L-X$
							não é uma LLC. \\
							(ii) Contraexemplo: $X=\Sigma^*$, sendo $\Sigma$ o alfabeto de $L$. No caso, $L-X=\emptyset$. Logo, se $L$ não
							é uma LLC, então $L-X$ pode ser uma LLC.
       \end{list}

 \item {\footnotesize Crie MTs padrão, cada uma com uma única transição, que reconheçam $a^+$:
       \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){\tt a/a D}
               \put(40,5){\makebox(0,0)[l]{Alfabeto de entrada: $\{{\tt a}\}$.}}
              \end{picture}
       \end{list}

 \item {\footnotesize Faça uma MT que reconheça a linguagem $\{xww^R\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,28)
        \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$/$\sqcup$ D} \\ {\tt b/b D, $\sqcup$/$\sqcup$ D}}}
        \drawloop[loopangle=270](1){\shortstack{{\tt a/a D, $\sqcup$/$\sqcup$ D} \\ {\tt b/b D, $\sqcup$/$\sqcup$ 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, $\sqcup$/a E} \\ {\tt b/b D, $\sqcup$/b 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, a/a D} \\ {\tt b/b D, b/b D}}}
        \drawedge(3,4){{\tt $\sqcup$/$\sqcup$ I}, {\tt $\sqcup$/$\sqcup$ I}}
       \end{picture}

 \item {\footnotesize Construa uma gramática que gere $\{{\tt 0}^{n}{\tt 1}^n{\tt 0}^n \,|\, n\geq 1\}$.}

       \emph{Solução}:

       \begin{quote}
			  $P \,\rightarrow\, {\tt 0}PX{\tt 0} \,|\, {\tt 010}$ \\
			  ${\tt 0}X \,\rightarrow\, X{\tt 0}$ \\
			  ${\tt 1}X \,\rightarrow\, {\tt 11}$
			 \end{quote}

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

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que $F$ seja finita. Se $L\cup F$ fosse recursiva, então $(L\cup F)-(F-L)$ seria recursiva. Mas
				      $(L\cup F)-(F-L)=L$, e $L$ não é recursiva! Portanto, se $F$ é finita, então $L\cup F$ não é recursiva.
        \item Suponha que $\overline{L}$ é LRE. Neste caso, se $L$ fosse LRE, então $L$ seria recursiva. Como $L$ não é
				      recursiva, 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)$ é uma linguagem regular.
        \item Dados uma MT $M$ e um símbolo $a$ de fita de $M$, determinar se a computação de $M$
              para a entrada $\lambda$ escreve $a$ na fita em algum momento.
       \end{list}}

       \emph{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item A propriedade de ser linguagem regular é \emph{não trivial}: existem LREs regulares e não regulares. 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
				      símbolo $a$ tais que:
							\begin{itemize}
							 \item $a$ é um símbolo 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)=[e,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$ escreve $a$
							na fita em algum momento.
       \end{list}

\end{enumerate}

\end{document}
