\documentclass[12pt,a4paper]{report}

%=================================================================
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\textwidth}{1.5cm}
%=================================================================
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas re-gu-lar re-gu-la-res}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG
 
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: \parbox[t]{14cm}{Newton Jos\'{e} Vieira \\
                     e-mail: nvieira@dcc.ufmg.br}
 
\noindent {\bf Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: at\'e 20/01/03

\begin{enumerate}
 \item Encontre ER's e GR's para os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\,$ \verb+a+'s s\'o podem ocorrer nas
              posi\c c\~oes pares de $w\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ n\~ao cont\'em \verb+aaa+$\}$.
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ n\~ao cont\'em \verb+aa+ nos
               \'ultimos 4 s\'{\i}mbolos$\}$.
       \end{list}

 \item Obtenha ER's que denotem as seguintes linguagens, a partir
       de um AFD para as mesmas, usando o m\'etodo visto em aula:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,n_{\verb+0+}(w) \mbox{ e }
                n_{\verb+1+}(w) \mbox{ s\~ao \'{\i}mpares}\}$.
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,n_{\verb+0+}(w) \mbox{ mod } 5=0
                \mbox{ e } n_{\verb+1+}(w) \mbox{ mod } 3=0\}$.
       \end{list}

 \item Seja uma {\em express\~ao regular estendida\/} sobre $\Sigma$ uma express\~ao
       regular sobre $\Sigma$ que:
         \begin{itemize}
          \item al\'em das express\~oes b\'asicas para denotar $\{a\}$, $\emptyset$ e
                $\lambda$, cont\'em uma express\~ao b\'asica para denotar $\Sigma$; e 
          \item al\'em dos operadores de uni\~ao, concatena\c c\~ao e fecho de Kleene,
                tem operadores tamb\'em para interse\c c\~ao, com\-ple\-men\-ta\-\c c\~ao,
                e ``pot\^encia'' (concatena\c c\~ao $n$ vezes).
         \end{itemize}
         Mostre como obter uma ER que denote a mesma linguagem que uma ER estendida.

 \item Construa APD's para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{(\verb+01+)^n\verb+1+(\verb+10+)^n\,\,|\,\,n\geq 0\}$.
        \item $\{\verb+0+^n\verb+1+^n0^k\,\,|\,\,n\geq 1 \mbox{ e } k\geq 0\}$.
        \item $\{\verb+0+^m\verb+1+^n\#\,\,|\,\,m\not=n\}$.
       \end{list}

 \item Construa APN's que reconhe\c cam as linguagens seguintes (usando o crit\'erio
       de reconhecimento que preferir):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\,n\leq k\leq 2n\}$.
        \item $\{(\verb+01+)^n\verb+0+(\verb+10+)^n\,\,|\,\,n\geq 0\}$.
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m\not=n\}$.
       \end{list}

 \item Construa GLC's para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^{3m+2n+1} \,\,|\,\, m,n\geq 0\}$.
        \item $\{\verb+a+,\verb+b+\}^*-\{ww^R\,\,|\,\, w\in\{\verb+a+,\verb+b+\}^*\}$.
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,\,|\,\, m\not=n \mbox{ ou } n\not=k\}$.
       \end{list}

 \item Construa uma GLC que gere o conjunto das express\~oes
       prefixadas\footnote{\em Prefix expressions.} com operando
       \verb+t+ e operadores \verb|+| e \verb|*|. Depois responda:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre deriva\c c\~oes mais \`a esquerda e mais \`a direita, e tamb\'em
              uma \'arvore de deriva\c c\~ao para a palavra \verb|+*+tttt|.
        \item A gram\'atica \'e amb\'{\i}g\"ua ou n\~ao?
       \end{list}

 \item Seja a gram\'atica $G$:
	\begin{enumerate}
	 \item[\ ] $P\,\rightarrow\,\verb+a+ P \,\,|\,\, \verb+a+ P \verb+b+ P
                    \,\,|\,\, \lambda$
	\end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada por $G$?
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma GLC n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item (Exerc\'{\i}cio 7.1.5 de Hopcroft, Motwani e Ullman.) Seja a gram\'atica:
	\begin{enumerate}
	 \item[\ ] $S\,\rightarrow\,\verb+a+ A \verb+a+ \,\,|\,\, \verb+b+ B
                                   \verb+b+\,\,|\,\, \lambda$
	 \item[\ ] $A\,\rightarrow\,C \,\,|\,\, \verb+a+$
	 \item[\ ] $B\,\rightarrow\,C \,\,|\,\, \verb+b+$
	 \item[\ ] $C\,\rightarrow\,C D E \,\,|\,\, \lambda$
	 \item[\ ] $D\,\rightarrow\,A \,\,|\,\, B \,\,|\,\, \verb+ab+$
	\end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se existirem s\'{\i}mbolos in\'uteis, elimine-os.
        \item Elimine regras $\lambda$.
        \item Elimine regras unit\'arias.
        \item Obtenha uma GLC equivalente na forma normal de Chomsky.
       \end{list}

  \item Seja $G$ uma gram\'{a}tica e $w\in L(G)$, de tamanho $n$. Para os casos em que $G$
        est\'a na forma normal de Chomsky e em que est\'a na forma normal de Greibach,
        determine:
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item O tamanho de uma deriva\c{c}\~{a}o de $w$.
	 \item A profundidade m\'{a}xima de uma AD de $w$.
	 \item A profundidade m\'{\i}nima de uma AD de $w$.
	\end{list}

 \item Seja o APD $M=(\{0,1\},\{\verb+a+,\verb+b+,\verb+c+\},\{A,B\},\delta,\{1\})$, onde
       $\delta$ \'e dada por:
       \begin{enumerate}
        \item[\ \ \ ] $\delta(0,\verb+a+,\lambda)=\{[0,A]\}$
        \item[\ \ \ ] $\delta(0,\verb+b+,A)=\{[1,B]\}$
        \item[\ \ \ ] $\delta(1,\verb+b+,A)=\{[1,B]\}$
        \item[\ \ \ ] $\delta(1,\verb+c+,B)=\{[1,\lambda]\}$
       \end{enumerate}
       Utilize o m\'etodo apresentado no Teorema 27 para obter uma gram\'atica que gere
       $L(M)$.

 \item Use o lema do bombeamento para mostrar que as seguintes linguagens n\~{a}o s\~{a}o
       livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^{n^2} \,\,|\,\, n\geq 0\}$.
        \item $\{\verb+a+^n\verb+b+^n\verb+a+^k \,\,|\,\, k\leq n\}$.
        \item $\{\verb+a+^n\verb+b+^{n^2} \,\,|\,\, n\geq 0\}$.
      \end{list}

 \item Mostre que sim ou que n\~ao: as LLC's s\~ao fechadas sob diferen\c ca.

 \item (Teorema 7.25 de Hopcroft, Motwani e Ullman.) Prove que as LLC's  s\~ao fechadas sob reverso.

 \item Seja um AP cuja pilha pode conter, no m\'aximo, $n$ s\'{\i}mbolos. Que
       limita\c c\~oes ter\'a tal tipo de AP? Justifique sua resposta.

 \item Prove que toda LLC \'{e} gerada por uma gram\'{a}tica na qual
       cada uma das regras \'{e} de uma das formas:
       \begin{list}{(\roman{conta})}{\usecounter{conta}}
        \item $P \,\,\,\rightarrow\,\,\, \lambda$ 
        \item $A \,\,\,\rightarrow\,\,\, a$
        \item $A \,\,\,\rightarrow\,\,\, aB$
        \item $A \,\,\,\rightarrow\,\,\, aBC$
       \end{list}
       onde $P$ \'e a vari\'avel de partida e $A, B, C \in V$ e $a \in \Sigma$.
       ({\em Sugest\~{a}o\/}: parta de uma gram\'{a}tica na forma normal de Greibach.)

 \item Prove que as seguintes afirmativas s\~{a}o ou n\~ao verdadeiras, considerando
       os casos em que (i) $X$ \'e finita e (ii) $X$ \'e regular.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma LLC, ent\~{a}o $L-X$ \'{e} uma LLC.
        \item Se $L$ n\~{a}o \'{e} uma LLC, ent\~{a}o $L-X$ n\~{a}o \'{e} uma LLC.
        \item Se $L$ n\~{a}o \'{e} uma LLC, ent\~{a}o $L\cup X$ n\~{a}o \'{e} uma LLC.
       \end{list}

\end{enumerate}

\end{document}
 




