\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} \hfill 02/05/2005

\vspace*{1mm}

\noindent {\bf Cada quest\~ao vale 3 pontos. 3 pontos extra!}

\vspace*{1mm}
\begin{enumerate}
 \item Seja a GLC $G=(\{B,Z,U\},\{{\tt 0},{\tt 1}\},R,B)$, onde $R$ s\'o cont\'em
       as regras:
       \begin{enumerate}
        \item[\ ] $B\,\rightarrow\, {\tt 0} B {\tt 1} \,|\, Z \,|\,  U$
        \item[\ ] $Z\,\rightarrow\, {\tt 0} Z \,|\, {\tt 0}$
        \item[\ ] $U\,\rightarrow\, {\tt 1} U \,|\, {\tt 1}$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e $L(G)$?
        \item Determine uma GLC equivalente a $G$ na forma normal de Greibach (FNG).
        \item Determine um APN para $L(G)$ a partir da FNG obtida.
       \end{list}

 \item Dadas duas GLC's $G_1$ e $G_2$, como seriam obtidas GLC's para gerar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G_1)L(G_2)\cup L(G_2)L(G_1)$.
        \item $(L(G_1)L(G_2))^*$.
        \item $(L(G_1)L(G_2))^*L(G_1)$.
       \end{list}

 \item Seja a linguagem $L$, de alfabeto $\{{\tt a},{\tt [},{\tt ]},{\tt +}\}$,
       definida recursivamente assim:
       \begin{itemize}
        \item ${\tt a}\in L$;
        \item se $x\in L$ e $y\in L$, ent\~ao $x{\tt +}y\in L$;
        \item se $x\in L$, ent\~ao ${\tt [} x {\tt ]}\in L$ e $x {\tt ]}\in L$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma GLC $G$ tal que $L(G)=L$.
        \item Desenhe uma \'arvore de deriva\c c\~ao para a palavra
              {\tt [a]]}.
        \item Se $G$ for amb\'{\i}g\"ua, mostre que \'e.
       \end{list}

 \item Construa um APD que reconhe\c ca
       $\{{\tt a}^n{\tt b}^{2n+2k}{\tt c}^k\,|\, n,k\geq 0\}$, se poss\'{\i}vel.
       Se n\~ao for poss\'{\i}vel, explique a raz\~ao da impossibilidade e
       fa\c ca um APN.

 \item Seja $\Sigma$ o alfabeto constitu\'{\i}do de todas as letras min\'usculas do
       alfabeto da lingua protugu\^esa. Mostre que $\{w\in\Sigma^*\,|\, w$
       tem quantidades iguais de {\tt a}'s, {\tt b}'s e {\tt c}'s$\}$ n\~ao \'e
       linguagem livre do contexto.

 \item Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se $L$ n\~ao \'e uma LLC e $X$ \'e finita, $L-X$
              n\~ao \'e uma LLC.
        \item Se $L$ n\~ao \'e uma LLC e $X$ \'e regular, $L-X$
              pode ser uma LLC.
       \end{list}
\end{enumerate}

\end{document}

