\documentclass[11pt, a4paper]{report}

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

\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\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 Prova} -- Turma W \hfill {02/06/2011}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} vale 4 pontos.

\vspace*{2mm}
%\noindent\framebox{\parbox{15.6cm}{\textbf{Aten\c{c}\~ao}:
%Nas questões 2(a) e 2(b) dever\~ao ser usados \textbf{m\'etodos vistos em aula ou no livro-texto}.
%Não será permitido o uso de outros métodos, mesmo os que levem a soluções corretas.}}

\begin{enumerate}
 \item Construa GLCs que gerem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^{2(m+n)}{\tt c}^n \,|\, m,n\geq 0\}$.
        \item $L_2=w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ não é palíndromo}\}$.
        \item $(L_1\cup L_2)^*L_2$.
       \end{list}
       (O item com pior resposta será desprezado. Os outros vão valer 2 pontos cada um.)
 \item Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ] $A \,\rightarrow\, ( A ) A \,|\, ( A ) \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
%        \item Que linguagem é gerada por $G$?
        \item Construa um AP que reconheça $L(G)$.
        \item Mostre que $G$ é ambígua.
        \item Construa uma GLC equivalente a $G$ não ambígua.
       \end{list}
       (O item com pior resposta será desprezado. Os outros vão valer 2 pontos cada um.)

 \item Seja a GLC $H$:
       \begin{enumerate}
        \item[\ ] $P \,\rightarrow\, ACA$
        \item[\ ] $A \,\rightarrow\, {\tt a}AAa \,|\, B \,|\, C$
        \item[\ ] $B \,\rightarrow\, {\tt b}B \,|\, {\tt b}$
        \item[\ ] $C \,\rightarrow\, {\tt c}C \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Explicite o conjunto das variáveis anuláveis de $H$ e uma GLC $H'$ equivalente a $H$
              sem regras $\lambda$.
        \item Explicite enc$(X)$ para cada variável de $H'$ e uma GLC $H''$ equivalente a $H'$ sem regras unitárias.
       \end{list}

% \item Obtenha uma gramática na forma normal de Chomsky equivalente à gramática $G$ da questão 2.

 \item Sabendo que as seguintes linguagens não são LLCs:
       \begin{itemize}
	      \item $L_1=\{{\tt a}^{n^2}\,|\, n\geq 0\}$
	      \item $L_2=\{{\tt a}^n{\tt b}^k{\tt a}^n{\tt b}^k\,|\, n,k\geq 0\}$
       \end{itemize}
       mostre que não são LLCs usando propriedades de fecho:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
	      \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, |w| \mbox{ é um quadrado perfeito}\}$
	      \item $\{ww \,|\, w\in\{{\tt a},{\tt b},{\tt c}\}^* \mbox{ e } |w|>1000\}$
       \end{list}
\end{enumerate}

\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{
 GLC: gramática livre do contexto; \\
 AP: aut\^omato de pilha (pode ser não determinístico); \\
 LLC: linguagem livre do contexto.
}}
\end{document}

