\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 2006 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent Monitor: Renato Vimieiro - vimieiro@dcc.ufmg.br \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill {\bf Entrega: 03/04/2006}

\begin{enumerate}
 \item Sobre conjuntos enumer\' aveis:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que o conjunto de n\'umeros inteiros \'{\i}mpares \' e enumer\'avel.
        \item Seja $\Sigma = \{{\tt a}\}$. O conjunto $\Sigma^*$ \'e enumer\'avel? E
              o conjunto ${\cal P}(\Sigma)$? Prove a sua resposta.
       \end{list}

 \item Fa\c ca defini\c c\~oes recursivas tradicionais (sem uso de gram\'atica)
       para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{0^m1^n\,|\,m,n\geq 0\}$
        \item $\{0^n1^n\,|\,n\geq 0\}$
        \item $\{w\in\{0,1\}^*\,|\,n_a(w)=n_b(w)\}$ \\
              $n_s(w)$ \'e o n\'umero de s\'{\i}mbolos $s$ na palavra $w$.
       \end{list}

 \item Sejam $\Sigma=\{{\tt 0},{\tt 1}\}$,  $A=\Sigma^5$ e $B=\{{\tt 0}\}\Sigma^*$.
       Para cada uma das linguagens abaixo, d\^e uma propriedade necess\'aria
       e suficiente para que uma palavra perten\c ca \`a mesma:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A^*$.
        \item $B^+$.
        \item $A\cap B$.
        \item $AB$.
        \item $A^*\cap B^*$.
       \end{list}

 \item Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas conjuntos finitos, opera\c c\~oes sobre conjuntos,
       concatena\c c\~ao e fecho de Kleene. Procure obter uma descri\c c\~ao bem
       concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras da forma ${\tt 0}^m{\tt 1}^n$, em que $m,n>0$.
        \item O conjunto das palavras que cont\^em pelo menos uma subpalavra
              da forma ${\tt 0}^m{\tt 1}^n$, em que $m,n>0$.
        \item O conjunto das palavras em que entre cada par de {\tt 0}s
              h\'a uma subpalavra ${\tt 1}^n$, sendo $n$ \'{\i}mpar.
              Observe que antes do primeiro {\tt 0} ou ap\'os o \'ultimo
              {\tt 0} pode ocorrer um n\'umero par de {\tt 1}s, se a palavra
              tiver {\tt 0}s.
        \item O conjunto das palavras que n\~ao cont\^em a subpalavra {\tt 00}.
        \item O conjunto das palavras de tamanho par que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras com tamanho m\'ultiplo de 3.
        \item O conjunto das palavras nas quais o n\'umero de {\tt 1}'s \'e m\'ultiplo
              de 3.
        \item O conjunto das palavras que cont\^em {\tt 101} e {\tt 11} como subpalavras.
       \end{list}

\pagebreak
 \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}S{\tt 1} \,|\, A \,|\, B$
               \item[\ ]      $A\,\rightarrow\,{\tt 0}A\,|\, {\tt 0}$
               \item[\ ]      $B\,\rightarrow\,B{\tt 1}\,|\, {\tt 1}$
              \end{enumerate}

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

        \item $G_3=(\{P,X\},\{{\tt a},{\tt b},{\tt c}\},R_3,P)$.
              \begin{enumerate}
               \item[$R_3$:] $P\,\rightarrow\,{\tt a} P {\tt a} \,|\, X$
               \item[\ ]   $X\,\rightarrow\, {\tt b} X {\tt c} \,|\, X {\tt c} \,|\, \lambda$
              \end{enumerate}

        \item $G_4=(\{P,A,X\},\{{\tt 0},{\tt 1}\},R_4,P)$.
              \begin{enumerate}
               \item[$R_4$:] $P\,\rightarrow\,{\tt a}P{\tt a} \,|\,{\tt b}P{\tt b}\,|\,A$ 
               \item[\ ]  $A\,\rightarrow\,{\tt a}X{\tt b} \,|\,{\tt b}X{\tt a}$
               \item[\ ]  $X\,\rightarrow\,{\tt 0}X \,|\,{\tt 1}X \,|\,\lambda$
              \end{enumerate}

        \item $G_5=(\{P,\},\{{\tt 0},{\tt 1}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:] $P\,\rightarrow\,{\tt 0} P {\tt 1}\,|\,\lambda$
               \item[\ ]     ${\tt 01}\,\rightarrow\,{\tt 10}$
              \end{enumerate}

       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}\}\{{\tt bb}\}^*\{{\tt c}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, \mbox{ toda seq\"u\^encia de
               {\tt a}'s em $w$ vem entre dois {\tt b}s}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, n_a(w) \,\mbox{\em mod } 3=1\}$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho \'{\i}mpar
              com pelo menos dois {\tt 1}s.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m>n\}$.
        \item $\{wxw^R\,|\, x,w\in\{{\tt a},{\tt b}\}^* \mbox{ e } |w|=|x|\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ toda posi\c c\~ao \'{\i}mpar
              de $w$ cont\'em {\tt 1}}\}$.
        \item $\{{\tt 01}\}^*\{{ \tt 10}\}^*$.
        \item $(\{{\tt 1}\}\cup\{{\tt 0}\}\{{\tt 0},{\tt 1}\})\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt a}^k{\tt b}^n\,|\, k+n\geq 3\}$.
        \item O conjunto das palavras em que entre cada par de {\tt 0}s
              h\'a uma subpalavra ${\tt 1}^n$, sendo $n$ \'{\i}mpar.
              Observe que antes do primeiro {\tt 0} ou ap\'os o \'ultimo
              {\tt 0} pode ocorrer um n\'umero par de {\tt 1}s, se a palavra
              tiver {\tt 0}s.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho \'{\i}mpar
              com pelo menos dois {\tt 1}s.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{{\tt 1}}(w) \,\mbox{\em mod}\, 3=2\}$.
       \end{list}

 \item Fa\c ca AFD's que reconhe\c cam: $X=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|$ \'e
       par$\}$. e $Y=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$
       n\~ao cont\'em {\tt 11}$\}$. Bastam apenas os diagramas
       de estados. Em seguida, obtenha o produto dos dois AFD's e explicite
       que estados finais ele deve ter para reconhecer
       $X\cap Y$ e $X\cup Y$.
\end{enumerate}

\end{document}
