\documentclass[12pt,a4paper]{report}

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

%=================================================================
%\addtolength{\topmargin}{1cm}
%\addtolength{\textheight}{1cm}
%=================================================================

\newcounter{conta}
%\pagestyle{empty}
\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{2}^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova/Solu\c c\~ao do professor} \hfill 29/10/2003

\begin{enumerate}

 \item Responda sem provar:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que rela\c c\~ao existe entre $L^+$ e $L^*$?

              {\em Solu\c c\~ao\/}: $L^*=L^+\cup\{\lambda\}$.

        \item Em que situa\c c\~oes $L_1^*L_2^*=L_2^*$?

              {\em Solu\c c\~ao\/}: uma condi\c c\~ao necess\'aria e
              suficiente \'e: $L_1\subseteq L_2^*$.

        \item Em que situa\c c\~oes $L_1^*\cup L_2^*=(L_1\cup L_2)^*$?

              {\em Solu\c c\~ao\/}: uma condi\c c\~ao necess\'aria e
              suficiente \'e: $L_1\subseteq L_2^*$ ou $L_2\subseteq L_1^*$.

       \end{list}

 \item Descreva mais formalmente (usando conjuntos finitos, uni\~ao,
       interse\c c\~ao, concatena\c c\~ao, fecho de Kleene, etc.) as
       seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras sem ocorr\^encias de {\tt 00}.

              {\em Solu\c c\~ao\/}: $\{{\tt 01},{\tt 1}\}^*\{\lambda,{\tt 0}\}$.

        \item O conjunto n\~ao vazio das palavras de tamanho m\'ultiplo
              de 5 cujo segundo s\'{\i}mbolo \'e {\tt 0}.

              {\em Solu\c c\~ao\/}: $\{{\tt 0},{\tt 1}\}\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^3
                                     (\{{\tt 0},{\tt 1}\}^5)^*$.

        \item O conjunto das palavras em que entre dois {\tt 0}'s ocorre sempre uma
              sequ\^encia de {\tt 1}'s de tamanho \'{\i}mpar. Exemplos: $\lambda$,
              {\tt 0}, {\tt 110}, {\tt 011}, {\tt 101011}, {\tt 110111110}.

              {\em Solu\c c\~ao\/}: $\{{\tt 1}\}^*(\{{\tt 0}\}\{{\tt 1}\}\{{\tt 11}\}^*)^*
                                     \{\lambda,{\tt 0},{\tt 1}\}$.

       \end{list}

 \item Para cada linguagem abaixo, se ela for regular, fa\c ca um
       aut\^omato finito (de qualquer modalidade) que a
       reconhe\c ca; caso contr\'ario, prove que ela n\~ao \'e regular
       utilizando o lema do bombeamento.\footnote{$n_s(w)$ denota o n\'umero
       de ocorr\^encias do s\'{\i}mbolo $s$ na palavra $w$.}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L=\{x{\tt 1}y\in \{{\tt 0},{\tt 1}\}^*\,|\,n_0(x)=n_1(y)\}$.

              {\em Solu\c c\~ao\/}: Suponha que $L$ \'e regular. Seja $k$ a constante
              do lema do bombeamento, e seja $z={\tt 0}^k{\tt 1}^{k+1}$. Como $z\in L$
              e $|z|>k$, o lema do bombeamento diz que existem $u$, $v$ e $w$ tais que
              $z=uvw$, $|uv|\leq k$, $|v|>0$ e $uv^iw\in L$ para todo $i\geq 0$. Sejam,
              ent\~ao, $u$, $v$ e $w$ tais que $z=uvw$, $|uv|\leq k$ e $|v|>0$. Neste
              caso, $uv^2w={\tt 0}^{k+|v|}{\tt 1}^{k+1}$, j\'a que $|uv|\leq k$. E
              ${\tt 0}^{k+|v|}{\tt 1}^{k+1}$ \'e da forma $x{\tt 1}y$, mas com
              $n_0(x)=k+|v|$ e $n_1(y)\leq k$; como $|v|>0$, n\~ao se pode ter
              $n_0(x)=n_1(y)$. Logo, $uv^2w\not\in L$, o que contraria o
              lema do bombeamento. Portanto, $L$ n\~ao \'e regular.


        \item $\{x{\tt 1}y\in \{{\tt 0},{\tt 1}\}^*\,|\,n_0(x)
               \mbox{ \'e par e } n_1(y) \mbox{ \'e \'{\i}mpar}\}$.

              {\em Solu\c c\~ao\/}:\footnote{Os aut\^omatos s\~ao apresentados aqui
              no formato tabular apenas por conveni\^encia. Na verdade, prefiro o
              formato gr\'afico nas provas e exerc\'{\i}cios.}
                     Um AFN para tal linguagem seria
                     $(\{p_0,i_0,p_1,i_1\},\{{\tt 0},{\tt 1}\},\delta,\{p_0\},\{i_1\})$,
              onde $\delta$ \'e dada por:
              \begin{center}
                     \begin{tabular}{c|cc}
                      $\delta$ & {\tt 0} & {\tt 1} \\ \hline
                        $p_0$ & $\{i_0\}$ & $\{p_0,p_1\}$ \\
                        $i_0$ & $\{p_0\}$ & $\{i_0\}$ \\
                        $p_1$ & $\{p_1\}$ & $\{i_1\}$ \\
                        $i_1$ & $\{i_1\}$ & $\{p_1\}$ \\
                      \end{tabular}
              \end{center}
       \end{list}

 \item Seja $L=\{{\tt a}^m{\tt b}^n\,|\, 0\leq m\leq 3 \mbox{ e } 1\leq n\leq 3\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFN que reconhe\c ca $L$. Ele dever\'a ter o
              menor n\'umero de estados e transi\c c\~oes poss\'{\i}vel.
              Lembre-se: (i) um AFN n\~ao pode ter transi\c c\~oes $\lambda$;
              (ii) um AFN pode ter v\'arios estados iniciais.

              {\em Solu\c c\~ao\/}: Um AFN para $L$ seria
                     \[(\{3a,2a,1a,0a,1b,2b,3b\},\{{\tt a},{\tt b}\},\delta_1,\{3a,2a,1a,0a\}
                     ,\{1b,2b,3b\})\mbox{,}\]
              onde $\delta_1$ \'e dada por:
              \begin{center}
                     \begin{tabular}{c|cc}
                      $\delta_1$ & {\tt a} & {\tt b} \\ \hline
                        $3a$ & $\{2a\}$ & $\{\}$ \\
                        $2a$ & $\{1a\}$ & $\{\}$ \\
                        $1a$ & $\{0a\}$ & $\{\}$ \\
                        $0a$ & $\{\}$ & $\{1b\}$ \\
                        $1b$ & $\{\}$ & $\{2b\}$ \\
                        $2b$ & $\{\}$ & $\{3b\}$ \\
                        $3b$ & $\{\}$ & $\{\}$
                      \end{tabular}
              \end{center}
        \item Construa um AFD que reconhe\c ca $L$.

              {\em Solu\c c\~ao\/}: Um AFD para $L$ seria
                     \[(\{3a,2a,1a,0a,1b,2b,3b\},\{{\tt a},{\tt b}\},\delta_2,3a,
                      \{1b,2b,3b\})\mbox{,}\]
              onde $\delta_2$ \'e dada por:
              \begin{center}
                     \begin{tabular}{r|cc}
                      $\delta_2$ & {\tt a} & {\tt b} \\ \hline
                        $3a$ & $2a$ & $1b$ \\
                        $2a$ & $1a$ & $1b$ \\
                        $1a$ & $0a$ & $1b$ \\
                        $0a$ & $e$ & $1b$ \\
                        $1b$ & $e$ & $2b$ \\
                        $2b$ & $e$ & $3b$ \\
                        $3b$ & $e$ & $e$ \\
                         $e$ & $e$ & $e$
                      \end{tabular}
              \end{center}
        \item Construa um AFD que reconhe\c ca $\mbox{\em suf\/}(L)=\{y\,|\,xy\in L\}$.

              {\em Solu\c c\~ao\/}: Um AFD seria
                     \[(\{3a,2a,1a,0a,1b,2b,3b\},\{{\tt a},{\tt b}\},\delta_3,3a,
                      \{3a,1b,2b,3b\})\mbox{,}\]
              onde $\delta_3=\delta_2$.

       \end{list}

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item se $L^*$ \'e linguagem regular, ent\~ao $L$ \'e linguagem regular.

              {\em Solu\c c\~ao\/}: N\~ao. Exemplo: $\{{\tt 1}^{n^2}\,|\,n\geq 0\}$ n\~ao \'e regular e
              $\{{\tt 1}^{n^2}\,|\,n\geq 0\}^*=\{{\tt 1}\}^*$ \'e regular.

        \item se $L^*$ n\~ao \'e linguagem regular, ent\~ao $L$ n\~ao \'e
              linguagem regular.

              {\em Solu\c c\~ao\/}: Sim. Como as linguagens regulares s\~ao fechadas sob
              fecho de Kleene, n\~ao pode ser o caso de que $L^*$ n\~ao seja regular e $L$
              seja.

        \item se $L_1L_2$ n\~ao \'e linguagem regular, ent\~ao $L_1$ e $L_2$
              n\~ao s\~ao linguagens regulares.

              {\em Solu\c c\~ao\/}: N\~ao. Exemplo: seja $L$ n\~ao regular; ent\~ao $L\{\lambda\}$
              n\~ao \'e regular e, no entanto, $\{\lambda\}$ \'e regular.

       \end{list}

\end{enumerate}

\end{document}
\begin{enumerate}
