\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 2006 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
{\bf Segunda Lista de Exerc\'{\i}cios} \hfill Entrega: 02/10/2006

\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 3 {\tt a}s, ou 3 {\tt b}s,
              ou 3 {\tt c}s$\}$.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$
              em que o \'ultimo s\'{\i}mbolo seja diferente do primeiro.
        \item O conjunto das palavras de $\{{\tt a},{\tt b},{\tt c}\}^*$, exceto $\lambda$,
              em que o \'ultimo s\'{\i}mbolo n\~ao tenha ocorrido antes. (Dica: use v\'arios estados
              iniciais.)
        \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 uma vez.
       \end{list}
 
 \item Seja o AFN com o diagrama de estados a seguir:

       \begin{picture}(100,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)(20,10){3}
        \node[Nmarks=r](4)(40,10){4}

        \drawedge[curvedepth=4](1,2){{\tt 0}}
        \drawedge[curvedepth=4](2,1){{\tt 0}}
        \drawedge[curvedepth=4](3,4){{\tt 1}}
        \drawedge[curvedepth=4](4,3){{\tt 1}}
        \drawloop[loopangle=90](1){{\tt 1}}
        \drawloop[loopangle=90](2){{\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 Seja a gram\'atica $G$:
       \begin{enumerate}
        \item[\ ] $P \,\rightarrow\, {\tt a}P \,|\, {\tt a}A \,|\, {\tt b}B \,|\, {\tt b}C$
        \item[\ ] $A \,\rightarrow\, {\tt a}C$
        \item[\ ] $B \,\rightarrow\, {\tt a}C$
        \item[\ ] $C \,\rightarrow\, {\tt a}C \,|\, {\tt a}$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha um AFN $N$ que reconhe\c{c}a $L(G)$ usando o m\'etodo visto em aula.
        \item Obtenha um AFD equivalente a $N$ usando o m\'etodo visto em aula.
       \end{list}

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

       \begin{picture}(100,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}

        \drawedge[curvedepth=0](A,B){$\lambda$}
        \drawedge[curvedepth=0](B,D){$\lambda$}
        \drawedge[curvedepth=0](A,C){$\lambda$}
        \drawedge[curvedepth=0](C,D){$\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}}
       \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 os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando o lema
       do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^k{\tt 1}^{2k}\,|\, k\geq 1\}$.
        \item $\{x{\tt 1}^n\,\,|\,\, n\geq 0, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|=n\}$.
        \item $\{{\tt 0}^k{\tt 1}^n{\tt 0}^k\,|\, k,n\geq 0\}$.
       \end{list}

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes
       opera\c c\~oes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pf\/}(L)=\{x \,|\, xy\in L\}$ (os prefixos das palavras de $L$).
        \item $\mbox{\em sf\/}(L)=\{y \,|\, xy\in L\}$ (os sufixos das palavras de $L$).
        \item $\mbox{\em pm\/}(L)=\{x \,|\, xy\in L$ e $|x|=|y|\}$ (as primeiras
              metades das palavras de $L$).
       \end{list}

 \item Seja $L$ uma linguagem {\bf n\~ao} regular, $R$ uma regular e
       $F$ uma linguagem finita. Mostre que \'e sempre regular, sempre
       n\~ao regular, ou nenhum dos dois (ou seja, \`as vezes \'e regular
       e \`as vezes n\~ao):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L-F$.
        \item $L-R$.
        \item $LF$.
        \item $LR$.
        \item $F^*$.
        \item $L^*$.
       \end{list}

 \item Encontre express\~oes regulares e gram\'aticas regulares para as
       seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\in \{0,2,4\}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em apenas um ou dois {\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 a},{\tt b},{\tt c}\}^*\,|\, w$ n\~ao termina com \verb+cc+$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em \verb+b+ e $|w| \mbox{ mod } 3=1\}$.
       \end{list}

 \item Obtenha express\~oes regulares que denotem as linguagens sobre $\{{\tt 0},{\tt 1}\}$
       abaixo, 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 {\tt 0}s s\'o podem ocorrer nas posic{c}\~oes
              pares.
        \item O conjunto das palavras com pelo menos um s\'{\i}mbolo em que os {\tt 0}s,
              se houver algum {\tt 0}, precedem os {\tt 1}s, se houver algum {\tt 1}.
        \item O conjunto das palavras que n\~ao cont\'em a subpalavra {\tt 000}.
       \end{list}

 \item Mostre que os seguintes problemas s\~ao decid\'{\i}veis, se $G_1$ e $G_2$ s\~ao
       gram\'aticas regulares quaisquer:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(G_1)=\emptyset$?
        \item $L(G_1)\subseteq L(G_2)$?
       \end{list}

\end{enumerate}

\end{document}
