\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 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: 15/04/04

\begin{enumerate}
 \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 a linguagem vazia $\emptyset$ n\~ao \'e a mesma que $\{\lambda\}$?
        \item Seja $L=\{\lambda,{\tt a}\}$. Quantas palavras tem $L^n$ para cada
              $n\geq 0$? Que palavras s\~ao essas?
        \item Sejam $A=\{{\tt a}\}$ e $A=\{{\tt b}\}$. Determine $A^nB$, $AB^n$ e
              $(AB)^n$.
        \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 Mostre que para quaisquer linguagens $A$ e $B$ $(AB)^R=B^RA^R$. Observe
       que, por defini\c c\~ao, $X^R=\{w^R\,|\,w\in X\}$. Na demonstra\c c\~ao
       voc\^e pode usar o fato de que $(xy)^R=y^Rx^R$ para quaisquer palavras
       $x$ e $y$.

 \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 com, no m\'{\i}nimo, dois  {\tt 0}'s.
        \item O conjunto das palavras com, no m\'aximo, quatro {\tt 0}'s.
        \item O conjunto das palavras de tamanho m\'ultiplo de 3.
        \item O conjunto das palavras com um n\'umero de {\tt 0}'s m\'ultiplo de 3.
        \item O conjunto das palavras que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras com um n\'umero de {\tt 0}'s m\'ultiplo de 3,
              que n\~ao cont\^em {\tt 00}.
        \item O conjunto das palavras de tamanho \'{\i}mpar que cont\^em pelo menos
              um {\tt 0}.
        \item O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de
              1's (ou ambos).
       \end{list}

 \item Que linguagens s\~ao geradas pelas gram\'aticas a seguir? Descreva-as
       formalmente. 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 A$
               \item[\ ]     $A\,\rightarrow\,{\tt 0}A\,|\, {\tt 0}$
               \item[\ ]     $B\,\rightarrow\,{\tt 1}B\,|\, \lambda$
              \end{enumerate}

\pagebreak
        \item $G_2=(\{Z,U\},\{{\tt 0},{\tt 1}\},R_2,Z)$.
              \begin{enumerate}
               \item[$R_2$:] $Z\,\rightarrow\,{\tt 0} Z \,|\, {\tt 1}U$
               \item[\ ]     $U\,\rightarrow\,{\tt 0} Z \,|\, {\tt 1}U\,|\, \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 01} X \,|\, \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 O conjunto das palavras sobre $\{{\tt 0},{\tt 1}\}$ em que cada {\tt 0}
              ocorre entre dois {\tt 1}'s.
        \item $\{{\tt 01}\}^*\{{\tt 1},{\tt 10}\}^*$.
        \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 a},{\tt b}\}^*\,|\, w \mbox{ tem n\'umero par de }
                    {\tt ab}\mbox{'s e \'{\i}mpar de {\tt b}'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=(\{X,Y,Z\},\{{\tt 0},{\tt 1}\},\delta_1,X,\{Z\})$, onde $\delta_1$
              \'e dada por:

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

              \begin{tabular}{c|cc}
               $\delta_2$ & {\tt 0} & {\tt 1} \\ \hline
                  $R$ & $S$ & $S$ \\
                  $S$ & $R$ & $R$
              \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_2)-L(M_1)$, ou seja,
              $L(M_2)\cap\overline{L(M_1)}$.
       \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\'u\-me\-ro de estados de $M$, ent\~ao $L(M)$ \'e infinita.
       \end{list}

 \item Mostre que a linguagem $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{enumerate}

\end{document}
