\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Prof.: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Prova} \hfill 24/05/01
 
\vspace*{3mm}
\noindent {\bf Cada item de cada quest\~ao vale 1 ponto.}

\begin{enumerate}
 \item Descreva mais formalmente (usando conjuntos, concatena\c c\~ao, fecho de Kleene, etc.)
       as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras de tamanho maior que zero.
        \item[(b)] O conjunto das palavras que cont\^em a subpalavra 001.
        \item[(c)] O conjunto das palavras de tamanho \'{\i}mpar terminadas em 1.
        \item[(d)] O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de 1's (ou
                   ambos).
        \item[(e)] O conjunto das palavras de tamanho par cuja primeira metade seja id\^entica
                   \`a segunda.
       \end{enumerate}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{a^nb^n\,\,|\,\, n\in\mbox{\bf N}\}$.
        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ de tamanho \'{\i}mpar terminadas em 1.
        \item[(c)] $\{w\in\{a,b\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em a subpalavra $aa$}\}$.
        \item[(d)] $\{ww^R\,\,|\,\, w\in\{a,b\}^*\}$.
       \end{enumerate}

 \item Construa aut\^omatos finitos determin\'{\i}sticos para:
       \begin{enumerate}
        \item[(a)] $\emptyset$.
        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ de tamanho \'{\i}mpar terminadas em 1.
        \item[(c)] $\{w\in\{a,b\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em a subpalavra $aa$}\}$.
        \item[(d)] $\{01\}^*\{10\}^*$.
       \end{enumerate}

\begin{flushright}
 {\bf Continua no verso.}
\end{flushright}

\pagebreak
 \item Sim ou n\~ao? Por que?
       \begin{enumerate}
        \item[(a)] Seja $J$ o conjunto de todos os programas escritos na linguagem Java que tenham, no
                   m\'aximo, $10^{10^{10}}$ caracteres. Existe um AFD que reconhece $J$.
        \item[(b)] Existe algoritmo que determina se $L(M)=\emptyset$ para quaquer AFD $M$.
        \item[(c)] Se um AFD $M$ reconhece uma palavra de tamanho igual ao n\'umero de estados de $M$,
                   ent\~ao $L(M)$ \'e infinita.
        \item[(d)] Suponha que existam AFD's para as linguagens $A$, $B$ e $C$. \'E poss\'{\i}vel
                   construir um AFD que reconhe\c ca $A-(B-C)$. (Lembre-se que $A-B=A\cap\overline{C}$.)
       \end{enumerate}
\end{enumerate}

\end{document}
 
