\documentclass[11pt,a4paper]{report}

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

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

\pagestyle{empty}
\newcounter{conta}

\begin{document}
 
\vspace*{1cm}
\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 2013 \\
Professor: Newton José Vieira \\
\noindent{\em Segunda prova}/Solução do professor    \hfill 22/10/2013

\begin{enumerate}
 \item {\footnotesize Para cada linguagem a seguir, construa um APD que a reconheça, se possível. Se não for possível,
       construa um APN. Critério de reconhecimento: por estado final \textbf{e} pilha vazia.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^n{\tt 1}^k\,|\, n>k\}$.
        \item $\{{\tt 0}^n{\tt 1}^k\,|\, n<k\}$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item APN:
				
				      \begin{picture}(120,20)(-5,0)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,5){}
               \node[Nmarks=r](2)(50,5){}

               \drawloop[loopangle=90](1){\shortstack{{\tt 0},$\lambda$/X \\ {\tt 0},$\lambda$/$\lambda$}}
               \drawedge[curvedepth=0](1,2){{\tt 0},$\lambda$/$\lambda$}
               \drawloop[loopangle=90](2){{\tt 1},X/$\lambda$}
              \end{picture}

        \item APD:
				
				      \begin{picture}(120,20)(-5,0)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,10){}
               \node(2)(50,10){}
               \node(3)(80,10){}
               \node[Nmarks=r](4)(110,10){}

               \drawedge[curvedepth=0](1,2){$\lambda$,$\lambda$/\#}
               \drawloop[loopangle=90](2){{\tt 0},$\lambda$/X}
               \drawedge[curvedepth=0](2,3){{\tt 1},X/$\lambda$}
               \drawloop[loopangle=90](3){{\tt 1},X/$\lambda$}
               \drawedge[curvedepth=0](3,4){{\tt 1},\#/$\lambda$}
               \drawloop[loopangle=90](4){{\tt 1},$\lambda$/$\lambda$}
               \drawedge[curvedepth=-7,ELside=r](2,4){{\tt 1},\#/$\lambda$}
              \end{picture}

       \end{list}

 \item {\footnotesize Seja $L=\{\verb+a+^m\verb+b+^n\verb+c+^p \,|\, m\geq n \textbf{ ou } m\geq p\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma GLC que gere $L$.
				\item Mostre que a GLC construída é ambígua ou apresente uma argumentação convincente de que não é.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P\,\rightarrow\, XC \,|\, Y$ \\
				      $X\,\rightarrow\, {\tt a}X{\tt b} \,|\, {\tt a}X \,|\, \lambda$ \\
							$C \,\rightarrow\, {\tt c}C \,|\, \lambda$ \\
				      $Y\,\rightarrow\, {\tt a}Y{\tt c} \,|\, {\tt a}Y \,|\, B$ \\
				      $B \,\rightarrow\, {\tt b}B \,|\, \lambda$
				\item A GLC é ambígua, pois há duas derivações mais à esquerda para $\lambda$:
				
				      $P\Rightarrow XC\Rightarrow C\Rightarrow \lambda$

				      $P\Rightarrow Y\Rightarrow B\Rightarrow \lambda$
       \end{list}

 \item {\footnotesize Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe gramática regular ambígua.
				\item Não existe linguagem regular inerentemente ambígua.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É ambígua: \parbox[t]{3cm}{$P\rightarrow {\tt a}A \,|\, {\tt a}$ \\ $A\rightarrow\lambda$}
				\item Para qualquer linguagem regular existe um AFD $M$ que a reconhece. Obtendo-se a gramática regular $G$ a
				      partir $M$, tem-se para qualquer palavra $w$:
							\begin{itemize}
							 \item Existe uma única computação possível para $w$ em $M$, pois $M$ é determinística.
							 \item À computação para $w$ em $M$ corresponde uma única derivação em $G$, propiciada por:
							   \[\delta(X,a)=Y \mbox{ é transição em } M \mbox{ sse } X\rightarrow aY \mbox{ é regra em } G\mbox{.}\]
							 \item Como $G$ é regular, tal derivação de $w$ é mais à esquerda. Portanto, existe uma única derivação mais
							       à esquerda de $w$ em $G$. Logo, $G$ não é ambígua.
							\end{itemize}
       \end{list}

 \item {\footnotesize Prove que $L=\{\verb+a+^m\verb+b+^n\verb+c+^p \,|\, m\geq n \textbf{ e } m\geq p\}$ não é
       livre do contexto.}

       \textit{Solução}:

       Suponha que $L$ é livre do contexto. Seja $k$ a constante do LB e $z={\tt a}^k{\tt b}^k{\tt c}^k$. Como
			 $|z|>k$, o lema diz que existem $u$, $v$, $w$, $x$ e $y$ tais que $z=uvwxy$, $|vwx|\leq k$, $vx\not=\lambda$ e
			 $uv^iwx^iy\in L$ para todo $i\in\textbf{N}$. Sejam, então, $u$, $v$, $w$, $x$ e $y$ tais que $z=uvwxy$, $|vwx|\leq k$ e
			 $vx\not=\lambda$. Dois casos a considerar:
			 \begin{itemize}
			 \item $vx$ contém {\tt a}. Como $uvwxy={\tt a}^k{\tt b}^k{\tt c}^k$ e $|vwx|\leq k$, $vx$ não contém {\tt c}s e,
			       portanto, $uv^0wx^0y$ tem menos {\tt a}s do que {\tt c}s. Portanto, $uv^0wx^0y\not\in L$.
			 \item $vx$ não contém {\tt a}. Como  $vx\not=\lambda$, $uv^2wx^2y$ tem menos {\tt a}s do que {\tt b}s ou
			       menos {\tt a}s do que {\tt c}s e, portanto, $uv^2wx^2y\not\in L$.
       \end{itemize}
       Assim, em qualquer caso existe $i$ tal que $uv^iwx^iy\not\in L$, o que contradiz o LB. Portanto, $L$ não é
			 livre do contexto.

 \item {\footnotesize Dada uma GLC qualquer, como se obtém uma GLC equivalente sem regras unitárias? Descreva de forma
       \textbf{precisa} um método para tal obtenção.  (Regras unitárias são da forma $A\,\rightarrow\,B$, em que $A$ e
			 $B$ são variáveis.)}

       \textit{Solução}:

        Seja uma GLC $G=(V,\Sigma,R,P)$. Para obter $G'$ sem regras unitárias equivalente:
			 \begin{itemize}
				 \item Determine para cada $X\in V$:
				       \[\mbox{enc}(X)=\{X\}\cup\{Y_n\in V\,|\, X\rightarrow Y_1,Y_1\rightarrow Y_2, \ldots,
				         Y_{n-1}\rightarrow Y_n\in R, \forall i\geq 1(Y_i\in V)\}\mbox{.}\]
				 \item $G'=(V,\Sigma,R',P)$, em que
               \[R'=\{X\rightarrow w \,|\, w\not\in V \mbox{ e } \mbox{ existe } Y\in \mbox{enc}(X) \mbox{ tal que }
                 Y\rightarrow w\in R\}\mbox{.}\]

			 \end{itemize}
			
 \item {\footnotesize Apresente exemplos de LLCs $L_1$ e $L_2$ tais que $L_1\cap L_2$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É regular.
        \item É LLC, mas não é regular.
				\item Não é LLC.
       \end{list}}

       \textit{Solução}:

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

\end{document}
