\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{1}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill
          {\bf Entrega: 27/03/2007}

\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 Sejam $\Sigma=\{{\tt 0}\}$ e $\Delta=\{{\tt 1}\}$.\footnote{Veja a
       Se\c{c}\~ao 1.6, p\'ag. 23, do livro-texto.}
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que $\Sigma^*$ \' e enumer\'avel.
        \item Prove que $\Sigma^*\Delta^*$ \' e enumer\'avel.
        \item Prove que o conjunto ${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel.
              ${\cal P}(X)$ \'e o \textit{conjunto pot\^encia\/} de $X$.
       \end{list}

 \item Defina as no\c c\~oes de prefixo, sufixo e subpalavra de uma palavra no
       alfabeto $\Sigma$, de uma maneira mais formal do que est\'a na apostila
       (na forma ``$x$ \'e um {\em prefixo\/} de $w$ se, e somente se, \ldots'' etc.).

 \item Perguntinhas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Por que $\emptyset\not=\{\lambda\}$?
        \item Seja $L=\{\lambda,{\tt a},{\tt b}\}$. Quantas palavras tem $L^n$ para cada
              $n\geq 0$? Que palavras s\~ao essas?
        \item Sejam $\Sigma=\{{\tt a},{\tt b}\}$,  $A=\{{\tt a}\}\Sigma^*$ e
              $B=\Sigma^+\{{\tt b}\}$. Descreva $A\cap B$, $A-B$ e $B^*$.
        \item Sob quais condi\c c\~oes $L^*=L^+$?
        \item Encontre linguagens $A$, $B$ e $C$ para as quais $A(B-C)\not=AB-AC$.
       \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$ \'e par e $n$ \'e \'{\i}mpar.
        \item O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de
              1's (ou ambos).
        \item O conjunto das palavras com, no m\'{\i}nimo, dois  {\tt 0}'s.
        \item O conjunto das palavras com, no m\'{a}ximo, dois s\'{\i}mbolos.
        \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}, mas n\~ao {\tt 11}.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}, nem {\tt 11}.
       \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\},\{{\tt 0},{\tt 1}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt 0}P\,|\, P {\tt 1} \,|\, \lambda$
              \end{enumerate}

        \item $G_2=(\{P,A,B\},\{{\tt a},{\tt b}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:]  $P\,\rightarrow\,{\tt a}P{\tt b} \,|\, A \,|\, B$
               \item[\ ]      $A\,\rightarrow\,{\tt a}A\,|\, {\tt a}$
               \item[\ ]      $B\,\rightarrow\,{\tt b}B\,|\, {\tt b}$
              \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} \,|\, {\tt b} P {\tt b}
                                            \,|\, X$
               \item[\ ]   $X\,\rightarrow\, X {\tt c} \,|\, {\tt c}$
              \end{enumerate}

        \item $G_5=(\{P,A,F\},\{{\tt a},{\tt b}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:] $P\,\rightarrow\,{\tt a}AP \,|\,F$ 
               \item[\ ]  $A{\tt a}\,\rightarrow\,{\tt a}A$
               \item[\ ]  $A{\tt b}\,\rightarrow\,{\tt b}A$
               \item[\ ]  $AF\,\rightarrow\,{\tt b}F{\tt a}$
               \item[\ ]  $F\,\rightarrow\,\lambda$
              \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 $\{01\}^*\{10\}^*$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o n\'umero de {\tt a}'s em
                   $w$ \'e par}\}$.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\not=n\}$.
        \item $\{{\tt a}^m{\tt b}^{m+n}{\tt c}^n\,|\, m,n\geq 0\}$.
       \end{list}

 \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 $\{{\tt 1},{ \tt 01}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ cada {\tt 0} de $w$ \'e imediatamente
              seguido de, no m\'{\i}nimo, dois {\tt 1}s$\}$.
        \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 tr\^es s\'{\i}mbolos
                 id\^enticos consecutivos}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ os tr\^es \'ultimos s\'{\i}mbolos
                 de $w$ n\~ao s\~ao {\tt 000}}\}$.
        \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\{{\tt 0},{\tt 1}\}^*\,|\,$ em $w$ o s\'{\i}mbolo da
               posi\c{c}\~ao $2i-1$ \'e diferente daquele na posi\c{c}\~ao $2i$
               para cada $i\geq 1\}$.
       \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}

 \item Explique:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se para um estado $e$ e uma palavra $x$, $\hat{\delta}(e,x)=e$,
              ent\~ao $\hat{\delta}(e,x^n)=e$ para todo $n\geq 0$.
        \item Se um AFD $M$ reconhece uma palavra de tamanho igual ao n\'umero de
              estados de $M$, ent\~ao $L(M)$ \'e infinita.
        \item 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}$.)
        \item $L=\{{\tt a}^m{\tt b}^n\,|\, m<n\}$ n\~ao pode ser reconhecida por AFD.
              Por contradi\c c\~ao, comece supondo que $L$ pode
              ser reconhecida por um AFD de $k$ estados, e mostre que se o AFD
              reconhece a palavra ${\tt a}^k{\tt b}^{k+1}$ (j\'a que ela pertence a $L$),
              ent\~ao ele reconhece tamb\'em palavra que n\~ao pertence a $L$. (Observe
              que para ``ler'' um prefixo de $k$ s\'{\i}mbolos, o AFD passa por $k+1$
              estados...)
       \end{list}
\end{enumerate}

\end{document}
