\documentclass[12pt]{report}

%\addtolength{\topmargin}{-1cm}
\usepackage[portuguese]{babel}
\usepackage{fullpage}
\addtolength{\textheight}{1cm}

\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Departamento de Ci\^encia da Computa\c c\~ao \hfill ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill
                            $2^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Terceira Prova} \hfill {\bf Dura\c c\~ao: 1h:30m}

\vspace*{2mm}
\noindent {\bf Cada quest\~ao vale 3 pontos.}

\vspace*{1mm}
\begin{enumerate}
 \item Seja $L_1=\{{\tt a}^{3n}({\tt abc})^n\} \,|\, n\geq 0\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um APD que reconhe\c ca $L_1$.
        \item Construa uma GLC que gere $L_1$.
       \end{list}

 \item Seja $L_2=\{{\tt a}^m{\tt b}^n \,|\, m\not=n\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um APN que reconhe\c ca $L_2$.
        \item Construa uma GLC que gere $L_2$.
       \end{list}

 \item Seja a GLC $G=(\{B\},\{{\tt 0},{\tt 1}\},R,B)$, onde $R$ s\'o cont\'em
       as regras:
       \begin{enumerate}
        \item[\ ] $B\,\rightarrow\, {\tt 0} B {\tt 1} \,|\, {\tt 0} B {\tt 11}
                                    \,|\, {\tt 0} B {\tt 111} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e $L(G)$?
        \item Mostre que $G$ \'e amb\'{\i}g\"ua.
        \item Se poss\'{\i}vel, construa uma GLC n\~ao amb\'{\i}g\"ua que
              reconhe\c ca $L(G)$.
       \end{list}

 \item Resolva \underline{usando os m\'etodos vistos em aula}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}} 
        \item Elimine regras $\lambda$ de:
              \begin{enumerate}
               \item[\ ] $X\,\rightarrow\, A B C$
               \item[\ ] $A\,\rightarrow\, {\tt a} A \,|\, \lambda$
               \item[\ ] $B\,\rightarrow\, {\tt a} B {\tt b} \,|\, \lambda$
               \item[\ ] $C\,\rightarrow\, A \,|\, B$
              \end{enumerate}

        \item Elimine regras unit\'arias de:
              \begin{enumerate}
               \item[\ ] $P\,\rightarrow\, A \,|\, B \,|\, C$
               \item[\ ] $A\,\rightarrow\, {\tt a} A \,|\, B$
               \item[\ ] $B\,\rightarrow\, {\tt a} B {\tt b} \,|\, {\tt b}$
               \item[\ ] $C\,\rightarrow\, A \,|\, {\tt aa}$
              \end{enumerate}

        \item Elimine recurs\~ao \`a esquerda de:
              \begin{enumerate}
               \item[\ ] $E\,\rightarrow\, E {\tt +} E \,|\, E {\tt *} E \,|\,
                          {\tt (} E {\tt )} \,|\, {\tt a}$
              \end{enumerate}
       \end{list}

 \item Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item As linguagens livres do contexto n\~ao s\~ao fechados sob
              diferen\c ca sim\'etrica. (Diferen\c ca sim\'etrica entre $L_1$ e $L_2$:
              $(L_1-L_2)\cup(L_2-L_1)$).
        \item Se $L$ n\~ao \'e linguagem livre do contexto, ent\~ao se
              forem retiradas 1 bilh\~ao de palavras de $L$, a linguagem
              obtida n\~ao \'e livre do contexto.
       \end{list}

\end{enumerate}

\end{document}
