\documentclass[11pt,a4paper]{book}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{verbatim}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\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}/DINTER
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Terceira Prova}/Solução do professor \hfill 19/11/2010

\vspace*{3mm}
\begin{flushleft}
Valor de cada quest\~ao: 4 pontos, exceto a última, que vale 2 pontos.
\end{flushleft}

\begin{enumerate}

 \item {\footnotesize Construa uma m\'aquina de Turing n\~ao determin\'{\i}stica de duas fitas que reconhe\c{c}a:
       \[\{x{\tt 1}^n \,|\, n\geq 0,\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=n\}\mbox{.}\]
       O cabe\c{c}ote da \textit{fita de entrada\/} (fita 1) s\'o poder\'a se movimentar para a \textit{direita\/}
       (ou seja, a m\'aquina dever\'a dar uma \'unica passada sobre a palavra de entrada).}

       \textit{Solução}:

       \mbox{\setlength{\unitlength}{1mm} \footnotesize
                    \begin{picture}(100,20)(0,4)
                     \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

                     \node[Nmarks=ir](0)(30,5){}
                     \node(1)(60,5){}
                     \node(2)(90,5){}
                     \node[Nmarks=r](3)(120,5){}

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

 \item {\footnotesize Fa\c{c}a uma gram\'atica irrestrita que gere:
       \[\{x{\tt 1}x \,|\, n\geq 0,\, x\in\{{\tt 0} \mbox{ e } {\tt 1}\}^*\}\mbox{.}\]
       Se a gramática for sensível ao contexto, você ganha um ponto a mais.}

       \textit{Solução}: Segue uma GSC.

       \begin{enumerate}
        \item[\ ] $P \,\rightarrow\, {\tt 0}PZ \,|\, {\tt 1}PU \,|\, M$
        \item[\ ] ${\tt 0}Z \,\rightarrow\, Z{\tt 0}$
        \item[\ ] ${\tt 1}Z \,\rightarrow\, Z{\tt 1}$
        \item[\ ] ${\tt 0}U \,\rightarrow\, U{\tt 0}$
        \item[\ ] ${\tt 1}U \,\rightarrow\, U{\tt 1}$
        \item[\ ] $MZ \,\rightarrow\, M{\tt 0}$
        \item[\ ] $MU \,\rightarrow\, M{\tt 1}$
        \item[\ ] $M \,\rightarrow\, {\tt 1}$
       \end{enumerate}

 \item {\footnotesize Sejam $R$ uma linguagem recursiva e $L$ uma linguagem recursivamente enumer\'avel. Para os
       casos a seguir, diga se a linguagem \'e (1) \underline{necessariamente} recursivamente
       enumer\'avel, (2) \underline{necessariamente} não recursivamente enumer\'avel, ou (3) nem uma
       coisa nem outra (ou seja, pode ser recursivamente enumerável e pode não ser). Justifique suas
       respostas (resposta sem justificativa válida será desconsiderada).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\Sigma^*-R$.
        \item $\Sigma^*-L$.
        \item $L-R$.
        \item $R-L$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\Sigma^*-R$ é recursiva, pois a classe das linguagens recursivas é fechada sob complementação.
              Logo, $\Sigma^*-R$ é necessariamente recursivamente enumerável.
        \item Como as linguagens recursivamente enumeráveis não são fechadas sob complementação, $\Sigma^*-L$
              pode não ser recursivamente enumerável. Mas pode ser (por exemplo, nos casos em que $L$ é
              recursiva).
        \item As linguagens recursivamente enumeráveis são fechadas sob interseção e as recursivas sob complementação.
              Logo, $L-R=L\cap \overline{R}$ é recursivamente enumerável.
        \item Segue de (b) que $R-L$ pode ser e pode não ser recursivamente enumerável.
       \end{list}

 \item {\footnotesize Mostre para cada um dos seguintes problemas, se ele é decid\'{\i}vel ou n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma máquina de Turing $M$ e um número natural $n$, determinar se $M$
              reconhece alguma palavra de $n$ símbolos.
        \item Dada uma máquina de Turing $M$ e uma palavra $w$, determinar se, ao processar $w$, $M$ passa
              por algum estado mais de uma vez.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Indecidível. Se este problema fosse decidível, o da fita em branco também seria, pois:
              \begin{quote}
               $\lambda \in L(M) \,\leftrightarrow\, M \mbox{ reconhece palavra com zero símbolos}$.
              \end{quote}
              Mas, o problema da fita em branco é indecidível.
        \item Decidível. Simulando-se $M$ sobre $w$, marcar cada estado em que $M$ passa. Se $M$ parar sem passar por
              algum estado já marcado, retornar \textit{não} ($M$ não passa por algum estado mais de uma vez).
              Se $M$ voltar a algum estado já marcado, retornar \textit{sim} ($M$ passa por algum estado mais
              de uma vez). Como o conjunto de estados de $M$ é finito, o processo termina retornando sim ou não.
       \end{list}

 \item {\footnotesize No contexto do Teorema de Rice, o que é uma propriedade trivial de LREs? Enuncie o Teorema de Rice
       e dê dois exemplos de aplicação dele.}

       \textit{Solução}:
       \begin{itemize}
        \item Uma propriedade trivial é aquela que é satisfeita por toda LRE ou por nenhuma LRE.
        \item Teorema de Rice: Se $P$ é uma propriedade não trivial, então $\{R\langle M\rangle \,|\, L(M)
              \mbox{ satisfaz } P\}$ não é recursiva.
        \item Dois exemplos de problemas indecidíveis, pelo Teorema de Rice:
              \begin{enumerate}
	             \item[(1)] Dada uma MT $M$, determinar se $\lambda\in L(M)$.
	             \item[(2)] Dada uma MT $M$, determinar se $L(M)$ é uma linguagem regular.
              \end{enumerate}
      \end{itemize}
\end{enumerate}

\end{document}