\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 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Primeira Prova} \hfill 18/03/97

\vspace*{5mm}
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 40 minutos.
 \item[Valores das quest\~{o}es:] quest\~{o}es 1 e 2: 2 pontos cada uma; quest\~{o}es
      restantes: 3 pontos cada uma.
\end{description}

\vspace*{2mm}
\begin{enumerate}
 \item Sejam $A$, $B$ e $C$ linguagens sobre um alfabeto $\Sigma$. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\times(B - C)=(A\times B)-(A\times C)$.
        \item n\~{a}o \'{e} sempre verdade que $A(B - C)= (AB)-(AC)$.
       \end{list}
 \item Seja $\Sigma=\{a\}$. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\Sigma^*$ \'e enumer\'avel.
        \item ${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel(${\cal P}(\Sigma^*)$
              \'e o conjunto pot\^encia de $\Sigma^*$).
       \end{list}
 \item Uma {\it \'arvore estritamente bin\'aria\/} \'e uma \'arvore em que cada
       nodo interno tem exatamente 2 filhos. D\^e uma defini\c c\~ao
       recursiva para a fam\'{\i}lia das \'arvores estritamente bin\'arias.
       Em seguida, mostre, por indu\c c\~ao, que $a(T)=2(f(T)-1)$ para toda
       \'arvore estritamente bin\'aria $T$, onde $a(T)$ \'e o n\'umero de arcos
       de $T$ e $f(T)$ \'e o n\'umero de folhas de $T$.
 \item Seja $L$ uma linguagem. Em que circunst\^ancias
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L^*=L^+$?
        \item $L^*$ \'e $\phi$? E $L^+$?
        \item $L^*$ \'e $\{\lambda\}$? E $L^+$?
        \item $L^*$ \'e finita? E $L^+$?
       \end{list}
 \item Construa express\~oes regulares para cada um dos seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \in \{a,b\}^* \,\,|\,\, w$ come\c ca com $a$ e tem tamanho
               par$\}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, w$ tem tamanho maior ou igual a 2 e
               todos os $a$'s (se houver algum) precedem todos os $b$'s (se
               houver algum)$\}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, w$ nunca tem mais de 2 $a$'s
               consecutivos$\}$
       \end{list}
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
                                                                    
