\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas ne-nhum}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG \\
\noindent {\it Fundamentos Te\'oricos da Computa\c c\~ao}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova/Solu\c c\~ao do professor} \hfill Data: 28/09/2000


\begin{enumerate}
 \item {\footnotesize Responda sem justificar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sejam $A=\{\lambda,\verb+a+\}$ e $B=\{\verb+a+,\verb+b+\}$. Quantos elementos tem
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $A^nB$
               \item $AB^n$
               \item $A^nB^n$
              \end{list}
              para $n\geq 0$ arbitr\'ario?
        \item Simplifique:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $(A^*)^+$
               \item $(A^+)^*$
               \item $A^*\cap A^+$
               \item $A^*A^+$
               \item $A^+-A^*$
               \item $A^*-A^+$
              \end{list}
       \end{list}}


       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $|A^nB|=2(n+1)$
               \item $|AB^n|=2^{n+1}$
               \item $|A^nB^n|=(n+1)2^{n}$
              \end{list}

        \item 
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $(A^*)^+=A^*$
               \item $(A^+)^*=A^*$
               \item $A^*\cap A^+=A^+$
               \item $A^*A^+=A^+$
               \item $A^+-A^*=\emptyset$
               \item $A^*-A^+=\emptyset$, se $\lambda\in A$; e $A^*-A^+=\{\lambda\}$,
                     se $\lambda\not\in A$. 
              \end{list}
       \end{list}

 \item {\footnotesize Descreva as seguintes linguagens sobre o alfabeto $\{\verb+0+,\verb+1+\}$, usando apenas as
       opera\c c\~oes de {\em concatena\c c\~ao\/}, {\em uni\~ao\/} e/ou {\em fecho de Kleene\/}
       aplicadas a conjuntos finitos espec\'{\i}ficos de palavras de $\{\verb+0+,\verb+1+\}^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item o conjunto das palavras com, no m\'aximo, um \verb+0+;
        \item o conjunto das palavras com n\'umero \'{\i}mpar de \verb+0+'s;
        \item o conjunto das palavras cujo antepen\'ultimo s\'{\i}mbolo \'e \verb+0+, {\em caso este
              exista\/}.
       \end{list}}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+1+\}^*\{\lambda,\verb+0+\}\{\verb+1+\}^*$
        \item $\{\verb+1+\}^*(\{\verb+0+\}\{\verb+1+\}^*\{\verb+0+\}\{\verb+1+\}^*)^*
               \{\verb+0+\}\{\verb+1+\}^*$
        \item $\{\verb+0+,\verb+1+\}^*\{\verb+0+\}\{\verb+0+,\verb+1+\}\{\verb+0+,\verb+1+\}
               \cup\{\lambda,\verb+0+,\verb+1+\}\{\lambda,\verb+0+,\verb+1+\}$
       \end{list}


 \item {\footnotesize Seja $\Sigma=\{\verb+a+\}$. Mostre que o conjunto $\Sigma^*$ \'e enumer\'avel, e que
       o conjunto  ${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel.}

       \begin{description}
        \item[$\Sigma^*$ \'e enumer\'avel.]
              Seja a fun\c c\~ao $f:\Sigma^*\rightarrow\mbox{\bf N}$ tal que $f(\verb+a+^n)=n$ para
              todo $n\in\mbox{\bf N}$. Como $f$ \'e bijetiva (com inversa
              $f^{-1}:\mbox{\bf N}\rightarrow\Sigma^*$ tal que $f(n)=\verb+a+^n$), segue-se que
              $\Sigma^*$ \'e enumer\'avel.
        \item[${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel.]
              Suponha que ${\cal P}(\Sigma^*)$ \'e enumer\'avel. Ent\~ao existe uma fun\c c\~ao
              bijetiva de ${\cal P}(\Sigma^*)$ para {\bf N}, de forma que os elementos de
              ${\cal P}(\Sigma^*)$ podem ser enumerados: $A_0,A_1,A_2,\ldots$. Seja o conjunto
              $B=\{\verb+a+^n\in\Sigma^*\,\,|\,\,a^n\not\in A_n\}$. Mas $B\not=A_i$ para qualquer
              $i\in\mbox{\bf N}$, j\'a que $\verb+a+^i\in B$ se, e somente se, $\verb+a+^i\not\in A_i$.
              Logo, a suposi\c c\~ao de que existe a enumera\c c\~ao $A_0,A_1,A_2,\ldots$ n\~ao \'e
              correta, ou seja, ${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel.
       \end{description}

 \item {\footnotesize Sejam $L_1$ e $L_2$ linguagens sobre um certo alfabeto $\Sigma$ tais que
       $L_1\subseteq L_2$. Prove que $L_1^*\subseteq L_2^*$.}

       Ser\'a feita uma prova por indu\c c\~ao forte sobre o tamanho das palavras $w$ de $\Sigma^*$ que
       se $w\in L_1^*$ ent\~ao $w\in L_2^*$. Para isto, suponha, como hip\'otese,
       que se $w\in L_1^*$ ent\~ao $w\in L_2^*$ para toda palavra $w\in\Sigma^*$ de tamanho menor
       que $n$. Ser\'a provado que o mesmo resultado vale para toda palavra $w$ de tamanho $n$. Tem-se
       dois casos a considerar:
       \begin{enumerate}
        \item[$|w|=0$.] Neste caso $w=\lambda$. E $\lambda\in L_2^*$, por defini\c c\~ao de fecho
                     de Kleene.
        \item[$|w|\not=0$.] Suponha que $w\in L_1^*$. Neste caso, $w=xy$ para $x\in L_1^*$ e $y\in L_1$,
                     $y\not=\lambda$. Como $|x|<n$, $x\in L_2^*$, pela hip\'otese de indu\c c\~ao. E como
                     $y\in L_1$ e $L_1\subseteq L_2$, $y\in L_2$. Assim, pela defini\c c\~ao de fecho
                     de Kleene, $xy\in L_2^*$.
       \end{enumerate}

 \item {\footnotesize Construa gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, \mbox{ $w$ n\~ao cont\'em a subpalavra 
              $\verb+a+\verb+b+$}\}$
        \item $\{\verb+a+^n\verb+b+^n\verb+c+^k\,\,|\,\, 0\leq n<k\}$
       \end{list}
       Para a gram\'atica do item (a), quantos passos s\~ao necess\'arios para gerar uma palavra de
       tamanho $n$?}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, \mbox{ $w$ n\~ao cont\'em a subpalavra 
              $\verb+a+\verb+b+$}\}$
              \begin{enumerate}
               \item[\ \ ] $P\,\,\rightarrow\,\, \verb+a+ A \,\,|\,\, \verb+b+ P \,\,|\,\, \lambda$ \\
                           $A\,\,\rightarrow\,\, \verb+a+ A \,\,|\,\, \lambda$ 
              \end{enumerate}
        \item $\{\verb+a+^n\verb+b+^n\verb+c+^k\,\,|\,\, 0\leq n<k\}$
              \begin{enumerate}
               \item[\ \ ] $P\,\,\rightarrow\,\, A S$ \\
                           $A\,\,\rightarrow\,\, \verb+a+ B \verb+b+ \verb+c+ \,\,|\,\, \lambda$  \\
                           $B\,\,\rightarrow\,\, \verb+a+ B \verb+b+ C \,\,|\,\, \lambda$  \\
                           $C \verb+b+\,\,\rightarrow\,\, \verb+b+ C$  \\
                           $C \verb+c+\,\,\rightarrow\,\, \verb+c+ \verb+c+$  \\
                           $S \,\,\rightarrow\,\, \verb+c+ S \,\,|\,\, \verb+c+$
              \end{enumerate}
       \end{list}
       Seguem esquemas de deriva\c c\~ao para todas as palavras geradas pela gram\'atica do item (a).
       Eles mostram que s\~ao necess\'arios $n+1$ passos para gerar uma palavra de tamanho $n$:
       \begin{tabbing}
        $P\,\,$\=$\stackrel{n}{\Rightarrow}\,\, \verb+b+^n P$ \ \ \ \ \=(regra $P \,\rightarrow\, \verb+b+ P$ $n$
                   vezes, $n\geq 0$) \\
                \>$\Rightarrow\,\, \verb+b+^n$ \>(regra $P \,\rightarrow\, \lambda$)
       \end{tabbing}

       \begin{tabbing}
        $P\,\,$\=$\stackrel{i}{\Rightarrow}\,\, \verb+b+^i P$ \ \ \ \ \=(regra $P\,\rightarrow\, \verb+b+ P$ $i$ vezes,
                   $i\geq 0$) \\
                \>$\Rightarrow\,\, \verb+b+^i\verb+a+ A$ \>(regra $P\,\rightarrow\, \verb+a+ A$) \\
                \>$\stackrel{j}{\Rightarrow}\,\, \verb+b+^i\verb+a+\verb+a+^j A$ 
                  \>(regra $A\,\rightarrow\,\verb+a+ A$ $j$ vezes, $j\geq 0$) \\
                \>$\Rightarrow\,\, \verb+b+^i\verb+a+\verb+a+^j$ 
                  \>(regra $A\,\rightarrow\,\lambda$)
       \end{tabbing}
       Observe que, neste \'ultimo caso, $n=i+j+1$.

       Uma solu\c c\~ao mais concisa: cada regra da gram\'atica \'e da forma $X\rightarrow aY$, onde $a$ \'e
       um terminal e $X$ e $Y$ s\~ao vari\'aveis, ou ent\~ao da forma $X\rightarrow\lambda$.
       Para gerar uma palavra de tamanho $n$, s\~ao aplicadas $n$ regras do tipo $X\rightarrow aY$ e, em
       seguida, para terminar a deriva\c c\~ao, uma regra do tipo $X\rightarrow\lambda$. Logo, s\~ao
       necess\'arios $n+1$ passos para gerar uma palavra de tamanho $n$.

 \item {\footnotesize Construa AFD's para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+01+\}^*\{\verb+10+\}^*$
        \item $\{a^kb^n\,\,|\,\, k+n\geq 2\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,|w|\leq 1 \mbox{ ou o pen\'ultimo s\'{\i}mbolo de $w$
               \'e \verb+0+}\}$
        \end{list}}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{0,1,2,3,\mbox{e}\},\{\verb+0+,\verb+1+\},\delta,0,\{0,3\})$, onde $\delta$ \'e dada por:

              \begin{tabular}{c|cc}
               $\delta$ & \verb+0+ & \verb+1+ \\ \hline
                      0 & 1 & 2 \\
                      1 & e & 0 \\
                      2 & 3 & e \\
                      3 & e & 2 \\
                      e & e & e
              \end{tabular}
        \item $(\{0,1,2,3,4,\mbox{e}\},\{\verb+a+,\verb+b+\},\delta,0,\{3,4\})$, onde $\delta$ \'e dada por:

              \begin{tabular}{c|cc}
               $\delta$ & \verb+a+ & \verb+b+ \\ \hline
                      0 & 1 & 2 \\
                      1 & 3 & 4 \\
                      2 & e & 4 \\
                      3 & 3 & 4 \\
                      4 & e & 4 \\
                      e & e & e
              \end{tabular}
        \item $(\{0,1,00,01,10,11\},\{\verb+0+,\verb+1+\},\delta,0,\{0,1,00,01\})$, onde $\delta$ \'e dada por:

              \begin{tabular}{c|cc}
               $\delta$ & \verb+0+ & \verb+1+ \\ \hline
                      0 & 00 & 1 \\
                      1 & 10 & 11 \\
                     00 & 00 & 01 \\
                     01 & 10 & 11 \\
                     10 & 00 & 01 \\
                     11 & 10 & 11
              \end{tabular}

        \end{list}


\item {\footnotesize Seja um AFD $M=(E,\Sigma,\delta,i,F)$. Um {\em aut\^omato reduzido\/} correspondente
      a $M$ \'e o AFD $M'=(E',\Sigma,\delta',i',F')$, onde:
      \begin{itemize}
       \item $E'=\{[e]\,\,|\,\, e\in E\}$;
       \item $\delta'([e],a)=[\delta(e,a)]$ para todo $(e,a)\in E\times\Sigma$;
       \item $i'=[i]$; e
       \item $F'=\{[e]\,\,|\,\, e\in F\}$.
      \end{itemize}
      Prove que $\hat{\delta'}([e],w)=[\hat{\delta}(e,w)]$ para todo $e\in E$ e $w\in\Sigma^*$.}

      Por indu\c c\~ao sobre $|w|$, para $w\in\Sigma^*$. Para $|w|=0$, tem-se $w=\lambda$ e
      \begin{tabbing}
       $\hat{\delta'}([e],\lambda)$\=$=[\hat{\delta}(e,\lambda)]$, \ \=pela \kill
       $\hat{\delta'}([e],\lambda)$\>$=[e]$, \>pela defini\c c\~ao de $\hat{\delta'}$ \\
                                   \>$=[\hat{\delta}(e,\lambda)]$, \>pela defini\c c\~ao de $\hat{\delta}$.
      \end{tabbing}
      Hip\'otese de indu\c c\~ao: $\hat{\delta'}([e],w)=[\hat{\delta}(e,w)]$ para todo $w\in\Sigma^*$ de
      tamanho $n$. Seja, ent\~ao, uma palavra $ay$ tal que $a\in\Sigma$ e $y\in\Sigma^*$, $y$ de 
      tamanho $n$. Tem-se:
      \begin{tabbing}
       $\hat{\delta'}([e],ay)$\=$=[\hat{\delta'}(\delta([e],a),y)]$,\ \= pela \kill
       $\hat{\delta'}([e],ay)$\>$=\hat{\delta'}(\delta'([e],a),y)$,\> pela defini\c c\~ao de $\hat{\delta'}$ \\
                              \>$=\hat{\delta'}([\delta([e],a)],y)$, \>pela defini\c c\~ao de $\delta'$ \\
                              \>$=[\hat{\delta}(\delta([e],a),y)]$, \>pela hip\a'otese de indu\c c\~ao \\
                                   \>$=[\hat{\delta}(e,ay)]$, \>pela defini\c c\~ao de $\hat{\delta}$.
      \end{tabbing}

\end{enumerate}

\end{document}
 
