\documentclass[12pt,a4paper]{report}

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

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

\newcounter{conta}

\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Terceira Prova} \hfill 26/11/2015

\vspace*{3mm}
\begin{enumerate}

 \item {\footnotesize Seja a MT $M=(\{1,2,3,4\},\{{\tt 0},{\tt 1}\},\{{\tt 0},{\tt 1},\langle,\sqcup\},
       \langle,\sqcup,\delta,1,\{3,4\})$ com o diagrama de estados:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,40)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i](1)(20,15){1}
         \node(2)(40,25){2}
         \node[Nmarks=r](3)(65,25){3}
         \node[Nmarks=r](4)(40,5){4}

         \drawedge[curvedepth=0](1,2){${\tt 0}/\sqcup$ {\sf D}}
         \drawedge[curvedepth=0,ELside=r](1,4){${\tt 1}/{\tt 1}$ {\sf D}}
         \drawloop[loopangle=90](2){${\tt 0}/\sqcup$ {\sf D}}
         \drawedge[curvedepth=0](2,3){$\sqcup/\sqcup$ {\sf E}}
         \drawloop[loopangle=0](4){\shortstack{${\tt 1}/{\tt 1}$ {\sf D} \\
                                                 $\sqcup/\sqcup$ {\sf D}}}
        \end{picture}
       } \\

       Expresse a linguagem reconhecida por $M$ por meio de uma \underline{expressão regular}.}

\vspace*{3mm}
       \textit{Solução}: $00^*+11^*0(0+1)^*$

  \item {\footnotesize Construa uma MT de duas fitas que reconheça $\{xy\in\{{\tt a},{\tt b}\}^*\,|\,n_{\tt a}(x)>n_{\tt b}(y)\}$.
	      ($n_{\tt a}(w)$: número de {\tt a}s na palavra $w$.) Para facilitar, pode usar não determinismo.}

\vspace*{3mm}
       \textit{Solução}:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(110,25)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i](1)(20,5){}
         \node(2)(75,5){}
         \node[Nmarks=r](3)(115,5){}

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

       Como a linguagem é igual a $\{x\in\{{\tt a},{\tt b}\}^*\,|\,n_{\tt a}(x)>0\}$, uma outra
			 solução é:
			
       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(110,15)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

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

         \drawloop[loopangle=90](1){${\tt b}/{\tt b}$ {\sf D}}
         \drawedge[curvedepth=0](1,2){${\tt a}/{\tt a}$ {\sf D}}
        \end{picture}
       } \\

 \item {\footnotesize Construa uma gramática que gere $\{{\tt a}^nxx\,|\,x\in\{{\tt a},{\tt b}\}^* \mbox{ e } |x|=n\}$.}

\vspace*{3mm}
       \textit{Solução}:
       \begin{quote}
			  $P \,\rightarrow\, {\tt a}PA{\tt a} \,\,|\,\, {\tt b}PB{\tt b} \,\,|\,\, M$ \\
			  $MA \,\rightarrow\, {\tt a}M$ \hspace*{6mm} $MB\,\rightarrow\, {\tt b}M$ \\
			  ${\tt a}A \,\rightarrow\, A{\tt a}$ \hspace*{9.5mm} ${\tt b}A\,\rightarrow\, A{\tt b}$ \\
			  ${\tt a}B \,\rightarrow\, B{\tt a}$ \hspace*{9.5mm} ${\tt b}B\,\rightarrow\, B{\tt b}$ \\
			  $M \,\rightarrow\, \lambda$
       \end{quote}

 \item {\footnotesize Mostre que se o problema da parada fosse decidível, toda linguagem recursivamente enumerável seria recursiva.}

\vspace*{3mm}
       \textit{Solução}: Suponha que $P$ seja uma MT que solucione o problema da parada. Seja $L$ uma linguagem recursivamente
			 enumerável e $M$ uma MT, que reconhece \emph{por parada}, tal que $L(M)=L$. Então pode-se construir uma MT $M'$ que
			 reconhece $L$ e que pare para qualquer palavra de entrada $w$ da seguinte maneira:
			 \begin{enumerate}
			  \item[1.] $M'$ obtém $R\langle M,w\rangle$ (no lugar de sua entrada $w$ ou em uma segunda fita);
				\item[2.] $M'$ se comporta como $P$ (sobre $R\langle M,w\rangle$);
        \item[3.] nas situações em que $P$ aceita (responde ``sim''), $M'$ aceita, e nas situações em que
				      $P$ rejeita (responde ``não''), $M'$ rejeita.
			 \end{enumerate}
			 Tem-se:
       $$w\in L(M) \mbox{ sse } M \mbox{ para se a entrada é } w \mbox{ sse } P \mbox{ aceita } R\langle M,w\rangle \mbox{ sse } w\in L(M')\mbox{.}$$
			Como $M'$ sempre para e $L(M')=L(M)=L$, segue-se que $L$ é recursiva.

 \item {\footnotesize Mostre que os seguintes problemas são indecidíveis:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dadas duas gramáticas livres do contexto $G_1$ e $G_2$, cada uma com \emph{uma única variável},
				      determinar se $L(G_1)\cap L(G_2)=\emptyset$.
        \item Dada uma MT $M$ e um símbolo $a$ de seu alfabeto de entrada, determinar se $M$ reconhece alguma palavra que
				      tenha uma ocorrência de $a$.
       \end{list}}

\vspace*{3mm}
       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O problema da correspondência de Post pode ser reduzido a este produzindo-se, a partir de um SCP $S$, as
				      gramáticas $G_X$ e $G_Y$. Note que cada uma destas GLCs tem uma única variável e são tais que $L(G_X)\cap L(G_Y)
							=\emptyset$ sse o PCP $S$ não tem solução.
        \item O problema da parada pode ser reduzido a este produzindo-se, a partir de $R\langle M,w\rangle$, $R\langle M',a\rangle$
				      em que $a$ é um símbolo qualquer do alfabeto de entrada de $M$ (que é o mesmo que o de $M'$) e $M'$ é tal que:
		 	        \begin{enumerate}
			         \item[1.] $M'$ apaga sua entrada qualquer que ela seja;
			         \item[2.] $M'$ escreve $w$ na fita;
				       \item[3.] $M'$ se comporta como $M$;
               \item[4.] nas situações em que $M$ para, $M'$ aceita.
			        \end{enumerate}
			        Com isto, $M$ para se a entrada é $w$ sse $L(M')=\Sigma^*$ sse $M'$ aceita alguma palavra com $a$.
       \end{list}

\end{enumerate}

\end{document}
