\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2000 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Solu\c c\~ao da Primeira Prova} \hfill 13/04/2000

\begin{enumerate}
 \item Expresse as seguintes linguagens, utilizando opera\c c\~oes sobre conjuntos finitos de
       palavras de $\{\verb+0+,\verb+1+\}^*$:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que cont\^em o s\'{\i}mbolo \verb+1+.

                {\bf Resposta:} $\{\verb+0+,\verb+1+\}^*\{\verb+1+\}\{\verb+0+,\verb+1+\}^*$.
                
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que come\c cam com \verb+0+ e terminam com \verb+1+.

                {\bf Resposta:} $\{\verb+0+\}\{\verb+0+,\verb+1+\}^*\{\verb+1+\}$.
 
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ com um n\'umero par de \verb+0+'s.

                {\bf Resposta:} $\{\verb+1+\}^*(\{\verb+0+\}\{\verb+1+\}^*\{\verb+0+\}
                 \{\verb+1+\}^*)^*$.

        \end{list}
    
 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item Fa\c ca uma defini\c c\~ao recursiva da linguagem $\{\verb+ab+\}^*\{\verb+ba+\}^*$.

               {\bf Resposta:}
               
               A linguagem $L=\{\verb+ab+\}^*\{\verb+ba+\}^*$ pode ser definida
              {\em recursivamente\/} como segue:
              \begin{list}{(\alph{conta}.\arabic{conta2})}{\usecounter{conta2}}
               \item $\lambda \in L$;
               \item se $x \in L$ ent\~ao $\verb+ab+x \in L$ e $x\verb+ba+ \in L$.
              \end{list}    

         \item Construa uma gram\'atica que gere a linguagem $\{\verb+ab+\}^*\{\verb+ba+\}^*$.

               {\bf Resposta:}
               
               $P\,\rightarrow\,\, \lambda \,\,|\,\, \verb+ab+ P \,\,|\,\, P\verb+ba+$

         \item Em quantos passos \'e derivada uma palavra de tamanho $n$, para a gram\'atica constru\'{\i}da?

               {\bf Resposta:} As deriva\c c\~oes s\~ao da forma:
               
               \begin{tabbing}
                $P$ \=$\stackrel{i+j}{\Rightarrow}(\verb+ab+)^i P (\verb+ba+)^j$ ($i,j\geq 0$) \\
                    \>$\Rightarrow (\verb+ab+)^i (\verb+ba+)^j$
               \end{tabbing}

               Como $n=2(i+j)$, s\~ao necess\'arios $i+j+1=(n/2)+1$ passos.
        \end{list}
               
 \item Construa aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam:
        \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+ab+\}^*$
    
                {\bf Resposta:}  
                 
                $(\{e_1,e_2,e_3\},\{\verb+a+,\verb+b+\},\delta_1,e_1,\{e_1\})$, onde
                $\delta_1$ \'e dada por:
                \begin{center}
                \begin{tabular}{c|cc}
                 $\delta_1$ & \verb+a+ & \verb+b+ \\ \hline
                 $e_1$ & $e_2$ & $e_3$ \\
                 $e_2$ & $e_3$ & $e_1$ \\
                 $e_3$ & $e_3$ & $e_3$
                \end{tabular}
                \end{center}

          \item $\{\verb+ab+\}^*\{\verb+ba+\}^*$
       
                {\bf Resposta:}
                
                 $(\{e_1,e_2,e_3,e_4,e_5\},\{\verb+a+,\verb+b+\},\delta_2,e_1,
                \{e_1,e_4\})$, onde $\delta_2$ \'e dada por:
                \begin{center}
                \begin{tabular}{c|cc}
                 $\delta_2$ & \verb+a+ & \verb+b+ \\ \hline
                 $e_1$ & $e_2$ & $e_3$ \\
                 $e_2$ & $e_5$ & $e_1$ \\
                 $e_3$ & $e_4$ & $e_5$ \\
                 $e_4$ & $e_5$ & $e_3$ \\
                 $e_5$ & $e_5$ & $e_5$
                \end{tabular}
                \end{center}
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, \mbox{$w$ n\~ao come\c ca com 00 nem termina com 11}\}$
     
                {\bf Resposta:}
                
                $(\{e_1,e_2,e_3,e_4,e_5,e_6\},\{\verb+0+,\verb+1+\},\delta_3,e_1,
                \{e_1,e_2,e_3,e_4\})$, onde $\delta_3$ \'e dada por:
                \begin{center}
                \begin{tabular}{c|cc}
                 $\delta_3$ & \verb+0+ & \verb+1+ \\ \hline
                 $e_1$ & $e_2$ & $e_3$ \\
                 $e_2$ & $e_6$ & $e_3$ \\
                 $e_3$ & $e_4$ & $e_5$ \\
                 $e_4$ & $e_4$ & $e_3$ \\
                 $e_5$ & $e_4$ & $e_5$ \\
                 $e_6$ & $e_6$ & $e_6$
                \end{tabular}
                \end{center}
         \end{list}

 \item Seja um aut\^omato finito determin\'{\i}stico com fun\c c\~ao de transi\c c\~ao $\delta$ e alfabeto $\Sigma$. Prove que
        $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$ para todas as palavras $x,y\in\Sigma^*$.
     
        {\bf Resposta:}

        A prova ser\'a feita por indu\c c\~ao sobre $|x|$. Assim, seja $|x|=0$, ou seja $x=\lambda$; tem-se:

        \begin{tabbing}
         $\hat{\delta}(\hat{\delta}(e,\lambda),y)$\=$=\hat{\delta}(e,y)$, pela defini\c c\~ao de $\hat{\delta}$, \\
              \>$=\hat{\delta}(e,\lambda y)$, pois $\lambda y=y$.
        \end{tabbing}
        Suponha, como hip\'otese de indu\c c\~ao, que
        $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$ para toda palavra
        $x$ de tamanho $n$, para $n\geq 0$ arbitr\'ario. Seja, ent\~ao, uma
        palavra $w$ de tamanho $n+1$, ou seja, uma palavra $w=az$, onde $a\in\Sigma$
        e $z\in\Sigma^*$ (observe que $|z|=n$). Tem-se:
        \begin{tabbing}
         $\hat{\delta}(\hat{\delta}(e,az),y)$\=$=\hat{\delta}(\hat{\delta}(\delta(e,a),z),y)$,
                pela defini\c c\~ao de $\hat{\delta}$, \\
           \>$=\hat{\delta}(\delta(e,a),zy)$, pela hip\a'otese de indu\c c\~ao, \\
           \>$=\hat{\delta}(e,a(zy))$, pela defini\c c\~ao de $\hat{\delta}$, \\
           \>$=\hat{\delta}(e,(az)y)$, pois $a(zy)=(az)y$. \\
        \end{tabbing}
        Conclui-se que $\hat{\delta}(e,xy)=\hat{\delta}(\hat{\delta}(e,x),y)$ para palavras $x$ de
        todo tamanho.

 \item Mostre que a linguagem $\{\verb+0+^n\verb+1+^{584}\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$ n\~ao pode ser reconhecida
       por aut\^omato finito determin\'{\i}stico.

       {\bf Resposta:}

       Seja $L$ a linguagem em quest\~ao, e seja um AFD de $k$ estados que aceite L. Seja a
       palavra $z=\verb+0+^k\verb+1+^{584}\verb+0+^k\in L$. Como $|z|>k$, $z$ \'e tal que:
       \begin{itemize}
        \item $z=uvw$;
        \item $v\not=\lambda$; e
        \item $uv^iw\in L$ para todo $i\geq 0$.
       \end{itemize}
       ($v$ seria uma subpalavra consumida em um ciclo do AFD.)
       Mas, $uv^0w\not\in L$, pois a retirada de uma subpalavra (diferente de $\lambda$) de $z$, d\'a como
       resultado uma palavra que n\~ao \'e da forma $\verb+0+^n\verb+1+^{584}\verb+1+^n$.
       Logo, a suposi\c c\~ao de existe um AFD que aceita $L$ \'e incorreta.

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFD $M_1$ para o conjunto das palavras com n\'umero par de \verb+0+'s.

              {\bf Resposta:}

              $M_1=(\{p,i\},\{\verb+0+,\verb+1+\},\delta_1,p,\{p\})$, onde $\delta_1$ \'e dada por:
              \begin{center}
                \begin{tabular}{c|cc}
                 $\delta_1$ & \verb+0+ & \verb+1+ \\ \hline
                 $p$ & $i$ & $p$ \\
                 $i$ & $p$ & $i$
                \end{tabular}
              \end{center}

        \item Construa um AFD $M_2$ para o conjunto das palavras que n\~ao cont\^em \verb+11+.

              {\bf Resposta:}

              $M_2=(\{0,1,e\},\{\verb+0+,\verb+1+\},\delta_2,0,\{0,1\})$, onde
                $\delta_2$ \'e dada por:
              \begin{center}
                \begin{tabular}{c|cc}
                 $\delta_2$ & \verb+0+ & \verb+1+ \\ \hline
                 $0$ & $0$ & $1$ \\
                 $1$ & $0$ & $e$ \\
                 $e$ & $e$ & $e$ 
                \end{tabular}
               \end{center}
                
        \item Construa um AFD $M_3$ para $L(M_1)\cap L(M_2)$ usando a t\'ecnica da simula\c c\~ao de $M_1$ e $M_2$
              em paralelo (aquela t\'ecnica em que o conjunto de estados de $M_3$ \'e o produto cartesiano dos conjuntos de
              estados de $M_1$ e $M_2$).

              {\bf Resposta:}

           $M_3=(\{[p,0],[p,1],[p,e],[i,0],[i,1],[i,e]\},\{\verb+0+,\verb+1+\},\delta_3,
                 [p,0],\{[p,0],[p,1]\})$, onde $\delta_3$ \'e dada por:
              \begin{center}
                \begin{tabular}{c|cc}
                 $\delta_3$ & \verb+0+ & \verb+1+ \\ \hline
                 $[p,0]$ & $[i,0]$ & $[p,1]$ \\
                 $[p,1]$ & $[i,0]$ & $[p,e]$ \\
                 $[p,e]$ & $[i,e]$ & $[p,e]$ \\
                 $[i,0]$ & $[p,0]$ & $[i,1]$ \\
                 $[i,1]$ & $[p,0]$ & $[i,e]$ \\
                 $[i,e]$ & $[p,e]$ & $[i,e]$ \\
                \end{tabular}
              \end{center}

         \end{list}

\end{enumerate}
\end{document}



