\documentclass[12pt,a4paper]{report}

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

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

\newcounter{conta}
\pagestyle{empty}
\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 2013 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Terceira Prova/Solução do professor} \hfill 26/11/2013

\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,\{1\})$ com o diagrama de estados a seguir:

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

         \node[Nmarks=ir](1)(50,5){1}
         \node(2)(80,5){2}

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

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

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

 \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 Dada uma gramática irrestrita $G$, como seria uma MT $M$ que reconhece L(G)? Basta mostrar
       um algoritmo, em alto nível, de $M$. \textit{Dica:} faça, como visto no curso, uma MT não determinística de
			 duas fitas, a primeira contendo a palavra a reconhecer e a segunda uma forma sentencial de $G$.}

      \textit{Solu\c{c}\~ao\/}: Seja uma gramática irrestrita $G=(V,\Sigma,R,P)$. Será apresentado um algoritmo para
			 uma MT não determinística de duas fitas, $M$, tal que $L(M)=L(G)$. Fita 1: palavra de entrada; fita 2: forma
			 sentencial de $G$.
      \begin{tabbing}
       xxx\=xxx\=xxx\=xxx\= \kill
          \>Escreva $P$ (a vari\a'avel de partida) na fita 2. \\
          \>{\bf laço} \\
          \>  \>selecione uma posi\c c\~ao $p$ na forma sentencial que est\a'a na fita 2; \\
          \>  \>selecione uma regra $u\rightarrow v\in R$; \\
          \>  \>{\bf se} $u$ ocorre a partir da posi\c c\~ao $p$ da fita 2 {\bf ent\~ao} \\
          \>  \>  \>substitua $u$ por $v$ na fita 2; \\
          \>  \>  \>{\bf se} a forma sentencial na fita 2 \a'e id\^entica \a`a palavra
          na fita 1 {\bf ent\~ao}  \\
          \>  \>  \>  \>aceite \\
          \>  \>  \>{\bf fimse} \\
          \>  \>{\bf sen\~ao} \\
          \>  \>  \> rejeite \\
          \>  \>{\bf fimse} \\
          \>{\bf fimlaço}. 
      \end{tabbing}

 \item {\footnotesize Faça uma gramática sensível ao contexto que gere a linguagem $\{wxw\,|\, w\in\{{\tt a},{\tt b}\}^*
       \mbox{ e } x\in\{{\tt c}\}^+ \}$.}

       \textit{Solu\c{c}\~ao\/}: 
			 \begin{quote}
			  $P\,\rightarrow\, {\tt a}PA \,|\, {\tt b}PB \,|\, C$ \\
			  $C\,\rightarrow\, C{\tt c} \,|\, {\tt c}$ \\
			  ${\tt c}A\,\rightarrow\, {\tt ca}$ \\
			  ${\tt c}B\,\rightarrow\, {\tt cb}$ \\
			  ${\tt a}A\,\rightarrow\, A{\tt a}$ \\
			  ${\tt a}B\,\rightarrow\, B{\tt a}$ \\
			  ${\tt b}A\,\rightarrow\, A{\tt b}$ \\
			  ${\tt b}B\,\rightarrow\, B{\tt b}$
			 \end{quote}

 \item {\footnotesize Seja $L=\{R\langle M\rangle\,|\, L(M)=\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}\}$.
       Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L$ é recursivamente enumerável.
				\item $L$ não é recursiva.
       \end{list}
			}

       \textit{Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Pode-se simular a execução de $M$ sobre cada uma das palavras de $\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}$
				      via uma MT $S$ que se comporte como a MT universal para cada uma das 4 entradas. $S$ tem 3 fitas; na
							fita 1 vem a entrada ($R\langle M\rangle$). Inicialmente, $S$ inicializa as fitas 2 e 3 com
							$R\langle{\tt 00}\rangle$ e $R\langle i\rangle$ ($i$ é o estado inicial de $M$) e se comporta como
							a MT universal. Nas situações em que $M$ aceita {\tt 00}, $S$ re-inicializa as fitas 2 e 3, agora com
							$R\langle{\tt 01}\rangle$ e $R\langle i\rangle$. E assim por diante, simulando também o processamento para as
							palavras {\tt 10} e {\tt 11}. $M$ aceitando todas, $S$ aceita. Note que, se $M$ entra em \textit{loop}
							para alguma das  palavras, $S$ também entra.
        \item A propridade ``$L(M)=\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}$'' é não trivial. Logo, pelo teorema de Rice,
				      $L$ não é recursiva.
       \end{list}

 \item {\footnotesize Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma MT, determinar se ela volta ao seu estado inicial se executada com a fita em branco.
        \item Dada uma GLC $G$ e uma gramática regular $H$, determinar se $L(G)=L(H)$.
       \end{list}}

       \textit{Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Indecidível. O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de
				      $M$, uma MT $M'$, com um estado inicial $i'$ diferente de todos os estados de $M$, que faz o seguinte:
							\begin{itemize}
							 \item De $i'$, $M'$ transita para o estado inicial de $M$, mantendo o cabeçote imóvel
							       (via a transição $\delta'(i',\sqcup)=[i,\sqcup,I]$, sendo $i$ o estado inicial de $M$).
							 \item $M'$ se comporta como $M$, mas nas situações em que $M$ para, $M'$ transita para $i'$
							       (faz $\delta'(e,a)=[i',a,I]$ para todo estado $e$ de $M$ e símbolo de fita $a$ de $M$ tais que
										 $\delta(e,a)$ é indefinido).
							\end{itemize}
							Com isto: $M$ para se sua fita é iniciada em branco sse $M'$ volta ao seu estado inicial se sua fita
							é iniciada em branco.
        \item Indecidível. O problema indecidível de determinar se $L(G)=\Sigma^*$ para GLCs $G$ pode ser
				      reduzido ao presente problema produzindo-se uma gramática regular $H$ tal que $L(H)=\Sigma^*$.
							Com isto, $L(G)=\Sigma^*$ se, e somente se $L(G)=L(H)$.
       \end{list}

\end{enumerate}

\end{document}
