\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage         {amsfonts}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2017 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Segunda Prova}/Solução do professor \hfill 7/11/2017

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Prove, usando o teorema da invariância à direita ou o lema do bombeamento, que a linguagem 
       $\{{\tt 0}^na{\tt 0}^n\,|\, a\in \{{\tt 0},{\tt 1}\} \mbox{ e } n\in\mathbb{N}\}$ não é regular.}

       \textit{Solução}:
			 Seja $L$ a linguagem em questão. Tome $R=\{{\tt 0}\}^*$ e sejam  ${\tt 0}^i,{\tt 0}^j\in R$, 
				      $i<j$, palavras arbitrárias de $R$. Tem-se que ${\tt 0}^i{\tt 1}{\tt 0}^i\in L$ e
							${\tt 0}^j{\tt 1}{\tt 0}^i\not\in L$. Logo, $L$ não é regular.
 \item {\footnotesize Sejam $L_1=\{{0}^{n^2} \,|\, n \in\mathbb{N}\}$ (não regular) e $L_2=\{{\tt 0}^k\}\{{\tt 0}\}^*$ (regular), em que
       $k$ é uma constante. Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$;
        \item $L_1\cap L_2$;
        \item $L_1\cup L_2$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L_3=\{{0}^n \,|\, n<k \mbox{ e }n \mbox{ é um quadrado perfeito}\}$. Como este conjunto
							é \textit{finito}, é regular.
        \item Se $L_4=\{{0}^n \,|\, n\geq k \mbox{ e }n \mbox{ é um quadrado perfeito}\}$ fosse regular,
              $L_4\cup L_3$ também seria, pois as linguagens regulares são fechadas sob união. Mas,
              $L_4\cup L_3=L_1$, que não é regular.
        \item Como $L_1\cup L_2=L_3\cup L_2$, $L_3$ e $L_2$ são regulares, segue-se por fechamento sob
              união que $L_1\cup L_2$ é regular.
       \end{list}

 \item {\footnotesize Construa uma expressão regular que denote $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w \mbox{ não termina com {\tt cc}}\}$.}

       \textit{Solução}: $(c^*(a+b))^*(\lambda+c)$
 \item {\footnotesize Construa um APD para a linguagem da questão 1, se possível. Se não for possível, construa APN.}

       \textit{Solução}:

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

                 \node[Nmarks=i](0)(20,7.5){}
                 \node[Nmarks=r](1)(45,7.5){}

                 \drawedge(0,1){\shortstack{${\tt 0},\lambda/\lambda$ \\ ${\tt 1},\lambda/\lambda$}}

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

 \item {\footnotesize Construa GLCs que gerem: 
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^n{\tt b}^{2n+k+1}{\tt c}^{3k} \,|\, n,k\in\mathbb{N}\}$;
        \item $L_2=\{{\tt a}^m{\tt b}^n{\tt c}^k \,|\, m>n+k\}$;
	      \item $(L_1L_2)^*$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $P_1\,\rightarrow\, X{\tt b}Y$ \\
              $X\,\rightarrow\, {\tt a} X {\tt bb}\,|\, \lambda$ \\
              $Y\,\rightarrow\, {\tt b} Y {\tt ccc}\,|\, \lambda$
        \item $P_2\,\rightarrow\, {\tt a}P_2 \,|\, {\tt a}A$ \\
              $A\,\rightarrow\, {\tt a} A {\tt c}\,|\, B$ \\
              $B\,\rightarrow\, {\tt a} B {\tt b} \,|\, \lambda$
        \item $P \,\rightarrow\, P_1P_2P \,|\, \lambda$ mais as regras em (a) e (b).
       \end{list}

 \item {\footnotesize Seja a gramática $G$ com as regras:
       \begin{enumerate}
        \item[\ ] $A\,\rightarrow\, {\tt a}A \,|\, {\tt b}B \,|\, \lambda$
        \item[\ ] $B\,\rightarrow\, {\tt b}B \,|\, A$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre duas árvores de derivação ou DMEs para a menor palavra para a qual existam duas árvores de derivação.
        \item Remova a ambiguidade de $G$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item DMEs para {\tt bb}:
			        \begin{enumerate}
						   \item[1.] $A \,\Rightarrow\, {\tt b}B \,\Rightarrow\, {\tt bb}B \,\Rightarrow {\tt bb}A \,\Rightarrow\, {\tt bb}$
						   \item[2.] $A \,\Rightarrow\, {\tt b}B \,\Rightarrow\, {\tt b}A \,\Rightarrow {\tt bb}B \,\Rightarrow\, {\tt bb}A
							          \,\Rightarrow\, {\tt bb}$
						  \end{enumerate}
        \item $A\,\rightarrow\, {\tt a}A \,|\, {\tt b}A \,|\, \lambda$
       \end{list}

 \item {\footnotesize Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1}$
        \item[\ ]$A \,\rightarrow\, {\tt 1}A{\tt 1} \,|\, S \,|\, \lambda$
       \end{enumerate}
       Obtenha GLCs equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item na forma normal de Chomsky;
        \item na forma normal de Greibach.
       \end{list}}

       \textit{Solução}:

			 Eliminando-se regras $\lambda$ ($VA=\{A\}$):
		 	 \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1} \,|\, {\tt 11}$
        \item[\ ]$A \,\rightarrow\, {\tt 1}A{\tt 1} \,|\, S \,|\, {\tt 11}$
       \end{enumerate}
			 Eliminando-se regras unitárias ($enc(S)=\{S\}$, $enc(A)=\{A,S\}$):
		 	 \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1} \,|\, {\tt 11}$
        \item[\ ]$A \,\rightarrow\, {\tt 1}A{\tt 1} \,|\, {\tt 0}S{\tt 0} \,|\, {\tt 11}$
       \end{enumerate}
       Não há variáveis inúteis.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Forma normal de Chomsky:
						 	\begin{enumerate}
               \item[\ ]$S \,\rightarrow\, ZX \,|\, UY \,|\, UU$
               \item[\ ]$A \,\rightarrow\, UY \,|\, ZX \,|\, UU$
               \item[\ ]$X \,\rightarrow\, SZ$
               \item[\ ]$Y \,\rightarrow\, AU$
               \item[\ ]$Z \,\rightarrow\, {\tt 0}$
               \item[\ ]$U \,\rightarrow\, {\tt 1}$
              \end{enumerate}
				\item Forma normal de Greibach:
		 	        \begin{enumerate}
               \item[\ ]$S \,\rightarrow\, {\tt 0}SZ \,|\, {\tt 1}AU \,|\, {\tt 1}U$
               \item[\ ]$A \,\rightarrow\, {\tt 1}AU \,|\, {\tt 0}SZ \,|\, {\tt 1}U$
               \item[\ ]$Z \,\rightarrow\, {\tt 0}$
               \item[\ ]$U \,\rightarrow\, {\tt 1}$
              \end{enumerate}
       \end{list}
\end{enumerate}

\end{document}
