\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage         {amsfonts}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Terceira Lista de Exercícios}/Solução do professor \hfill Data de entrega: 05/12/2017 \hfill Valor: 10 pontos

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Para cada linguagem a seguir, mostre que ela é ou não é LLC:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=n_{\tt b}(w)\}$;
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)\not=n_{\tt b}(w)\}$;
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=n_{\tt b}(w)=n_{\tt c}(w)\}$;
        \item O complemento de $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=n_{\tt b}(w)=n_{\tt c}(w)\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item É LLC. Uma GLC para a linguagem:
							\begin{enumerate}
							 \item[\ ] $P\,\rightarrow\, {\tt a}P{\tt b}P\,|\, {\tt b}P{\tt a}P\,|\, {\tt c} P \,|\, \lambda$
							\end{enumerate}
        \item É LLC. Uma GLC para a linguagem:
							\begin{enumerate}
							 \item[\ ] $P\,\rightarrow\, A \,|\, B$
							 \item[\ ] $A\,\rightarrow\, X{\tt a}A \,|\, X{\tt a}X$
							 \item[\ ] $B\,\rightarrow\, X{\tt b}B \,|\, X{\tt b}X$
							 \item[\ ] $X\,\rightarrow\, {\tt a}X{\tt b}X \,|\, {\tt b}X{\tt a}X \,|\, {\tt c}X \,|\, \lambda$
							\end{enumerate}
        \item Não é LLC. Seja $L$ a linguagem em questão. Suponha que $L$ seja LLC.
              Então:\[L\cap \{{\tt a}\}^*\{{\tt b}\}^*\{{\tt c}\}^*=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\geq 0\}\]
              Como as LLCs são fechadas sob interseçcão com linguagens regulares, tem-se uma contradição, visto que
              $\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\geq 0\}$ não é LLC. Portanto, $L$ não é LLC.
        \item É LLC. Seja $L$ o complemento de $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=n_{\tt b}(w)=
				      n_{\tt c}(w)\}$. Tem-se que $L=L_1\cup L_2\cup L_3$, em que $L_1=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*
							\,|\, n_{\tt a}(w)\not=n_{\tt b}(w)\}$, $L_2=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,
							n_{\tt a}(w)\not=n_{\tt c}(w)\}$ e $L_3=\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt b}(w)\not=
							n_{\tt c}(w)\}$. No item (b) mostrou-se que $L_1$ é LLC. De forma análoga, $L_2$ e $L_3$ também
							são LLCs. Como $L_1$, $L_2$ e $L_3$ são LLCs e as LLCs são fechadas sob união, conclui-se que $L$ é
							LLC.
       \end{list}

 \item {\footnotesize Mostre que a classe das linguagens \textbf{não} inerentemente ambíguas não é fechada sob as operações de
       união e interseção.}

       \textit{Solução}:
       Sejam $L_1=\{{\tt a}^n{\tt b}^n\,|\,n\in\mathbb{N}\}\{{\tt c}\}^*$ e $L_2=\{{\tt a}\}^*\{{\tt b}^n{\tt c}^n
      \,|\,n\in\mathbb{N}\}$. Nenhuma das duas é inerentemente ambígua. Tem-se:
			\begin{itemize}
			 \item $L_1 \cup L_2=\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m=n \mbox{ ou } n=k\}$; e
			 \item $L_1 \cap L_2=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\in\mathbb{N}\}$.
			\end{itemize}
			A primeira é inerentemente ambígua e a segunda não é LLC, como já visto. Segue-se o resultado.


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

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

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

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

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

       \textit{Solução}: $\lambda+11^*0(0+1)^*$.

 \item {\footnotesize Projete uma MT de dois estados que reconheça $\{{\tt a}^{2n}\,|\, n\geq 0\}$.}

       \textit{Solução}:

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

               \node[Nmarks=ir](1)(20,5){}
               \node(2)(45,5){}

               \drawedge[curvedepth=3](1,2){${\tt a}/{\tt a}$ {\tt D}}
               \drawedge[curvedepth=3](2,1){${\tt a}/{\tt a}$ {\tt D}}
            \end{picture}
            } \\

 \item {\footnotesize Construa MTs que reconheçam \underline{por parada} as seguintes linguagens de alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item o conjunto das palavras que contêm {\tt 00};
        \item o conjunto das palavras que não contêm {\tt 00}.
      \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item MT para o conjunto das palavras que contêm {\tt 00}:

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

               \node[Nmarks=i](1)(20,20){}
               \node(2)(45,20){}
               \node(3)(70,20){}
               \node(4)(70,5){}

               \drawloop[loopangle=90](1){${\tt 1}/{\tt 1}$ {\tt D}}
               \drawedge[curvedepth=3](1,2){${\tt 0}/{\tt 0}$ {\tt D}}
               \drawedge[curvedepth=3](2,1){${\tt 1}/{\tt 1}$ {\tt D}}
               \drawedge[curvedepth=0](2,3){${\tt 0}/{\tt 0}$ {\tt D}}
               \drawedge[curvedepth=-2](2,4){$\sqcup/\sqcup$ {\tt D}}
               \drawedge[curvedepth=-8,ELside=r](1,4){$\sqcup/\sqcup$ {\tt D}}
               \drawloop[loopangle=0](4){$\sqcup/\sqcup$ {\tt D}}
              \end{picture}
             } \\
        \item MT para o conjunto das palavras que não contêm {\tt 00}.

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

               \node[Nmarks=i](1)(20,10){}
               \node(2)(45,10){}
               \node(3)(70,10){}

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

 \item {\footnotesize Escreva MTs não determinísticas de duas fitas que reconheçam as linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{xx\,|\,x\in\{{\tt 0},{\tt 1}\}^*\}$;
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 0}(w)>n_{\tt 1}(w)\}$;
        \item $\{xx^Ry\,|\,x,y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|>|y|\}$.
       \end{list}
       Procure obter MTs com o menor número de transições possível.}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Supondo $b\in\{{\tt 0},{\tt 1}\}$:

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

                \node[Nmarks=i, Nmarks=r](1)(10,10){}
                \node(2)(40,10){}
                \node(3)(70,10){}
                \node(4)(100,10){}
                \node[Nmarks=r](5)(130,10){}

                \drawedge[curvedepth=0, ELside=r](1,2){$b/\sqcup$ {\tt D},$\sqcup/b$ {\tt D}}
                \drawedge[curvedepth=0, ELside=r](2,3){$b/b$ {\tt D},$\sqcup/\sqcup$ {\tt I}}
                \drawloop[loopangle=90](2){$b/\sqcup$ {\tt D},$\sqcup/b$ {\tt D}}
                \drawedge[curvedepth=0, ELside=r](3,4){$\sqcup/\sqcup$ {\tt E},$\sqcup/\sqcup$ {\tt E}}
                \drawloop[loopangle=90](3){$b/b$ {\tt D},$\sqcup/\sqcup$ {\tt I}}
                \drawedge[curvedepth=0, ELside=r](4,5){$\sqcup/\sqcup$ {\tt E},$\langle/\langle$ {\tt D}}
                \drawloop[loopangle=90](4){$b/b$ {\tt E},$b/b$ {\tt E}}
               \end{picture}
              } \\
        \item MT com 2 fitas:

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

                \node[Nmarks=i](1)(10,10){}
                \node(2)(40,10){}
                \node[Nmarks=r](3)(70,10){}

                \drawloop[loopangle=90](1){\shortstack{${\tt 0}/\sqcup$ {\tt D},$\sqcup/{\tt 0}$ {\tt D} \\
								                                           ${\tt 1}/{\tt 1}$ {\tt D},$\sqcup/\sqcup$ {\tt I}}}
                \drawedge[curvedepth=0, ELside=r](1,2){$\sqcup/\sqcup$ {\tt E},$\sqcup/\sqcup$ {\tt E}}
                \drawloop[loopangle=90](2){\shortstack{$\sqcup/\sqcup$ {\tt E},${\tt 0}/{\tt 0}$ {\tt I} \\
								                                           ${\tt 1}/{\tt 1}$ {\tt E},${\tt 0}/{\tt 0}$ {\tt E}}}
                \drawedge[curvedepth=0](2,3){$\langle/\langle$ {\tt D},${\tt 0}/{\tt 0}$ {\tt I}}
               \end{picture}
              } \\
        \item Supondo $b\in\{{\tt 0},{\tt 1}\}$:

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

                \node[Nmarks=i](1)(20,30){}
                \node(2)(50,30){}
                \node(3)(90,30){}
                \node[Nmarks=r](4)(70,5){}

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

 \item {\footnotesize Seja uma MT $M=(E,\Sigma,\Gamma,\delta,i,\{f\})$ cuja única diferença com relação a uma MT-padrão é que ela
       tem apenas um estado final. Suponha que a linguagem reconhecida por $M$ seja
       \[\{w\in\Sigma^*\,|\, [i,\langle\underline{w}]\stackrel{*}{\vdash} [f,x\underline{a}y]\}\mbox{.}\]
       Ou seja, para qualquer $w\in\Sigma^*$ $M$ reconhece $w$ se, e somente se, $M$ atinge o estado $f$ ao
			 processar $w$. Mostre que qualquer linguagem recursivamente enumerável pode ser
       reconhecida por uma MT desse tipo.}

       \textit{Solução}:
       Uma MT com um único estado final que reconhece
       $L(M)$ por estado final é $M'=(E\cup\{f\},\Sigma,\Gamma,\delta',i,\{f\})$, em que $f\not\in E$ e
       $\delta'$ é tal que:
       \begin{itemize}
        \item $\delta'(e,a)=\delta(e,a)$ para todo $(e,a)$ tal que $\delta(e,a)$ é definido;
        \item $\delta'(e,a)=[f,a,{\tt D}]$ para todo $(e,a)\in F\times\Gamma$ tal que
              $\delta(e,a)$ é indefinido;
        \item $\delta'(e,a)$ é indefinido nos casos restantes.
       \end{itemize}

 \item {\footnotesize Construa gramáticas irrestritas que gerem as linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{{\tt 0}^n{\tt 1}^k{\tt 0}^n{\tt 1}^k\,|\, n,k\geq 0\}$;
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\, m<n<k\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Gramática para $\{{\tt 0}^n{\tt 1}^k{\tt 0}^n{\tt 1}^k\,|\,
              n,k\geq 0\}$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A B$
               \item[\ ] $A\,\rightarrow\, {\tt 0} A Z \,|\, \lambda$
               \item[\ ] $B\,\rightarrow\, {\tt 1} B {\tt 1} \,|\, X$
               \item[\ ] $Z {\tt 1}\,\rightarrow\, {\tt 1} Z$
               \item[\ ] $Z X\,\rightarrow\, X {\tt 0}$
               \item[\ ] $X\,\rightarrow\, \lambda$
              \end{enumerate}
        \item Gramática para $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m<n<k\}$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt a}BP{\tt c}\,|\,{\tt b}X{\tt c}$
               \item[\ ] $B{\tt a}\,\rightarrow\, {\tt a}B$
               \item[\ ] $B{\tt b}\,\rightarrow\, {\tt bb}$
               \item[\ ] $X\,\rightarrow\, {\tt b}X{\tt c} \,|\, X{\tt c}\,|\,{\tt c}$
              \end{enumerate}
       \end{list}

 \item {\footnotesize Construa GSCs para:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{{\tt a}^n{\tt b}^{n+1}{\tt c}^{n+2}\,|\,n\geq 0\}$;
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m<n<k\}$;
        \item $\{wxw\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{{\tt c}\}^+ \}$.
       \end{list}
       Procure obter GSCs com um número mínimo de regras.}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Uma gramática com 4 regras que gera $\{{\tt a}^n{\tt b}^{n+1}{\tt c}^{n+2}\,|\,n\geq 0\}$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt a} P B {\tt c} \,|\, {\tt bcc}$
               \item[\ ] ${\tt c} B\,\rightarrow\, B {\tt c}$
               \item[\ ] ${\tt b} B\,\rightarrow\, {\tt bb}$
              \end{enumerate}
        \item Uma gramática com 6 regras que gera $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m<n<k\}$:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, {\tt a}PB{\tt c}\,|\,PB{\tt c}\,|\,P{\tt c}\,|\,{\tt bcc}$
               \item[\ ] ${\tt c}B\,\rightarrow\, B{\tt c}$
               \item[\ ] ${\tt b}B\,\rightarrow\, {\tt bb}$
              \end{enumerate}
				\item Uma gramática com 11 regras para $\{wxw\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{{\tt c}\}^+ \}$:
              \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}
       \end{list}

 \item {\footnotesize Sejam $L$ uma LRE e $R$ uma linguagem recursiva. Mostre:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L-R$ é uma LRE;
        \item $L-R$ pode não ser recursiva;
        \item $R-L$ pode não ser uma LRE.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Como as linguagens recursivas são fechadas sob complementação,
              $\overline{R}$ é recursiva. Assim, $\overline{R}$ é LRE. Como as LREs
              são fechadas sob interseção, segue-se que $L\cap\overline{R}$ é LRE.
              Como $L-R=L\cap\overline{R}$, $L-R$ é uma LRE.
        \item $\emptyset$ é recursiva. E se $L$ não é recursiva, $L-\emptyset=L$
              não é recursiva.
        \item $\Sigma^*$ é recursiva. E $\Sigma^*-L$ pode não ser uma LRE, pois as
              LREs não são fechadas sob complementação.
       \end{list}

 \item {\footnotesize Seja $L$ uma linguagem \emph{não} recursivamente enumerável. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Se $F$ é finita, $L-F$ não é recursivamente enumerável.
        \item Se $R$ é regular, $L-R$ pode ser regular ou não.
        \item $\overline{L}$ pode ser recursivamente enumerável.
       \end{list}}

       \textit{Solução}:
       Seja $L$ uma linguagem \emph{não} recursivamente enumerável.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que $F$ seja finita. Caso $L-F$ seja recursivamente enumerável, então, como $L\cap F$ é finita, e portanto
				      recursivamente enumerável, segue-se pelo fechamento sob união que $(L-F)\cup(L\cap F)$ é recursivamente enumerável.
							Mas, $(L-F)\cup(L\cap F)=L$, contradizendo o fato de que $L$ não é recursivamente enumerável. Logo, $L-F$ não pode
							ser recursivamente enumerável.
        \item $L-\Sigma^*=\emptyset$, que é regular. $L-\emptyset=L$, que não é recursivamente enumerável e, portanto, não é regular.
        \item Se $\overline{L}$ é recursivamente enumerável e não recursiva, então $L$ não é recursivamente enumerável.
       \end{list}

 \item {\footnotesize Seja a seguinte representação de certa gramática $G$, utilizando-se a codificação concebida em exemplo da Seção 5.2:
       \[R\langle G\rangle={\tt 1101101011101011100101100110111101101111001100}\mbox{.}\]
       Supondo que $G$ tenha os terminais {\tt a}, representado por {\tt 111}, e {\tt b}, representado por {\tt 1111}, que
			 linguagem é gerada por $G$?}

       \textit{Solução}: $\{{\tt a}^n{\tt b}^{2k}{\tt a}^n\,|\, n,k\in\mathbb{N}\}$.

 \item {\footnotesize Exiba as linguagens associadas ao PD ``determinar se $n$ é um número par menor do que 10'' para as duas representações
       apresentadas em exemplo da Seção 5.2.}

       \textit{Solução}:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 1}^2,{\tt 1}^4,{\tt 1}^6,{\tt 1}^8\}$.
        \item $\{{\tt 0}^n{\tt 1}{\tt 0}^k \,|\, n\in\mathbb{N} \mbox{ e } 0\leq k\leq 3\}$.
       \end{list}

 \item {\footnotesize Mostre que a linguagem $\{R\langle M\rangle\,|\, L(M)\not=\emptyset\}$ é LRE.}

       \textit{Solução}:
       A MT universal pode ser alterada para uma MT não determinística que reconhece a linguagem em questão da seguinte forma:
        \begin{itemize}
         \item No passo 1 escreve, \emph{não deterministicamente}, uma palavra na fita 2.
         \item No passo 3.5.1, a MT entra em estado final.
        \end{itemize}

 \item {\footnotesize Seja a linguagem $\{R\langle M,w\rangle\,|\, \mbox{$M$ não para se a entrada for $w$}\}$. Prove que essa linguagem
			 não é recursivamente enumerável. Observe que essa linguagem é $\overline{L_{P}}$, excluídas as palavras que não
			 estejam na forma $R\langle M,w\rangle$.}

       \textit{Solução}:
       Seja $X=\{R\langle M,w\rangle\,|\, \mbox{$M$ não para se a entrada é $w$}\}$. Como se sabe, a linguagem
        $L_P=\{R\langle M,w\rangle\,|\, \mbox{$M$ para se a entrada é $w$}\}$ é LRE mas não é recursiva. Então,
				como $L_P$ é LRE, se $X$ fosse LRE, então $L_P$ seria recursiva. Como $L_P$ não é recursiva, segue-se que
				$X$ não pode ser LRE.

 \item {\footnotesize Mostre que se o problema da parada fosse decidível, então \mbox{toda LRE seria recursiva}.}

       \textit{Solução}:
       Suponha que o problema da parada seja decidível, ou seja, que haja uma MT $P$ que reconheça
       $\{R\langle M,w\rangle\,|\, \mbox{$M$ para se a entrada é $w$}\}$ e que sempre pare para toda entrada
			 $R\langle M,w\rangle$. Seja $M$ uma MT que reconheça uma LRE $L$ \emph{por parada}. Uma MT $M'$ tal que $L(M')=L(M)$, e
			 que sempre para, pode ser construída, como a seguir, utilizando-se $P$ e $M$. Seja $w$ a entrada para $M'$. Então $M'$ se
			 comporta assim:
			 \begin{enumerate}
			  \item[1.] substitui $w$ por $R\langle M,w\rangle$ na fita;
				\item[2.] se comporta como $P$ sobre esse conteúdo; nas situações em que $P$ reconhece $R\langle M,w\rangle$,
				       $M'$ para em estado final; e nas situações em que $P$ rejeita $R\langle M,w\rangle$, $M'$ para em estado não final.
			 \end{enumerate}
			 Com isto, $M'$ reconhece $w$ sse $P$ reconhece $R\langle M,w\rangle$, ou seja, 
			 $M'$ reconhece $w$ sse $M$ para se sua entrada é $w$. Como $M$ reconhece por parada, $L(M')=L(M)$. E como $M'$ sempre
			 para, qualquer que seja $w$, $L$ é recursiva.

 \item {\footnotesize Para cada PD a seguir, mostre que o mesmo é indecidível:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item dados uma MT $M$, uma palavra $w$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada
				      $w$ atinge o estado $e$;
        \item dados uma MT $M$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada $\lambda$ atinge
				      o estado $e$;
        \item dada uma MT $M$, determinar se a computação de $M$ para a entrada $\lambda$ ``volta'' ao estado inicial de $M$;
        \item dados uma MT $M$ e um símbolo $a$ de $M$, determinar se a computação de $M$ para a entrada $\lambda$ escreve
				      $a$ na fita em algum momento;
        \item dados uma MT $M$ e uma expressão regular $r$, determinar se $L(M)\cap L(r)\not=\emptyset$.
       \end{list}}

       \textit{Solução}:
       \begin{enumerate}
        \item[(a)] O problema da parada pode ser reduzido a este produzindo-se, a partir de $R\langle M,w\rangle$,
				      $R\langle M',w,e\rangle$, em que $e$ é um estado {\em novo} (não pertencente a $M$), e $M'$ é como $M$,
							a única diferença estando em que, nas situações em que $M$ para, $M'$ faz uma transição para o estado $e$.
        \item[(b)] O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de $R\langle M\rangle$,
				      $R\langle M',e\rangle$, em que $e$ é um estado {\em novo} (não pertencente a $M$), e $M'$ é como $M$,
							a única diferença estando em que, nas situações em que $M$ para, $M'$ faz uma transição para o estado $e$.
        \item[(c)] O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de $R\langle M\rangle$,
				      $R\langle M'\rangle$, em que $M'$ se comporta assim:
							\begin{enumerate}
							 \item o estado inicial de $M'$ é um estado $i$ diferente de todos os estados de $M$;
							 \item em $M'$ há uma transição de $i$ para o estado inicial de $M$ sob branco;
							 \item o resto de $M'$ é como $M$, só que nas situações em que $M$ para, $M'$ transita para o estado $i$.
							\end{enumerate}
							Com isto, $M$ para se a fita está em branco sse $M'$ volta a seu estado inicial se a fita está em branco.
        \item[(d)] O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de $R\langle M\rangle$,
				      $R\langle M',a\rangle$, em que $a$ é um símbolo de fita diferente de todos os de $M$ e $M'$ se comporta como $M$,
							a única diferença estando em que, nas situações em que $M$ para, $M'$ escreve $a$ (e vai para um estado qualquer).
        \item[(e)] O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de $R\langle M\rangle$,
				      $R\langle M,\lambda\rangle$. Supondo que o critério de reconhecimento é por parada, tem-se que:
							$\lambda \in L(M)$ (ou seja, $M$ para se a fita está em branco) sse $L(M)\cap L(\lambda)=\{\lambda\}\not=\emptyset$.
        \end{enumerate}

 \item {\footnotesize Mostre que é decidível ou que não é: dada uma MT $M$, determinar se a computação de $M$ percorre alguma transição da
       forma $\delta(e,a)=[e,b,d]$ (um laço), quando a fita é iniciada em branco.}

       \textit{Solução}:
       É indecidível. O problema da fita em branco pode ser reduzido a este produzindo-se, a partir da MT $M$, uma MT $M'$
       que é como $M$, exceto com relação aos seguintes aspectos:
			 \begin{itemize}
				\item cada laço $\delta(e,a)=[e,b,d]$ de $M$ é substituído por duas transições $\delta(e,a)=[e',b,{\tt I}]$ e
				      $\delta(e',b)=[e,b,d]$, em que $e'$ é um estado novo;
				\item se em $M$ $\delta(e,a)$ é indefinido, em $M'$ $\delta'(e,a)=[d,\sqcup,{\tt I}]$, sendo $d$ um estado novo;
				\item $M'$ contém uma transição da forma $\delta'(d,\sqcup)=[d,\sqcup,{\tt I}]$ (um laço).
			 \end{itemize}
			 Desta forma, $M$ para se iniciada com a fita em branco sse $M'$ percorre um laço se iniciada com a fita em branco.

 \item {\footnotesize Seja o problema: \emph{dada uma MT $M$, determinar se $x\in L(M)$, onde $x$ é uma palavra específica.}
       (Observe que \textbf{\textsl{o único parâmetro}} desse problema é $M$.)
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Pode-se usar o Teorema de Rice para mostrar que esse problema é indecidível? Justifique.
        \item Reduza o problema da parada a este.
        \item A linguagem $L_x=\{R\langle M\rangle\,|\,x\in L(M)\}$ é LRE? Justifique.
       \end{list}}

       \textit{Solução}:
			 \begin{enumerate}
        \item[(a)] Como $x\in L(M)$ é uma propriedade não trivial de LREs, segue-se que o problema é indecidível pelo
				       Teorema de Rice.
        \item[(b)] Uma redução mais simples do que a do teorema citado: o problema da fita em branco pode ser reduzido ao
				       problema em questão produzindo-se $R\langle M'\rangle$ a partir de $R\langle M\rangle$, de forma que:
							\begin{enumerate}
							 \item $M'$ apaga a palavra de entrada;
							 \item $M'$ se comporta como $M$.
							\end{enumerate}
							Com isto, $\lambda\in L(M)$ sse $x\in L(M)$ (qualquer que seja $x$).
				\item[(c)] $L_x$ é LRE, pois a MT universal, restrita a entradas $R\langle M,x\rangle$ reconhece $L_x$.
       \end{enumerate}

 \item {\footnotesize Mostre que os seguintes problemas são decidíveis ou não:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item Dada uma MT $M$, determinar se ela é a única que reconhece $L(M)$;
			  \item Dadas uma MT $M$, determinar se $R\langle M\rangle \in L(M)$;
			  \item Dadas MTs $M_1$ e $M_2$, determinar se $\lambda\in L(M_1)\cup L(M_2)$;
			  \item Dada uma MT $M$, determinar se $L(M)=\{R\langle M\rangle\}$;
			  \item Dada uma MT $M$, determinar se há alguma palavra com menos de 100 símbolos reconhecida por $M$;
			  \item Dada uma MT $M$, determinar se ela para se recebe como entrada um palíndromo.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item Decidível. A propriedade ``$M$ é a única MT que reconhece $L(M)$'' é trivial: qualquer linguagem é reconhecível por
				      mais de uma MT.
			  \item Indecidível. A propriedade $R\langle M\rangle \in L(M)$ não é trivial; logo, pelo teorema de Rice, o problema é
				      indecidível.
			  \item Indecidível. O problema da fita em branco pode ser reduzido a este produzindo-se, a partir de $M$ o par
				      $(M,M)$, já que $\lambda\in L(M)$ sse $\lambda\in L(M)\cup L(M)$.
			  \item Indecidível. A propriedade de ser igual a $\{R\langle M\rangle\}$ é não trivial.
			  \item Indecidível. A propriedade de ter uma palavra com menos de 100 símbolos é não trivial.
			  \item Indecidível. A propriedade de ter um palíndromo não é trivial.
       \end{list}

 \item {\footnotesize Mostre que é decidível ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Dadas uma GR $R$ e uma GLC $G$, determinar se $L(G)\subseteq L(R)$;
        \item Dadas uma GR $R$ e uma GLC $G$, determinar se $L(R)\subseteq L(G)$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Decidível. $L(G)\subseteq L(R)$ sse $L(G)\cap \overline{L(R)}=\emptyset$ sse $L(G')=\emptyset$, em que
				      $G'$ é obtida assim:
				      \begin{enumerate}
							 \item de $R$ obtém-se um AFD $M$ tal que $L(M)=L(R)$ e de $G$ uma AP $P$ tal que $L(P)=L(G)$;
							 \item de $M$ obtém-se um AFD $M'$ tal que $L(M')=\overline{L(M)}$;
							 \item de $P$ e $M'$ obtém-se um AP $P'$ tal que $L(P')=L(P)\cap L(M')$;
							 \item de $P'$ obtém-se uma GLC $G'$ tal que $L(G')=L(P')$.
							\end{enumerate}
							Como o problema de determinar se $L(G)=\emptyset$, para GLCs $G$, é decidível, o problema em questão é decidível.
        \item Indecidível. O problema de determinar se $L(G)=\Sigma^*$ pode ser reduzido a este, produzindo-se uma GR
				      que gera $\Sigma^*$, pois $L(G)=\Sigma^*$ sse $\Sigma^*\subseteq L(G)$.
       \end{list}

 \item {\footnotesize Mostre que o seguinte problema é ou não decidível: dadas duas GLCs $G_1$ e $G_2$, cada uma com uma única variável,
       determinar se $L(G_1)\cap L(G_2)=\emptyset$.}

       \textit{Solução}:
       O problema é indecidível. O PCP pode ser reduzido a este via a produção de $G_x$ e $G_y$.

 \item {\footnotesize Mostre que são indecidíveis os problemas de se determinar, dadas duas GLCs $G_1$ e
       $G_2$, que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L(G_1)=L(G_2)$;
        \item $L(G_1)\subseteq L(G_2)$.
       \end{list}}

       \textit{Solução}:
       Como $L(G)=\Sigma^*$ se e somente se $\Sigma^*\subseteq L(G)$ o problema indecidível de determinar
       se $L(G)=\Sigma^*$ pode ser reduzido a ambos os problemas fazendo-se $G_1$ uma gramática qualquer que gere
			 $\Sigma^*$ e $G_2=G$.

\end{enumerate}
\end{document}
