\documentclass[11pt,a4paper]{report}

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

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

\newcounter{conta}
\newcounter{conta2}
\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 2013 \\
Professor: Newton José Vieira \\
{\bf Segunda Lista de Exercícios preparatória para a Segunda Prova}

\vspace*{3mm}
\noindent \textbf{Obs:} Para quem entregar as soluções até o dia da prova, esta lista valerá 13 pontos (dos 33 da segunda prova).
\begin{enumerate}
 \item Para cada linguagem, construa um APD, se for possível; se não for,
       construa um APN.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^n\,|\, n\geq 0\}^2$.
        \item $\{\verb+0+^n\verb+1+^n\verb+2+^k\,|\,n,k\geq 0\}$.
        \item $\{\verb+0+^n\verb+1+^n\verb+0+^k\,|\,n,k\geq 0\}$.
        \item $\{\verb+0+^n\verb+1+^n\verb+0+^k\,|\,n\geq 1 \mbox{ e } k\geq 0\}$.
        \item $w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ tem prefixo com mais {\tt 0}s que
              {\tt 1}s$\}$.
        \item $w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ tem sufixo com mais {\tt 0}s que
              {\tt 1}s$\}$.
       \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+^{2(m+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>n \mbox{ ou } n>k\}$.
       \end{list}

 \item Encontre uma deriva\c cão mais \`a direita para {\tt abaca} distinta da
       deriva\c cão
       	\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ão existem duas regras $A$ (regras em que o lado esquerdo contém
       $A$) cujo lado direito comece com o mesmo terminal. Que rela\c cão
       existe entre este tipo de gram\'atica e:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Determinismo de AFs?
        \item Ambiguidade?
       \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ão pode ser inerentemente ambígua.
       (Linz(1997), ex. 8, se\c cão 5.2, p\'ag. 150).

 \item Mostre que a gram\'atica a seguir é ambí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ão 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í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ão são
       livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+a+^n\verb+b+^{n^2} \,|\, n\geq 0\}$.
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,|\, m,n<k\}$.
       \end{list}

 \item Prove que as LLCs  são fechadas sob reverso.
       (Teorema 7.25 de Hopcroft et al.(2001).)

 \item Seja $a$ um certo símbolo. Mostre que a classe das linguagens
       livres do contexto é ou não é fechada sob cada uma das opera\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pref\/}_a(L)=\{x \,|\, xa\in L \}$.
        \item $\mbox{\em suf\/}_a(L)=\{y \,|\, ay\in L \}$.
        \item $\mbox{\em resto\/}_a(L)=\{xy \,|\, xay\in L \}$.
       \end{list}

 \item Seja um AP cuja pilha pode conter, no m\'aximo, $n$ sí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ímbolo,
       equivalente a um AFN.

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

\end{enumerate}

\end{document}
 




