\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{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent Monitor: Ricardo Augusto Rabelo - rabelo @dcc.ufmg.br \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill {\bf Entrega: 28/03/2005}

\begin{enumerate}
 \item Sobre conjuntos enumer\' aveis:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que o conjunto de n\'umeros inteiros pares \' e enumer\'avel.
        \item Uma fun\c c\~ao total de {\tt N} para {\tt N} \'e dita ser monotonicamente
              crescente se $f(n) < f(n+1)$, para todo $n \in N$. O conjunto constitu\'{\i}do por tais
              fun\c c\~oes \' e enumer\'avel? Prove a sua resposta.
        \item Seja $\Sigma = \{{\tt a}\}$. O conjunto $\Sigma^*$ \'e enumer\'avel ? E
              o conjunto ${\cal P}(\Sigma)$? Prove a sua resposta.
       \end{list}

   \item Defini\c c\~oes recursivas:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
           \item Seja $X$ um conjunto finito. D\^e uma defini\c c\~ao recursiva do
                 conjunto pot\^encia de $X$, ${\cal P }(X)$. Use a uni\~ao como operador
                 na defini\c c\~ao.
           \item D\^e uma defini\c c\~ao recursiva do conjunto de palavras sobre
                 $\{{\tt a},{\tt b}\}$ que cont\'em apenas as palavras que possuam
                 o n\'umero de {\tt a}'s igual ao de {\tt b}'s.
         \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, uni\~ao, concatena\c c\~ao,
       fecho de Kleene, etc.) as seguintes linguagens sobre o alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto de palavras que cont\^em as subpalavras {\tt 11} e {\tt 00}.
        \item O conjunto de palavras no qual a palavra {\tt 11} acontece pelo menos duas vezes.
        \item O conjunto de palavras que n\~ao cont\'em a subpalavra {\tt 00}.
        \item O conjunto de palavras nas quais o n\'umero de {\tt 1}'s \'e m\'ultiplo
              de 2 e o n\'umero de {\tt 0}'s \'e m\'ultiplo de 5.
        \item O conjunto de palavras de tamanho \'{\i}mpar que cont\^em exatamente dois
              {\tt 1}'s.
        \item O conjunto de palavras nas quais cada {\tt 1} \'e imediatamente precedido
              ou imediatamente seguido por um {\tt 0}. Por exemplo: {\tt 0}, {\tt 010},
              {\tt 0110}.
        \item O conjunto de palavras com tamanho 4.
       \end{list}

 \item Identifique as linguagens que s\~ao geradas pelas gram\'aticas a seguir:

\begin{list}{(\alph{conta})}{\usecounter{conta}}
  \item $G_1=(\{S,A\},\{{\tt 0},{\tt 1}\},R_1,S)$.
  \begin{enumerate}
    \item[$R_1$:]  $S\,\rightarrow\,{\tt 0}A$
    \item[\ ]      $A\,\rightarrow\,{\tt 1}{\tt 0}A\,|\, \lambda$
     \end{enumerate}

     \item $G_2=(\{S,X\},\{{\tt 0},{\tt 1}\},R_2,S)$.
       \begin{enumerate}
        \item[$R_2$:] $S\,\rightarrow\,{\tt 0}X$
        \item[\ ]  $X\,\rightarrow\,{\tt 0}X |{\tt 1}X |\,{\tt 0}$
      \end{enumerate}


    \item $G_3=(\{S,X\},\{{\tt 0},{\tt 1}\},R_3,S)$.
              \begin{enumerate}
               \item[$R_3$:] $S\,\rightarrow\,{\tt 0} S \,|\, {\tt 1}X\,|\, \lambda$
               \item[\ ]     $X\,\rightarrow\,{\tt 0} X \,|\,{\tt 1}S $
              \end{enumerate}

  \item $G_4=(\{S,A,B\},\{{\tt 0},{\tt 1}\},R_4,S)$.
       \begin{enumerate}
        \item[$R_4$:] $S\,\rightarrow\,A |\,{\tt 1}B$
        \item[\ ]  $A\,\rightarrow\,{\tt 0}S|\,{\tt 0}$
        \item[\ ]  $B\,\rightarrow\,{\tt 1}S |\,{\tt 1}$
      \end{enumerate}

  \item $G_5=(\{S,A,B\},\{{\tt 0},{\tt 1}\},R_5,S)$.
              \begin{enumerate}
               \item[$R_5$:] $S\,\rightarrow\,{\tt 0} S\,|\, {\tt 1}A\,|\lambda$
               \item[\ ]     $A\,\rightarrow\,{\tt 1} A \,|\, {\tt 0}B$
               \item[\ ]     $B\,\rightarrow\,{\tt 0} S \,|\, {\tt 1}B \,|\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 } 3=1\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o n\'umero de {\tt a}'s em
                   $w$ \'e par}\}$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho \'{\i}mpar
              com pelo menos um {\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 3m\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) que reconhe\c cam:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{ \tt 10}\}^*\{{\tt 01}\}^*$.
        \item $\{{\tt 0} \}^*\{{ \tt 11} \}^*\{{ \tt 1 , \tt 0}\} \{{\tt 10}\}^*$.
        \item $\{{{\tt0 , \tt11}\}^*}\{{\tt0}\}^*\{{\tt 1}\}$.
        \item $\{{\tt 0, \tt 1}\}^*\{{\tt 10, \tt 111}\}\{{\tt 1}\}^*$.
        \item $\{{\tt a}^k{\tt b}^n\,|\, k+n\not= 3\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ cont\'em {\tt ab} e {\tt ba}}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt aba}}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w \mbox{ tem n\'umero par de }
                    {\tt aba}\mbox{'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$.
       \end{list}

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

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

              \begin{tabular}{c|cc}
               $\delta_2$ & {\tt 0} & {\tt 1} \\ \hline
                  $A$ & $B$ & $C$ \\
                  $B$ & $A$ & $A$ \\
                  $C$ & $A$ & $A$
              \end{tabular}
       \end{enumerate}

       Descreva formalmente as linguagens $L(M_1)$  e $L(M_2)$.


 \item Fa\c ca um programa que dado um AFD qualquer como entrada, teste algumas
       palavras fornecidas via terminal, verificando
       se s\~ao reconhecidas por esse AFD. Por exemplo, dada a entrada:

 \texttt{$Q=\{0,1,2\}$}

 \texttt{$F=2$}

 \texttt{$i=0$}

  \texttt{$\Sigma=\{a,b\}$}

 \texttt{$\delta=\{[0,a,1];[0,b,2];[1,a,0];[1,b,2];[2,a,2];[2,b,2]\}$}

e as palavras:

\texttt{aab}

\texttt{aaa}

 o programa gera a sa\' ida:

\texttt{aab -> Palavra reconhecida.}

\texttt{aaa -> Palavra n\~ao reconhecida.}


Observa\c c\~ oes:
      \begin{list}{(\alph{conta})}{\usecounter{conta}}
       \item O formato das transi\c c\~oes \' e a seguinte:

             \texttt{[estado original, s\'{\i}mbolo, estado final]}

       \item As configura\c c\~oes da m\'aquina de estados que vai ser testada
            devem estar em um arquivo chamado afd.txt.

       \item As palavras de entrada devem ser lidas do terminal ({\tt scanf}) e os
             resultados impressos no terminal ({\tt printf}).

       \item O programa deve ser compilado com gcc em um terminal Unix.

       \item Devem ser entregues o execut\'avel e o c\'odigo fonte, encaminhados para o
             email do monitor.

\end{list}
\end{enumerate}

\end{document}
