\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2003 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: 23/10/03

\begin{enumerate}
 \item Calcule:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantas palavras de tamanho $n$ existem sobre um alfabeto $\Sigma$.
        \item Quantos prefixos tem uma palavra de tamanho $n$.
        \item Quantas subpalavras tem uma palavra de tamanho $n$.
       \end{list}

 \item Sejam $A$, $B$ e $C$ linguagens. Mostre que:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item $A(B\cup C)=(AB)\cup(AC)$.
       \item Nem sempre $A(B\cap C)=(AB)\cap(AC)$.
      \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, concatena\c c\~ao,
       fecho de Kleene, etc.) as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que cont\^em {\tt 00}.
        \item O conjunto das palavras com, no m\'aximo, dois {\tt 0}'s.
        \item O conjunto das palavras de tamanho m\'ultiplo de 3.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras de tamanho m\'ultiplo de 3 que
              n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras que come\c cam com 0, n\~ao
              cont\^em {\tt 10} e terminam com 1.
        \item O conjunto das palavras de tamanho par que cont\^em pelo menos um 0.
        \item O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de
              1's (ou ambos).
       \end{list}

 \item Em que condi\c c\~oes $A^*\cup B^*=(A\cup B)^*$?

 \item Que linguagens s\~ao geradas pelas gram\'aticas a seguir? N\~ao \'e preciso
       provar.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{X,A,B\},\{{\tt 0},{\tt 1}\},R_1,X)$.
              \begin{enumerate}
               \item[$R_1$:] $X\,\rightarrow\, A B$
               \item[\ ]     $A\,\rightarrow\,{\tt 0}A{\tt 0}\,|\, {\tt 0}$
               \item[\ ]     $B\,\rightarrow\,{\tt 1}B\,|\, \lambda$
              \end{enumerate}
        \item $G_2=(\{P,I\},\{{\tt 0},{\tt 1}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:] $P\,\rightarrow\,{\tt 0} P \,|\, {\tt 1}I$
               \item[\ ]     $I\,\rightarrow\,{\tt 0} I\,|\, {\tt 1}P\,|\, \lambda$
              \end{enumerate}
        \item $G_3=(\{P,X\},\{{\tt 0},{\tt 1}\},R_3,P)$.
              \begin{enumerate}
               \item[$R_3$:] $P\,\rightarrow\,{\tt 0} P {\tt 0}\,|\, {\tt 1}P{\tt 1}\,|\, X$
               \item[\ ]     $X\,\rightarrow\,{\tt 0} X{\tt 1}\,|\, \lambda$
              \end{enumerate}
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a}\}^*\,|\, |w| \,\mbox{\em mod } 2=0\}$
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o n\'umero de {\tt a}'s em
                   $w$ \'e maior que 2}\}$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho \'{\i}mpar
                   terminadas em {\tt 1}.
        \item $\{wxw^R\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{{\tt b}\}^*\}$.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\leq n\leq 2m\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}^*\{{\tt 10}\}^*$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho \'{\i}mpar
                   terminadas em {\tt 1}.
        \item $\{{\tt a}^k{\tt b}^n\,|\, k+n\not= 3\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt bba}}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ n\~ao termina com bba}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem n\'umero par de }
                    {\tt ab}\mbox{'s}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem n\'umero par de }
                    {\tt ab}\mbox{'s e \'{\i}mpar de {\tt a}'s}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{{\tt 1}}(w)
                    \,\mbox{\em mod}\, 3=2\}$, onde
                   $n_s(w)$ \'e a quantidade do s\'{\i}mbolo $s$ na palavra $w$.
        \item $\{w\in\{0,1\}^*\,|\,n_0(w) \,\mbox{\em mod } 3 >
                                   n_1(w) \,\mbox{\em mod } 3\}$
        \item $\{x{\tt baa}\,|\,x\in\{{\tt a},{\tt b}\}^*
                    \mbox{ e } x \mbox{ tem n\'umero par de }{\tt a}\mbox{'s}\}$.
       \end{list}

 \item Sejam os seguintes AFD's:
       \begin{enumerate}
        \item $M_1=(\{p,i\},\{{\tt 0},{\tt 1}\},\delta_1,p,\{p\})$, onde $\delta_1$
              \'e dada por:

              \begin{tabular}{c|cc}
               $\delta_1$ & {\tt 0} & {\tt 1} \\ \hline
                  $p$ & $i$ & $p$ \\
                  $i$ & $p$ & $i$
              \end{tabular}
        \item $M_2=(\{p,i\},\{{\tt 0},{\tt 1}\},\delta_2,p,\{i\})$, onde $\delta_2$
              \'e dada por:

              \begin{tabular}{c|cc}
               $\delta_2$ & {\tt 0} & {\tt 1} \\ \hline
                  $p$ & $i$ & $i$ \\
                  $i$ & $p$ & $p$
              \end{tabular}
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagens s\~ao $L(M_1)$ e $L(M_2)$?
        \item Utilizando as t\'ecnicas do Teorema 4, da Se\c c\~ao 2.2.3, obtenha
              um AFD que reconhe\c ca $L(M_1)-L(M_2)$, ou seja,
              $L(M_1)\cap\overline{L(M_2)}$.
       \end{list}

 \item Explique: {\em Se um AFD $M$ reconhece uma palavra de tamanho igual ao
       n\'u\-me\-ro de estados de $M$, ent\~ao $L(M)$ \'e infinita\/}.

 \item Mostre que n\~ao existe AFD que reconhece $\{{\tt 0}^ny\,|\,
       y\in\{{\tt 1},{\tt 2}\}^* \mbox{ e } |y|=n\}$.

\end{enumerate}

\end{document}
