\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 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} \hfill 06/06/2006

\vspace*{1mm}

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

\vspace*{1mm}
\begin{enumerate}
 \item Seja a GLC $G=(\{A,B\},\{{\tt 0},{\tt 1}\},R,A)$, onde $R$ s\'o cont\'em
       as regras:
       \begin{enumerate}
        \item[\ ] $A\,\rightarrow\, {\tt 00} A {\tt 1} \,|\, B$
        \item[\ ] $B\,\rightarrow\, {\tt 0} B {\tt 1} \,|\, \lambda$
       \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 Chomsky.
       \end{list}

 \item Dadas duas GLC's $G_1=(V_1,\Sigma_1,R_1,P_1)$ e $G_2=(V_2,\Sigma_2,R_2,P_2)$,
       tais que $V_1\cap V_2=\emptyset$, 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)\cup L(G_2))^*$?
       \end{list}

 \item Seja a gram\'atica $G=(\{P,A,B\},\{\verb+a+,\verb+b+\},R,P)$,
       onde $R$ consta das regras:
       \begin{enumerate}
        \item[\ \ ] $P\,\,\rightarrow\,\, AB\,\,|\,\,\lambda$
        \item[\ \ ] $A\,\,\rightarrow\,\, \verb+a+A\verb+b+\,\,|\,\,\lambda$
        \item[\ \ ] $B\,\,\rightarrow\,\, \verb+bb+B\verb+a+\,\,|\,\,\lambda$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem $G$ gera?
        \item $G$ \'e ambig\"ua? Se for, remova a ambiguidade de $G$ modificando-a o
              m\'{\i}nimo poss\'{\i}vel.
       \end{list}

 \item Obtenha uma GLC equivalente \`a GLC $G$ da quest\~ao anterior sem regras
       $\lambda$ e sem regras unit\'arias. Para isto, utilize os m\'etodos vistos
       no curso (determinando vari\'aveis anul\'aveis etc.)

 \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}

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

       Al\'em dos resultados da quest\~ao anterior, voc\^e pode usar propriedades
       de fechamento e o fato que $\{{\tt a}^n{\tt b}^n{\tt c}^n\,|\, n\geq 0\}$ n\~ao \'e
       livre do contexto para quaisquer s\'{\i}mbolos {\tt a}, {\tt b} e {\tt c} distintos
       entre si. Caso queira usar o lema do bombeamento, tamb\'em pode.
\end{enumerate}

\end{document}
