\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1995
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Terceira Prova} \hfill 13/06/95
 
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 30 minutos.
 \item[Valores das quest\~{o}es:] 5 pontos cada uma.
\end{description}
 
\begin{enumerate}
 
 \item Seja a gram\'atica regular $G = (\{S,A,B\}, \{a,b\}, P, S)$, onde $P$
       consta das regras:
       \begin{enumerate}
        \item[\ \ \ ] $S \rightarrow a S \,\,|\,\, b S \,\,|\,\, a A$
        \item[\ \ \ ] $A \rightarrow a \,\,|\,\, b B$
        \item[\ \ \ ] $B \rightarrow b A$
       \end{enumerate}
       Construa, a partir de $G$, um aut\^omato finito n\~ao determin\'{\i}stico que
       aceite $L(G)$, utilizando o m\'etodo visto no curso.
 \item Prove que a linguagem $\{0^{n^3} \,\,|\,\, n \geq 0\}$ n\~ao \'e regular.
 \item Seja $L$ uma linguagem regular sobre o alfabeto $\{a,b,c\}$. Mostre que
       cada um dos seguintes conjuntos \'{e} regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \,\,|\,\, w \in L \mbox{ e $w$ cont\'{e}m pelo menos um $a$}
	       \}$
        \item $\{w \,\,|\,\, w \in L \mbox{ ou $w$ cont\'{e}m pelo menos um $a$
	         (ou ambos)}\}$
        \item $\{w \,\,|\,\, w \not\in L \mbox{ e $w$ n\~{a}o cont\'{e}m $a$'s}
	       \}$
       \end{list}
 
 \item Construa um aut\^omato a pilha para a linguagem $\{a^ib^jc^i \,\,|\,\,
       i,j \geq 0\}$.
 \item Seja o aut\^omato a pilha $M = (\{q_0, q_1\},\{0, 1\}, \{A\}, \delta,
       q_0, \{q_0, q_1\})$, onde $\delta$ \'e dada por:
	\begin{enumerate}
	 \item[\ \ \ ] $\delta(q_0,0,\lambda) = \{[q_0,A]\}$
	 \item[\ \ \ ] $\delta(q_0,1,A) = \{[q_1,\lambda]\}$
	 \item[\ \ \ ] $\delta(q_1,1,A) = \{[q_1,\lambda]\}$
	\end{enumerate}
       Construa, a partir de $M$, uma gram\'atica livre do contexto $G$ que gere
       $L(M)$, utilizando o m\'etodo visto no curso.
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
 
