\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 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova} \hfill 10/07/2002 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turmas M e G}

\vspace*{2mm}
\noindent {\bf Cada item de cada quest\~ao vale 1 ponto.}

\vspace*{1mm}
\begin{enumerate}
 \item Expresse as linguagens a seguir utilizando opera\c c\~oes sobre conjuntos
       finitos de palavras de $\{\verb+0+,\verb+1+\}^*$. Considere o alfabeto
       como sendo $\{\verb+0+,\verb+1+\}$.
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras que t\^em exatamente 10 s\'{\i}mbolos.
          \item O conjunto das palavras que t\^em \verb+00+ como prefixo e \verb+11+
                como sufixo.
          \item O conjunto das palavras em que todo \verb+0+ \'e seguido de \verb+1+.
                Exemplos: $\lambda$, \verb+111+, \verb+011+, \verb+11010111011+.
          \item O conjunto das palavras que cont\^em um ou dois \verb+1+'s.
        \end{list}

 \item  \begin{list}{(\alph{conta})}{\usecounter{conta}}
           \item Fa\c ca uma defini\c c\~ao recursiva da linguagem
                  $\{\verb+ab+\}^*\{\lambda,\verb+b+\}\{\verb+ba+\}^*$.
           \item Construa uma gram\'atica que gere a linguagem
                  $\{\verb+ab+\}^*\{\lambda,\verb+b+\}\{\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 $\{\lambda\}$
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que cont\^em
                um ou dois \verb+1+'s.
          \item $\{\verb+ab+\}^*\{\lambda,\verb+b+\}\{\verb+ba+\}^*$
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, \mbox{$w$ n\~ao come\c ca com
                00 nem termina com 11}\}$
%          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w| \mbox{ mod } 3=0 
%                \mbox{ e } w \mbox{ n\~ao cont\'em }\verb+00+\}$
         \end{list}

 \item Sejam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$
        \item $\{\verb+0+^n\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$
       \end{list}
       Mostre que a primeira n\~ao pode ser reconhecida por AFD, e que a
       segunda pode.

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se a linguagem $L$ pode ser reconhecida por AFD, qualquer subconjunto
              de $L$ tamb\'em pode.
        \item Para qualquer linguagem finita $L$ existe AFD que reconhece $L$.
       \end{list}

\end{enumerate}
\end{document}

