\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\\
\noindent {\bf Primeira Prova} \hfill {06/09/2006}

\vspace*{3mm}
\begin{enumerate}

 \item Sejam $\Sigma=\{{\tt a},{\tt b}\}$,  $A=(\Sigma\Sigma)^*$ e $B=\{{\tt a}\}\Sigma^9$.
       Para cada uma das linguagens abaixo, d\^e uma propriedade necess\'aria
       e suficiente para que uma palavra perten\c ca \`a mesma. N\~ao precisa
       dizer que a palavra deve conter apenas {\tt a}s e {\tt b}s (fica
       impl\'{\i}cito).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $B\cap B^R$.
        \item $B-A$.
        \item $B^+$.
       \end{list}
       Exemplo: uma propriedade necess\'aria e suficiente para que uma palavra
       perten\c{c}a a $A-B$ \'e: tem n\'umero par de s\'{\i}mbolos, mas se tem
       10 s\'{\i}mbolos, come\c{c}a com {\tt b}.

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas conjuntos finitos, opera\c c\~oes sobre conjuntos,
       concatena\c c\~ao e fecho de Kleene. Procure obter uma descri\c c\~ao bem
       concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que cont\^em {\tt 00}, mas n\~ao {\tt 11}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras com n\'umero par de {\tt 0}s.
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 11}\}^*\{{\tt 0}\}\{{\tt 00}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt \#}\}^*\,|\,$ {\tt 0}'s em $w$ nunca s\~ao seguidos de
              {\tt 1}s e {\tt 1}s nunca s\~ao seguidos de {\tt 0}s$\}$. (Ou seja, seq\"u\^encias
              de {\tt 0}s e de {\tt 1}s s\~ao separadas por um ou mais ${\tt \#}$s.)
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\geq n\}$.
       \end{list}

 \item Construa AFDs que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}^*\{{ \tt 10}\}^*\{11\}^+$.
        \item A linguagem da quest\~ao 3(b).
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ o primeiro s\'{\i}mbolo de
               $w$ \'e igual ao \'ultimo ou ent\~ao $w=\lambda\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \eta(w)\, \mbox{\em mod\/}\, 3=1\}$.
              ($\eta(w)$ \'e o n\'umero representado por $w$ em bin\'ario.)
       \end{list}

 \item Dados dois AFDs $M_1=(E_1,\Sigma,\delta_1,i_1,F_1)$ e
       $M_2=(E_2,\Sigma,\delta_2,i_2,F_2)$, explique como obter AFDs que
       reconhe\c{c}am as linguagens a seguir.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(M_1)\cup L(M_2)$.
        \item $L(M_1)-L(M_2)$.
       \end{list}
       Para cada um dos casos, sendo o AFD $(E_3,\Sigma,\delta_3,i_3,F_3)$,
       basta dizer o que s\~ao: $E_3$, $\delta_3$, $i_3$, e $F_3$.
\end{enumerate}

\end{document}
