\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{2}^{\mbox{\underline{o}}}$ semestre de 1996
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Primeira Prova} \hfill 05/08/96

\vspace*{5mm}
\begin{description}
 \item[Dura\c{c}\~{a}o:] 1 hora e 30 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*{3mm}
\begin{enumerate}
 \item Sejam $A$, $B$ e $C$ linguagens sobre um alfabeto $\Sigma$. Mostre que:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A(B\cup C)=(AB)\cup(AC)$
        \item n\~{a}o \'{e} sempre verdade que $A(B\cap C)= (AB)\cap(AC)$
       \end{list}
 \item Seja $\Sigma_1=\{0\}$, e $\Sigma_2=\{1\}$. Mostre que os conjuntos abaixo,
       s\~{a}o enumer\'{a}veis (se quizer, pode apenas mostrar um trecho inicial de uma
       enumera\c{c}\~{a}o poss\'{\i}vel).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\Sigma_1^*$
        \item $\Sigma_1^*\Sigma_2^*$
       \end{list}
 \item Prove que $(w^R)^i = (w^i)^R$ para todo {\em string\/} $w$ e todo $i\in
       \mbox{\bf N}$. ({\em Sugest\~{a}o\/}: utilize indu\c{c}\~{a}o sobre $i$.)
 \item Seja $\Sigma=\{a,b,c\}$. As express\~{o}es regulares em cada par abaixo
       s\~{a}o equivalentes? Justifique.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $(a\cup b)^*a^*$} e {\boldmath $((a\cup b)a)^*$}
        \item {\boldmath $\phi^{**}$} e {\boldmath $\lambda$}
        \item {\boldmath $((a\cup b)c)^*$} e {\boldmath $(ac\cup bc)^*$}
       \end{list}
 \item Construa express\~oes regulares para cada um dos seguintes conjuntos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \in \{a,b,c\}^* \,\,|\,\, w$ tem pelo menos um $a$, e
               o primeiro $a$ n\~{a}o \'{e} precedido de nenhum $b\}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ tem ambos, $aa$ e $bb$,
               como {\em substrings}}\}$
        \item $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ n\~ao cont\'em os
              {\it substrings\/} $aa$ nem $bb$}\}$
       \end{list}
 
\end{enumerate}
 
\end{document}
\endinput
\end
 
                                                                    
