\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova} \hfill 13/04/2000

\vspace*{3mm}
\noindent {\em Valores das quest\~oes\/}: 2,5 pontos cada uma.

\begin{enumerate}
 \item Expresse as seguintes linguagens, utilizando opera\c c\~oes sobre conjuntos finitos de palavras de $\{\verb+0+,\verb+1+\}^*$:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que cont\^em o s\'{\i}mbolo \verb+1+.
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que come\c cam com \verb+0+ e terminam com \verb+1+.
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ com um n\'umero par de \verb+0+'s.
        \end{list}

 \item  \begin{list}{(\alph{conta})}{\usecounter{conta}}
           \item Fa\c ca uma defini\c c\~ao recursiva da linguagem $\{\verb+ab+\}^*\{\verb+ba+\}^*$.
           \item Construa uma gram\'atica que gere a linguagem $\{\verb+ab+\}^*\{\verb+ba+\}^*$.
           \item Em quantos passos \'e derivada uma palavra de tamanho $n$, para a gram\'atica constru\'{\i}da?
          \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+ab+\}^*$
          \item $\{\verb+ab+\}^*\{\verb+ba+\}^*$
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, \mbox{$w$ n\~ao come\c ca com 00 nem termina com 11}\}$
         \end{list}

 \item Seja um aut\^omato finito determin\'{\i}stico com fun\c c\~ao de transi\c c\~ao $\delta$ e alfabeto $\Sigma$. Prove que
         $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$ para todas as palavras $x,y\in\Sigma^*$.

 \item Mostre que a linguagem $\{\verb+0+^n\verb+1+^{584}\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$ n\~ao pode ser reconhecida
         por aut\^omato finito determin\'{\i}stico.

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item Construa um AFD $M_1$ para o conjunto das palavras com n\'umero par de \verb+0+'s.
          \item Construa um AFD $M_2$ para o conjunto das palavras que n\~ao cont\^em \verb+11+.
          \item Construa um AFD $M_3$ para $L(M_1)\cap L(M_2)$ usando a t\'ecnica da simula\c c\~ao de $M_1$ e $M_2$
                  em paralelo (aquela t\'ecnica em que o conjunto de estados de $M_3$ \'e o produto cartesiano dos conjuntos de
                  estados de $M_1$ e $M_2$).
         \end{list}

\end{enumerate}
\end{document}
