\documentclass[11pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

%=================================================================
%\addtolength{\topmargin}{1cm}
%\addtolength{\textheight}{1cm}
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\textwidth}{1.5cm}
%=================================================================
 
\newcounter{conta}
\newcounter{conta2}

\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{2}^{\mbox{\underline{o}}}$ semestre de 2005
 
\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: 13/09/05

\begin{enumerate}
 \item Encontre o erro na seguinte demonstra\c c\~ao, por indu\c c\~ao, de
       que {\em em qualquer conjunto de cavalos, todos t\^em a mesma cor}.
       \begin{quote}
        Em um conjunto com 1 cavalo, evidentemente todos os cavalos t\^em a mesma
        cor. Seja $n\geq 1$ e suponha, como hip\'otese de indu\c c\~ao que, em um
        conjunto de $n$ cavalos, todos t\^em a mesma cor. Seja um conjunto $C$ de
        $n+1$ cavalos. Basta, para concluir a demonstra\c c\~ao, mostrar que todos os
        cavalos em $C$ t\^em a mesma cor. Seja $C_1$ um conjunto obtido removendo-se
        um cavalo $c_1$ de $C$. Pela hip\'otese de indu\c c\~ao, os cavalos em $C_1$ t\^em
        a mesma cor. Agora, seja $C_2$ um conjunto obtido removendo-se um cavalo $c_2$
        de $C$, diferente de $c_1$. Analogamente, pela hip\'otese de indu\c c\~ao,
        os cavalos em $C_2$ t\^em a mesma cor. Portanto, todos os cavalos de $C$ t\^em
        a mesma cor! (Sipser (1997), prob. 0.11, p\'ag. 27.)
       \end{quote}

 \item Prove que $(L_1L_2)^R=L_2^RL_1^R$.

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que o conjunto $\{{\tt 0},{\tt 1}\}^*$ \'e enumer\'avel.
              Para isto, construa uma fun\c c\~ao bijetora $f:\{{\tt 0},{\tt 1}\}^*
              \rightarrow \mbox{\bf N}$.
        \item Mostre que o conjunto $F=\{C\subseteq\{{\tt 0},{\tt 1}\}^*\,|\, C
              \mbox{ \'e finito}\}$ \'e enumer\'avel. Para isto, construa uma fun\c c\~ao
              bijetora $g:F\rightarrow \mbox{\bf N}$.
        \item Mostre que o conjunto ${\cal P}(\{{\tt 0},{\tt 1}\}^*)$ n\~ao \'e enumer\'avel.
       \end{list}

 \item Expresse as linguagens a seguir utilizando opera\c c\~oes sobre conjuntos
       finitos de palavras de $\{{\tt 0},{\tt 1}\}^*$. O alfabeto \'e
       $\{{\tt 0},{\tt 1}\}$ para todas.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com, no m\'inimo, dois {\tt 1}s.
        \item O conjunto das palavras com n\'umero par de {\tt 1}s.
        \item O conjunto das palavras com n\'umero par de {\tt 1}s
              e \'{\i}mpar de {\tt 0}s.
        \item O conjunto das palavras em que as posi\c c\~oes \'{\i}mpares
              s\'o cont\^em {\tt 1}s. Exemplos: $\lambda$, {\tt 1}, {\tt 10}, {\tt 11},
              {\tt 101}, {\tt 111}.
        \item O conjunto das palavras em que cada {\tt 0} \'e precedido por um n\'umero
              \'{\i}mpar de {\tt 1}s (ap\'os o {\tt 0} anterior, se houver, ou ap\'os o
              in\'{\i}cio da palavra). Exemplos: $\lambda$, {\tt 11}, {\tt 1011},
              {\tt 1110101110}.
       \end{list}
       Procure ser bem preciso e conciso.

 \item Que linguagens s\~ao geradas pelas gram\'aticas a seguir? Procure se
       expressar com clareza e simplicidade.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{S,A,B\},\{{\tt a},{\tt b}\},R_1,S)$.
                   \begin{enumerate}
                    \item[$R_1$:] $S\,\,\rightarrow\,\, {\tt a} A$
                    \item[\ ]   $A\,\,\rightarrow\,\,{\tt b}S$
                    \item[\ ]   $S\,\,\rightarrow\,\,\lambda$
                   \end{enumerate}
                   (Linz (1997), ex. 9, p\'ag. 27.)
        \item $G_2=(\{S,A,B\},\{{\tt a},{\tt b}\},R_2,S)$.
                   \begin{enumerate}
                    \item[$R_2$:] $S\,\,\rightarrow\,\, A{\tt a}$
                    \item[\ ]   $A\,\,\rightarrow\,\,B$
                    \item[\ ]   $B\,\,\rightarrow\,\,A{\tt a}$
                   \end{enumerate}
                   (Linz (1997), ex. 10, p\'ag. 27.)
        \item $G_3=(\{P,X\},\{{\tt a},{\tt b}\},R_3,P)$.
                   \begin{enumerate}
                    \item[$R_3$:] $P\,\,\rightarrow\,\,{\tt a} P {\tt b}\,\,|\,\,
                                            {\tt b}X\,\,|\,\, X{\tt a}$
                    \item[\ ]   $X\,\,\rightarrow\,\,{\tt a} X\,\,|\,\, {\tt b} X
                                            \,\,|\,\, \lambda$
                   \end{enumerate}
        \item $G_4=(\{P,X,C\},\{{\tt a},{\tt b},{\tt c}\},R_4,P)$.
                   \begin{enumerate}
                    \item[$R_4$:] $P\,\,\rightarrow\,\,P {\tt c} \,\,|\,\, X {\tt c}$
                    \item[\ ]   $X\,\,\rightarrow\,\, X {\tt b} C\,\,|\,\, Y$
                    \item[\ ]   $Y\,\,\rightarrow\,\,{\tt a} Y {\tt b} C \,\,|\,\, \lambda$
                    \item[\ ]   $C {\tt b}\,\,\rightarrow\,\,{\tt b} C$
                    \item[\ ]   $C {\tt c}\,\,\rightarrow\,\,{\tt cc}$
                  \end{enumerate}
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens sobre $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\,\,|\,\, \mbox{o n\'umero de {\tt 1}s ap\'os cada {\tt 0} em $w$ \'e par}\}$.
        \item O conjunto das palavras da forma $x\overline{x}$. O sufixo $\overline{x}$ \'e
              constitu\'{\i}do dos d\'{\i}gitos ``invertidos'' de $x$. Por exemplo,
              $\overline{{\tt 0100}}={\tt 1011}$
        \item $\{{\tt 0}^m{\tt 1}^n{\tt 0}^k\,\,|\,\, n=m+k\}$.
        \item $\{{\tt 0}^m{\tt 1}^n{\tt 0}^k\,\,|\,\, k=m+n\}$.
       \end{list}

 \item Como o conceito de {\em redu\c c\~ao\/} pode ser usado para mostrar
       que um problema \'e decid\'{\i}vel? E como ele pode ser usado para
       mostrar que um problema \'e indecid\'{\i}vel?

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFDs) para:
       \begin{enumerate}
        \item[(a)] $\{{\tt 10}\}^*\{{\tt 01}\}^*$.
        \item[(b)] $\{{\tt 0}\}^*\{{\tt 10}\}^*\{{\tt 01}\}^*$.
        \item[(c)] $\{{\tt 0},{\tt 11}\}^*\{{\tt 0}\}^*\{{\tt 1}\}$.
        \item[(d)] $\{w\in\{{\tt a},{\tt b}\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em {\tt 0110}}\}$.
        \item[(e)] $\{w\in\{{\tt a},{\tt b}\}^*\,\,|\,\, w \mbox{ n\~ao termina com {\tt 0110}}\}$.
        \item[(f)] Conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ em que cada subpalavra de quatro
                   s\'{\i}mbolos cont\'em, no m\'{\i}nimo, tr\^es {\tt 1}s. (Moret (1998), ex. 3, p\'ag. 86.)
        \item[(g)] Conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ que cont\^em um n\'umero par de
                   {\tt 0}s ou no m\'aximo tr\^es {\tt 0}s. (Moret (1998), ex. 4, p\'ag. 86.)
        \item[(h)] $\{w\in\{{\tt 0},{\tt 1}\}^*\,\,|\,\,n_{{\tt 0}}(w)\,\,
                    \mbox{\em mod}\,\, 3=1
                    \mbox{ e } n_{{\tt 1}}(w)\,\,\mbox{\em mod}\,\, 3=2\}$.
       \end{enumerate}

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe algoritmo que determina se $L(M_1)\cap L(M_2)\not=\emptyset$ para quaisquer
              AFDs $M_1$ e $M_2$.
        \item Se um AFD $M$ reconhece alguma palavra de tamanho igual ou maior do que o n\'umero
              de estados de $M$, ent\~ao, dado um n\'umero natural $n$ qualquer,
              $M$ reconhece palavras de tamanho maior do que $n$.
        \item Se $X\subseteq Y$ e existe AFD que reconhece $X$, ent\~ao existe AFD
              que reconhece $Y$.
        \item Se $X\subseteq Y$ e existe AFD que reconhece $Y$, ent\~ao existe AFD
              que reconhece $X$.
       \end{list}

 \item Construa AFNs para cada uma das seguintes linguagens, procurando
       utilizar o menor n\'umero de estados poss\'{\i}vel:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}\}\cup\{{\tt b}\}^+$. O AFN deve ter apenas um estado final
              e n\~ao pode ter transi\c c\~ao $\lambda$.
              (Linz (1997), ex. 8, p\'ag. 64.)
        \item $\{w\in\{a,b,c\}^*\,\,|\,\,$ o \'ultimo s\'{\i}mbolo de $w$
              tenha ocorrido antes$\}$. (Hopcroft et al. (2001), ex. 2.3.4(a), p\'ag. 67.)
        \item $\{w\in\{a,b,c\}^*\,\,|\,\,$ o \'ultimo s\'{\i}mbolo de $w$
              n\~ao tenha ocorrido antes$\}$. (Hopcroft et al. (2001), ex. 2.3.4(b), p\'ag. 67.)
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,\,|\,\, |x| \,\mbox{\em mod\/}\, 3 = 1
              \mbox{ e } \eta(y) \,\mbox{\em mod\/}\, 3 = 1\}$, sendo
              $\eta(y)$ o n\'umero representado por $y$ na base 2. 
       \end{list}

 \item Obtenha AFDs equivalentes aos AFNs dos dois primeiros itens da quest\~ao
       anterior, usando o m\'etodo visto no curso ({\em subset construction}).

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares utilizando o
       lema do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto dos pal\'{\i}ndromos de $\{{\tt a},{\tt b}\}^*$.
        \item $\{xy\in\{{\tt a},{\tt b}\}^* \,\,|\,\, |x|=|y| \mbox{ e }
               n_{{\tt a}}(x)=n_{{\tt b}}(y)\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt a}^n \,\,|\,\, m\leq 10 \mbox{ e }
               n\geq 0\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt a}^n \,\,|\,\, m\geq 10 \mbox{ e }
               n\geq 0\}$.
       \end{list}

 \item Seja $a$ um certo s\'{\i}mbolo. Mostre que a classe das linguagens regulares
       \'e ou n\~ao \'e fechada sob cada uma das opera\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pref\/}_a(L)=\{x \,\,|\,\, xa\in L \}$.
        \item $\mbox{\em suf\/}_a(L)=\{y \,\,|\,\, ay\in L \}$.
        \item $\mbox{\em resto\/}_a(L)=\{xy \,\,|\,\, xay\in 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$ e $L_2$ n\~ao s\~ao regulares, $L_1\cup L_2$ n\~ao \'e regular.
          \item se $L_1$ e $L_2$ n\~ao s\~ao regulares, $L_1\cap L_2$ n\~ao \'e regular.
          \item se $L_1$ n\~ao \'e regular, $\overline{L_1}$ n\~ao \'e regular.
          \item se $L_1$ \'e regular e $L_2$ n\~ao \'e regular, $L_1\cup L_2$ n\~ao \'e regular.
          \item se $L_1$ \'e regular, $L_2$ n\~ao \'e regular e $L_1\cap L_2$ \'e regular,
                $L_1\cup L_2$ n\~ao \'e regular.
          \item se $L_1$ \'e regular, $L_2$ n\~ao \'e regular e $L_1\cap L_2$ n\~ao \'e regular,
                $L_1\cup L_2$ n\~ao \'e regular.
         \end{list}
         (Martin (1991), ex. 8.6, p\'ag. 153.)
\end{enumerate}

\end{document}
