\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 W}/Solução do professor \hfill {\bf 08/05/2012}

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

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

        \drawedge[curvedepth=0](1,3){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt a}}
        \drawedge[curvedepth=0](3,4){{\tt b},{\tt c}}
        \drawloop[loopangle=90](1){{\tt a},{\tt b}}
        \drawloop[loopangle=270](2){{\tt a},{\tt c}}
       \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}(100,40)
        \gasset{Nw=8, Nh=6, Nmr=4, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](12)(20,25){12}
        \node(1)(40,40){1}
        \node(123)(40,25){123}
        \node(2)(40,10){2}
        \node[Nmarks=r](14)(60,32.5){14}
        \node[Nmarks=r](24)(60,17.5){24}
        \node(13)(80,32.5){13}
        \node(23)(80,17.5){23}
        \node[Nmarks=r](4)(100,25){4}

        \drawedge[curvedepth=0](12,1){{\tt b}}
        \drawedge[curvedepth=0](12,123){{\tt a}}
        \drawedge[curvedepth=0](12,2){{\tt c}}
        \drawloop[loopangle=90](1){{\tt b}}
        \drawedge[curvedepth=7](1,13){{\tt a}}
        \drawloop[loopangle=90](123){{\tt a}}
        \drawedge[curvedepth=0](123,14){{\tt b}}
        \drawedge[curvedepth=0](123,24){{\tt c}}
        \drawloop[loopangle=90](2){{\tt c}}
        \drawedge[curvedepth=-7,ELside=r](2,23){{\tt a}}
        \drawedge[curvedepth=0,ELside=r](14,1){{\tt b}}
        \drawedge[curvedepth=3](14,13){{\tt a}}
        \drawedge[curvedepth=0](24,2){{\tt c}}
        \drawedge[curvedepth=3](24,23){{\tt a}}
        \drawloop[loopangle=90](13){{\tt a}}
        \drawedge[curvedepth=3](13,14){{\tt b}}
        \drawedge[curvedepth=0](13,4){{\tt c}}
        \drawloop[loopangle=270](23){{\tt a}}
        \drawedge[curvedepth=3](23,24){{\tt c}}
        \drawedge[curvedepth=0](23,4){{\tt b}}
       \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=ir, iangle=180](1)(20,20){1}
        \node(2)(35,30){2}
        \node(3)(35,10){3}
        \node(4)(50,20){4}
        \node[Nmarks=r,iangle=180](5)(70,20){5}

        \drawloop[loopangle=90](1){{\tt a}}
        \drawedge[curvedepth=0](1,2){$\lambda$}
        \drawedge[curvedepth=0,ELside=r](1,3){$\lambda$}
        \drawloop[loopangle=90](2){{\tt b}}
        \drawedge[curvedepth=0](2,4){{\tt a}}
        \drawloop[loopangle=270](3){{\tt c}}
        \drawedge[curvedepth=0,ELside=r](3,4){{\tt a}}
        \drawloop[loopangle=90](4){{\tt a}}
        \drawedge[curvedepth=0](4,5){$\lambda$}
        \drawloop[loopangle=0](5){{\tt b},{\tt c}}
       \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,37)(10,0)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=ir, iangle=180](1)(20,20){1}
        \node[Nmarks=i, iangle=135](2)(35,30){2}
        \node[Nmarks=i, iangle=225](3)(35,10){3}
        \node(4)(50,20){4}
        \node[Nmarks=r,iangle=180](5)(70,20){5}

        \drawloop[loopangle=90](1){{\tt a}}
        \drawedge[curvedepth=0](1,2){\tt a}
        \drawedge[curvedepth=0,ELside=r](1,3){\tt a}
        \drawloop[loopangle=90](2){{\tt b}}
        \drawedge[curvedepth=0](2,4){{\tt a}}
        \drawedge[curvedepth=8](2,5){{\tt a}}
        \drawloop[loopangle=270](3){{\tt c}}
        \drawedge[curvedepth=0,ELside=r](3,4){{\tt a}}
        \drawedge[curvedepth=-8,Elside=r](3,5){{\tt a}}
        \drawloop[loopangle=90](4){{\tt a}}
        \drawedge[curvedepth=0](4,5){\tt a}
        \drawloop[loopangle=0](5){{\tt b},{\tt c}}
        
        \put(85,30){\makebox(0,0)[l]{$\delta'(1,{\tt a})=f\lambda(\delta(1,{\tt a}))=f\lambda(\{1\})=\{1,2,3\}$}}
        \put(85,24){\makebox(0,0)[l]{$\delta'(2,{\tt a})=f\lambda(\delta(2,{\tt a}))=f\lambda(\{4\})=\{4,5\}$}}
        \put(85,18){\makebox(0,0)[l]{$\delta'(3,{\tt a})=f\lambda(\delta(3,{\tt a}))=f\lambda(\{4\})=\{4,5\}$}}
        \put(85,12){\makebox(0,0)[l]{$\delta'(4,{\tt a})=f\lambda(\delta(4,{\tt a}))=f\lambda(\{4\})=\{4,5\}$}}
       \end{picture}

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

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(11+10(00)^*01)^*(0+11+10(00)*1)$.
        \item AF que reconhece a linguagem:
        
              \begin{picture}(120,20)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

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

              \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:
        
              \begin{picture}(120,23)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

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

              \drawloop[loopangle=90](0){0}
              \drawedge[curvedepth=3](0,1){1}
              \drawedge[curvedepth=3](1,0){1}
              \drawloop[loopangle=90](1){$01^*0$}
             \end{picture}

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

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

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Como $L_1\subset L_3$, $L_1\cup L_3=L_3$. Logo, $L_1\cup L_3$ \textbf{não é regular}.
        \item Como $L_3\subset L_2$, $L_2\cup L_3=L_2$. Portanto, $L_2\cup L_3$ \textbf{é regular}.
       \end{list}
\end{enumerate}

\end{document}
