\documentclass[12pt,a4paper]{report}

%=================================================================
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
%\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 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: 04/12/02

\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)=5$,
        \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)^n$.

 \item Prove que $X=Y$ se, e somente se $X-Y=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 $\{0,1\}^*$. O alfabeto \'e $\{0,1\}$ para todas.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com \verb+001+ como subpalavra.
        \item O conjunto das palavras que n\~ao t\^em mais de tr\^es 1's.
        \item O conjunto das palavras com n\'umero par de \verb+1+'s.
        \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 $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w| \mbox{ \'e \'{\i}mpar}\}$.
        \item $\{0\}^*\{1\}^*$.
        \item $\{0^n1^n\,\,|\,\, n\in\mbox{\bf N}\}$.
        \item $\{0^{n^2}\,|\, 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\},\{\verb+0+,\verb+1+\},R_1,X)$.
                   \begin{enumerate}
                    \item[$R_1$:] $X\,\,\rightarrow\,\, A B$
                    \item[\ ]   $A\,\,\rightarrow\,\,\verb+0+A\,\,|\,\, \lambda$
                    \item[\ ]   $B\,\,\rightarrow\,\,\verb+1+B\,\,|\,\, \verb+1+$
                   \end{enumerate}
        \item $G_2=(\{P,I\},\{\verb+0+,\verb+1+\},R_2,P)$.
                   \begin{enumerate}
                    \item[$R_2$:] $P\,\,\rightarrow\,\,\verb+0+ P \,\,|\,\,
                                                \verb+1+I \,\,|\,\, \lambda$
                    \item[\ ]   $I\,\,\rightarrow\,\,\verb+0+ I\,\,|\,\,
                                               \verb+1+ P \,\,|\,\, \lambda$
                   \end{enumerate}
        \item $G_3=(\{P,X\},\{\verb+0+,\verb+1+\},R_3,P)$.
                   \begin{enumerate}
                    \item[$R_3$:] $P\,\,\rightarrow\,\,\verb+0+ P \verb+0+\,\,|\,\, \verb+1+X$
                    \item[\ ]   $X\,\,\rightarrow\,\,\verb+1+ X\verb+1+\,\,|\,\, \lambda$
                   \end{enumerate}
        \item $G_4=(\{P,X,Z,U,\#\},\{\verb+0+,\verb+1+\},R_4,P)$.
                   \begin{enumerate}
                    \item[$R_4$:] $P\,\,\rightarrow\,\,X\#$
                    \item[\ ]   $X\,\,\rightarrow\,\,\verb+0+ Z X\,\,|\,\,\verb+1+ U X
                                                                       \,\,|\,\, \lambda$
                    \item[\ ]   $Z \verb+0+\,\,\rightarrow\,\,\verb+0+ Z$
                    \item[\ ]   $Z \verb+1+\,\,\rightarrow\,\,\verb+1+ Z$
                    \item[\ ]   $U \verb+0+\,\,\rightarrow\,\,\verb+0+ U$
                    \item[\ ]   $U \verb+1+\,\,\rightarrow\,\,\verb+1+ U$
                    \item[\ ]   $Z \#      \,\,\rightarrow\,\,\#\verb+0+$
                    \item[\ ]   $U \#      \,\,\rightarrow\,\,\#\verb+1+$
                    \item[\ ]   $\#      \,\,\rightarrow\,\,\lambda$
                  \end{enumerate}
       \end{list}

 \item Obtenha gram\'aticas para as seguintes linguagens sobre $\{\verb+0+,\verb+1+\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\,\,|\,\, n_{\verb+1+}(w) \,\,\mbox{\em mod}\,\, 3=0\}$.
        \item $\{w\,\,|\,\, n_{\verb+1+}(w) \,\,\mbox{\em mod}\,\, 3>0\}$.
        \item $\{a^mb^n\,\,|\,\, m\geq n\}$.
        \item $\{ww^R\,\,|\,\, w\in\{a,b\}^*\}$.
        \item $\{w\in\{a,b\}^*\,\,|\,\,$ o n\'umero de a's em $w$ \'e igual ao de
               b'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)] $\{\verb+01+\}^*$.
        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ com n\'umero \'{\i}mpar
                   de \verb+1+'s e terminadas em 1.
        \item[(c)] $\{\verb+a+^k\verb+b+^n\,\,|\,\, k+n\geq 3\}$.
        \item[(d)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em aabb}\}$.
        \item[(e)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ n\~ao termina com aabb}\}$.
        \item[(f)] $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w \mbox{ tem n\'umero
                    \'{\i}mpar de } \verb+ab+\mbox{'s}\}$.
        \item[(g)] $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, n_{\verb+1+}(w)
                    \,\,\mbox{\em mod}\,\, 3=1\}$.
        \item[(h)] $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,n_{\verb+0+}(w)\,\,
                    \mbox{\em mod}\,\, 3=1
                    \mbox{ e } n_{\verb+1+}(w)\,\,\mbox{\em mod}\,\, 3=2\}$.
       \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 Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Seja ${\cal C}$ o conjunto de todos os programas escritos na linguagem C++
              que tenham sido produzidos at\'e as 10h 28min do dia 6 de novembro de
              2002. 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..
       \end{list}

 \item Sejam $M_A$ e $M_B$ AFD's para as linguagens $A$ e $B$. Descreva um
       m\'etodo para obter um AFD, a partir destes dois, que reconhe\c ca a
       diferen\c ca sim\'etrica entre $A$ e $B$, $A\bigoplus B=(A-B)\cup(B-A)$.
       Procure obter um m\'etodo que d\^e o menor ``trabalho'' poss\'{\i}vel.

 \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\verb+1+y\,\,|\,\, x,y\in\{\verb+0+,\verb+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 da quest\~ao anterior, usando o
       m\'etodo visto no curso.

 \item Prove que os seguintes conjuntos s\~ao ou n\~ao s\~ao linguagens regulares:
       \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 $\{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\}$
        \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 $\{xyx\in\{\verb+0+,\verb+1+\}^*\,|\,|x|=|y| \mbox{ e } |x|\geq n\}$,
              onde $n$ \'e um certo n\'umero (qualquer).
        \item $\{xyx\in\{\verb+0+,\verb+1+\}^*\,|\,|x|=|y| \mbox{ e } |x|\leq n\}$,
              onde $n$ \'e um certo n\'umero (qualquer).
        \item $\{\verb+0+^n\verb+1+^i\verb+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\subseteq L_2$ e $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 $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}
