\documentclass[12pt,a4paper]{report}

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

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

\newcounter{conta}
\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 2015 \\
\textbf{Segunda Prova}/Solução do professor \hfill 27/10/2015 \\
 
\vspace*{2mm}
\begin{enumerate}
 \item {\footnotesize Encontre uma expressão regular que denote $\{{\tt 0}^m{\tt 1}^n\,|\, m+n \mbox{ é ímpar }\}$.}

       \emph{Solução}: $(00)^*(0+1)(11)^*$.

 \item {\footnotesize Construa um AFN  de 3 estados que reconheça $(a+b)^*bc^*+(a+d)^*dc^*$.}

       \emph{Solução}:

         \begin{picture}(50,42)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

          \drawloop[loopangle=90](1){{\tt a},{\tt b}}
          \drawedge[curvedepth=0](1,3){\tt b}
          \drawloop[loopangle=270](2){{\tt a},{\tt d}}
          \drawedge[curvedepth=0](2,3){\tt d}
          \drawloop[loopangle=0](3){\tt c}
         \end{picture}

 \item {\footnotesize Construa uma GLC e um AP para a linguagem $\{\verb+a+^{m+n}\verb+b+^{m}\verb+c+^n \,|\, m+n\geq 1\}$.}

       \emph{Solução}:

       GLC:
			 \begin{quote}
			  $P\,\rightarrow\, {\tt a}P{\tt c} \,|\, {\tt a}X{\tt b} \,|\, {\tt a}X{\tt c}$ \\
			  $X\,\rightarrow\, {\tt a}X{\tt b} \,|\, \lambda$
			 \end{quote}

       AP:

         \begin{picture}(50,30)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

          \drawedge[curvedepth=0](1,2){$\lambda,\lambda/P$}
          \drawloop[loopangle=0](2){\shortstack[l]{${\tt a},P/P{\tt c} \;\; \lambda,X/\lambda$ \\
					 ${\tt a},P/X{\tt b} \;\; {\tt b},{\tt b}/\lambda$ \\
					 ${\tt a},P/X{\tt c} \;\; {\tt c},{\tt c}/\lambda$ \\ ${\tt a},X/X{\tt b}$}}
         \end{picture}

 \item {\footnotesize Descreva como eliminar regras unitárias em GLCs.}

       \emph{Solução}: Uma GLC equivalente a $G=(V,\Sigma,R,P)$ sem regras unitárias é
			 $G'=(V,\Sigma,R',P)$, em que
       \[R'=\{X\rightarrow w \,|\, \mbox{ existe } Y\in \mbox{\em enc\/}(X) \mbox{ tal que }
       Y\rightarrow w\in R \mbox{ e } w\not\in V\}\mbox{,}\]
			 em que $\mbox{\em enc\/}(X)$ é o conjunto de toda $Z\in V$ tal que $Z=X$ ou existe uma
			 sequência de regras $X\rightarrow Y_1$, $Y_1\rightarrow Y_2$, \ldots, $Y_n\rightarrow Z$
			 em $R$, $n\geq 0$ (no caso em que $n=0$, há apenas a regra $X\rightarrow Z$). 

 \item {\footnotesize Use o lema do bombeamento para mostrar que $\{\verb+0+^{n^2} \,|\, n\geq 0\}$ não é LLC.}

       \emph{Solução}: Suponha que tal linguagem seja LLC e seja $k$ a constante do LB. Seja
			 $z={\tt 0}^{k^2}$ e, de acordo com o LB, $u$, $v$, $w$, $x$ e $y$ tais que $uvwxy=z$,
			 $|vwx|\leq k$ e $|vx|>0$. Como $|vx|>0$, $|uv^2wx^2y|>k^2$, e como $|vwx|\leq k$,
			 $|uv^2wx^2y|\leq k^2+k$. Portanto, $k^2<|uv^2wx^2y|\leq k^2+k<k^2+2k+1=(k+1)^2$. Segue-se
			 que $uv^2wx^2y$ não pertence à linguagem, contradizendo o LB. Logo, a linguagem em questão
			 não é LLC.

 \item {\footnotesize Prove que a afirmativa
       \begin{quote}
        \emph{se $L$ não é uma LLC, então $(L-X)\cup(X-L)$ não é uma LLC}
			 \end{quote}
			 é ou não verdadeira, considerando os casos em que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X$ é finita.
        \item $X$ é regular.
       \end{list}}

       \emph{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X$ é finita. Suponha que $L$ não seja LLC e que, no entanto, $(L-X)\cup(X-L)$
				      seja LLC. Como $L\cap X$ e $X-L=X\cap \overline{L}$ são finitas, são regulares.
							Além disso, como linguagens regulares são fechadas sob complemento, $\overline{X-L}$
							é regular. Como as linguagens livres do contexto são fechadas sob interseção com
							linguagem	regular e sob união, então
							$[((L-X)\cup(X-L))-(X-L)]\cup (X\cap L)=[((L-X)\cup(X-L))\cap\overline{X-L}]\cup
							(X\cap L)$ deve ser LLC. Mas esta é igual a $L$, o que contradiz o fato de
							que $L$ não é LLC. Portanto, a afirmativa é verdadeira.
							
        \item $X$ é regular. Sejam $L$ uma linguagem não LLC, $\Sigma$ o alfabeto de $L$ e
				      $X=\Sigma^*$. Segue-se que $(L-X)\cup(X-L)=\emptyset\cup\overline{L}=\overline{L}$.
							Como as linguagens livres do contexto não são fechadas sob complemento,
							$\overline{L}$ pode ser LLC (com complemento $\overline{\overline{L}}=L$ não LLC).
							Portanto, a afirmativa é falsa.
       \end{list}
\end{enumerate}
\end{document}
