\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}
 
\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} \hfill Entrega: at\'e 24/11/03

\vspace*{5mm}
\noindent\ \hrulefill \       

\vspace*{2mm} 
\noindent {\bf Observa\c{c}\~oes:}
\begin{itemize}
 \item {\bf O trabalho \'e individual.}

 \item Cada quest\~ao vale 1,5 pontos.

 \item A interpreta\c c\~ao de cada quest\~ao faz parte do trabalho. Caso alguma
       quest\~ao esteja amb\'{\i}gua ou incorreta, ou caso falte(m) elemento(s)
       importante(s) para o seu entendimento, fa\c ca as suposi\c c\~oes e/ou
       corre\c c\~oes que achar convenientes {\bf e explicite-as}.

 \item Na corre\c{c}\~ao de cada quest\~ao ser\'a analisado se a mesma
       foi respondida com {\bf rigor}, {\bf clareza} e {\bf objetividade}. O
       aluno perder\'a pontos nas seguintes situa\c{c}\~oes, por exemplo, {\it
       mesmo se sua resposta estiver correta\/}:
       \begin{itemize}
        \item usa frases incoerentes, ou sem sentido, ou incorretas, ou que nada
              tenham a ver com o que foi perguntado;
        \item apresenta uma solu\c{c}\~ao sem apresentar a(s) id\'eia(s)
              subjacente(s), dificultando a corre\c{c}\~ao;
        \item apresenta uma solu\c c\~ao conceitualmente deselegante;
        \item \'e prolixo, escrevendo coisas desnecess\'arias ao entendimento
              da solu\c c\~ao.
       \end{itemize}
       Dependendo do ``grau'' de tais impropriedades, o aluno pode at\'e perder
       todos os pontos relativos \`a quest\~ao.

 \item Devolu\c c\~ao: at\'e as 16:00 horas do dia 24/11/2003, na sala 4023, ou em
       meu escaninho na Recep\c c\~ao do DCC, ou via {\it email\/}.
\end{itemize}

\vspace*{2mm}
\noindent\ \hrulefill \       

\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'\/}$.

 \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}

\begin{figure}
   \centering
   \includegraphics[width=1.0\textwidth]{19.pdf}
   \caption{page 19}
\end{figure}

\begin{figure}
   \centering
   \includegraphics[width=1.0\textwidth]{20.pdf}
   \caption{page 20}
\end{figure}

\begin{figure}
   \centering
   \includegraphics[width=1.0\textwidth]{21.pdf}
   \caption{page 21}
\end{figure}

\end{document}
