\documentclass[12pt,a4paper]{report}

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

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova/Solu\c{c}\~ao do professor} \hfill 22/11/2006

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

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

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

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

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

       Que linguagem \'e reconhecida por $M$? Se poss\'{\i}vel, expresse-a por
       meio de uma express\~ao regular.}

       \textit{Solu\c{c}\~ao\/}: $1^*0$.

 \item {\footnotesize Construa uma MT que reconhe\c{c}a $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 0}(w)>
       n_{\tt 1}(w)\}$. Pode usar mais de uma fita, n\~ao determinismo etc.}

       \textit{Solu\c{c}\~ao\/}: MT de duas fitas, a segunda para conter o n\'umero de {\tt 0}s:

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

         \node[Nmarks=i](1)(30,5){1}
         \node(2)(70,5){2}
         \node[Nmarks=r](3)(110,5){3}

         \drawedge[curvedepth=0](1,2){$\sqcup/\sqcup$ {\tt E}, $\sqcup/\sqcup$ {\tt E}}
         \drawedge[curvedepth=0](2,3){$\langle/\langle$ {\tt I}, ${\tt X}/{\tt X}$ {\tt I}}

         \drawloop[loopangle=90, ELside=l](1){\shortstack{${\tt 1}/{\tt 1}$ {\tt D},
                                                          $\sqcup/\sqcup$ {\tt I} \\
                                                          ${\tt 0}/{\tt 0}$ {\tt D},
                                                          $\sqcup/{\tt X}$ {\tt D}}}
         \drawloop[loopangle=90, ELside=l](2){\shortstack{${\tt 1}/{\tt 1}$ {\tt E},
                                                          ${\tt X}/{\tt X}$ {\tt E} \\
                                                          ${\tt 0}/{\tt 0}$ {\tt E},
                                                          ${\tt X}/{\tt X}$ {\tt I}}}
        \end{picture}
       } \\


 \item {\footnotesize Seja uma m\'aquina de Turing padr\~ao $M=(E,\Sigma,\Gamma,\langle,\sqcup,\delta,i,F)$.
       Suponha que existe um trecho de uma gram\'atica $G$ que gera qualquer forma sentencial
       do tipo $\langle i w \sqcup\rangle$, onde $w\in\Sigma^*$, sendo $\langle$, $i$,
       $\sqcup$ e $\rangle$ vari\'aveis da gram\'atica. Construa um conjunto de regras
       para adicionar a $G$ de tal forma que \[\langle i w \sqcup\rangle\stackrel{*}{\Rightarrow}_G
       \lambda \leftrightarrow \mbox{ $M$ aceita $w$.}\] (A gram\'atica resultante
       \'e irrestrita.)}

       \textit{Solu\c{c}\~ao\/}: Primeiro, regras para permitir a simula\c c\~ao de $M$
       sobre a configura\c c\~ao instant\^anea $\langle i w\sqcup\rangle$:
       \begin{itemize}
        \item para cada transi\c c\~ao em $M$ da forma $\delta(e,a)=[e',b,\mbox{D}]$:

             $e a\,\rightarrow\, b e'$ \\
             $e \rangle\,\rightarrow\, b e' \rangle$ se $a=\sqcup$

        \item para cada transi\c c\~ao em $M$ da forma $\delta(e,a)=[e',b,\mbox{E}]$:

             $c e a\,\rightarrow\, e' c b$ para cada $c\in\Gamma$ \\
             $c e \rangle\,\rightarrow\, e' c b\rangle$ para cada $c\in\Gamma$, se $a=\sqcup$.
       \end{itemize}
       Para terminar, regras para o apagamento da configura\c c\~ao instant\^anea quando
       ela for do tipo $\langle x e a\ldots$, onde $e\in F$ e $\delta(e,a)$ \'e
       indefinido:
       \begin{itemize}
        \item para cada par $(e,a)$ tal que $e\in F$ e $\delta(e,a)$ \'e indefinido:

              $e a\,\rightarrow\, \#$ se $a\not=\langle$ \\
              $e \langle\,\rightarrow\, \langle\#$ se $a=\langle$ \\
              $e \rangle\,\rightarrow\, \#\rangle$ se $a=\sqcup$ \\
              $\# c\,\rightarrow\, \#$ para cada $c\in\Gamma-\{\langle\}$ \\
              $c \# \,\rightarrow\, \#$ para cada $c\in\Gamma-\{\langle\}$ \\
              $\langle \# \rangle\,\rightarrow\, \lambda$
       \end{itemize}

 \item {\footnotesize Mostre que as LREs s\~ao fechadas sob concatena\c{c}\~ao. Dica: se usar
       MTs, use n\~ao determinismo; se usar GIs, n\~ao funciona fazer
       simplesmente ``$P\,\rightarrow\,P_1P_2$''.}

       \textit{Solu\c{c}\~ao\/}: Dadas duas MTs padr\~ao $M_1$ e $M_2$, pode-se construir
       uma MT n\~ao determin\'{\i}stica $M_3$ de duas fitas para $L(M_1)L(M_2)$, onde $M_3$
       faz o seguite:
       \begin{enumerate}
        \item[1.] seleciona na fita 1, n\~ao deterministicamente, uma posi\c{c}\~ao
                  $p$ na palavra de entrada;
        \item[2.] copia o sufixo que inicia em $p$ para a fita 2, apagando-o da fita 1;
        \item[3.] volta o cabe\c{c}ote da fita 1 para a segunda posi\c{c}\~ao
                  e o da fita 2 para a primeira;
        \item[4.] se comporta como $M_1$ sobre a fita 1;
        \item[5.] nas situa\c{c}\~oes em que $M_1$ p\'ara em estado final, fazer
                  transi\c{c}\~ao para um estado a partir do qual se comporta
                     como $M_2$ sobre a fita 2.
        \item[6.] aceita examente nas situa\c{c}\~oes em que $M_2$ aceitaria.
       \end{enumerate}

       Por gram\'aticas: Sejam $G_1=(V_1,\Sigma_1,R_1,P_1)$ e $G_2=(V_2,\Sigma_2,R_2,P_2)$
       duas GIs tais que $V_1\cap V_2=\emptyset$. Seja $N$ o conjunto das
       regras $A_a\,\rightarrow\,a$, onde $a\in\Sigma_1\cup\Sigma_2$,
       e $A_a$ \'e uma vari\'avel diferente para cada vari\'avel $a$ e diferente de todas as
       vari\'aveis em $V_1\cup V_2$ (logo, s\~ao $|\Sigma_1\cup\Sigma_2|$ vari\'aveis novas
       e o mesmo tanto de regras em $N$). Seja $R'$ o conjunto resultante de substituir
       em cada regra de $R$ todo terminal $a$ pela vari\'avel $A_a$. Seja $P\not\in
       V_1\cup V_2\cup\{A_a\,|\,a\in\Sigma_1\cup\Sigma_2\}$. Ent\~ao, uma GI
       para $L(G_1)L(G_2)$ seria $(V_3,\Sigma_1\cup\Sigma_2,R_3,P)$, em que:
       \begin{itemize}
        \item $V_3=V_1\cup V_2\cup\{A_a\,|\,a\in\Sigma_1\cup\Sigma_2\}\cup\{P\}$;
        \item $R_3=R_1'\cup R_2'\cup N\cup\{P\,\rightarrow\,P_1P_2\}$.
       \end{itemize}
       (Com as modifica\c{c}\~oes nas regras de $G_1$ e de $G_2$, usando-se
        $R_1'$ e $R_2'$ em vez de $R_1$ e $R_2$, evita-se que o lado esquerdo
        de uma regra possa ser id\^entico a uma subpalavra $x$ de alguma
        forma sentencial, tendo parte(s) de $x$ sido gerada por regras de
        $R_1$ outra(s) parte(s) de $x$ por regras de $R_2$.)

 \item {\footnotesize Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{R\langle M,w\rangle\,|\,$ $M$ passa
              por um mesmo estado duas vezes ao processar $w\}$ \'e recursiva.
        \item $\{R\langle M,w,e\rangle\,|\,M$ passa pelo estado
              $e$ duas vezes ao processar $w\}$ n\~ao \'e recursiva.
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $k$ o n\'umero de estados de $M$. Simulando a MT $M$ sobre
              $w$, se $M$ n\~ao parar antes sem repetir estados, ela vai
              repetir um estado no mais tardar na sua $k$-\'esima
              transi\c{c}\~ao.
        \item O problema da parada pode ser reduzido ao de se passar duas vezes
              por algum estado produzindo-se, a
              partir de $R\langle M,w\rangle$, $R\langle M',w,p\rangle$, onde
              $p$ \'e um estado que n\~ao aparece em $M$ e as \'unicas
              diferen\c{c}as entre $M'$ e $M$, al\'em de $M'$ ter o estado $p$
              a mais, \'e que, para cada par $(e,a)$ tal que $\delta(e,a)$ \'e
              indefinido em $M$, faz-se $\delta'(e,a)=[p,a,I]$ e $\delta'(p,a)
              =[p,a,I]$ em $M'$.
              Com isto, tem-se que $M$ p\'ara se a entrada \'e $w$ se, e
              somente se, $M'$ passa duas vezes por $p$ se a entrada \'e $w$.
       \end{list}

 \item {\footnotesize Mostre que \'e decid\'{\i}vel ou que n\~ao \'e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dado um AFN $M$, determinar se ele aceita alguma palavra
              terminada com {\tt 0}.
        \item Dados um conjunto finito $F$ e uma LLC $L$, determinar se
              $F\subseteq L$.
        \item Dados um AFD $M$ e um APN $P$, determinar se $L(M)\subseteq L(P)$.
        \item Dada uma LRE, verificar se ela cont\'em algum pal\'{\i}ndromo.
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Decid\'{\i}vel. Dado um AFD m\'{\i}nimo $M'$ equivalente a $M$,
              $x{\tt 0}\in L(M)$ se, e somente se, existe uma transi\c{c}\~ao
              para um estado final de $M'$ sob {\tt 0}.
        \item Decid\'{\i}vel. Como o problema de, dadas uma palavra $w$ e uma
              LLC $L$, deteminar se $w\in L$ \'e decid\'{\i}vel, basta
              verificar, para cada palavra $w\in F$, se $w\in L$.
        \item Indecid\'{\i}vel. O problema indecid\'{\i}vel de determinar se
              $L(G)=\Sigma^*$ para GLCs $G$ pode ser reduzido ao presente
              problema produzindo-se um AFD $M$ tal que $L(M)=\Sigma^*$ e
              um APN $P$ tal que $L(P)=L(G)$. Com isto,
              $L(G)=\Sigma^*$ se, e somente se $\Sigma^*\subseteq L(G)$ se, e
              somente se, $L(M)\subseteq L(P)$.
        \item A propriedade de conter um pal\'{\i}ndromo \'e n\~ao trivial
              para LREs, visto que algumas cont\^em pal\'{i}ndromos, como
              $\{\lambda\}$, e outras n\~ao, como $\emptyset$. Assim, pelo
              teorema de Rice o problema \'e indecid\'{\i}vel.
       \end{list}

\end{enumerate}

\end{document}
