\documentstyle[12pt]{artigo}
 
\newcounter{conta}
\newcounter{conta2}
\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 Segunda Lista de Exerc\'{\i}cios}

\begin{flushleft} \Large\bf
{Linguagens}
\end{flushleft}

\begin{enumerate}
 \item {\it Sejam $A$, $B$ e $C$ linguagens sobre um alfabeto $\Sigma$. Mostre
       que:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A(B\cup C)=(AB)\cup(AC)$
        
              \begin{eqnarray*}
               x \in A(B\cup C) & \Leftrightarrow & x = uv \mbox{, onde } u\in A
                                   \mbox{ e } v\in B\cup C \\
                                & \Leftrightarrow & x = uv \mbox{, onde } u\in A
                                   \mbox{ e } (v\in B \mbox { ou } v\in C) \\
                                & \Leftrightarrow & x = uv \mbox{, onde } (u\in A
                                   \mbox{ e } v\in B) \mbox { ou } (u\in A
                                   \mbox{ e } v\in C) \\
                                & \Leftrightarrow & x\in (AB) \mbox { ou }
                                   x\in (AC) \\
                                & \Leftrightarrow & x \in (AB) \cup (AC) 
             \end{eqnarray*}
             
        \item {\it n\~{a}o \'{e} sempre verdade que $A(B\cap C)= (AB)\cap(AC)$}
        
              Sejam $A=\{\lambda,a\}$, $B=\{b\}$ e $C=\{ab\}$. Neste caso,
              $A(B\cap C)=\{a,\lambda\}\phi=\phi$. No entanto, $(AB)\cap(AC)=
              \{b,ab\})\cap(\{ab,aab\}=\{ab\}$.
       \end{list}
       
 \item {\it Seja $\Sigma_1=\{0\}$, e $\Sigma_2=\{1\}$. Mostre que os seguintes
       conjuntos s\~{a}o enumer\'{a}veis:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\Sigma_1^*$
        
              Uma fun\c c\~ao bijetiva, $f: \Sigma_1^* \rightarrow \mbox{\bf N}$,
              seria $f(0^n)=n$ para $n\in \mbox{\bf N}$.
               
        \item $\Sigma_1^*\Sigma_2^*$
        
              Uma fun\c c\~ao bijetiva, $g: \Sigma_1^*\Sigma_2^* \rightarrow
              \mbox{\bf N}$, seria $f(0^i1^j)=(\sum_{i=0}^{i+j}i) + j=
              [(i+j)(i+j+1)/2] + j$ para $i,j\in \mbox{\bf N}$.
    
       \end{list}
 \item {\it Prove que $(w^R)^i=(w^i)^R$ para todo {\em string\/} $w$ e todo
       $i\geq 0$.}
       
       Ser\'a usada indu\c c\~ao sobre $i$. Inicialmente, observe que
       $(w^R)^0=\lambda$, e $(w^0)^R=\lambda^R=\lambda$. Suponha que a
       proposi\c c\~ao seja verdadeira para $i=n$. Deve-se provar ent\~ao que
       $(w^R)^{n+1}=(w^{n+1})^R$. Ora,
       
               \begin{eqnarray*}
                (w^R)^{n+1} & = & (w^R)^nw^R\mbox{, por defini\c c\~ao} \\
                            & = & (w^n)^Rw^R\mbox{, pela hip\'otese de indu\c c\~ao} \\
                            & = & (ww^n)^R\mbox{, pois $(uv)^R=v^Ru^R$} \\
                            & = & (w^{n+1})^R\mbox{, por defini\c c\~ao.}
            \end{eqnarray*}
             
      
 \item {\it Quais s\~{a}o os {\em strings\/} em $\{\lambda,a\}^n$,
       para um certo $n$ arbitr\'{a}rio?}
       
       Os {\em strings\/} do conjunto $\{a^i \,\,|\,\, 0\leq i\leq n\}$.
       
 \item {\it Prove que sim ou que n\~{a}o: $L^+=L^*-\{\lambda\}$.}
 
       N\~ao. Se $\lambda \in L$, $\lambda \in L^+$.
 
 \item {\it Pode $L^*$ ou $L^+$ ser $\phi$? Sob quais
       circunst\^{a}ncias $L^*$ \'{e} finito? E $L^+$?}
       
       $L^*$ n\~ao pode ser $\phi$, pois $\lambda\in L^*$ para qualquer $L$; mas
       $L^+=\phi$, no caso em que $L=\phi$. Ambos, $L^*$ e $L^+$, s\'o s\~ao
       finitos quando $L=\phi$ (neste caso, $L^*=\{\lambda\}$ e $L^+=\phi$) ou
       $L=\{\lambda\}$ (neste caso, $L^*=L^+=\{\lambda\}$).
 
 \item {\it D\^{e} express\~{o}es regulares que denotem os seguintes conjuntos:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ que n\~{a}o
              cont\^{e}m $aa$.}
        
              {\boldmath $(b\cup c\cup a(b\cup c))^*(a\cup \lambda)$}
              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b,c\}$ nos quais cada
              $b$ \'{e} seguido por pelo menos um $c$.}
              
              {\boldmath $(a\cup c\cup bc)^*$}
              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais o
              n\'{u}mero de $a$'s \'{e} divis\'{\i}vel por 3.}
              
              {\boldmath $(b^*ab^*ab^*a)^*b^*$}
              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ nos quais
              cada $a$ \'{e} precedido (imediatamente) ou seguido
              (imediatamente) por $b$.}
              
              {\boldmath $(b\cup ba\cup ab\cup aba)^*$}
              
        \item {\it o conjunto dos {\em strings\/} sobre $\{a,b\}$ com n\'{u}mero par de
              $a$'s e n\'{u}mero par de $b$'s.}
              
              {\boldmath $(aa\cup bb\cup (ab\cup ba)(aa\cup bb)^*(ab\cup ba))^*$}
              
        \item {\it o conjunto dos {\em strings\/} de tamanho \'{\i}mpar sobre
              $\{a,b\}$ que cont\^{e}m exatamente dois $b$'s.}
              
              ({\sf p}{\boldmath $b$}{\sf p}{\boldmath $b$}{\sf i})
              {\boldmath $\cup$}
              ({\sf p}{\boldmath $b$}{\sf i}{\boldmath $b$}{\sf p})
              {\boldmath $\cup$}
              ({\sf i}{\boldmath $b$}{\sf p}{\boldmath $b$}{\sf p})
              {\boldmath $\cup$}
              ({\sf i}{\boldmath $b$}{\sf i}{\boldmath $b$}{\sf i})

              onde ${\sf p}=\mbox{\boldmath $(aa)^*$}$ e ${\sf i}=
              \mbox{\boldmath $a(aa)^*$}$.
       \end{list}

\item {\it Construa express\~oes regulares que denotem os conjuntos:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\it $\{w \in \{a,b,c\}^* \,\,|\,\, w$ tem pelo menos um $a$, e
               o primeiro $a$ n\~{a}o \'{e} precedido de nenhum $b\}$}
               
               {\boldmath $c^*a(a\cup b\cup c)^*$}
               
        \item {\it $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ tem ambos, $aa$ e $bb$,
               como {\em substrings}}\}$}
               
               {\boldmath $(a\cup b)^*(aa(a\cup b)^*bb\cup bb(a\cup b)^*aa)
               (a\cup b)^*$}
               
        \item {\it $\{w \in \{a,b\}^* \,\,|\,\, \mbox{$w$ n\~ao cont\'em os
              {\it substrings\/} $aa$ nem $bb$}\}$}
              
              {\boldmath $(ab)^*(a\cup\lambda)\cup (ba)^*(b\cup\lambda)$}
       \end{list}

 \item {\it Descreva, em portugu\^{e}s, os conjuntos denotados pelas
       seguintes express\~{o}es regulares:}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $(11\cup 0)^*(00\cup 1)^*$}
        
              Definamos: {\em Substring maximal de 1's: substring de 1's que (a)
              \'e prefixo ou \'e delimitado \`a esquerda por 0, e (b) \'e sufixo ou
              \'e delimitado \`a direita por 0. Substring maximal de 0's:}
              an\'alogo, trocando 1 por 0, e vice-versa. Ent\~ao: conjunto dos
              strings sobre $\{0,1\}$ em que ap\'os o primeiro {\it substring
              maximal de 1's\/} de tamanho \'{\i}mpar, se houver, os {\it
              substrings maximais de 0's\/} , se houver algum, s\~ao de tamanho
              par.
        
        \item {\boldmath $(1\cup 01\cup 001)^*(\lambda\cup 0\cup 00)$}
        
              Conjunto dos {\em strings\/} sobre $\{0,1\}$ em que n\~ao existem mais de
              dois $0$'s consecutivos.
        
        \item {\boldmath $[00\cup 11\cup
                  (01\cup 10)(00\cup 11)^*(01\cup 10)]^*$}
        
              Conjunto dos {\em strings\/} sobre $\{0,1\}$ com n\'{u}mero par de
              $0$'s e n\'{u}mero par de $1$'s.
        
       \end{list}
       
 \item {\it Simplifique as seguintes express\~{o}es regulares:}
 
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\boldmath $\phi^*\cup a^*\cup b^*\cup (a \cup b)^*$}
 
              \begin{eqnarray*}
               \mbox{\boldmath $\phi^*\cup a^*\cup b^*\cup (a \cup b)^*$} & = &
                 \mbox{\boldmath $\phi^*\cup a^*\cup (a \cup b)^*$} \\
                 & = & \mbox{\boldmath $\phi^*\cup (a \cup b)^*$} \\
                 & = & \mbox{\boldmath $\lambda\cup (a \cup b)^*$} \\
                 & = & \mbox{\boldmath $(a \cup b)^*$}
              \end{eqnarray*}

        \item {\boldmath $(aa)^*a\cup (aa)^*$}
        
              \begin{eqnarray*}
               \mbox{\boldmath $(aa)^*a\cup (aa)^*$} & = & \mbox{\boldmath $a^*$}
              \end{eqnarray*}

        \item {\boldmath $(a \cup b)^*a(a\cup b)^*$}
        
              \begin{eqnarray*}
                \mbox{\boldmath $(a \cup b)^*a(a\cup b)^*$} & = & 
                  \mbox{\boldmath $b^*a(a\cup b)^*$}
              \end{eqnarray*}

        \item {\boldmath $a(\lambda \cup aa)^*a \cup \lambda$}
        
              \begin{eqnarray*}
                \mbox{\boldmath $a(\lambda \cup aa)^*a \cup \lambda$} & = & 
                  \mbox{\boldmath $a(aa)^*a \cup \lambda$} \\
                  & = & \mbox{\boldmath $(aa)^+ \cup \lambda$} \\
                  & = & \mbox{\boldmath $(aa)^*$}
              \end{eqnarray*}
        
        \item {\boldmath $(a\cup b)(\lambda \cup aa)^*(\lambda\cup aa) \cup a\cup b$}
        
              \begin{eqnarray*}
                \mbox{\boldmath $(a\cup b)(\lambda \cup aa)^*(\lambda\cup aa)
                      \cup a\cup b$} & = & 
                  \mbox{\boldmath $(a\cup b)(aa)^*(\lambda\cup aa)\cup a\cup b$} \\
                  & = &  \mbox{\boldmath $(a\cup b)(aa)^*\cup a\cup b$} \\
                  & = &  \mbox{\boldmath $(a\cup b)(aa)^*$}
             \end{eqnarray*}
        
       \end{list}
\end{enumerate}

\end{document}
