\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{Lista de Recupera\c{c}\~{a}o} \hfill 06/06/95
 
\begin{description}
 \item[Devolu\c{c}\~{a}o:] 08/08/95 at\'{e} 13:05 h.
 \item[Valores das quest\~{o}es:] 2 pontos cada uma.
\end{description}
 
\begin{enumerate}
 \item Fa\c{c}a uma defini\c{c}\~ao recursiva do {\it conjunto de ancestrais
       de um nodo\/} $x$ de uma \'arvore $(N,A,r)$ (lembre-se que, para nossos
       prop\'{o}sitos, $x$ \'e ancestral de si mesmo).
 
 \item Prove, por indu\c{c}\~ ao, que uma \'arvore estritamente $k$-\'aria de
       $n$ folhas tem \[(kn-1)/(k-1)\] nodos. (Uma \'arvore estritamente
       $k$-\'aria \'{e} aquela em que cada nodo tem, ou zero, ou $k$ filhos.)
 
 \item Construa express\~oes regulares para cada um dos seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \in \{a,b,c\}^* \,\,|\,\, \mbox{os $a$'s (se houver) de $w$
	       precedem os $b$'s (se houver)}\}\mbox{;}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ tem apenas $1$ ou $2$
	          $a$'s}\}\mbox{;}$
        \item $\{w \in \{a,b,c\}^* \,\,|\,\, \mbox{o n\'umero total de $a$'s
	       e/ou $b$'s em $w$ \'e m\'{u}ltiplo de $2$}\}\mbox{;}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ n\~ao cont\'em o
	       {\it substring\/} $aaa$}\}\mbox{.}$
       \end{list}
 
 \item Construa uma gram\'atica sobre $\{a,b,c\}$ cuja linguagem seja
       \[\{a^ib^jc^k \,\,|\,\, j>i+k\}\mbox{.}\]
 
 \item Seja $G$ a gram\'atica
       \begin{center}
       \begin{tabular}{ccl}
        $S$ & $\rightarrow$ & $A B$ \\
        $A$ & $\rightarrow$ & $a A b \,\,|\,\, c$ \\
        $B$ & $\rightarrow$ & $b B c \,\,|\,\, a$ \\
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma deriva\c{c}\~ao mais a esquerda de $a c b b b a c c$.
	\item Construa a \'arvore de deriva\c{c}\~ao para a deriva\c{c}\~ao
	      constru\'{\i}da em (a).
	\item Defina $L(G)$ utilizando nota\c{c}\~ao de conjunto.
       \end{list}

\pagebreak 
 \item Seja a gram\'{a}tica $G$:
 
       \hspace*{1cm} $S \rightarrow aS \,\,|\,\, Sb \,\,|\,\, ab \,\,|\,\, SS$
 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Identifique o \underline{menor {\it string\/}} gerado por $G$
	      para o qual existem duas \'{a}rvores de deriva\c{c}\~{a}o
	      diferentes.
	\item Construa uma gram\'{a}tica n\~{a}o amb\'{\i}gua equivalente a
	      $G$.
       \end{list}
 
 \item Seja a gram\'{a}tica $G=(\{E,T,F\},\{+,*,(,),a\},P,E)$, em que $P$ \'{e}
       constitu\'{\i}do das regras:
 
       \hspace*{1cm} $E \rightarrow E + T \,\,|\,\, T$ \\
       \hspace*{1cm} $T \rightarrow T + F \,\,|\,\, F$ \\
       \hspace*{1cm} $F \rightarrow ( E ) \,\,|\,\, a$
 
       Obtenha uma gram\'{a}tica equivalente a $G$ que n\~{a}o tenha regras
       com recursividade \`{a} esquerda, nem regras de cadeias.
 
 \item Construa uma gram\'{a}tica na forma normal de Greibach equivalente \`{a}
       seguinte gra\-m\'{a}\-ti\-ca:
 
       \hspace*{1cm} $S \rightarrow A B \,\,|\,\, C S B$ \\
       \hspace*{1cm} $A \rightarrow a B \,\,|\,\, C$ \\
       \hspace*{1cm} $B \rightarrow b b B \,\,|\,\, b$ \\
       \hspace*{1cm} $C \rightarrow c C \,\,|\,\, \lambda$
 
 \item Seja a linguagem \[L=\{w \in \{a,b\}^* \,\,|\,\, \mbox{o terceiro
       s\'{\i}mbolo \underline{da direita para a esquerda} \'{e} $b$}\}\mbox{.}
       \]
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um aut\^{o}mato finito n\~{a}o determin\'{\i}stico de 4
	      estados que gere $L$.
        \item Construa um aut\^{o}mato finito determin\'{\i}stico que gere $L$.
       \end{list}
 
 \item Construa uma express\~{a}o regular que denote a linguagem reconhecida
       pelo aut\^{o}mato finito, $M$, definido abaixo, utilizando o m\'{e}todo
       do grafo de express\~{o}es:
 
       \hspace*{1cm} $M=(\{q_0,q_1,q_2\},\{a,b\},\delta,q_0,\{q_2\})$, sendo
       $\delta$ dada por:
 
       \hspace*{2cm} \begin{tabular}{c|cc}
        $\delta$ & a & b \\ \hline
	$q_0$ & $\{q_1\}$ & $\{\}$ \\
	$q_1$ & $\{q_0\}$ & $\{q_2\}$ \\
	$q_2$ & $\{\}$ & $\{q_1\}$
       \end{tabular}
 
 \item Prove que a linguagem $\{a^ib^j \,\,|\,\, i>j\}$ n\~{a}o \'{e} regular.
 
 \item Prove que a linguagem $\{0^{n^3} \,\,|\,\, n \geq 0\}$ n\~{a}o \'{e}
       regular.
 
 \item Prove que a linguagem $\{a^nb^{n^2} \,\,|\,\, n \geq 0\}$ n\~{a}o \'{e}
       livre de contexto.
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
