\documentclass[12pt,a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
%\usepackage[pdftex]{graphicx,color}

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

\begin{document} \footnotesize
 
\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 Trabalho Especial/Solu\c c\~ao do professor}

\vspace*{3mm}

\begin{enumerate}
 \item Segue uma defini\c c\~ao recursiva do conjunto dos pal\'{\i}ndromos
       sobre $\Sigma$, {\em Pal\/}:
       \begin{enumerate}
        \item $\lambda\in\mbox{\em Pal}$;
        \item $a\in\mbox{\em Pal\/}$ para todo $a\in\Sigma$;
        \item se $x\in\mbox{\em Pal\/}$ e $a\in\Sigma$ ent\~ao $axa\in\mbox{\em Pal\/}$;
        \item nenhuma palavra \'e membro de {\em Pal\/}, a menos que possa ser obtida como
              mostrado em a, b e c.
       \end{enumerate}
       O conjunto dos pal\'{\i}ndromos sobre $\Sigma$ pode tamb\'em ser definido
       utilizando-se a opera\c c\~ao {\em reverso\/}:
       $\mbox{\em Pal'\/}=\{w\in\Sigma^*\,|\,w=w^R\}$. A opera\c c\~ao
       reverso, por sua vez pode ser assim definida:
       \begin{enumerate}
        \item $\lambda^R=\lambda$;
        \item $(xa)^R=ax^R$ para quaisquer $x\in\Sigma^*$ e $a\in\Sigma$.
       \end{enumerate}
       Prove que $\mbox{\em Pal\/}=\mbox{\em Pal'\/}$.

       {\em Solu\c c\~ao\/}: Inicialmente, ser\'a provado que
       $\mbox{\em Pal\/}\subseteq\mbox{\em Pal'\/}$. Ser\'a usada indu\c c\~ao sobre
       o n\'umero de aplica\c c\~oes do passo (c) da defini\c c\~ao de $\mbox{\em Pal\/}$.
       As \'unicas palavras de $\mbox{\em Pal\/}$ obtidas sem aplica\c c\~oes do passo
       (c) s\~ao $\lambda$ (passo (a)) e $a$ para cada $a\in\Sigma$ (passo (b)). Tem-se
       que  $\lambda\in\mbox{\em Pal'\/}$, pois $\lambda^R=\lambda$ por (a) da defini\c c\~ao
       de reverso; e $a\in\mbox{\em Pal'\/}$, pois $a^R=a$:
       \begin{tabbing}
        xxxxxx\=$a^R$\=xxxxxxxxxx\= \kill
              \>$a^R$\>$=(\lambda a)^R$ \\
              \>     \>$=a\lambda^R$ \> pela defini\c c\~ao de reverso \\
              \>     \>$=a\lambda$ \> pela defini\c c\~ao de reverso \\
              \>     \>$=a$
       \end{tabbing}
       Seja $x$ uma palavra arbitr\'aria de $\Sigma^*$, e suponha, como hip\'otese de
       indu\c c\~ao, que se $x\in \mbox{\em Pal\/}$ en\~ao $x\in \mbox{\em Pal'\/}$.
       Resta provar, ent\~ao, que para qualquer $a\in\Sigma$ se $axa\in \mbox{\em Pal\/}$ ent\~ao
       $axa\in \mbox{\em Pal'\/}$, ou seja $(axa)^R=axa$, o que \'e feito a seguir:
       \begin{tabbing}
        xxxxxx\=$(axa)^R$\=xxxxxxxxxxxxx\= \kill
              \>$(axa)^R$\>$=a(a x)^R$  \> pela defini\c c\~ao de reverso \\
              \>         \>$=a(x^Ra^R)$ \> pois $(xy)^R=y^Rx^R$ \\
              \>         \>$=(ax^R)a^R$ \\
              \>         \>$=(ax^R)a$   \> pois $a^R=a$, como visto acima\\
              \>         \>$=axa$       \> pela hip\a'otese de indu\c c\~ao
       \end{tabbing}
       Portanto, $\mbox{\em Pal\/}\subseteq\mbox{\em Pal'\/}$.

       Agora ser\'a provado que $\mbox{\em Pal'\/}\subseteq\mbox{\em Pal\/}$. Para isto,
       ser\'a mostrado, por indu\c c\~ao sobre $|w|$ que se $w\in\mbox{\em Pal'\/}$ ent\~ao
       $w\in\mbox{\em Pal\/}$. A \'unica palavra de tamanho 0 \'e $\lambda$; e
       $\lambda\in\mbox{\em Pal\/}$, por defini\c c\~ao. Suponha, como hip\'otese de
       indu\c c\~ao, que se $x\in \mbox{\em Pal'\/}$ en\~ao $x\in \mbox{\em Pal\/}$ para
       palavras $x$ tais que $|x|\leq n$. Basta ent\~ao mostrar que se $|w|=n+1$ e
       $w\in \mbox{\em Pal'\/}$ en\~ao $w\in \mbox{\em Pal\/}$. Se $|w|=1$, $w\in\mbox{\em Pal\/}$
       pela defini\c c\~ao. Suponha que $|w|\geq 2$. Ent\~ao $w=axb$ para algum $a,b\in\Sigma$.
       Como $w\in\mbox{\em Pal'\/}$, $w^R=w$. Mas $w^R=(axb)^R=b(xb)^R$ pela defini\c c\~ao de
       reverso. Mas $axb$ (que \'e $w$) s\'o pode ser igual a $b(xb)^R$ (que \'e $w^R$),
       se $a=b$; logo, $w=axa$. Tem-se tamb\'em que:
       \begin{tabbing}
        xxxxxx\=$w^R$\=xxxxxxxxxxxxx\= \kill
              \>$w^R$\>$=(a xa)^R$         \\
              \>         \>$=a(ax)^R$   \> pela defini\c c\~ao de reverso\\
              \>         \>$=ax^Ra^R$   \> pois $(xy)^R=y^Rx^R$ \\
              \>         \>$=ax^Ra$     \> pois $a^R=a$, como visto acima
       \end{tabbing}
       Como $w^R=w$, segue-se que $x^R=x$; logo, $x\in\mbox{\em Pal'\/}$. Como $|x|\leq n$,
       tem-se pela hip\'otese de indu\c c\~ao que $x\in \mbox{\em Pal\/}$. Finalmente, pela
       defini\c c\~ao de {\em Pal\/}, $axa=w\in\mbox{\em Pal\/}$.

 \item Seja, para $n\geq 1$ e $b\geq 2$,
       \[L_{n,b}=\{x\in\{0,1,\ldots,b-1\}^*\;|\;\eta_b(x) \;\mbox{\em mod}\; n=0\}\mbox{,}\]
       onde $\eta_b(x)$ \'e o n\'umero representado por $x$ na base $b$. Na Se\c c\~ao
       2.1.2 da apostila foi mostrado um AFD para $L_{6,2}$. Em anexo, segue um trecho
       de Kozen\footnote{Kozen, D.C. {\it Automata and Computability\/}, Springer, 1997.}
       em que \'e mostrado como construir um AFD para $L_{3,2}$, e
       onde est\'a desenvolvida uma prova da corre\c c\~ao de tal AFD. Generalize o
       m\'etodo e a prova para $n$ e $b$ arbitr\'arios.

 \item Seja a linguagem:
       \[L=\{a^ib^jc^k\;|\;i\not=j \;\mbox{\em ou}\; j\not=k\}\mbox{.}\]
       Suponha que na aplica\c c\~ao do lema do bombeamento (LB) para provar que $L$
       n\~ao \'e regular, seja escolhida $z=a^kb^{k!+k}c^{k!+k}$, onde
       $k$ \'e a constante do LB. Descubra a raz\~ao ``misteriosa'' para tal escolha.

 \item Mostre que as linguagens regulares s\~ao fechadas sob a opera\c c\~ao {\em metade\/}:
       \[\mbox{\em metade\/}(L)=\{x\;|\; xy\in L \;\mbox{\em e}\; |x|=|y|\}\mbox{.}\]
       {\em Sugest\~ao\/}: mostre como obter um AF $M'$ tal que $L(M')=\mbox{\em metade\/}(L)$,
       a partir de um AF $M$ para $L$; em seguida, prove que $M'$ reconhece $\mbox{\em metade\/}(L)$.

 \item Construa AFN$\lambda$'s para as linguagens a seguir, usando transi\c c\~oes $\lambda$
       para {\em simplificar\/} a concep\c c\~ao.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que consistem de zero ou mais {\tt a}'s, seguidos
              por zero ou mais {\tt b}'s, seguidos por zero ou mais {\tt c}'s.
        \item O conjunto das palavras que consistem, ou de {\tt 01} repetida uma ou mais
              vezes, ou de {\tt 010} repetida uma ou mais vezes.
        \item O conjunto das palavras de {\tt 0}'s e {\tt 1}'s tais que pelo menos uma
              das dez \'ultimas posi\c c\~oes cont\'em {\tt 1}.
       \end{list}
\end{enumerate}

\end{document}
