\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{2}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Prof.: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill Devolu\c c\~ao: 05/09/01


\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}
       Procure ser bem preciso e conciso.

 \item D\^e defini\c c\~oes recursivas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{0\}^*\{1\}^*$
        \item[(b)] $\{0^n1^n\,\,|\,\, n\in\mbox{\bf N}\}$
        \item[(c)] $\{0^010^110^21\ldots 0^n1\,\,|\,\, n\in {\bf N}\}$
       \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 (AFD's) 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)] $\{w\in\{a,b\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em $aaa$ nem
                   $bbb$}\}$.
        \item[(e)] $\{01\}^*\{10\}^*$.
        \item[(d)] $\{w\in\{a,b\}^*\,\,|\,\, w \mbox{ os 3 \'ultimos s\'{\i}mbolos de
                   $w$ n\~ao s\~ao $bbb$}\}$.
       \end{enumerate}

 \item Construa AFD's para as linguagens sobre o alfabeto $\{\verb+0+,\verb+1+\}$,
       a seguir. Considere que o s\'{\i}mbolo na posi\c c\~ao 1 de uma palavra \'e o
       primeiro s\'{\i}mbolo desta, o s\'{\i}mbolo na posi\c c\~ao 2 \'e o segundo, e
       assim por diante.
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras em que o s\'{\i}mbolo na posi\c c\~ao $2i$ \'e
                diferente do s\'{\i}mbolo na posi\c c\~ao $2i+2$, para $i\geq 1$.
          \item O conjunto das palavras em que o s\'{\i}mbolo na posi\c c\~ao $2i-1$ \'e
                diferente do s\'{\i}mbolo na posi\c c\~ao $2i$, para $i\geq 1$.
          \item O conjunto das palavras em que o s\'{\i}mbolo na posi\c c\~ao $i$ \'e
                diferente do s\'{\i}mbolo na posi\c c\~ao $i+2$, para $i\geq 1$.
          \item O conjunto das palavras com n\'umero \'{\i}mpar de \verb+0+'s nas
                po\-si\-\c c\~oes  \'{\i}mpares e n\'umero par de \verb+0+'s nas
                po\-si\-\c c\~oes pares.
          \item O conjunto das palavras de tamanho par com \verb+1+'s nas
                po\-si\-\c c\~oes pares, acrescido das palavras de
                tamanho \'{\i}mpar com \verb+1+'s nas po\-si\-\c c\~oes \'{\i}mpares.
         \end{list}

 \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{B}$.)
       \end{enumerate}
\end{enumerate}

\end{document}
 
