\documentclass[11pt, a4paper]{report}

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

\usepackage{fullpage}

\newcounter{conta}

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

\begin{enumerate}

 \item Para cada linguagem a seguir, construa um APD com reconhecimento padrão (estado final \underline{e} pilha vazia):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}      
        \item $\{{\tt a}^{2n}{\tt b}^{3n}\,|\,n\geq 0\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,w \mbox{ tem um {\tt b} a mais do que {\tt a}s}\}$.
       \end{list}

 \item Construa um APD que reconheça $\{{\tt a}^{m}{\tt b}^{n}\,|\,m\not=n\}$ em uma das 3
       modalidades reconhecimento, caso possível. (Use o APD para $\{{\tt a}^{m}{\tt b}^{n}\,|\,m\not=n\}$
       de 3 estados visto em aula como inspiração.)

 \item Construa GLC's para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{2n}{\tt 1}^{3n}\,|\, n\geq 0\}$.
        \item $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}^2\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w=w^R\}
              \{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}^2$.
        \item $\{{\tt a}^n{\tt b}^{k}{\tt c}^{n+k}\,|\,n,k\geq 0\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,k\geq m+n\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,k\geq m+n\}^*$.
       \end{list}

 \item Sejam as gram\'aticas:
       \begin{itemize}
        \item $G_1$: \parbox[t]{10cm}{$X \,\rightarrow\, {\tt a}X \,|\, X{\tt b} \,|\, \lambda$}
        \item $G_2$: \parbox[t]{10cm}{$P \,\rightarrow\, P{\tt ,}P \,|\, P{\tt ;}P \,|\, Z$ \\
                                      $Z \,\rightarrow\, {\tt a}Z \,|\, {\tt b}Z \,|\, \lambda$}
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagens são geradas por $G_1$ e por $G_2$?
        \item Mostre que ambas as gramáticas são amb\'{\i}guas.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a cada uma delas.
       \end{list}

 \item Seja a gram\'atica:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, P A A  \,|\,  B \,|\, A {\tt b} \,|\, CD$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B \,|\, BC$
	      \item[\ ] $B\,\rightarrow\,\lambda$
	      \item[\ ] $C\,\rightarrow\, BC$
	      \item[\ ] $D\,\rightarrow\, {\tt b}D \,|\, {\tt bb}$
	     \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}

\pagebreak
 \item Obtenha uma GLC na forma normal de Chomsky que gere $L(G)-\{\lambda\}$, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, PP \,|\, P(P) \,|\, \lambda$}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, P(P) \,|\, \lambda$}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, ABA$ \\ $A\,\rightarrow\, {\tt a}A \,|\, \lambda$ \\
               $B\,\rightarrow\, {\tt b}B \,|\, \lambda$}
      	\end{list}

 \item Construa um APN que aceite a linguagem gerada pela gram\'atica:
	\begin{enumerate}
	 \item[\ ] $L\,\rightarrow\, L;C \,|\, C$
	 \item[\ ] $C\,\rightarrow\, I \,|\, J \,|\, K$
	 \item[\ ] $I\,\rightarrow\, {\tt a}(L)$
	 \item[\ ] $J\,\rightarrow\, {\tt b}(I;L)$
	 \item[\ ] $K\,\rightarrow\, {\tt c}(L)(L)$
	\end{enumerate}

 \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) \mbox{ ou } n_a(w)<n_c(w)\}$.
        \item $\{w\in\{\verb+a+,\verb+b+,\verb+c+\}^* \,|\, n_a(w)<n_b(w)<n_c(w)\}$.
       \end{list}
       Obs: $n_s(w)$ \'e a quantidade do s\'{\i}mbolo {\tt s} na palavra $w$.

 \item Mostre que cada linguagem a seguir é LLC, mas que o complemento não é LLC:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\, m\geq n \mbox{ ou } n\geq k\}$
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\, m\not= n \mbox{ ou } n\not= k\}$
       \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}
