\documentclass[12pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{amsfonts}
\usepackage{gastex}
\usepackage[usenames]{color}

\usepackage{fullpage}

\newcounter{conta}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computação} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2016 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\it Terceira Prova}/Solução do professor  \hfill 28/6/2016

\begin{enumerate}
 \item {\footnotesize Dê exemplos de linguagens $L_1$ e $L_2$ tais que $L_1\subseteq L_2$ e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1$ é LLC e $L_2$ também é LLC.
        \item $L_1$ é LLC, mas $L_2$ não é LLC.
        \item $L_1$ não é LLC, mas $L_2$ é LLC.
        \item $L_1$ não é LLC e $L_2$ também não é LLC.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=L_2=\emptyset$.
        \item $L_1=\emptyset$, $L_2=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\in\mathbb{N}\}$.
        \item $L_1=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\in\mathbb{N}\}$, $L_2=\{{\tt a},{\tt b},{\tt c}\}^*$.
        \item $L_1=L_2=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\,n\in\mathbb{N}\}$.
       \end{list}

 \item {\footnotesize Crie MTs que reconheçam $(aa)^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item por parada;
        \item por estado final.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \ 
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(66,11)
                \gasset{Nw=5, Nh=5, Nmr=5, ELdist=0.5, loopdiam=4, fillgray=0.9}

                \node[Nmarks=i](1)(20,6){}
                \node(2)(40,6){}

                \drawedge[curvedepth=3](1,2){${\tt a}/\sqcup\, {\tt D}$}
                \drawedge[curvedepth=3](2,1){${\tt a}/\sqcup\, {\tt D}$}
                \drawloop[loopangle=0](2){$\sqcup/\sqcup\, {\tt D}$}
               \end{picture}
              }
        \item \ 
				
				      \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(66,24)
                \gasset{Nw=5, Nh=5, Nmr=5, ELdist=0.5, loopdiam=4, fillgray=0.9}

                \node[Nmarks=i](1)(20,19){}
                \node(2)(40,19){}
                \node[Nmarks=r](3)(20,4){}

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

 \item {\footnotesize Faça uma MT de \emph{duas fitas} que reconheça a linguagem:
       $$\{xx^Ry \,|\, x\in\{{\tt 0},{\tt 1}\}^*, y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|>|y|\}\mbox{.}$$
			 Ela pode ser \emph{não determinística}.}

       \textit{Solução}:

       Supondo $b\in\{{\tt 0},{\tt 1}\}$:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,40)
         \gasset{Nw=5, Nh=5, Nmr=5, ELdist=0.5, loopdiam=4, fillgray=0.9}

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

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

 \item {\footnotesize Construa uma gramática sensível ao contexto que gere $\{xwx \,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e }
       w\in\{{\tt a},{\tt b}\}^+\}\mbox{.}$}

       \textit{Solução}:

       \begin{quote}
			  $P\,\rightarrow\, {\tt 0}PZ \,|\, {\tt 1}PU \,|\, X$ \\
			  $XZ\,\rightarrow\, X{\tt 0}$ \\
			  $XU\,\rightarrow\, X{\tt 1}$ \\
			  ${\tt 0}Z\,\rightarrow\, Z{\tt 0}$ \\
			  ${\tt 1}Z\,\rightarrow\, Z{\tt 1}$ \\
			  ${\tt 0}U\,\rightarrow\, U{\tt 0}$ \\
			  ${\tt 1}U\,\rightarrow\, U{\tt 1}$ \\
			  $X\,\rightarrow\, {\tt a}X \,|\, {\tt b}X \,|\, {\tt a} \,|\, {\tt b}$
			 \end{quote}

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

       \textit{Solução}:

       Seja $M$ uma MT qualquer. Se o problema da parada fosse decidível, então seria possível construir uma MT $M'$,
			 equivalente a $M$, que sempre para, como segue. Seja $w$ uma palavra de entrada qualquer para $M'$.
			 \begin{enumerate}
			  \item $M'$ verifica se $M$ para se a entrada é $w$, usando uma subMT (solução do problema da parada) para isso,
				      já que o problema é decidível;
				\item no caso em que $M$ para: se para em estado final, $M'$ para em estado final; caso contrário,
				      $M'$ para em estado não final;
				\item no caso em que $M$ não para: $M'$ para em estado não final.
       \end{enumerate}
       Como $M'$, se comportando como descrito, reconhece a mesma linguagem que $M$ e sempre para qualquer que seja a
			 palavra de entrada, $L(M)$ seria recursiva.

 \item {\footnotesize Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item dada uma gramática irrestrita $G$, determinar se $L(G)\not=\emptyset$.
        \item dada uma MT $M$, determinar se $M$ passa duas vezes por algum estado ao processar $\lambda$.
			 \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Pelo Teorema de Rice, o problema de, dada uma MT $M$, determinar se $L(M)\not=\emptyset$ é indecidível, pois a
				      propriedade $L(M)\not=\emptyset$ é não trivial. A partir de uma MT $M$ qualquer é possível construir uma gramática
							irrestrita $G$ tal que $L(G)=L(M)$, como visto no curso, reduzindo-se, assim, aquele problema indecidível ao
							presente problema. Logo este é indecidível.

        \item Simulando-se $M$ para a palavra de entrada $\lambda$ por meio de uma MT $M'$, $M'$ anota os estados por que
				      vai passando (por exemplo, em uma fita extra). Como o conjunto de estados é finito, $M'$ será capaz de detectar
							se algum estado se repete. Logo, o problema é decidível.
			 \end{list}
\end{enumerate}

\end{document}
