\documentclass[12pt,a4paper]{report}

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

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

\usepackage{comment}

\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 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Prova Suplementar}/Solução do professor \hfill 7/12/2017

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Apresente diagramas de estados de AFDs mínimos que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $(00+1)^*(0+11)^*$;
        \item o complemento da linguagem anterior.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item \ 
				
				 \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,10)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=ir](A)(20,5){}
          \node[Nmarks=r](B)(40,5){}
          \node(C)(60,5){}
          \node[Nmarks=r](D)(80,5){}

          \drawedge[curvedepth=3](A,B){{\tt 0}}
          \drawloop[loopangle=90](A){{\tt 1}}
          \drawedge[curvedepth=3](B,A){{\tt 0}}
          \drawedge[curvedepth=0](B,C){{\tt 1}}
          \drawedge[curvedepth=3](C,D){{\tt 1}}
          \drawedge[curvedepth=3](D,C){{\tt 1}}
          \drawloop[loopangle=90](D){{\tt 0}}
         \end{picture}
        }

			\item \ 
			
			   \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,25)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=i](A)(20,20){}
          \node(B)(40,20){}
          \node[Nmarks=r](C)(60,20){}
          \node(D)(80,20){}
          \node[Nmarks=r](E)(60,5){}

          \drawedge[curvedepth=3](A,B){{\tt 0}}
          \drawloop[loopangle=90](A){{\tt 1}}
          \drawedge[curvedepth=3](B,A){{\tt 0}}
          \drawedge[curvedepth=0](B,C){{\tt 1}}
          \drawedge[curvedepth=3](C,D){{\tt 1}}
          \drawedge[curvedepth=3](D,C){{\tt 1}}
          \drawloop[loopangle=90](D){{\tt 0}}
          \drawloop[loopangle=0](E){{\tt 0},{\tt 1}}
          \drawedge[curvedepth=0](C,E){{\tt 0}}
         \end{picture}
        }
       \end{list}

 \item {\footnotesize Seja o AFN$\lambda$ com o diagrama de estados:

       \begin{picture}(65,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(10,20){1}
        \node(2)(25,30){2}
        \node(3)(25,10){3}
        \node[Nmarks=r](4)(40,20){4}

%        \put(30,0){\makebox(0,0){\textbf{(a) AFN$\lambda$ 1.}}}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawedge[curvedepth=0, ELside=r](1,3){{\tt a}}
        \drawedge[curvedepth=0](2,4){{\tt b}}
        \drawloop[loopangle=90](2){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](3,4){$\lambda$}
        \drawloop[loopangle=270](3){{\tt b}}
        \drawloop[loopangle=0](4){{\tt c}}
       \end{picture}

       Obtenha:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item um AFN equivalente usando o método visto no curso;
        \item para cada $(e,s)$ tal que $s\not=\lambda$ e $|\delta(e,s)|>1$ indique o cálculo de
				      $\delta'(e,s)$, sendo $\delta$ a função de transição do AFN$\lambda$ e $\delta'$ a do
							AFN obtido.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
               \item AFN:

    						\mbox{\setlength{\unitlength}{1mm}
                 \begin{picture}(65,40)
                  \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
                  \node[Nmarks=i, iangle=180](1)(10,25){1}
                  \node[Nmarks=i ,iangle=180](2)(25,35){2}
                  \node(3)(25,15){3}
                  \node[Nmarks=r](4)(40,25){4}

                  \drawedge[curvedepth=0, ELside=r](1,3){{\tt a}}
                  \drawedge[curvedepth=0](1,4){{\tt a}}
                  \drawedge[curvedepth=0](2,4){{\tt b}}
                  \drawloop[loopangle=90](2){{\tt a}}
                  \drawedge[curvedepth=0, ELside=r](3,4){\tt b}
                  \drawloop[loopangle=270](3){{\tt b}}
                  \drawloop[loopangle=0](4){{\tt c}}
                 \end{picture}
								}
							 \item $\delta'(1,{\tt a})=f\lambda(\delta(1,{\tt a}))=f\lambda(\{3\})=\{3,4\}$; \\
                     $\delta'(3,{\tt b})=f\lambda(\delta(3,{\tt b}))=f\lambda(\{3\})=\{3,4\}$.
				\end{list}

  \item {\footnotesize Para a linguagem $\{x\overline{x}^R\,|\, x\in \{{\tt 0},{\tt 1}\}^+\}$ ($\overline{x}$ é o complemento de $x$):
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item mostre que ela é livre do contexto;
        \item prove que ela não é regular usando o teorema da invariância à direita ou o lema do bombeamento.
			 \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item GLC: $P \,\rightarrow\, {\tt 0}P{\tt 1} \,|\, {\tt 1}P{\tt 0} \,|\, {\tt 01} \,|\, {\tt 10}$
        \item Seja $R=\{{\tt 0}\}^+$, e sejam ${\tt 0}^i$ e ${\tt 0}^j$ ($i\not=j$) duas palavras arbitrárias de $R$.
							Tem-se que ${\tt 0}^i{\tt 1}^i$ pertence à linguagem e ${\tt 0}^j{\tt 1}^i$ não pertence. Logo,
							pelo teorema da invariância à direita, a linguagem em questão não é regular.
			 \end{list}

 \item {\footnotesize Seja a gramática:
	     \begin{enumerate}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
	      \item[\ ] $A\,\rightarrow\, ABC \,|\, A{\tt a}$
	      \item[\ ] $B\,\rightarrow\, CBC \,|\, CE$
	      \item[\ ] $C\,\rightarrow\, EB \,|\, {\tt b}C \,|\, \lambda$
	      \item[\ ] $D\,\rightarrow\, BB \,|\, AE \,|\, {\tt b}$
	      \item[\ ] $E\,\rightarrow\, DCC \,|\, {\tt ab} \,|\, \lambda$
	      \end{enumerate}
       Explicite o conjunto de variáveis anuláveis e apresente uma GLC equivalente sem regras $\lambda$.}

       \textit{Solução}:
       Variáveis anuláveis: $\textit{VA}=\{C,E,B,D\}$. A GLC resultante é:
	     \begin{enumerate}
	      \item[\ ] $A\,\rightarrow\, ABC \,|\, AB \,|\, AC \,|\, A{\tt a}$
	      \item[\ ] $B\,\rightarrow\, CBC \,|\, BC \,|\, CB \,|\, CC \,|\, B \,|\, C \,|\, CE \,|\, E$
	      \item[\ ] $C\,\rightarrow\, EB \,|\, B \,|\, E \,|\, {\tt b}C \,|\, {\tt b}$
	      \item[\ ] $D\,\rightarrow\, BB \,|\, B \,|\, AE \,|\, A \,|\, {\tt b}$
	      \item[\ ] $E\,\rightarrow\, DCC \,|\, CC \,|\, DC \,|\, C \,|\, D \,|\, {\tt ab}$
	      \end{enumerate}

 \item {\footnotesize Seja $L$ uma linguagem \emph{não} recursiva. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\overline{L}$ não é recursiva;
        \item se $L$ é LRE, então $\overline{L}$ não é LRE.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Suponha que $\overline{L}$ seja recursiva. Então, como as linguagens recursivas
              são fechadas sob complementação, $\overline{\overline{L}}=L$ é recursiva.
              Mas $L$ não é recursiva! Logo, $\overline{L}$ não pode ser recursiva.
        \item Se $L$ e $\overline{L}$ fossem ambas LREs, então, pelo Teorema 36, $L$ seria recursiva.
              Mas $L$ não é recursiva! Logo, se $L$ é LRE, $\overline{L}$ não é LRE.
       \end{list}

\item {\footnotesize Para cada problema a seguir, mostre que ele é decidível ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item dada 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)| \leq 1$;
			  \item dada uma MT $M$, determinar se ela é a única que reconhece $L(M)$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item $R\langle M\rangle \in L(M)$ é uma propriedade não trivial de LRE. Logo, pelo Teorema de Rice o problema é
				      indecidível.
			  \item O problema indecidível de determinar se $\lambda\in L(M)$ pode ser reduzido a este fazendo-se
				      $M_1=M_2=M$.
			  \item $|L(M)| \leq 1$ é uma propreidade não trivial de LRE. Logo, pelo Teorema de Rice o problema é
				      indecidível.
			  \item A resposta é sempre não: nenhuma MT é a única que reconhece uma LRE. Logo, o problema é decidível.
       \end{list}
\end{enumerate}

\end{document}
