\documentclass[12pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$
         semestre de 2005 \\
Professor: Newton Jos\'{e} Vieira \\
{\bf Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: at\'e 17/10/2005

\begin{enumerate}
 \item Obtenha ERs que denotem as seguintes linguagens, a partir
       de um AFN para as mesmas, usando o m\'etodo visto em aula:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, w$ n\~ao cont\'em \verb+101+$\}$.
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, w$ n\~ao cont\'em \verb+00+ nos
               \'ultimos 4 s\'{\i}mbolos$\}$.
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,n_{\verb+0+}(w) \mbox{ \'e par e }
                n_{\verb+1+}(w) \mbox{ \'e \'{\i}mpar}\}$.
       \end{list}

 \item Uma ER est\'a na {\bf forma normal disjuntiva} se ela est\'a na forma
       $r_1+r_2+\cdots+r_n$ para algum $n\geq 1$, sendo que nenhuma das subERs
       $r_i$ cont\'em uma ocorr\^encia de $+$. Mostre que toda express\~sao
       regular \'e equivalente a uma outra na forma normal disjuntiva.
       (Lewis \& Papadimitriou (1998), prob. 1.8.7.\footnote{\bf Aten\c c\~ao!
       Servi\c co de utilidade p\'ublica: n\~ao compre nem consulte a vers\~ao traduzida deste
       livro, pois ela \'e de p\'essima qualidade!})

 \item Para cada linguagem, construa um APD, se for poss\'{\i}vel; se n\~ao for,
       construa um APN.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{(\verb+01+)^n\verb+0+(\verb+10+)^n\,\,|\,\,n\geq 0\}$.
        \item $\{(\verb+01+)^n\verb+1+(\verb+10+)^n\,\,|\,\,n\geq 0\}$.
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m\not=n\}$.
        \item $\{\verb+0+^m\verb+1+^n\#\,\,|\,\,m\not=n\}$.
        \item $\cup_{m\geq 0}\{\verb+0+^n\verb+1+^{2n}\,\,|\,\,n\geq 0\}^m$.
       \end{list}

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

 \item Encontre uma deriva\c c\~ao mais \`a direita para {\tt abaca} distinta da
       deriva\c c\~ao
       	\begin{enumerate}
	 \item[\ ] $S\,\Rightarrow\,S{\tt c}S\,\Rightarrow\,S{\tt ca}\,\Rightarrow\,S{\tt b}S{\tt ca}
                    \,\Rightarrow\,S{\tt baca}\,\Rightarrow\,{\tt abaca}$
	\end{enumerate}
       para a GLC $S\rightarrow S{\tt b}S\,|\,S{\tt c}S\,|\,{\tt a}$.
       (Kelley (1995), ex. 3.4.3, p\'ag. 97.)

 \item Considere uma gram\'atica {\em regular\/} em que, para cada vari\'avel $A$,
       n\~ao existem duas regras $A$ (regras em que o lado esquerdo cont\'em
       $A$) cujo lado direito comece com o mesmo terminal. Que rela\c c\~ao
       existe entre este tipo de gram\'atica e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Determinismo de AFs?
        \item Ambig\"uidade?
       \end{list}
       Agora, substitua a palavra ``{\em regular\/}'' por ``{\em livre do
       contexto na forma normal de Greibach}'' e AFs por APs, e responda as mesmas
       perguntas.

 \item Mostre que uma linguagem regular n\~ao pode ser inerentemente amb\'{\i}gua.
       (Linz(1997), ex. 8, se\c c\~ao 5.2, p\'ag. 150).

 \item Mostre que a gram\'atica a seguir \'e amb\'{\i}gua.
       	\begin{enumerate}
	 \item[\ ] $S\,\rightarrow\,{\tt a}S{\tt b}S\,|\,{\tt b}S{\tt a}\,|\,\lambda$
	\end{enumerate}
       (Linz(1997), ex. 12, se\c c\~ao 5.2, p\'ag. 150).

 \item 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}
       (Hopcroft et al.(2001), ex. 7.1.5, p\'ag. 272.)

 \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+^m\verb+b+^n \,\,|\,\, m\leq n^2\}$.
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,\,|\,\, m,n<k\}$.
       \end{list}

 \item Seja a classe das linguagens livres do contexto {\bf n\~ao} inerentemente
       amb\'{\i}guas. Mostre que ela n\~ao \'e fechada sob:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Uni\~ao.
        \item Interse\c c\~ao.
      \end{list}
      (Linz(1997), exs. 13 e 14, se\c c\~ao 8.2, p\'ag. 227).

 \item Prove que as LLCs  s\~ao fechadas sob reverso.
       (Teorema 7.25 de Hopcroft et a.(2001).)

 \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 Mostre como obter um APN de 3 estados e uma ``pilha'' de um \'unico s\'{\i}mbolo,
       equivalente a um AFN.

 \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}
 




