\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 N \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}^n \,|\, m\not=n\}$.
%        \item $L_1=\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o número de {\tt a}s em $w$ é diferente do número de {\tt b}s}\}$.
        \item $L_2=\{{\tt a}^{m+n}{\tt b}^m{\tt c}^n \,|\, m \mbox{ é par e $n$ é ímpar}\}$.
        \item $L_1L_2\cup L_1^*$.
       \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[\ ] $E \,\rightarrow\, {\tt a} R \,|\, ( E ) R$
        \item[\ ] $R \,\rightarrow\, {\tt +} E R\,|\, {\tt *} E R \,|\, \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[\ ] $A \,\rightarrow\, ABC \,|\, ACE \,|\, {\tt a}$
        \item[\ ] $B \,\rightarrow\, EBCC \,|\, CE$
        \item[\ ] $C \,\rightarrow\, EC \,|\, E \,|\, {\tt b} \,|\, \lambda$
        \item[\ ] $D \,\rightarrow\, BB \,|\, DE \,|\, {\tt b}$
        \item[\ ] $E \,\rightarrow\, DCC \,|\, {\tt ab} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Explicite o conjunto das variáveis anuláveis de $H$.
        \item Apresente uma GLC $H'$ equivalente a $H$ sem regras $\lambda$.
       \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\,|\, n \mbox{ é um número primo}\}$
	      \item $L_2=\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\, n\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}\}^*\,|\, \mbox{o número de {\tt a}s em $w$ é primo}\}$
	      \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, |w|>1000 \mbox{ e } w \mbox{ tem quantidades idênticas de {\tt a}s {\tt b}s e {\tt c}s}\}$
       \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}

