\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
{\bf Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: 30/09/2010

\begin{enumerate}

 \item Construa AFNs para as seguintes linguagens, com o {\em menor n\'umero de
       estados e de transi\c c\~oes\/} que conseguir:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ tem pelo menos uma
              ocorr\^encia de {\tt aba} ou de {\tt bcb} ou de {\tt cac}$\}$.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$,
              de tr\^es ou mais s\'{\i}mbolos, em que o \'ultimo s\'{\i}mbolo
              seja diferente do primeiro.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$ em que o
              \'ultimo s\'{\i}mbolo tenha ocorrido antes no m\'{\i}nimo uma vez.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$ em que o
              \'ultimo s\'{\i}mbolo tenha ocorrido antes no m\'aximo duas vezes.
       \end{list}
 
 \item Seja o AFN com o diagrama de estados a seguir:

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

        \drawedge[curvedepth=4](1,2){{\tt 0}}
        \drawedge[curvedepth=4](2,1){{\tt 0}}
        \drawedge[curvedepth=0](2,3){{\tt 0}}
        \drawedge[curvedepth=4](3,4){{\tt 1}}
        \drawedge[curvedepth=4](4,3){{\tt 1}}
        \drawloop[loopangle=90](1){{\tt 1}}
        \drawloop[loopangle=270](3){{\tt 0}}
        \drawloop[loopangle=270](4){{\tt 0}}
       \end{picture}

       Construa um AFD equivalente usando o m\'etodo visto em aula
       (\textit{subset construction}). Em seguida, minimize o AFD
       constru\'{\i}do.

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

 \item Seja o AFN$\lambda$ $M$:

       \begin{picture}(120,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](A)(20,30){A}
        \node(B)(40,30){B}
        \node(C)(20,10){C}
        \node[Nmarks=r](D)(40,10){D}
        \node[Nmarks=r](E)(60,10){E}

        \drawedge[curvedepth=0](A,B){$\lambda$}
        \drawedge[curvedepth=0](B,D){$\lambda$}
        \drawedge[curvedepth=0](A,C){$\lambda$}
        \drawedge[curvedepth=0](C,D){$\lambda$}
        \drawedge[curvedepth=0](D,E){$\lambda$}
        \drawloop[loopangle=90](A){{\tt a}}
        \drawloop[loopangle=0](B){{\tt b}}
        \drawloop[loopangle=180](C){{\tt c}}
        \drawloop[loopangle=270](D){{\tt d}}
        \drawloop[loopangle=270](E){{\tt a}}
       \end{picture}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa um AFN $N$, equivalente a $M$, usando o m\'etodo visto
              em aula.
        \item A partir do AFN $N$, construa uma express\~ao regular que
              denote a linguagem reconhecida.
       \end{list}

 \item Prove que $\{{\tt 10}^n{\tt 1}^{n}\,|\, n\geq 1\}$ n\~ao \'e 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 $\{x{\tt 1}^n\,|\, n\geq 0, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e }
              |x|=n\}$.
        \item $\{{\tt 0}^m{\tt 1}^{n}\,|\, m\not=n\}$.
        \item $\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o n\'umero de {\tt 0}s
              em $w$ \'e par e o de {\tt 1}s \'e primo}\}$.
       \end{list}

 \item Sejam as linguagens
       $L_1=\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}$ e
       $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\eta(w) \mbox{ mod } 3\not=0\}$, sendo
       $\eta(w)$ o n\'umero representado por $w$ na base dois.
       Construa um aut\^omato finito para $L_1-L_2$.

 \item Seja $L$ uma linguagem regular sobre um alfabeto $\Sigma_1$. Prove que
       o conjunto das palavras sobre $\Sigma_2$ (que pode ser igual ou n\~ao a
       $\Sigma_1$) que t\^em como sufixo alguma palavra de $L$ \'e regular.

 \item Encontre express\~oes regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\in \{0,1,3\}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em um, dois ou tr\^es
              {\tt b}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o n\'umero de {\tt a}s
               mais o de {\tt b}s em $w$ \'e par$\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em o s\'{\i}mbolo
              \verb+1+ e $\eta(w) \mbox{ mod } 3=0\}$.
       \end{list}

 \item Obtenha express\~oes regulares que denotem as linguagens sobre
       $\{{\tt 0},{\tt 1}\}$ a seguir, a partir de AFs que reconhe\c cam as
       mesmas, usando o m\'etodo visto em aula. N\~ao simplifique as ERs.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que come\c{c}am com {\tt 1}, terminam com
              {\tt 1} e t\^em algum {\tt 0}.
        \item O conjunto das palavras que n\~ao cont\'em a subpalavra
              {\tt 0101}.
       \end{list}

\end{enumerate}

\end{document}
