\documentclass[11pt, a4paper]{article}
 
\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
%\usepackage{gastex}
%\usepackage[usenames]{color}

\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{2}^{\mbox{\underline{o}}}$ semestre de 1993
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Solu\c{c}\~ao da Primeira Prova}
 
\vspace*{3mm}
\begin{enumerate}
 \item Fa\c{c}a uma defini\c{c}\~ao recursiva do {\it conjunto de descendentes de
       um nodo\/} $x$ de uma \'arvore $(N,A,r)$ (lembre-se que $x$ \'e
       descendente de si mesmo).
 
       \vspace*{1mm}
       Seguem duas solu\c{c}\~oes:
 
       \begin{list}{\roman{conta}.}{\usecounter{conta}}
        \item O conjunto dos descendentes de um nodo $x$ de uma \'arvore
	      $(N,A,r)$ \'e definido como abaixo:
	      \begin{list}{(\alph{conta2})}{\usecounter{conta2}}
	       \item $x$ \'e descendente de $x$;
	       \item se $y$ \'e descendente de $x$ e $[y,z] \in A$, ent\~ao
	             $z$ \'e descendente de $x$;
	       \item s\'o s\~ao descendentes de $x$ os nodos que podem ser
	             determinados como tais de acordo com (a) e (b).
	      \end{list}
        \item O conjunto dos descendentes de um nodo $x$ de uma \'arvore
	      $(N,A,r)$, $D(x)$, \'e o menor conjunto tal que:
	      \begin{list}{(\alph{conta2})}{\usecounter{conta2}}
	       \item $x \in D(x)$;
	       \item se $y \in D(x)$ e $[y,z] \in A$, ent\~ao $z \in D(x)$.
	      \end{list}
       \end{list}
 \item Prove, por indu\c{c}\~ao, que uma \'arvore estritamente bin\'aria de
       profundidade (n\'{\i}vel) $n$ tem, no m\'{\i}nimo, $2n+1$ nodos.
 
       \vspace*{1mm}
       A prova ser\'a feita por indu\c{c}\~ao sobre o n\'{\i}vel $n$. Se
       $n = 0$, a \'arvore tem um \'unico nodo, por defini\c{c}\~ao; e,
       neste caso, $2\times 0+1=1$. Hip\'otese de indu\c{c}\~ao: toda
       \'arvore estritamente bin\'aria de n\'{\i}vel $n \leq k$ tem, no
       m\'{\i}nimo, $2n+1$ nodos. Basta provar, ent\~ao, que \'arvores de
       n\'{\i}vel $k+1$ t\^em, no m\'{\i}nimo, $2(k+1)+1$ nodos. Por
       defini\c{c}\~ao, uma \'arvore estritamente bin\'aria, $T$, de
       n\'{\i}vel $k+1$ (portanto, maior que 0) tem a forma:
 
       \begin{picture}(200,70)
        \put(100,65){\makebox(0,0){$r$}}
	\put(97,60){\line(-2,-1){20}}
	\put(103,60){\line(2,-1){20}}
	\put(77,50){\line(-1,-2){20}}
	\put(77,50){\line(1,-2){20}}
	\put(57,10){\line(1,0){40}}
	\put(77,20){\makebox(0,0)[b]{$T_1$}}
	\put(123,50){\line(-1,-2){20}}
	\put(123,50){\line(1,-2){20}}
	\put(103,10){\line(1,0){40}}
	\put(123,20){\makebox(0,0)[b]{$T_2$}}
       \end{picture}
 
       $T$ ter\'a um n\'umero m\'{\i}nimo de nodos quando uma das sub-\'arvores,
       $T_1$ ou $T_2$, tiver um \'unico nodo, e a outra tiver $2k+1$ nodos
       (esta \'ultima, pela hip\'otese de indu\c{c}\~ao, visto que ela ter\'a
       n\'{\i}vel $k$, j\'a que o n\'{\i}vel de $T$ \'e $k+1$). Somando-se
       a estes $2k+2$ nodos o nodo raiz de $T$, tem-se que $T$ ter\'a, no
       m\'{\i}nimo, $2k+3=2(k+1)+1$ nodos.
 
\pagebreak
 \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 e/ou $c$'s (se houver)}\}\mbox{;}$
 
               \vspace*{1mm}
	       Solu\c{c}\~ao: {\boldmath $a^*(b\cup c)^*$}
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{o n\'umero total de $a$'s
	       em $w$ \'e $2$ ou $3$}\}\mbox{;}$
 
               \vspace*{1mm}
	       Solu\c{c}\~ao: {\boldmath $b^*ab^*ab^*(a\cup \lambda)b^*$}
        \item $\{w \in \{a,b,c\}^* \,\,|\,\, \mbox{o n\'umero total de $a$'s
	       e/ou $b$'s em $w$ \'e $3$}\}\mbox{;}$
 
               \vspace*{1mm}
	       Solu\c{c}\~ao: {\boldmath $c^*(a\cup b)c^*(a\cup b)c^*(a\cup  b)
	                                 c^*$}
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ n\~ao cont\'em o
	       {\it substring\/} $aaa$}\}\mbox{.}$
 
               \vspace*{1mm}
	       Solu\c{c}\~ao: {\boldmath $(b\cup ab\cup aab)^*(\lambda\cup a\cup
	                        aa)$}
       \end{list}
 \item Construa uma gram\'atica sobre $\{a,b,c\}$ cuja linguagem seja
       \[\{a^mb^nc^i \,\,|\,\, m>n+i\}\mbox{.}\]
 
       \vspace*{1mm}
       Uma outra forma de descrever esta linguagem \'e:
       \[\{a^ka^ia^nb^nc^i \,\,|\,\, i,n\geq 0 \,\mbox{e}\, k>0\}\mbox{.}\]
       o que sugere imediatamente a seguinte gram\'atica:
       \begin{center}
       \begin{tabular}{ccl}
        $S$ & $\rightarrow$ & $a S \,\,|\,\, a A$ \\
        $A$ & $\rightarrow$ & $a A c \,\,|\,\, B$ \\
        $B$ & $\rightarrow$ & $a B b \,\,|\,\, \lambda$ \\
       \end{tabular}
       \end{center}
 
 \item Seja $G$ a gram\'atica
       \begin{center}
       \begin{tabular}{ccl}
        $S$ & $\rightarrow$ & $A S B \,\,|\,\, \lambda$ \\
        $A$ & $\rightarrow$ & $a A b \,\,|\,\, \lambda$ \\
        $B$ & $\rightarrow$ & $b B a \,\,|\,\, b a$ \\
       \end{tabular}
       \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma deriva\c{c}\~ao mais a esquerda de $a a b b b a$.
	
              \vspace*{1mm}
	      Solu\c{c}\~ao:
	
              \begin{tabular}{cclcl}
               $S$ & $\Rightarrow$ & $A S B$ & \ \ \ & $(S \rightarrow A S B)$ \\
                   & $\Rightarrow$ & $a A b S B$ & & $(A \rightarrow a A b)$ \\
                   & $\Rightarrow$ & $a a A b b S B$ & & $(A \rightarrow a A b)$\\
                   & $\Rightarrow$ & $a a b b S B$ & & $(A \rightarrow \lambda)$\\
                   & $\Rightarrow$ & $a a b b B$ & & $(S \rightarrow \lambda)$\\
                   & $\Rightarrow$ & $a a b b b a$ & & $(B \rightarrow b a)$
	       \end{tabular}
	\item Construa a \'arvore de deriva\c{c}\~ao para a deriva\c{c}\~ao
	      constru\'{\i}da em (a).
	
              \vspace*{1mm}
	      Solu\c{c}\~ao:
	
	      \begin{picture}(300,135)
	       \put(150,130){\makebox(0,0){$S$}}
	       \put(147,125){\line(-2,-1){40}}
	       \put(150,125){\line(0,-1){20}}
	       \put(153,125){\line(2,-1){40}}
 
	       \put(107,100){\makebox(0,0){$A$}}
	       \put(104,95){\line(-1,-1){20}}
               \put(84,70){\makebox(0,0){$a$}}
	       \put(107,95){\line(0,-1){20}}
               \put(107,70){\makebox(0,0){$A$}}
	       \put(104,65){\line(-1,-1){20}}
               \put(84,40){\makebox(0,0){$a$}}
	       \put(107,65){\line(0,-1){20}}
               \put(107,40){\makebox(0,0){$A$}}
	       \put(107,35){\line(0,-1){20}}
	       \put(107,10){\makebox(0,0){$\lambda$}}
	       \put(110,65){\line(1,-1){20}}
               \put(130,40){\makebox(0,0){$b$}}
	       \put(110,95){\line(1,-1){20}}
               \put(130,70){\makebox(0,0){$b$}}
 
               \put(150,100){\makebox(0,0){$S$}}
	       \put(150,95){\line(0,-1){20}}
               \put(150,70){\makebox(0,0){$\lambda$}}
 
               \put(193,100){\makebox(0,0){$B$}}
	       \put(191,95){\line(-1,-1){20}}
               \put(171,70){\makebox(0,0){$b$}}
	       \put(195,95){\line(1,-1){20}}
               \put(215,70){\makebox(0,0){$a$}}
              \end{picture}
	\item Defina $L(G)$ utilizando nota\c{c}\~ao de conjunto.
	
              \vspace*{1mm}
	      Observe, inicialmente, que:
	      \[S \stackrel{k}{\Rightarrow} A^k S B^k \Rightarrow A^k B^k \
	      (k \geq 0)
	      \mbox{.}\]
	      Observe tamb\'em que:
	      \[\{w \in \Sigma^* \,\,|\,\, A \stackrel{*}{\Rightarrow} w\}
	        = \{a^nb^n \,\,|\,\, n \geq 0\}\,\,\,\mbox{e}\,\,\,
		\{w \in \Sigma^* \,\,|\,\, B \stackrel{*}{\Rightarrow} w\}
	        = \{b^ma^m \,\,|\,\, m \geq 1\}\mbox{.}\]
	      Assim, $L(G)$ nada mais \'e que:
	      \[\bigcup_{k\geq 0}(\{a^nb^n \,\,|\,\, n \geq 0\}^k
	        \{b^ma^m \,\,|\,\, m \geq 1\}^k)\mbox{.}\]
       \end{list}
\end{enumerate}
 
\end{document}
\endinput
\end
 
