\documentclass[11pt, 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 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: 04/09/2006}

\vspace*{3mm}
\noindent \textbf{Aten\c{c}\~ao:} Para a constru\c{c}\~ao dos AFDs
(quest\~oes 7, 8 e 9),
j\'a pensando nos assuntos futuros, recomendo o uso
do software JFLAP sugerido na p\'agina da disciplina. L\'a tem um
\textit{link\/} para um relat\'orio bem simples que ensina a usar o JFLAP.

\vspace*{3mm}
\begin{enumerate}
 \item Sobre conjuntos enumer\' aveis:\footnote{Veja a Se\c{c}\~ao 1.6, p\'ag. 23, do
       livro-texto.}
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que o conjunto de n\'umeros inteiros \'{\i}mpares \' e enumer\'avel.
        \item Prove que o conjunto $\{{\tt 0}\}^*$ \' e enumer\'avel.
        \item Prove que o conjunto ${\cal P}(\{{\tt 0}\}^*)$ n\~ao \'e enumer\'avel.
       \end{list}

 \item Fa\c ca defini\c c\~oes recursivas tradicionais (sem uso de gram\'atica)
       para as linguagens:\footnote{Veja a Se\c{c}\~ao 1.7, p\'ag. 28, do
       livro-texto.}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}^*\{{\tt 1}\}^*$
        \item $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w$ n\~ao cont\'em {\tt 00} nem {\tt 11}$\}$
       \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. N\~ao precisa
       dizer que a palavra deve conter apenas {\tt 0}s e {\tt 1}s (fica
       impl\'{\i}cito).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A\cap B$.
        \item $AB$.
        \item $B-A$.
        \item $A^*$.
        \item $B^+$.
        \item $A^*\cap B^*$.
       \end{list}
       Exemplo: uma propriedade necess\'aria e suficiente para que uma palavra
       perten\c{c}a a $A-B$ \'e: come\c{c}a com {\tt 1} e tem 5 s\'{\i}mbolos.

 \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$ \'e par
              e $n$ \'e \'{\i}mpar.
        \item O conjunto das palavras em que entre cada par de {\tt 0}s
              h\'a uma subpalavra ${\tt 1}^n$, sendo $n$ par.
              Observe que antes do primeiro {\tt 0} ou ap\'os o \'ultimo
              {\tt 0} pode ocorrer um n\'umero \'{\i}mpar de {\tt 1}s, \textit{se a palavra
              tiver {\tt 0}s}.
        \item O conjunto das palavras que cont\^em {\tt 00} ou {\tt 11} ou ambas.
        \item O conjunto das palavras que cont\^em {\tt 00} ou {\tt 11}, mas n\~ao ambas.
        \item O conjunto das palavras que cont\^em {\tt 00} e {\tt 11}.
        \item O conjunto das palavras que cont\^em {\tt 00}, mas n\~ao {\tt 11}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}, nem {\tt 11}.
        \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 nas quais o n\'umero de {\tt 1}'s \'e m\'ultiplo
              de 3, exceto aquelas com um n\'umero par de s\'{\i}mbolos.
       \end{list}

 \item Identifique as linguagens que s\~ao geradas pelas gram\'aticas a seguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{P,Z\},\{{\tt 0},{\tt 1}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt 0}P{\tt 1} \,|\, Z$
               \item[\ ]      $Z\,\rightarrow\,{\tt 0}Z\,|\, {\tt 0}$
              \end{enumerate}

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

        \item $G_3=(\{S,X\},\{{\tt 0},{\tt 1}\},R_3,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_4=(\{P,X\},\{{\tt a},{\tt b},{\tt c}\},R_4,P)$.
              \begin{enumerate}
               \item[$R_4$:] $P\,\rightarrow\,{\tt a} P {\tt a} \,|\, X$
               \item[\ ]   $X\,\rightarrow\, {\tt b} X {\tt c} \,|\, X {\tt c} \,|\, \lambda$
              \end{enumerate}

        \item $G_5=(\{P,A,B,F\},\{{\tt a},{\tt b}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:] $P\,\rightarrow\,{\tt a}AP \,|\,{\tt b}BP\,|\,F$ 
               \item[\ ]  $A{\tt a}\,\rightarrow\,{\tt a}A$
               \item[\ ]  $A{\tt b}\,\rightarrow\,{\tt b}A$
               \item[\ ]  $B{\tt a}\,\rightarrow\,{\tt a}B$
               \item[\ ]  $B{\tt b}\,\rightarrow\,{\tt b}B$
               \item[\ ]  $AF\,\rightarrow\,F{\tt a}$
               \item[\ ]  $BF\,\rightarrow\,F{\tt b}$
               \item[\ ]  $F\,\rightarrow\,\lambda$
              \end{enumerate}

        \item $G_6=(\{P\},\{{\tt 0},{\tt 1}\},R_6,P)$.
              \begin{enumerate}
               \item[$R_6$:] $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 0}\}\{{\tt 11}\}^*\{{\tt 0}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt \#}\}^*\,|\, \mbox{ toda seq\"u\^encia de
               {\tt 0}'s em $w$ vem entre dois {\tt \#}s}\}$.
        \item O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ de tamanho par
              com pelo menos dois {\tt 1}s.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\not=n\}$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFDs) que reconhe\c cam
       as linguagens da quest\~ao 3. Apresente apenas os diagramas de estados.

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFDs) que reconhe\c cam
       as linguagens da quest\~ao 4. Apresente apenas os diagramas de estados.

 \item Construa AFDs 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 par
              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 $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o pen\'ultimo s\'{\i}mbolo
              de $w$ \'e {\tt 1}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ n\~ao cont\'em {\tt 000}
                 nem {\tt 111}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ em $w$ o s\'{\i}mbolo da
               posi\c{c}\~ao $2i$ \'e diferente daquele na posi\c{c}\~ao $2i+2$
               para cada $i\geq 1\}$. Exemplos de palavras nesta linguagem: qualquer
               palavra com menos de 4 s\'{\i}mbolos, as 4 palavras da forma {\tt a0b1},
               onde a e b podem ser {\tt 0} ou {\tt 1}, as 4 palavras da forma
               {\tt a1b0} etc.
       \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:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X\cap Y$.
        \item $X\cup Y$.
        \item $X-Y$.
       \end{list}
\end{enumerate}

\end{document}
