\documentclass[12pt,a4paper]{report}

%=================================================================
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\textwidth}{1.5cm}
%=================================================================
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas re-gu-lar re-gu-la-res}
\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 Teoria de Linguagens}
 \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: \parbox[t]{14cm}{Newton Jos\'{e} Vieira \\
                     e-mail: nvieira@dcc.ufmg.br}
 
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill Entrega: at\'e 29/04/02

\begin{enumerate}
 \item Use indu\c c\~ao sobre o tamanho de $X$ para mostrar que se $X$ \'e um conjunto
       finito, ent\~ao $|{\cal P}(X)|=2^{|X|}$.

 \item Prove que se $X\subseteq Y$, ent\~ao $\overline{Y}\subseteq\overline{X}$.

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

 \item Responda sem justificar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sejam $A=\{\lambda,\verb+a+\}$ e $B=\{\verb+a+,\verb+aa+\}$. Determine
              quantos elementos tem: (a) $AB$; (a) $A^nB$; (b) $AB^n$; (c) $A^nB^n$. 
        \item Simplifique: (a) $(L^*)^+$; (b) $(L^+)^*$; (c) $L^*\cup L^+$;
              (d) $L^*\cap L^+$ (e) $L^*L^+$ (f) $L^+-L^*$ (g) $L^*-L^+$.
       \end{list}

 \item Descreva mais formalmente (usando conjuntos, concatena\c c\~ao, fecho de
       Kleene, etc.) as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras com, no m\'aximo, um \verb+0+.
        \item[(b)] O conjunto das palavras de tamanho \'{\i}mpar terminadas em 1.
        \item[(c)] O conjunto das palavras cujo antepen\'ultimo s\'{\i}mbolo \'e
                   \verb+0+, {\em caso este exista\/}.
        \item[(d)] O conjunto das palavras com n\'umero par de 0's.
        \item[(e)] O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de
                   1's (ou ambos).
        \item[(f)] O conjunto das palavras de tamanho par, cuja primeira metade \'e
                   id\^entica \`a segunda.
       \end{enumerate}
       Procure ser bem preciso e conciso.

 \item D\^e defini\c c\~oes recursivas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{0\}^*$
        \item[(b)] $\{0\}^*\{1\}^*$
        \item[(c)] $\{0^n1^n\,\,|\,\, n\in\mbox{\bf N}\}$
        \item[(d)] $\{0\}^*\{1\}^*\{2\}^*$
       \end{enumerate}

 \item Mostre que linguagens s\~ao geradas pelas gram\'aticas a seguir. N\~ao \'e preciso
       provar.
       \begin{enumerate}
        \item[(a)] $G_1=(\{P,A\},\{\verb+0+,\verb+1+\},R_1,P)$.
                   \begin{enumerate}
                    \item[$R_1$:] $P\,\,\rightarrow\,\,\verb+0+A$
                    \item[\ ]   $A\,\,\rightarrow\,\,\verb+1+P\,\,|\,\, \lambda$
                   \end{enumerate}
        \item[(b)] $G_2=(\{X,P,D\},\{\verb+0+,\verb+1+\},R_2,X)$.
                   \begin{enumerate}
                    \item[$R_2$:] $X\,\,\rightarrow\,\,P\verb+1+$
                    \item[\ ]   $P\,\,\rightarrow\,\,DDP\,\,|\,\, \lambda$
                    \item[\ ]   $D,\,\rightarrow\,\,\verb+0+\,\,|\,\, \verb+1+$
                   \end{enumerate}
        \item[(c)] $G_3=(\{A,B,C,X,Y\},\{\verb+0+,\verb+1+,\verb+2+\},R_3,X)$.
                   \begin{enumerate}
                    \item[$R_3$:] $A\,\,\rightarrow\,\,\verb+0+A\verb+10+\,\,|\,\,X$
                    \item[\ ]   $X\verb+0+\,\,\rightarrow\,\,\verb+2+X$
                    \item[\ ]   $\verb+10+\,\,\rightarrow\,\,\verb+01+$
                    \item[\ ]   $X\,\,\rightarrow\,\,\lambda$
                   \end{enumerate}
       \end{enumerate}

 \item Obtenha gram\'aticas para as seguintes linguagens sobre $\{\verb+1+\}^*$:
       \begin{enumerate}
        \item[(a)] $\{w\,\,|\,\, |w| \,\,\mbox{\em mod}\,\, 3=0\}$.
        \item[(b)] $\{w\,\,|\,\, |w| \,\,\mbox{\em mod}\,\, 3>0\}$.
        \item[(c)] $\{w\,\,|\,\, |w| \,\,\mbox{\em mod}\,\, 3\not=|w| \,\,\mbox{\em mod}\,\, 2\}$.
       \end{enumerate}

 \item Considere o conceito de {\em redu\c c\~ao\/} de um problema de decis\~ao a outro.
       Segue da defini\c c\~ao de redu\c c\~ao que: {\em se um problema pode ser reduzido
       a um problema decid\'{\i}vel, ent\~ao ele \'e decid\'{\i}vel\/}. Explique como a
       {\em contrapositiva\/} desta afirmativa pode ser tomada como base para mostrar que
       um problema \'e indecid\'{\i}vel.

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para:
       \begin{enumerate}
        \item[(a)] $\verb+0+^*$.
        \item[(b)] O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ de tamanho \'{\i}mpar
                   terminadas em 1.
        \item[(c)] $\{\verb+a+^k\verb+b+^n\,\,|\,\, k+n\geq 2\}$.
        \item[(d)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em abba}\}$.
        \item[(e)] $\{\verb+01+\}^*\{\verb+10+\}^*$.
        \item[(f)] $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,n_{\verb+0+}(w)\,\,\mbox{\em mod}\,\, 2=0
                    \mbox{ e } n_{\verb+1+}(w)\,\,\mbox{\em mod}\,\, 3=0\}$, onde
                   $n_s(w)$ \'e a quantidade do s\'{\i}mbolo $s$ na palavra $w$.
       \end{enumerate}

 \item Construa AFD's para as linguagens sobre o alfabeto $\{\verb+0+,\verb+1+\}$,
       a seguir. Considere que o s\'{\i}mbolo na posi\c c\~ao 1 de uma palavra \'e o
       primeiro s\'{\i}mbolo desta, o s\'{\i}mbolo na posi\c c\~ao 2 \'e o segundo, e
       assim por diante.
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras em que o s\'{\i}mbolo na posi\c c\~ao $2i$ \'e
                diferente do s\'{\i}mbolo na posi\c c\~ao $2i+2$, para $i\geq 1$.
          \item O conjunto das palavras em que o s\'{\i}mbolo na posi\c c\~ao $2i-1$ \'e
                diferente do s\'{\i}mbolo na posi\c c\~ao $2i$, para $i\geq 1$.
          \item O conjunto das palavras em que o s\'{\i}mbolo na posi\c c\~ao $i$ \'e
                diferente do s\'{\i}mbolo na posi\c c\~ao $i+2$, para $i\geq 1$.
          \item O conjunto das palavras com n\'umero \'{\i}mpar de \verb+0+'s nas
                po\-si\-\c c\~oes  \'{\i}mpares e n\'umero par de \verb+0+'s nas
                po\-si\-\c c\~oes pares.
          \item O conjunto das palavras de tamanho par com \verb+1+'s nas
                po\-si\-\c c\~oes pares, acrescido das palavras de
                tamanho \'{\i}mpar com \verb+1+'s nas po\-si\-\c c\~oes \'{\i}mpares.
         \end{list}

 \item Prove que sim ou que n\~ao: se $M=(E,\Sigma,\delta,i,F)$ \'e um AFD m\'{\i}nimo
       para uma linguagem regular $L$, ent\~ao $\hat{M}=(E,\Sigma,\delta,i,E-F)$ \'e um
       AFD m\'{\i}nimo para $\overline{L}$.

 \item Sim ou n\~ao? Por que?
       \begin{enumerate}
        \item[(a)] Seja ${\cal C}$ o conjunto de todos os programas escritos na linguagem C++
                   que tenham, no m\'aximo, 1 trilh\~ao de caracteres. Existe um AFD que
                   reconhece ${\cal C}$.
        \item[(b)] Existe algoritmo que determina se $L(M)=\emptyset$ para quaquer AFD
                   $M$.
        \item[(c)] Se um AFD $M$ reconhece uma palavra de tamanho igual ao n\'umero de
                   estados de $M$, ent\~ao $L(M)$ \'e infinita.
        \item[(d)] Suponha que existam AFD's para as linguagens $A$, $B$ e $C$. \'E
                   poss\'{\i}vel construir um AFD que reconhe\c ca $A-(B-C)$. (Lembre-se
                   que $A-B=A\cap\overline{C}$.)
       \end{enumerate}

 \item Construa AFN's para as seguintes linguagens, com o {\em menor n\'umero de estados\/}
       poss\'{\i}vel:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de $\{\verb+0+,\verb+1+\}^*$ em que existem pelo menos
              duas ocorr\^encias de \verb+01+ com um n\'umero \'{\i}mpar de s\'{\i}mbolos
              entre elas.
        \item $\{x\verb+1+y\,\,|\,\, x,y\in\{\verb+0+,\verb+1+\}^* \mbox{ e } \eta(y)
               \,\,\mbox{\em mod}\,\, 3=0\}$, onde $\eta(y)$ \'e o n\'umero representado por
               $y$ na base 2.
       \end{list}

 \item Obtenha AFD's equivalentes aos AFN's da quest\~ao anterior, usando o
       m\'etodo visto no curso.

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando o lema
       do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x \verb+c+ x \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
        \item $\{x\verb+c+y \,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e }
               n_{\verb+a+}(x)=n_{\verb+b+}(y)\}$
        \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq0\}$
       \end{list}

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares,
       utilizando propriedades de fechamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, m<n\}\cup\{\verb+0+^m\verb+1+^n\,\,|\,\,
               m>n\}$
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ o n\'umero de \verb+0+'s em $w$ \'e
              duas vezes o de \verb+1+'s$\}$
        \item $\{\verb+0+^m\verb+1+^n\verb+2+^{m+n}\,\,|\,\, m,n>0\}$
        \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, \mbox{\em mdc\/}(m,n)=1\}$
       \end{list}
       Se n\~ao conseguir, use o lema do bombeamento.

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes
       opera\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pref\/}_a(L)=\{x \,\,|\,\, xa\in L \}$, onde $a$ \'e um certo
              s\'{\i}mbolo do alfabeto de $L$.
        \item $\mbox{\em pref\/}(L)=\{x \,\,|\,\, xy\in L \}$ (os prefixos das palavras
               de $L$).
        \item $\mbox{\em suf\/}_a(L)=\{y \,\,|\,\, ay\in L \}$, onde $a$ \'e um certo
              s\'{\i}mbolo do alfabeto de $L$.
        \item $\mbox{\em suf\/}(L)=\{y \,\,|\,\, xy\in L \}$ (os sufixos das palavras de $L$).
       \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens. Mostre que sim ou que n\~ao:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1\cup L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
                regular.
          \item se $L_1L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem
                regular.
          \item se $L_1^*$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem regular.
          \item se $L_1$ \'e uma linguagem regular ent\~ao $\{w \,\,|\,\, w $ \'e uma
                subpalavra de $L_1\}$ \'e uma linguagem regular.
         \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens {\bf n\~ao} regulares. Mostre que sim ou que n\~ao:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1\cup L_2$ \'e uma linguagem n\~ao regular.
          \item se $L_1L_2$ \'e uma linguagem n\~ao regular.
          \item se $L_1^*$ \'e uma linguagem n\~ao regular.
          \item $\{w \,\,|\,\, w $ \'e uma subpalavra de $L_1\}$ \'e uma linguagem n\~ao regular.
         \end{list}

\end{enumerate}

\end{document}
 


