\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\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 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Terceira Prova} -- Turmas B e E\hfill {05/11/2009}

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

\vspace*{2mm}
\noindent\framebox{\parbox{15.6cm}{\textbf{Aten\c{c}\~ao}:
Na quest\~ao 3(b e c) devem ser usados m\'etodos vistos em aula ou no livro-texto.
Qualquer resultado, mesmo que correto, obtido de forma \emph{ad-hoc\/} n\~ao ser\'a considerado.
Assim, \'e importante que explicite claramente os passos executados.}}

\begin{enumerate}
 \item Sejam $L_1=\{{\tt a}^n{\tt b}^{n}\,|\, n\geq 0\}$ e $L_2=\{{\tt b}^{n}{\tt a}^{n}\,|\, n\geq 0\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um APD que reconhe\c{c}a $L_1$.
        \item Construa um APD que reconhe\c{c}a $L_1L_2$.
        \item Construa um APN que reconhe\c{c}a $L_1\cup \{{\tt a}\}^*$.
       \end{list}

 \item Construa GLCs para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt 0}^n{\tt 1}^{k}{\tt 0}^{n+k}\,|\,n,k\geq 0\}$.
        \item $L_2=\{{\tt 0}^n{\tt 1}^{k}\,|\,k>2n\}$.
        \item $L_1^*\cup L_2^*\cup (L_1L_2)^+$.
       \end{list}

 \item Seja a GLC $G=(\{P,A,B,Q,R\},\{{\tt a},{\tt b}\},X,P)$ em que $X$ cont\'em as regras:
              \begin{quote}
               $P\,\rightarrow\, Q \,|\, R$ \\
               $Q \,\rightarrow\, {\tt a}Q{\tt a} \,|\, B$ \\
               $B \,\rightarrow\, {\tt b}B{\tt b} \,|\, \lambda$ \\
               $R \,\rightarrow\, {\tt b}R{\tt b} \,|\, A$ \\
               $A \,\rightarrow\, {\tt a}A{\tt a} \,|\, \lambda$
              \end{quote} 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que $G$ \'e amb\'{\i}gua.
        \item Construa uma GLC $G'$ equivalente a $G$ sem regras $\lambda$.
        \item Construa uma GLC equivalente a $G'$ sem regras unit\'arias.
       \end{list}

 \item Sabendo que $\{{\tt a}^{n^2}\,|\, n \geq 0\}$ n\~ao \'e uma LLC, mostre que
       \[\{w\in \{{\tt a},{\tt b}\}^*\,|\, n_{\tt a}(w) \mbox{ \'e um quadrado perfeito e } n_{\tt b}(w)
         \mbox{ \'e  par}\}\]
       n\~ao \'e uma LLC.
\end{enumerate}

\vspace*{3mm}
\hrule

\vspace*{.5mm}
\hrule
\vspace*{3mm}
\begin{itemize}
	\item APN: aut\^omato de pilha n\~ao determin\'{\i}stico;
	\item APD: aut\^omato de piliha determin\'{\i}stico;
	\item GLC: gram\'atica livro do contexto.
	\item LLC: linguagem livre do contexto.
	\item $n_{\tt a}(w)$: n\'umero de {\tt a}s em $w$.
\end{itemize}
\end{document}


