\documentclass[12pt,a4paper]{report}

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

%=================================================================
\addtolength{\topmargin}{1cm}
\addtolength{\textheight}{1cm}
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\textwidth}{1.5cm}
%=================================================================
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-ma 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{2}^{\mbox{\underline{o}}}$ semestre de 2003
 
\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: 29/10/03

\begin{enumerate}
 \item Seja a fun\c c\~ao $f$ definida {\em recursivamente\/} por:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $f(1)=1$,
        \item $f(2)=3$,
        \item $f(n)=f(n-1)+2f(n-2)$ para $n>2$.
       \end{list}
       Prove por indu\c c\~ao que $f(n)=(2^{n+1}+(-1)^n)/3$.

 \item Prove que $X=Y$ se, e somente se $(X-Y)\cup(Y-X)=\emptyset$.

 \item Mostre que o conjunto $\Sigma^*$ \'e enumer\'avel para qualquer alfabeto
       $\Sigma$, e que o conjunto ${\cal P}(\Sigma^*)$ n\~ao \'e enumer\'avel.

 \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 prefixo {\tt 001} e subpalavra {\tt 10}.
        \item O conjunto das palavras com um a tr\^es {\tt 1}'s.
        \item O conjunto das palavras com n\'umero de {\tt 1}'s m\'ultiplo de 3.
        \item O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de
                   1's (ou ambos).
        \item O conjunto das palavras em que as posi\c c\~oes pares s\'o
              t\^em 0's e as \'{\i}mpares s\'o t\^em 1's. Exemplos: $\lambda$,
              1, 10, 101, etc.
        \item O conjunto das palavras em que cada 0 \'e seguido de um n\'umero
              \'{\i}mpar de 1's (antes do pr\'oximo 0, se houver, ou antes do
              final da palavra). Exemplos: $\lambda$, 11, 1101, 0111010111.
       \end{list}
       Procure ser bem preciso e conciso.

 \item D\^e defini\c c\~oes recursivas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras em que as posi\c c\~oes pares s\'o
              t\^em 0's e as \'{\i}mpares s\'o t\^em 1's.
        \item $\{0\}^*\{1\}^*$.
        \item $\{0^n1^{k+n}\,\,|\,\, n\in\mbox{\bf N}\}$, sendo $k$ uma constante.
        \item $\{0^n1^{kn}\,\,|\,\, n\in\mbox{\bf N}\}$, sendo $k$ uma constante.
        \item $\{0^{n^2}\,|\, n\geq 0\}$.
        \item $\{0^{n^2+n}\,|\, n\geq 0\}$.
       \end{list}

 \item Que linguagens s\~ao geradas pelas gram\'aticas a seguir?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{X,A,B\},\{{\tt 0},{\tt 1}\},R_1,X)$.
                   \begin{enumerate}
                    \item[$R_1$:] $X\,\,\rightarrow\,\, A B$
                    \item[\ ]   $A\,\,\rightarrow\,\,{\tt 0}A\,\,|\,\, {\tt 0}$
                    \item[\ ]   $B\,\,\rightarrow\,\,{\tt 1}B{\tt 1}\,\,|\,\, \lambda$
                   \end{enumerate}
        \item $G_2=(\{P,I\},\{{\tt 0},{\tt 1}\},R_2,P)$.
                   \begin{enumerate}
                    \item[$R_2$:] $P\,\,\rightarrow\,\,{\tt 0} P \,\,|\,\,
                                                {\tt 1}I \,\,|\,\, \lambda$
                    \item[\ ]   $I\,\,\rightarrow\,\,{\tt 0} I\,\,|\,\, {\tt 1} P$
                   \end{enumerate}
        \item $G_3=(\{P,X\},\{{\tt 0},{\tt 1}\},R_3,P)$.
                   \begin{enumerate}
                    \item[$R_3$:] $P\,\,\rightarrow\,\,{\tt 0} P {\tt 0}\,\,|\,\,
                                            {\tt 1}P{\tt 1}\,\,|\,\, {\tt 0} X{\tt 1}
                                            \,\,|\,\,  {\tt 1} X{\tt 0}$
                    \item[\ ]   $X\,\,\rightarrow\,\,{\tt 0} X\,\,|\,\, {\tt 1} X
                                            \,\,|\,\, \lambda$
                   \end{enumerate}
        \item $G_4=(\{P,X,Z,U,\#\},\{{\tt 0},{\tt 1}\},R_4,P)$.
                   \begin{enumerate}
                    \item[$R_4$:] $P\,\,\rightarrow\,\,X\#$
                    \item[\ ]   $X\,\,\rightarrow\,\,{\tt 0} Z X\,\,|\,\,{\tt 1} U X
                                                                       \,\,|\,\, \lambda$
                    \item[\ ]   $Z {\tt 0}\,\,\rightarrow\,\,{\tt 0} Z$
                    \item[\ ]   $Z {\tt 1}\,\,\rightarrow\,\,{\tt 1} Z$
                    \item[\ ]   $U {\tt 0}\,\,\rightarrow\,\,{\tt 0} U$
                    \item[\ ]   $U {\tt 1}\,\,\rightarrow\,\,{\tt 1} U$
                    \item[\ ]   $Z \#      \,\,\rightarrow\,\,\#{\tt 0}$
                    \item[\ ]   $U \#      \,\,\rightarrow\,\,\#{\tt 1}$
                    \item[\ ]   $\#      \,\,\rightarrow\,\,\lambda$
                  \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{\em $w$ n\~ao cont\'em {\tt 0100}}\}$.
        \item $\{a^mb^n\,\,|\,\, m\geq 2n\}$.
        \item O conjunto dos pal\'{\i}ndromos.
        \item $\{w\,\,|\,\,$ o n\'umero de {\tt 0}'s em $w$ \'e igual ao de
               {\tt 1}'s$\}$.
       \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 (AFD's) para:
       \begin{enumerate}
        \item[(a)] $\{{\tt 01}\}^*\{{\tt 10}\}^*$.
        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ com n\'umero par
                   de {\tt 0}'s terminadas em 1.
        \item[(c)] $\{{\tt a}^k{\tt b}^n\,\,|\,\, k+n \mbox{ \'e par}\}$.
        \item[(d)] $\{w\in\{{\tt a},{\tt b}\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em aabb}\}$.
        \item[(e)] $\{w\in\{{\tt a},{\tt b}\}^*\,\,|\,\, w \mbox{ n\~ao termina com aabb}\}$.
        \item[(f)] $\{w\in\{{\tt a},{\tt b}\}^*\,\,|\,\, w \mbox{ tem n\'umero
                    \'{\i}mpar de } {\tt ab}\mbox{'s}\}$.
        \item[(g)] $\{w\in\{{\tt 0},{\tt 1}\}^*\,\,|\,\, n_{{\tt 1}}(w)
                    \,\,\mbox{\em mod}\,\, 3=1\}$.
        \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 Construa AFD's para as linguagens sobre o alfabeto $\{{\tt 0},{\tt 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 com n\'umero \'{\i}mpar de {\tt 0}'s nas
                po\-si\-\c c\~oes  \'{\i}mpares e n\'umero par de {\tt 0}'s nas
                po\-si\-\c c\~oes pares.
          \item O conjunto das palavras de tamanho par com {\tt 1}'s nas
                po\-si\-\c c\~oes pares, acrescido das palavras de
                tamanho \'{\i}mpar com {\tt 1}'s nas po\-si\-\c c\~oes \'{\i}mpares.
         \end{list}

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja ${\cal C}$ o conjunto de todos os emails
              que tenham sido produzidos at\'e as 11h 11min do dia 24 de setembro de
              2003. Existe um AFD que reconhece ${\cal C}$.
        \item Existe algoritmo que determina se $L(M)=\Sigma^*$ para quaquer AFD $M$.
        \item Se um AFD $M$ n\~ao reconhece palavras de tamanho menor que o n\'umero
              de estados de $M$, ent\~ao n\~ao reconhece palavra alguma.
        \item Se um AFD $M$ reconhece uma palavra de tamanho igual ao n\'umero
              de estados de $M$, ent\~ao $L(M)$ \'e infinita.
       \end{list}

 \item Seja $M_C$ um AFD ``correto'' e $M_E$ um AFD ``incorreto'' para uma certa
       linguagem. Descreva m\'etodos (algoritmos) para determinar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que palavras $M_E$ deveria reconhecer e n\~ao reconhece.
        \item Que palavras $M_E$ reconhece e n\~ao deveria reconhecer.
       \end{list}

 \item Construa AFN's para cada uma das seguintes linguagens, procurando
       utilizar o menor n\'umero de estados poss\'{\i}vel:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{a,b,c\}^*\,\,|\,\,$ o \'ultimo s\'{\i}mbolo de $w$
              tenha ocorrido antes$\}$.
        \item $\{w\in\{a,b,c\}^*\,\,|\,\,$ o \'ultimo s\'{\i}mbolo de $w$
              n\~ao tenha ocorrido antes$\}$.
        \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 AFD's equivalentes aos AFN's dos dois primeiros itens da quest\~ao anterior, usando o
       m\'etodo visto no curso ({\em subset construction}).

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^m{\tt 1}^n\,\,|\,\, m\not=n+1\}$
        \item $\{x{\tt c}y \,\,|\,\, x,y\in\{{\tt a},{\tt b}\}^* \mbox{ e }
               n_{{\tt a}}(x)=n_{{\tt b}}(y)\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,\,|\,\,$ o n\'umero de {\tt 0}'s em $w$ \'e
              duas vezes o de {\tt 1}'s$\}$.
        \item $\{x{\tt 1}x\in\{{\tt 0},{\tt 1}\}^*\,|\, |x|\leq k\}$,
              sendo $k$ uma constante.
        \item $\{x{\tt 1}x\in\{{\tt 0},{\tt 1}\}^*\,|\, |x|\geq k\}$,
              sendo $k$ uma constante.
        \item $\{{\tt 0}^i{\tt 1}^n{\tt 2}^j\,\,|\,\, n>i+j\}$.
       \end{list}

 \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$).
        \item $\mbox{\em subp\/}(L)=\{y \,\,|\,\, xyz\in L \}$ (as subpalavras 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$ \'e regular, existe $L_2$ tal que $L_1\subseteq L_2$ e
                $L_2$ n\~ao \'e regular.
          \item Se $L_1$ n\~ao \'e regular, existe $L_2$ tal que $L_1\subseteq L_2$ e
                $L_2$ \'e regular.
          \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$ n\~ao \'e regular e $L_2$ \'e regular, $L_1\cup L_2$ n\~ao \'e regular.
          \item se $L_1$ n\~ao \'e regular e $L_2$ \'e finita, $L_1\cup L_2$ n\~ao \'e regular.
         \end{list}

\end{enumerate}

\end{document}
