\documentclass[11pt, a4paper]{report}

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

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

\begin{document}

\vspace*{1cm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turmas B e C \hfill {28/11/2010}

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

\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_0=\{{\tt a}^{3n} \,|\, n\geq 0\}$.
        \item $L_1=\{{\tt a}^{n}{\tt b}^k \,|\, n\geq k\}$.
        \item $L_2=\{{\tt a}^{n+k}{\tt b}^n{\tt c}^k \,|\, n,k\geq 0\}$.
        \item $(L_1\cup L_2)^*L_1$.
       \end{list}

 \item Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ] $P \,\rightarrow\, {\tt a} P {\tt bb} \,|\, {\tt a} P \,|\, \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}

 \item Seja a GLC $H$:
       \begin{enumerate}
        \item[\ ] $P \,\rightarrow\, ABC \,|\, {\tt b}CC$
        \item[\ ] $A \,\rightarrow\, {\tt a}AA \,|\, BB$
        \item[\ ] $B \,\rightarrow\, \lambda$
        \item[\ ] $C \,\rightarrow\, ABC \,|\, {\tt b}$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Explicite o conjunto das variáveis anuláveis.
        \item Apresente uma GLC $H'$ equivalente a $H$ sem regras $\lambda$.
        \item Elimine as variáveis inúteis de $H'$.
        \item Em seguida, elimine as regras unitárias.
       \end{list}

 \item Sejam:
       \begin{itemize}
	      \item $L_1=\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{o número de {\tt a}s em $w$ é múltiplo de }3\}$.
	      \item $L_2=\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{o número de {\tt a}s é idêntico ao de {\tt b}s em $w$}\}$;
       \end{itemize}
       Mostre que são ou não LLCs usando propriedades de fecho:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\overline{L_1}$.
        \item $L_1\cap L_2$.
        \item $(L_2\cap \overline{L_1})\cup(L_1L_2)(L_1L_2)^*$.
       \end{list}
\end{enumerate}

\vspace*{.5mm}
\hrule

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

