\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{1}^{\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 10/06/02

\begin{enumerate}

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando o lema
       do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x \verb+c+ x \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{x\verb+c+y \,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e }
               n_{\verb+a+}(x)=n_{\verb+b+}(y)\}$
        \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq0\}$
       \end{list}

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares,
       utilizando propriedades de fechamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, m<n\}\cup\{\verb+0+^m\verb+1+^n\,\,|\,\,
               m>n\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ o n\'umero de \verb+0+'s em $w$ \'e
              duas vezes o de \verb+1+'s$\}$
        \item $\{\verb+0+^m\verb+1+^n\verb+2+^{m+n}\,\,|\,\, m,n>0\}$
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, \mbox{\em mdc\/}(m,n)=1\}$
       \end{list}
       Se n\~ao conseguir, use o lema do bombeamento.

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes
       opera\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pref\/}_a(L)=\{x \,\,|\,\, xa\in L \}$, onde $a$ \'e um certo
              s\'{\i}mbolo do alfabeto de $L$.
        \item $\mbox{\em pref\/}(L)=\{x \,\,|\,\, xy\in L \}$ (os prefixos das palavras
               de $L$).
        \item $\mbox{\em suf\/}_a(L)=\{y \,\,|\,\, ay\in L \}$, onde $a$ \'e um certo
              s\'{\i}mbolo do alfabeto de $L$.
        \item $\mbox{\em suf\/}(L)=\{y \,\,|\,\, xy\in L \}$ (os sufixos das palavras de $L$).
       \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens. Mostre que sim ou que n\~ao:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1\cup L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
                regular.
          \item se $L_1L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
                regular.
          \item se $L_1^*$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem regular.
          \item se $L_1$ \'e uma linguagem regular ent\~ao $\{w \,\,|\,\, w $ \'e uma
                subpalavra de $L_1\}$ \'e uma linguagem regular.
         \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens {\bf n\~ao} regulares. Mostre que sim ou que n\~ao:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1\cup L_2$ \'e uma linguagem n\~ao regular.
          \item se $L_1L_2$ \'e uma linguagem n\~ao regular.
          \item se $L_1^*$ \'e uma linguagem n\~ao regular.
          \item $\{w \,\,|\,\, w $ \'e uma subpalavra de $L_1\}$ \'e uma linguagem n\~ao regular.
         \end{list}

 \item Encontre ER's e GR's para os seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, 2\leq |w|\leq 5\}$
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em \verb+a+ e tem tamanho
              par$\}$
        \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$ cont\'em exatamente um \verb+bb+$\}$
       \end{list}

 \item Obtenha ER's que denotem as seguintes linguagens sobre $\{\verb+0+,\verb+1+\}$ a partir
       de um AFD para as mesmas, usando o m\'etodo visto em aula:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que come\c cam com \verb+1+ e terminam com \verb+1+.
        \item O conjunto das palavras com n\'umeros \'{\i}mpar de \verb+0+'s e \'{\i}mpar de
              \verb+1+'s.
       \end{list}

 \item Construa APD's para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^{3n}\verb+1+^{2n}\,\,|\,\,n\geq 0\}$
        \item $\{w\verb+0+w^R\,\,|\,\,w\in\{\verb+1+,\verb+2+\}^*\}$
        \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 Explique porque n\~ao h\'a APD para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{ww^R\,\,|\,\,w\in\{\verb+1+,\verb+2+\}^*\}$
        \item $\{\verb+0+^n\verb+1+^n0^k\,\,|\,\,n,k\geq 0\}$
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m>n\}$
       \end{list}

 \item Construa APN's que reconhe\c cam as linguagens seguintes por estado final e pilha
       vazia:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+^n\,\,|\,\,n\geq 0\}\cup\{\verb+0+^n\verb+1+^{2n}\,\,|\,\,
              n\geq 0\}$
        \item $\{\verb+0+^n\verb+1+^k\,\,|\,\,n\leq k\leq 2n\}$
        \item $\{\verb+0+^n\verb+1+^n\verb+0+^k\,\,|\,\,n,k\geq 0\}$
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\,m>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+^n\verb+b+^{2n+k}\verb+c+^{3k} \,\,|\,\, n,k\geq 0\}$
	 \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,\,|\,\, n>m+k\}$
       \end{list}

 \item Seja a gram\'atica $G$:
       \begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $\verb+a+ P \verb+b+ \,\,|\,\, \verb+a+ \verb+a+ P \verb+b+
                    \,\,|\,\, \lambda$
	\end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item Construa uma gram\'atica sem regras $\lambda$ equivalente
	\`a seguinte gra\-m\'a\-ti\-ca:
	\begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $B P A \,\,|\,\, A$ \\
	 $A$ & $\rightarrow$ & $\verb+a+ A \,\,|\,\, \lambda$ \\
	 $B$ & $\rightarrow$ & $B \verb+b+ \verb+a+ \,\,|\,\, \lambda$
	\end{tabular}
	\end{center}

  \item Seja a gram\'atica $G$:
	\begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $A \,\,|\,\, B C $ \\
	 $A$ & $\rightarrow$ & $B \,\,|\,\, C$ \\
	 $B$ & $\rightarrow$ & $\verb+b+ B \,\,|\,\, \verb+b+$ \\
	 $C$ & $\rightarrow$ & $\verb+c+ C \,\,|\,\, \verb+c+$ \\
	\end{tabular}
	\end{center}
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item Construa uma gram\'atica equivalente a $G$, sem regras de
	       cadeias.
	 \item Mostre que a gram\'atica constru\'{\i}da cont\'em s\'{\i}mbolos
	       in\'uteis.
	\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+^{2n}\verb+a+^n \,\,|\,\, n\geq 0\}$
       \end{list}

 \item Mostre que sim ou que n\~ao: as linguagens livres do contexto s\~ao fechadas sob
       diferen\c ca.

 \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 linguagem livre do contexto \'{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:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ \'{e} uma linguagem livre do contexto e $F$ \'{e} finita, ent\~{a}o
              $L-F$ \'{e} linguagem livre do contexto.
        \item Se $L$ \'{e} uma linguagem livre do contexto e $R$ \'{e} regular, ent\~{a}o
              $L-R$ \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e} finita,
              ent\~{a}o $L-F$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $R$ \'{e} regular,
              ent\~{a}o $L-R$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $F$ \'{e} finita,
              ent\~{a}o $L\cup F$ n\~{a}o \'{e} linguagem livre do contexto.
        \item Se $L$ n\~{a}o \'{e} uma linguagem livre do contexto e $R$ \'{e} regular,
              ent\~{a}o $L\cup R$ n\~{a}o \'{e} linguagem livre do contexto.
       \end{list}

\end{enumerate}

\end{document}
 




