\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG
 
\noindent {\bf Terceira Lista de Exerc\'{\i}cios} \hfill Entrega: 02/09/02 (M), 03/09/02 (A)

\begin{enumerate}

 \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 $\{w\in\{\verb+0+,\verb+1+\}\,\,|\,\,n_{\verb+0+}(w)\not\not=
               n_{\verb+1+}(w)\}$
       \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 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 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}
 




