\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} \hfill 16/09/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 $|AB|\not=|A|\times|B|$. ($|A|$ \'e o n\'umero de palavras de $A$.)
        \item $(A\cup B)^*\not=A^*\cup B^*$.
        \item $A\not\subseteq B$ e $B\not\subseteq A$ e $(A\cup B)^*=A^*\cup 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 e/ou fecho de Kleene.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com um n\'umero par de {\tt 0}'s.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ come\c ca com {\tt 0} e
              cont\'em {\tt 11}$\}$.
        \item $\{{\tt 0}y\,|\,y\in\{{\tt 0},{\tt 1}\}^*$ e $y$ n\~ao
              cont\'em {\tt 11}$\}$.
       \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\},\{{\tt a},{\tt b},{\tt c}\},R,P)$.
               \begin{enumerate}
                \item[$R$:] $P\,\rightarrow\,B A B$
                \item[\ ]   $A\,\rightarrow\,{\tt a} A {\tt a} \,|\, \lambda$
                \item[\ ]   $B\,\rightarrow\,{\tt a} B {\tt a} \,|\, {\tt b} B {\tt b}
                                             \,|\, {\tt c}$
               \end{enumerate}
        \item Obtenha uma gram\'atica que gere o conjunto das palavras sobre
              $\{{\tt a},{\tt b},{\tt c}\}$ que n\~ao contenham {\tt ab} como
              subpalavra.
       \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 1},{\tt 10}\}^*$.
        \item $\{{\tt 0}y\,|\,y\in\{{\tt 0},{\tt 1}\}^*$ e $y$ n\~ao
              cont\'em {\tt 11}$\}$.
        \item O complemento da linguagem do item (b).
       \end{list}

 \item Seja um AFD $M=(\{i,e,f,\ldots\},\{{\tt 0},{\tt 1}\},\delta,i,\{f\})$ e
       suponha que $\hat{\delta}(i,x)=e$, $\hat{\delta}(e,y)=e$ e
       $\hat{\delta}(e,z)=f$, onde $\hat{\delta}$ \'e a fun\c c\~ao de transi\c c\~ao
       estendida para $M$. Explique porque:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $xz\in L(M)$.
        \item $xyyz\in L(M)$.
        \item $L(M)$ \'e infinita.
       \end{list}
\end{enumerate}

\end{document}

