\documentclass[11pt, a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{fullpage}
\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\newcounter{conta}

\begin{document}

\vspace*{5mm}
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2012 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova/Turma N}/Solução do professor \hfill {\bf 08/05/2012}

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Seja o AFN com o diagrama de estados:

       \begin{picture}(120,20)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=270](1)(20,10){1}
        \node(2)(40,10){2}
        \node[Nmarks=i, iangle=270](3)(60,10){3}
        \node[Nmarks=r](4)(80,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=90](2){{\tt 1}}
        \drawloop[loopangle=90](3){{\tt 0}}
        \drawloop[loopangle=90](4){{\tt 0}}
       \end{picture}

       Obtenha o diagrama de estados de um AFD equivalente usando o método visto em aula (\emph{subset construction}).}


       \textit{Solução}:

       \begin{picture}(120,40)
        \gasset{Nw=10, Nh=6, Nmr=4, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](13)(20,20){13}
        \node(23)(40,30){23}
        \node[Nmarks=r](14)(40,10){14}
        \node[Nmarks=r](24)(60,20){24}
        \node[Nmarks=r](134)(80,20){134}
        \node[Nmarks=r](234)(100,20){234}

        \drawedge[curvedepth=3](13,23){{\tt 0}}
        \drawedge[curvedepth=3, ELside=r](13,14){{\tt 1}}
        \drawedge[curvedepth=3, ELside=r](23,13){{\tt 0}}
        \drawedge[curvedepth=3](23,24){{\tt 1}}
        \drawedge[curvedepth=3](14,13){{\tt 1}}
        \drawedge[curvedepth=0, ELside=r](14,24){{\tt 0}}
        \drawedge[curvedepth=3](24,23){{\tt 1}}
        \drawedge[curvedepth=0](24,134){{\tt 0}}
        \drawloop[loopangle=90](134){{\tt 1}}
        \drawedge[curvedepth=4](134,234){{\tt 0}}
        \drawloop[loopangle=90](234){{\tt 1}}
        \drawedge[curvedepth=4](234,134){{\tt 0}}
       \end{picture}

 \item {\footnotesize Seja o AFN$\lambda$ com o diagrama de estados:

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

        \drawedge[curvedepth=2](1,2){$\lambda$,{\tt b}}
        \drawedge(1,3){$\lambda$}
        \drawedge[curvedepth=2](2,1){{\tt a}}
        \drawedge(2,4){{\tt b}}
        \drawloop[loopangle=270](3){{\tt b}}
        \drawedge(3,5){{\tt a}}
        \drawedge(4,5){$\lambda$}
        \drawedge[curvedepth=2](5,6){{\tt a}}
        \drawedge[curvedepth=2](6,5){{\tt a}}
       \end{picture}

       Obtenha o diagrama de estados de um AFN equivalente \textbf{utilizando o método visto em aula}.
       Para cada $(e,s)$ tal que $s\not=\lambda$ e $\delta'(e,s)\not=\delta(e,s)$ indique o c\'alculo de
       $\delta'(e,s)$. ($\delta$ é a função de transi\c{c}\~ao do AFN$\lambda$ e $\delta'$ a do AFN obtido.)}

       \textit{Solução}:

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

        \drawedge[curvedepth=2](1,2){{\tt b}}
        \drawedge[curvedepth=2](2,1){{\tt a}}
        \drawedge(2,3){{\tt a}}
        \drawedge(2,4){{\tt b}}
        \drawedge(2,5){{\tt b}}
        \drawloop[loopangle=70](2){{\tt a}}
        \drawloop[loopangle=270](3){{\tt b}}
        \drawedge(3,5){{\tt a}}
        \drawedge[curvedepth=2](5,6){{\tt a}}
        \drawedge[curvedepth=2](6,5){{\tt a}}
        
        \put(60,-1){\makebox(0,0)[l]{$\delta'(2,{\tt a})=f\lambda(\delta(2,{\tt a}))=f\lambda(\{1\})=\{1,2,3\}$}}
        \put(60,-7){\makebox(0,0)[l]{$\delta'(2,{\tt b})=f\lambda(\delta(2,{\tt b}))=f\lambda(\{4\})=\{4,5\}$}}
       \end{picture}

\pagebreak
 \item {\footnotesize Encontre expressões regulares que denotem:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(\{{\tt 00},{\tt 11}\}\cup\{{\tt 01},{\tt 10}\}\{{\tt 00},{\tt 11}\}^*\{{\tt 01},{\tt 10}\})^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^+\,|\,\eta(w) \textit{ mod } 3 = 0\}$, sendo $\eta(w)$ o número representado
              por $w$ na base 2.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(00+11+(01+10)(00+11)^*(01+10))^*$.
        \item AF que reconhece a linguagem:

              \begin{picture}(120,30)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

               \node[Nmarks=i, iangle=180](i)(20,5){i}
               \node[Nmarks=r](0)(20,20){0}
               \node(1)(40,20){1}
               \node(2)(60,20){2}

              \drawedge[curvedepth=0](i,0){0}
              \drawedge[curvedepth=-6, ELside=r](i,1){1}
              \drawloop[loopangle=90](0){0}
              \drawedge[curvedepth=3](0,1){1}
              \drawedge[curvedepth=3](1,0){1}
              \drawedge[curvedepth=3](1,2){0}
              \drawedge[curvedepth=3](2,1){0}
              \drawloop[loopangle=90](2){1}
             \end{picture}

       Eliminando-se o estado 2, e depois o estado 1, obtém-se:

             \begin{picture}(120,30)
              \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

              \node[Nmarks=i, iangle=180](i)(20,5){i}
              \node[Nmarks=r](0)(20,20){0}
              \node(1)(40,20){1}

              \drawedge[curvedepth=0](i,0){0}
              \drawedge[curvedepth=-6, ELside=r](i,1){1}
              \drawloop[loopangle=90](0){0}
              \drawedge[curvedepth=3](0,1){1}
              \drawedge[curvedepth=3](1,0){1}
              \drawloop[loopangle=0](1){$01^*0$}

              \node[Nmarks=i, iangle=180](ix)(90,5){i}
              \node[Nmarks=r](0x)(90,20){0}

              \drawedge[curvedepth=0](ix,0x){$0+1(01^*0)^*1$}
              \drawloop[loopangle=0](0x){$0+1(01^*0)^*1$}

             \end{picture}

             Obtém-se, então, a expressão $(0+1(01^*0)^*1)^+$.
       \end{list}

 \item {\footnotesize Sejam as seguintes linguagens de alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{itemize}
        \item $L_1=\{{\tt 0}^n \,|\, n\geq 1000\}$ (regular)
        \item $L_2=\{{\tt 0}^n{\tt 1}^k \,|\, n\geq k\}$ (não regular)
        \item $L_3=\{{\tt 0}^n \,|\, n \mbox{ é número primo}\}$ (não regular)
       \end{itemize}
       Mostre que é regular ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L_2-L_1$. %Resp: não regular, pois L1 contida em L2; logo, (L2-L1) U L1 = L2.
        \item $L_3-L_1$. %Resp: regular, pois é finita.
       \end{list}}

       \textit{Solução}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Como $L_1\subset L_2$, $(L_2-L_1)\cup L_1=L_2$. Como as linguages regulares são fechadas sob união,
              se $L_2-L_1$ fosse regular, como $L_1$ é regular, então $L_2$ teria que ser regular. Mas $L_2$ não é
              regular. Logo, \textbf{$L_2-L_1$ não é regular}.
        \item $L_3-L_1=\{{\tt 0}^n\,|\, n \mbox{ é primo e } n<1000\}$. Tal linguagem é finita. Logo \textbf{é regular}.
       \end{list}

\end{enumerate}

\end{document}
