\documentclass[11pt,a4paper]{report}

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

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

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2014 \\
Professor: Newton José Vieira \\
 
\noindent {\bf Segunda Prova}/Solução do professor

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Construa um AFD que reconheça a linguagem denotada por $(01)^*(00+1)^*01$.}

       \textit{Solução:}

       Um AFN$\lambda$:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,26)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(20,8){1}
          \node(2)(20,25){2}
          \node(3)(40,8){3}
          \node(4)(40,25){4}
          \node(5)(60,8){5}
          \node[Nmarks=r](6)(80,8){6}

          \drawedge[curvedepth=3](1,2){\tt 0}
          \drawedge[curvedepth=0](1,3){$\lambda$}
          \drawedge[curvedepth=3](2,1){\tt 1}
          \drawloop[loopangle=270](3){\tt 1}
          \drawedge[curvedepth=3](3,4){\tt 0}
          \drawedge[curvedepth=3](4,3){\tt 0}
          \drawedge[curvedepth=0](3,5){\tt 0}
          \drawedge[curvedepth=0](5,6){\tt 1}
         \end{picture}
        }
      \end{center}

       AFN correspondente:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,26)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(20,8){1}
          \node(2)(20,25){2}
          \node[Nmarks=i](3)(40,8){3}
          \node(4)(40,25){4}
          \node(5)(60,8){5}
          \node[Nmarks=r](6)(80,8){6}

          \drawedge[curvedepth=3](1,2){\tt 0}
          \drawedge[curvedepth=0](2,3){\tt 1}
          \drawedge[curvedepth=3](2,1){\tt 1}
          \drawloop[loopangle=270](3){\tt 1}
          \drawedge[curvedepth=3](3,4){\tt 0}
          \drawedge[curvedepth=3](4,3){\tt 0}
          \drawedge[curvedepth=0](3,5){\tt 0}
          \drawedge[curvedepth=0](5,6){\tt 1}
         \end{picture}
        }
      \end{center}

       AFD correspondente:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,28)
          \gasset{Nw=8, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](13)(20,25){13}
          \node(245)(40,27){245}
          \node[Nmarks=r](136)(60,22){136}
          \node(3)(20,5){3}
          \node(45)(40,0){45}
          \node[Nmarks=r](6)(60,0){6}

          \drawedge[curvedepth=0](13,245){\tt 0}
          \drawedge[curvedepth=0,ELside=r](13,3){\tt 1}
          \drawedge[curvedepth=0,ELside=r](245,3){\tt 0}
          \drawedge[curvedepth=2](245,136){\tt 1}
          \drawedge[curvedepth=2](136,245){\tt 0}
          \drawedge[curvedepth=0,ELside=r](136,3){\tt 1}
          \drawloop[loopangle=180](3){\tt 1}
          \drawedge[curvedepth=2](3,45){\tt 0}
          \drawedge[curvedepth=2](45,3){\tt 0}
          \drawedge[curvedepth=0](45,6){\tt 1}
         \end{picture}
        }
      \end{center}

 \item {\footnotesize Obtenha uma expressão que denote a linguagem reconhecida pelo AFD:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,38)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(20,28){1}
          \node[Nmarks=r](2)(50,28){2}
          \node(3)(50,8){3}
          \node[Nmarks=r](4)(20,8){4}

          \drawloop[loopangle=90](1){\tt 1}
          \drawedge[curvedepth=0](1,2){\tt 0}
          \drawloop[loopangle=90](2){\tt 0}
          \drawedge[curvedepth=0](2,3){\tt 1}
          \drawloop[loopangle=270](3){\tt 1}
          \drawedge[curvedepth=0](3,4){\tt 0}
          \drawedge[curvedepth=0](4,1){\tt 1}
          \drawedge[curvedepth=0](4,2){\tt 0}
         \end{picture}
        }
      \end{center}}

      \textit{Solução:}

      Acrescentando-se um estado final, $f$, com transições $\lambda$ de 2 e de 4 para $f$, e eliminando-se 3 em seguida:

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

          \node[Nmarks=i](1)(20,10){1}
          \node(2)(45,20){2}
          \node[Nmarks=r](f)(70,10){f}
          \node(4)(45,0){4}

          \drawloop[loopangle=90](1){$1$}
          \drawedge[curvedepth=0](1,2){$0$}
          \drawloop[loopangle=90](2){$0$}
          \drawedge[curvedepth=2](2,4){$1^+0$}
          \drawedge[curvedepth=0](2,f){$\lambda$}
          \drawedge[curvedepth=0](4,1){$1$}
          \drawedge[curvedepth=2](4,2){$0$}
          \drawedge[curvedepth=0](4,f){$\lambda$}
         \end{picture}
        }
      \end{center}

      Eliminando-se 4:

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

          \node[Nmarks=i](1)(20,8){1}
          \node(2)(45,8){2}
          \node[Nmarks=r](f)(70,8){f}

          \drawloop[loopangle=90](1){$1$}
          \drawedge[curvedepth=2](1,2){$0$}
          \drawloop[loopangle=90](2){$0+1^+00$}
          \drawedge[curvedepth=0](2,f){$\lambda+1^+0$}
          \drawedge[curvedepth=2](2,1){$1^+01$}
         \end{picture}
        }
      \end{center}

      Eliminando-se 2:

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

          \node[Nmarks=i](1)(20,8){1}
          \node[Nmarks=r](f)(70,8){f}

          \drawloop[loopangle=90](1){$1+0(0+1^+00)^*1^+01$}
          \drawedge[curvedepth=0](1,f){$0(0+1^+00)^*(\lambda+1^+0)$}
         \end{picture}
        }
      \end{center}

      ER: $(1+0(0+1^+00)^*1^+01)^*0(0+1^+00)^*(\lambda+1^+0)$.

 \item {\footnotesize Construa uma GLC que gere $\{\verb+a+^m\verb+b+^n\verb+c+^k \,|\, m\geq n \mbox{ ou } n\leq k\}$.
       Prove que sua GLC é ambígua mostrando duas derivações mais a esquerda de $\lambda$ (se houver).}

      \textit{Solução:}

      GLC:
			\begin{quote}
			 $P \,\rightarrow\, XC \,|\, AY$ \\
			 $X \,\rightarrow\, {\tt a}X \,|\, {\tt a}X{\tt b} \,|\, \lambda$ \ \ \ \ gera $\{\verb+a+^m\verb+b+^n \,|\, m\geq n\}$\\
			 $C \,\rightarrow\, {\tt c}C \,|\, \lambda$ \\
			 $Y \,\rightarrow\, {\tt b}Y{\tt c} \,|\, Y{\tt c} \,|\, \lambda$ \ \ \ \ gera $\{\verb+b+^n\verb+c+^k \,|\, n\leq k\}$\\
			 $A \,\rightarrow\, {\tt a}A \,|\, \lambda$ \\
			\end{quote}

       Duas derivações mais a esquerda de $\lambda$:
			\begin{quote}
			 1: $P \,\Rightarrow\, XC \,\Rightarrow\, C \,\Rightarrow\, \lambda$ \\
			 2: $P \,\Rightarrow\, AY \,\Rightarrow\, Y \,\Rightarrow\, \lambda$
			\end{quote}

 \item {\footnotesize Seja a GLC:
     	\begin{enumerate}
	     \item[\ ] $P\,\rightarrow\, A \,|\, {\tt 10}$
     	 \item[\ ] $A\,\rightarrow\, {\tt 0} A {\tt 1} \,|\, B$
	     \item[\ ] $B\,\rightarrow\, {\tt 00}B \,|\, B{\tt 11} \,|\, \lambda$
	    \end{enumerate}
 	    Aplique, em sequência, os métodos vistos em aula para:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item eliminar regras $\lambda$;
       \item eliminar regras unitárias.
       \item obter uma GLC equivalente na forma normal de Chomsky.
      \end{list}}

      \textit{Solução:}

      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item Variáveis anuláveis: $\{B,A,P\}$. GLC resultante:
     	      \begin{quote}
	           $P\,\rightarrow\, A \,|\, {\tt 10} \,|\, \lambda$ \\
     	       $A\,\rightarrow\, {\tt 0} A {\tt 1} \,|\, {\tt 01} \,|\, B$\\
	           $B\,\rightarrow\, {\tt 00}B \,|\, B{\tt 11} \,|\, {\tt 00} \,|\, {\tt 11}$
	          \end{quote}
       \item $\mbox{enc}(P)=\{P,A,B\}$, $\mbox{enc}(A)=\{A,B\}$, $\mbox{enc}(B)=\{B\}$. GLC resultante:
     	      \begin{quote}
	           $P\,\rightarrow\, {\tt 0} A {\tt 1} \,|\, {\tt 01} \,|\, {\tt 10} \,|\, {\tt 00}B \,|\, B{\tt 11} \,|\,
						                   {\tt 00} \,|\, {\tt 11} \,|\, \lambda$ \\
     	       $A\,\rightarrow\, {\tt 0} A {\tt 1} \,|\, {\tt 01} \,|\, {\tt 00}B \,|\, B{\tt 11} \,|\, {\tt 00} \,|\, {\tt 11}$\\
	           $B\,\rightarrow\, {\tt 00}B \,|\, B{\tt 11} \,|\, {\tt 00} \,|\, {\tt 11}$
	          \end{quote}
       \item Forma normal de Chomsky:
     	      \begin{quote}
	           $P\,\rightarrow\, ZR \,|\, ZU \,|\, UZ \,|\, ZS \,|\, BT \,|\, ZZ \,|\, UU \,|\, \lambda$ \\
     	       $A\,\rightarrow\, ZR \,|\, ZU \,|\, ZS \,|\, BT \,|\, ZZ \,|\, UU$\\
	           $B\,\rightarrow\, ZS \,|\, BT \,|\, ZZ \,|\, UU$ \\
	           $R\,\rightarrow\,  AU$ \\
	           $S\,\rightarrow\,  ZB$ \\
	           $T\,\rightarrow\,  UU$ \\
	           $Z\,\rightarrow\, {\tt 0}$ \\
	           $U\,\rightarrow\, {\tt 1}$
	          \end{quote}
      \end{list}
 \item {\footnotesize Prove que $\{\verb+a+^m\verb+b+^n\verb+c+^k \,|\, k=\textit{min}(m,n)\}$ é ou que não é livre do contexto.
       $\textit{min}(m,n)$ é o menor valor entre $m$ e $n$.}

      \textit{Solução:}

      Seja $L$ a linguagem em questão e suponha que a mesma seja livre do contexto. Seja $k$ a constante do LB e
			$z={\tt a}^k{\tt b}^k{\tt c}^k$. Como $|z|>k$, o LB diz que existem $u,v,w,x,y$ tais que $z=uvwxy$, $|vwx|\leq k$,
			$|vx|>0$ e $uv^iwx^iy\in L$ para todo $i\geq 0$. Considere os dois casos:
			\begin{enumerate}
			 \item[1.] $vx$ contém o símbolo {\tt c}. Como $|vwx|\leq k$, $vx$ não contém {\tt a}s. E como $|vx|>0$, $uv^2wx^2y$
			         contém mais {\tt c}s do que {\tt a}s (o número de {\tt a}s é $k$ e o de {\tt c}s é maior do que $k$) e,
							 portanto, o número de {\tt c}s não é o mínimo entre o número de {\tt a}s e o de {\tt b}s . Logo,
							 $uv^2wx^2y\not\in L$.
			 \item[2.] $vx$ não contém {\tt c}. Como $|vx|>0$, $uv^0wx^0y$ contém mais {\tt c}s do que {\tt a}s e/ou {\tt b}s
			         (o número de {\tt a}s e/ou de {\tt b}s é menor do que $k$ e o de {\tt c}s é $k$) e, portanto, o número de
							 {\tt c}s não é o mínimo entre o número de {\tt a}s e o de {\tt b}s. Logo, $uv^2wx^2y\not\in L$.
			\end{enumerate}
      Portanto, em qualquer caso há contradição com o que diz o LB, podendo-se concluir que $L$ não é livre do contexto.
\end{enumerate}

\end{document}
