\documentclass[11pt, a4paper]{report}

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

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Lista de Exerc\'{\i}cios} \hfill Entrega: 06/11/2006

\begin{enumerate}

 \item Para cada linguagem a seguir, construa um APD, se poss\'{\i}vel.
       Se n\~ao for poss\'{\i}vel, constua um APN (se poss\'{\i}vel).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^n{\tt b}^k{\tt c}^{n+k}\,|\,n,k\geq 0\}$.
        \item $\{{\tt a}^n{\tt b}^{n+k}{\tt c}^k\,|\,n,k\geq 0\}$.
        \item $\{{\tt a}^n{\tt b}^k\,|\,n\leq k\leq 3k\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,n_{\tt a}(w)=n_{\tt b}(w)+1\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,n_{\tt a}(w)=2n_{\tt b}(w)\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,n_{\tt a}(w)=n_{\tt b}(w)+
               n_{\tt c}(w)\}$.
       \end{list}

 \item Construa GLC's para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^n{\tt b}^k{\tt c}^{n+k}\,|\,n,k\geq 0\}$.
        \item $\{{\tt a}^n{\tt b}^{n+k}{\tt c}^k\,|\,n,k\geq 0\}$.
        \item $\{{\tt a}^n{\tt b}^k\,|\,n\leq k\leq 3k\}$.
        \item $\{x{\tt c}y\,|\, x,y\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\not=y^R\}$.
       \end{list}

 \item Seja a gram\'atica $G$:
       \begin{center}
	\begin{tabular}{ccl}
	 $P$ & $\rightarrow$ & $AB \,|\, {\tt aa}B$ \\
	 $A$ & $\rightarrow$ & ${\tt a} \,|\, A{\tt a}$ \\
	 $B$ & $\rightarrow$ & ${\tt b}$
	\end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada por $G$?
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a $G$.
       \end{list}

 \item Mostre que uma linguagem regular n\~ao pode ser inerentemente amb\'{\i}gua.

 \item Construa uma gram\'atica equivalente \`a gram\'atica a seguir sem vari\'aveis
       in\'uteis.
	\begin{center}
	\begin{tabular}{ccl}
	 $S$ & $\rightarrow$ & ${\tt a} \,|\, {\tt a} A \,|\, B \,|\, C$ \\
	 $A$ & $\rightarrow$ & ${\tt a} B \,|\,\lambda$ \\
	 $B$ & $\rightarrow$ & ${\tt bb} A{\tt a}$ \\
	 $C$ & $\rightarrow$ & ${\tt c} CD$ \\
	 $D$ & $\rightarrow$ & ${\tt ddd}$
	\end{tabular}
	\end{center}

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

\pagebreak
 \item  Seja a gram\'atica:
	\begin{enumerate}
	 \item[\ ] $P\,\rightarrow\, A A A  \,|\,  B$
	 \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B \,|\, BC$
	 \item[\ ] $B\,\rightarrow\,\lambda$
	 \item[\ ] $C\,\rightarrow\, BC$
	\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 a gram\'atica:
	\begin{enumerate}
	 \item[\ ] $S\,\rightarrow\, {\tt ab}AB$
	 \item[\ ] $A\,\rightarrow\,{\tt b} AB \,|\, \lambda$
	 \item[\ ] $B\,\rightarrow\,{\tt b} BA{\tt a} \,|\, \lambda$
	 \item[\ ] $C\,\rightarrow\, BC$
	\end{enumerate}
        Obtenha uma GLC equivalente na forma normal de Chomsky.

 \item Construa um APN correspondente \`a gram\'atica:
	\begin{enumerate}
	 \item[\ ] $S\,\rightarrow\, {\tt a}ABB \,|\, {\tt a}AA$
	 \item[\ ] $A\,\rightarrow\,{\tt a} BB \,|\, {\tt a}$
	 \item[\ ] $B\,\rightarrow\,{\tt b} BB \,|\, A$
	\end{enumerate}

 \item Use o lema do bombeamento para mostrar que $\{{\tt a}^{n}{\tt b}^{2n}{\tt a}^{n}
       \,|\, n\geq 0\}$ n\~ao \'e uma linguagem livre do contexto.

 \item Mostre que s\~ao ou que n\~ao s\~ao linguagens livres do contexto:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+,\verb+c+\}^* \,\,|\,\, n_a(w)<n_b(w)\}$.
        \item $\{w\in\{\verb+a+,\verb+b+,\verb+c+\}^* \,\,|\,\, n_a(w)=n_b(w)=n_c(w)\}$.
        \item $\{\verb+a+^m\verb+b+^n\verb+c+^k \,\,|\,\, m<n<k\}$.
       \end{list}

 \item Mostre que sim ou que n\~ao; as linguagens livres do contexto s\~ao fechadas sob:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Diferen\c ca.
        \item Diferen\c ca sim\'etrica.
       \end{list}

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




