\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}

%\vspace*{2cm}
\noindent {\it Fundamentos da Teoria da Computação}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012 \\
Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
{\bf Segunda Lista de Exercícios} \hfill Entrega: até 7/5/2011 às 18h

\vspace*{2mm}
\noindent \textbf{\underline{Importante}:}
\begin{quote}
 \textbf{Questões ilegíveis não serão corrigidas (nota zero).\\
 Quem copiar ou deixar copiar uma questão terá nota zero na lista. \\
 Locais de recebimento: salas 3018, 4010 e 4023. \\
 Após as 18h do dia 7/5 começa o primeiro dia de atraso.}
\end{quote}


\begin{enumerate}
 \item Construa AFNs para as seguintes linguagens, com o \emph{menor número de estados} que conseguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras de $\{{\tt a},{\tt b}\}^*$ em que o último símbolo (se houver)
              seja idêntico ao primeiro (se houver). Note que $\lambda$, {\tt a} e {\tt b} são palavras da linguagem.
        \item O conjunto das palavras de $\{{\tt a},{\tt b}\}^*$ em que o último símbolo tenha ocorrido antes. Cada
              palavra da linguagem tem no mínimo dois símbolos.
        \item O conjunto das palavras de $\{{\tt a},{\tt b}\}^*$ em que o último símbolo (caso exista) tenha ocorrido
              antes no máximo uma vez.
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{{\tt 1}}(x) \mbox{ mod } 3=1 \mbox{ e }
              n_{{\tt 0}}(y) \mbox{ mod } 3=1\}$ onde $n_s(w)$ é o número de ocorrências
              do símbolo $s$ na palavra $w$.
       \end{list}
 
 \item Seja o AFN com o diagrama de estados a seguir:

       \begin{picture}(120,22)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(20,10){1}
        \node[Nmarks=ir, iangle=270](3)(40,10){3}
        \node[Nmarks=ir, iangle=0](2)(60,10){2}

        \drawedge[curvedepth=0](1,3){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt b}}
        \drawloop[loopangle=90](1){{\tt b}}
        \drawloop[loopangle=90](2){{\tt a}}
       \end{picture}

       Construa um AFD equivalente usando o m\'etodo visto em aula (\textit{subset construction}). Apresente apenas
       seu diagrama de estados, com cada estado do AFD nomeado com os estados respectivos do AFN e com estados de erro,
       se houver.

 \item Obtenha um AFN $K$ com um único estado inicial, equivalente ao AFN da
       quest\~ao anterior, {\em que contenha todos os estados e transi\c{c}\~oes
       lá contidos}. Em seguida, obtenha uma gramática regular para $L(K)$
       usando o m\'etodo visto em aula.

 \item Sejam as linguagens:
       \begin{itemize}
        \item $A=\{w\in\{{\tt a},{\tt b}\}^*\,|\,\mbox{o número de {\tt a}s em $w$ é par}\}$
        \item $B=\{w\in\{{\tt b},{\tt c}\}^*\,|\,\mbox{o número de {\tt b}s em $w$ é ímpar}\}$
        \item $C=\{w\in\{{\tt a},{\tt c}\}^*\,|\,\mbox{o número de {\tt c}s em $w$ é par}\}$
       \end{itemize}
       Obtenha um AFN $M$ tal que $L(M)=ABC$ assim:
       \begin{enumerate}
        \item obtenha AFDs para $A$, $B$ e $C$;
        \item obtenha um AFN$\lambda$ para $ABC$ a partir dos três AFDs;
        \item converta o AFN$\lambda$ para um AFN equivalente usando o método visto em aula.
       \end{enumerate}

\pagebreak
 \item Prove que $\{x{\tt \#}x^R\,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$ não é linguagem regular usando o lema do bombeamento.

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares,
       usando propriedades de fecho:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^m{\tt 1}^{n}\,|\, m\not=n\}$.
        \item $\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o número de {\tt 0}s
              em $w$ \'e par e o de {\tt 1}s \'e primo}\}$.
       \end{list}

 \item Sejam as linguagens $L_1=\{w\in\{{\tt 0},{\tt 1}\}^+\,|\,\eta(w) \mbox{ mod } 3=0\}$, sendo $\eta(w)$ o número
       representado por $w$ na base dois, e $L_2=\{{\tt 1}\}^*(\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*)^*$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que $L_1-L_2$ \'e regular usando propriedades de fecho.
        \item Construa um aut\^omato finito para $L_1-L_2$.
       \end{list}

 \item Encontre expressões regulares que denotem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 1}\}^*(\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*)^*$
        \item A linguagem $ABC$ da questão 4.
        \item A linguagem $\{x{\tt \#}x^R\,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$ da questão 5.
       \end{list}

 \item Encontre express\~oes regulares para as linguagens da questão 1.

\end{enumerate}

\end{document}
