\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\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2011 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
{\bf Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: 10/05/2011

\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 O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$, de dois ou mais s\'{\i}mbolos,
              em que o \'ultimo s\'{\i}mbolo seja idêntico ao 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 duas vezes.
        \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.
        \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,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}).

 \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 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$ é par}\}$
        \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$. \textit{Dica}: obtenha antes um AFN$\lambda$ e depois converta-o para
       um AFN.

\pagebreak
 \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$,{\tt b},{\tt c}}
        \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}

       Construa um AFN equivalente a $M$ usando o m\'etodo visto em aula.

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares,
       usando o lema do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{n}{\tt 1}^{2n}\,|\, n\geq 0\}$.
        \item $\{x{\tt \#}x\,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$.
       \end{list}

 \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\'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=0\}$, sendo
       $\eta(w)$ o n\'umero representado por $w$ na base dois.
       \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\~oes regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\geq 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 em que a subpalavra {\tt 01} ocorre um n\'umero par de vezes.
        \item O conjunto das palavras que n\~ao contêm a subpalavra
              {\tt 0101}.
       \end{list}

\end{enumerate}

\end{document}
