\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\newcounter{conta3}
\begin{document} \footnotesize
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 1997
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent \underline{Solu\c c\~ao da S\'etima Lista de Exerc\'{\i}cios}

\begin{flushleft} \large\bf
 {Linguagens e Conjuntos Regulares}
\end{flushleft}

\begin{enumerate}
 \item {\it Use o corol\'{a}rio 7.5.2 de S88 para mostrar que os seguintes
       conjuntos n\~{a}o s\~{a}o regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos {\em strings\/} sobre $\{a,b\}$ com o mesmo n\'{u}mero
              de $a$'s e $b$'s.
        \item Conjunto dos pal\'{\i}ndromos sobre $\{a,b\}$ de tamanho par.
        \item Conjunto dos {\em strings\/} sobre $\{(,)\}$ nos quais cada ``(''
              tem um ``)'' correspondente.
        \item $\{a^i(ab)^j(ca)^{2i} \,\,\,|\,\,\, i,j>0\}$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $L$ o conjunto dos {\em strings\/} sobre $\{a,b\}$ com o mesmo
              n\'{u}mero de $a$'s e $b$'s. 
              Fazendo-se $u_i=a^i$ e $v_i=b^i$, tem-se que
              \[\left\{\begin{array}{ll}
                        u_iv_i\in L & \mbox{para todo $i\geq 0$,} \\
                        u_iv_j\not\in L & \mbox{para todo $i\not = j$.}
                       \end{array} \right.\]
              Logo, pelo lema 7.5.2,$L$ n\~ao \'e regular.
              
        \item Conjunto dos pal\'{\i}ndromos sobre $\{a,b\}$ de
              tamanho par. De forma similar ao item (a), basta fazer $u_i=a^ib$
              e $v_i=ba^i$ e aplicar o lema.
              
        \item Conjunto dos {\em strings\/} sobre $\{(,)\}$ nos quais cada ``(''
              tem um ``)'' correspondente. Tamb\'em de forma similar aos itens
              anteriores, basta fazer $u_i=(^i$ e $v_i=)^i$ e aplicar o lema.
              
        \item $\{a^i(ab)^j(ca)^{2i} \,\,\,|\,\,\, i,j>0\}$.
              Tamb\'em de forma similar aos itens anteriores, basta fazer
              $u_i=a^iaab$ e $v_i=caca(ca)^{2i}$ e aplicar o lema.
        
       \end{list}
      
 \item {\it Use o {\em pumping lemma\/} para mostrar que
       os seguintes conjuntos n\~{a}o s\~{a}o regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos pal\'{\i}ndromos sobre $\{a,b\}$.
        \item $\{a^nb^m \,\,\,|\,\,\, n<m\}$.
        \item $\{ww \,\,\,|\,\,\, w\in\{a,b\}^*\}$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $L$ o conjunto dos pal\'{\i}ndromos sobre $\{a,b\}$.
        
              Suponha que $L$ \'e regular. Seja um AFD de $k$ estados que
              reconhe\c ca $L$, e seja $z=a^kba^k$. Pelo {\em pumping lemma\/},
              $z$ pode ser escrito na forma $uvw$, onde $|uv|\leq k$, $|v|>0$ e
              $uv^iw\in L$ para todo $i\geq 0$. Mas,
              \[uv^0w=a^{k-|v|}ba^k\not\in L\mbox{,}\]
              contraditando o {\em pumping lemma\/}. Logo, a
              suposi\c c\~ao original de que $L$ \'e regular est\'a incorreta.
              
        \item $L=\{a^nb^m \,\,\,|\,\,\, n<m\}$.

              Suponha que $L$ \'e regular. Seja um AFD de $k$ estados que
              reconhe\c ca $L$, e seja $z=a^kb^{k+1}$. Pelo {\em pumping lemma\/},
              $z$ pode ser escrito na forma $uvw$, onde $|uv|\leq k$, $|v|>0$ e
              $uv^iw\in L$ para todo $i\geq 0$. Mas,
              \[uv^2w=a^{k+|v|}b^{k+1}\not\in L\mbox{,}\]
              contraditando o {\em pumping lemma\/}. Logo, a
              suposi\c c\~ao original de que $L$ \'e regular est\'a incorreta.
              
        \item $L=\{ww \,\,\,|\,\,\, w\in\{a,b\}^*\}$.

              Suponha que $L$ \'e regular. Seja um AFD de $k$ estados que
              reconhe\c ca $L$, e seja $z=a^kba^kb$. Pelo {\em pumping lemma\/},
              $z$ pode ser escrito na forma $uvw$, onde $|uv|\leq k$, $|v|>0$ e
              $uv^iw\in L$ para todo $i\geq 0$. Mas,
              \[uv^0w=a^{k-|v|}ba^kb\not\in L\mbox{,}\]
              o que contraria o {\em pumping lemma\/}. Logo, a
              suposi\c c\~ao original de que $L$ \'e regular est\'a incorreta.
              
       \end{list}
       
 \item {\it Seja $L$ uma linguagem regular sobre $\{a,b,c\}$.
       Mostre que cada um dos seguintes conjuntos \'{e} regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w \,\,\,|\,\,\, w\in L \mbox{ e } w \mbox{ cont\'{e}m algum $a$}\}$.
        \item $\{w \,\,\,|\,\,\, w\in L \mbox{ ou } w \mbox{ cont\'{e}m algum $a$}\}$.
        \item $\{w \,\,\,|\,\,\, w\not\in L \mbox{ e } w \mbox{ n\~{a}o cont\'{e}m
              $a$'s}\}$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $X=\{w \,\,\,|\,\,\, w\in L \mbox{ e } w \mbox{ cont\'{e}m algum $a$}\}$.

              $X=L\cap \mbox{\boldmath $b^*a(a\cup b)^*$}$. Como as linguagens
              regulares s\~ao fechadas sob interse\c c\~ao, $X$ \'e regular.

        \item $Y=\{w \,\,\,|\,\,\, w\in L \mbox{ ou } w \mbox{ cont\'{e}m algum $a$}\}$.

              $Y=L\cup \mbox{\boldmath $b^*a(a\cup b)^*$}$. Como as linguagens
              regulares s\~ao fechadas sob uni\~ao, $Y$ \'e regular.

        \item $Z=\{w \,\,\,|\,\,\, w\not\in L \mbox{ e } w \mbox{ n\~{a}o cont\'{e}m
              $a$'s}\}$.

              $Z=\overline{Y}$. Como as linguagens regulares s\~ao fechadas sob
              complementa\c c\~ao, $Z$ \'e regular.

       \end{list}

\item {\it Seja $L$ uma linguagem regular. Mostre que cada uma das
       seguintes linguagens \'{e} regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto $P=\{u \,\,\,|\,\,\, uv\in L\}$ dos prefixos de $L$.
        \item O conjunto $S=\{v \,\,\,|\,\,\, uv\in L\}$ dos sufixos de $L$.
        \item O conjunto $L^R=\{w^R \,\,\,|\,\,\, w\in L\}$ dos reversos de $L$.
        \item O conjunto $E=\{uv \,\,\,|\,\,\, v\in L\}$ dos {\em strings\/}
              que t\^{e}m sufixos em $L$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P=\{u \,\,\,|\,\,\, uv\in L\}$

              Seja $M=(Q,\Sigma,\delta,q_0,F)$ um aut\^omato finito
              determin\'{\i}stico que reconhe\c ca $L$. O aut\^omato finito
              $M'=(Q,\Sigma,\delta,q_0,F')$ reconhece $P$, onde
              \[F'=\{q_i\in Q \,\,|\,\, \hat{\delta}(q_i,w)\in F
                \mbox{ para algum $w\in \Sigma^*$}\}\mbox{.}\]

        \item $S=\{v \,\,\,|\,\,\, uv\in L\}$

              Seja $M=(Q,\Sigma,\delta,q_0,F)$ um aut\^omato finito
              determin\'{\i}stico que reconhe\c ca $L$. O aut\^omato finito
              $M'=(Q,\Sigma,\delta',q_0,F)$
              reconhece $S$, onde $\delta'$ \'e como $\delta$, acrescentadas as
              transi\c c\~oes-$\lambda$:
              \[q_i\in \delta'(q_0,\lambda)\mbox{, para todo $q_i$ tal que
                exista $w\in\Sigma^*$ tal que $\hat{\delta}(q_0,w)=q_i$.}\]

        \item $L^R=\{w^R \,\,\,|\,\,\, w\in L\}$
        
               Ser\'a feita uma prova por indu\c c\~ao, com base na
               defini\c c\~ao de conjunto regular, ou seja, por indu\c c\~ao
               sobre o n\'umero de operadores utilizados para constituir $L$.
               Caso $L$ seja $\phi$, $\{\lambda\}$ ou $\{a\}$, tem-se que
               $L^R=L$, portanto, regular. Suponhamos, como hip\'otese de
               indu\c c\~ao, que $X^R$ \'e regular, dado que o conjunto regular
               $X$ tenha sido constitu\'{\i}do com $k$ ou menos operadores
               ($\cup$, concatena\c c\~ao e/ou {\it Kleene star\/}). Seja um
               conjunto $Z$ constitu\'{\i}do com $k+1$ operadores. Tem-se 3
               casos a considerar:
               \begin{enumerate}
                \item[.] $Z=X\cup Y$; neste caso, $Z^R=(X\cup Y)^R=
                          X^R\cup Y^R$, pela defini\c c\~ao de reverso; e
                          portanto, $Z^R$ \'e regular (pela hip\'otese de
                          indu\c c\~ao e pelo fato de que conjuntos regulares
                          s\~ao fechados sob uni\~ao).
                \item[.] $Z=XY$; neste caso, $Z^R=(XY)^R=Y^RX^R$, pois $(uv)^R=
                         v^Ru^R$ para quaisquer {\it strings\/} $u$ e $v$; e
                         portanto, $Z^R$ \'e regular (pela hip\'otese de
                         indu\c c\~ao e pelo fato de que conjuntos regulares
                         s\~ao fechados sob concaten\c c\~ao).
                \item[.] $Z=X^*$; neste caso, $Z^R=(X^*)^R=(X^R)^*$, pois
                         $(u_1u_2\ldots u_n)^R=u_n^R\ldots u_2^Ru_1^R$ para
                         quaisquer {\it strings\/} $u_1$, $u_2$, \ldots, $u_n$,
                         $n\geq 0$;
                         e portanto, $Z^R$ \'e regular (pela hip\'otese de
                         indu\c c\~ao e pelo fato de que conjuntos regulares
                         s\~ao fechados sob {\it Kleene star\/}).
               \end{enumerate}
               
        \item $E=\{uv \,\,\,|\,\,\, v\in L\}$

              $E=\Sigma^*L$, $\Sigma^*$ \'e uma linguagem regular, e as
              linguagens regulares s\~ao fechadas sob concatena\c c\~ao.

       \end{list}
       
 \item {\it Seja $L$ uma linguagem regular que s\'{o} tem {\em
       strings\/} de tamanho par. Seja $L'=\{u \,\,\,|\,\,\, uv\in L \mbox{ e }
       |u|=|v|\}$. Prove que $L'$ \'{e} regular.}
       
       Seja $M=(Q,\Sigma,\delta,q_0,F)$ um aut\^omato finito determin\'{\i}stico
       que reconhe\c ca $L$. O aut\^omato finito
       $M'=(Q\times Q,\Sigma,\delta',[q_0,q_f],F)$, onde $q_f\not\in Q$,
       reconhece $S$, onde $\delta'$ \'e como segue:
       \begin{enumerate}
        \item[.] $\delta'([q_0,q_f],a)=\{[q_k,q_l] \,\,|\,\, \delta(q_0,a)=q_k
               \mbox{ e existe $b$ tal que $\delta(q_l,b)=q_j$ para algum
               $q_j\in F$}$
        \item[.] $\delta'([q_i,q_j],a)=\{[q_k,q_l] \,\,|\,\, \delta(q_i,a)=q_k
               \mbox{ e existe $b$ tal que $\delta(q_l,b)=q_j$}$, para todo
               $q_i,q_j\in Q$.
       \end{enumerate}
       
 \item {\it Sejam $\Sigma_1$ e $\Sigma_2$ dois alfabetos. Um {\em
       homomorfismo\/} \'{e} uma fun\c{c}\~{a}o total $h:\Sigma_1^*\rightarrow
       \Sigma_2^*$ que preserva concatena\c{c}\~{a}o. Ou seja, $h$ satisfaz:
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item $h(\lambda)=\lambda$
        \item $h(uv)=h(u)h(v)$.
       \end{list}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja $L_1\in\Sigma_1^*$ uma linguagem regular. Mostre que
              $\{h(w) \,\,\,|\,\,\, w\in L_1\}$ \'{e} regular. Tal conjunto
              \'{e} denominado {\em imagem homom\'{o}rfica\/} de $L_1$ sob $h$.
        \item Seja $L_2\in\Sigma_2^*$ uma linguagem regular. Mostre que
              $\{w\in \Sigma_1^* \,\,\,|\,\,\, h(w)\in L_2\}$ \'{e} regular. Tal
              conjunto \'{e} denominado {\em imagem inversa\/} de $L_2$ sob $h$.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L=\{h(w) \,\,\,|\,\,\, w\in L_1\}$

              Dada uma express\~ao regular para $L_1$, obt\'em-se uma
              express\~ao regular para $L$ substituindo-se cada {\boldmath $a$}
              por $h(a)$.

        \item $L=\{w\in \Sigma_1^* \,\,\,|\,\,\, h(w)\in L_2\}$.

              Seja $M=(Q,\Sigma_2,\delta,q_0,F)$ um aut\^omato finito
              determin\'{\i}stico que reconhe\c ca $L_2$. O aut\^omato finito
              determin\'{\i}stico $M'=(Q,\Sigma_1,\delta',q_0,F)$ reconhece $L$,
              onde $\delta'$ \'e definida assim:
              \[\delta'(q_i,a)=q_k \mbox{ se, e somente se,
                 $\hat{\delta}(q_i,h(a))=q_k$.}\]

       \end{list}
       
 \item {\it Uma gram\'{a}tica livre do contexto $G=(V,\Sigma,P,S)$ \'{e}
       denominada {\em regular \`{a} esquerda\/} se cada uma de suas regras \'{e} de
       uma das formas:
       \begin{list}{(\arabic{conta})}{\usecounter{conta}}
        \item $A \,\,\,\rightarrow\,\,\, \lambda$
        \item $A \,\,\,\rightarrow\,\,\, a$
        \item $A \,\,\,\rightarrow\,\,\, Ba$
       \end{list}
       onde $A,B\in V$ e $a\in\Sigma$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Fa\c{c}a um algoritmo para construir um AFN que aceite a linguagem
              gerada por uma gram\'{a}tica regular \`{a} esquerda.
        \item Mostre que as gram\'{a}ticas regulares \`{a} esquerda geram exatamente os
              conjuntos regulares.
       \end{list}}
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Para construir um AFN que aceite a linguagem gerada por uma
              gram\'{a}tica regular \`{a} esquerda:
              
              Obter $(V\cup \{Z\},\Sigma,\delta,Z,\{S\})$, onde $\delta$ \'e
              constru\'{\i}da assim:
              \begin{enumerate}
               \item para cada regra $A \,\,\,\rightarrow\,\,\, \lambda$,
                     colocar uma transi\c c\~ao $A\in \delta(Z,\lambda)$;
               \item para cada regra $A \,\,\,\rightarrow\,\,\, a$,
                     colocar uma transi\c c\~ao $A\in \delta(Z,a)$;
               \item para cada regra $A \,\,\,\rightarrow\,\,\, Ba$,
                     colocar uma transi\c c\~ao $A\in \delta(B,a)$.
              \end{enumerate}
              
        \item As gram\'{a}ticas regulares \`{a} esquerda geram exatamente os
              conjuntos regulares.
              
              Dado o resultado do item anterior, basta mostrar agora como obter
              uma gram\'{a}tica regular \`{a} esquerda que gere a linguagem
              reconhecida por um AFD. Seja, assim, um AFD $M=(Q,\Sigma,\delta,
              q_0,F)$. Uma gram\'{a}tica regular \`{a} esquerda que gera $L(M)$
              \'e $(Q\cup \{S\},\Sigma,P,S)$, onde $P$ \'e constru\'{\i}do
              assim:
              \begin{enumerate}
               \item para cada transi\c c\~ao $\delta(q_i,a)=q_j$, onde $q_j\not
                     \in F$, uma regra $q_j \,\,\,\rightarrow\,\,\, q_ia$;
               \item para cada transi\c c\~ao $\delta(q_i,a)=q_j$, onde $q_j\in
                     F$, uma regra $S \,\,\,\rightarrow\,\,\, q_ia$;
               \item finalmente, colocar a regra $q_0 \,\,\,\rightarrow\,\,\, 
                     \lambda$.
              \end{enumerate}
              
              
       \end{list}
\end{enumerate}

\end{document}

