\documentclass[12pt, a4paper]{report}

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

\newcounter{conta}
\newcounter{conta2}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova/Especila} \hfill 23/11/2004

\vspace*{3mm}
\noindent {\bf As quest\~oes 1, 2 e 3 valem 3 pontos cada uma; a quest\~ao
4 vale 4,5 pontos; e a quest\~ao 5 vale 1,5 pontos.}

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

 \item Para cada um dos casos abaixo, encontre exemplos de linguagens $A$ e $B$
       sobre $\{{\tt a},{\tt b}\}$ que satisfa\c cam a condi\c c\~ao apresentada:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $|A^2|<|A|^2$. ($|A|$ \'e o n\'umero de palavras de $A$.)
        \item $A^*=B^*$ e $A\not = B$.
        \item $(A-B)^*=B^*$.
       \end{list}

 \item Descreva as linguagens abaixo, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando conjuntos finitos e \underline{apenas} as opera\c c\~oes:
       concatena\c c\~ao, uni\~ao, interse\c c\~ao, diferen\c ca e/ou fecho de Kleene.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com n\'umero de s\'{\i}mbolos m\'ultiplo de 3.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em no m\'aximo dois
              {\tt 1}'s$\}$.
        \item $\{y\in\{{\tt 0},{\tt 1,{\tt 2}}\}^* \,|\, y$ n\~ao
              cont\'em {\tt 01}$\}$.
       \end{list}

 \item Sobre gram\'aticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada pela gram\'atica $G$ definida a seguir?

              $G=(\{P,A,B,X\},\{{\tt a},{\tt b}\},R,P)$.
               \begin{enumerate}
                \item[$R$:] $P\,\rightarrow\,A B$
                \item[\ ]   $A\,\rightarrow\,{\tt a} X \,|\, \lambda$
                \item[\ ]   $X\,\rightarrow\, A {\tt b}$
                \item[\ ]   $B\,\rightarrow\,{\tt a} B {\tt a} \,|\, {\tt b} B {\tt b}
                                             \,|\, \lambda$
               \end{enumerate}
        \item Obtenha uma gram\'atica que gere o conjunto das palavras sobre
              $\{{\tt a},{\tt b},{\tt c}\}$ com n\'umero par de {\tt a}'s e no
              m\'aximo dois {\tt c}'s.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para as linguagens
       a seguir. Apresente apenas o \underline{diagrama de estados} de cada AFD
       (pode ser no estilo simplificado).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}^*\{{\tt 00}\}^*$.
        \item $\{y\in\{{\tt 0},{\tt 1,{\tt 2}}\}^* \,|\, y$ n\~ao
              cont\'em {\tt 01}$\}$.
        \item O complemento da linguagem do item (b).
       \end{list}

 \item Explique porque sim ou porque n\~ao:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe AFD que reconhece $\{{\tt 0}^n{\tt 0}^n\,|\, n\geq 0\}$.
        \item Existe AFD que reconhece $\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}$.
       \end{list}
\end{enumerate}

\end{document}

