\documentclass[11pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}
\newcounter{conta}
\usepackage{gastex}
\usepackage[usenames]{color}

\begin{document}

\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Prova/Solu\c{c}\~ao do professor} \hfill {26/04/2007}

\vspace*{1mm}
\noindent \textbf{Dura\c{c}\~ao:} 1 hora e 30 minutos. \\
\noindent \textbf{Valor de cada quest\~ao:} 3 pontos.

\vspace*{2mm}
\begin{enumerate}

\item {\footnotesize Construa um AFN que reconhe\c{c}a a linguagem a seguir usando o
      \textit{menor n\'umero de estados e de transi\c c\~oes\/} que conseguir:
      \[\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, \mbox{ o \'ultimo
      s\'{\i}mbolo de $w$ ocorre antes um n\'umero \'{\i}mpar de
      vezes}\}\mbox{.}\] Observe que o n\'umero \textbf{total} de
      ocorr\^encias do \'ultimo s\'{\i}mbolo \'e par. Suponha tamb\'em que
      $\lambda$ n\~ao \'e palavra da linguagem em quest\~ao.}

      \textit{Solu\c{c}\~ao}:

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

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

 \item {\footnotesize Seja o AFNE com o diagrama de estados:

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

        \drawedge[curvedepth=0](1,3){$\lambda$}
        \drawedge[curvedepth=3](2,4){{\tt bb},{\tt cc}}
        \drawedge[curvedepth=3](4,2){{\tt a}}
        \drawedge[curvedepth=0](4,3){$\lambda$}
        \drawloop[loopangle=90](1){{\tt aa}}
        \drawloop[loopangle=90](3){{\tt ab},{\tt ac}}
       \end{picture}

       Obtenha, em seq\"u\^encia, \underline{usando os m\'etodos vistos em
       aula}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um AFN$\lambda$ equivalente.
        \item Um AFN equivalente.
       \end{list}}

       \textit{Solu\c{c}\~ao}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFN$\lambda$: \\
              \begin{picture}(100,37)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9,
                       loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,20){1}
               \node(1a)(20,32){1a}
               \node[Nmarks=i, iangle=0](2)(80,20){2}
               \node(2b)(70,8){2b}
               \node(2c)(70,32){2c}
               \node[Nmarks=r](3)(40,20){3}
               \node(3a)(40,32){3a}
               \node(4)(60,20){4}

               \drawedge[curvedepth=0](1,3){$\lambda$}
               \drawedge[curvedepth=3](2,2b){{\tt b}}
               \drawedge[curvedepth=3](2b,4){{\tt b}}
               \drawedge[curvedepth=-3, ELside=r](2,2c){{\tt c}}
               \drawedge[curvedepth=-3, ELside=r](2c,4){{\tt c}}
               \drawedge[curvedepth=0](4,2){{\tt a}}
               \drawedge[curvedepth=0](4,3){$\lambda$}
               \drawedge[curvedepth=2](1,1a){\tt a}
               \drawedge[curvedepth=2](1a,1){\tt a}
               \drawedge[curvedepth=2](3,3a){\tt a}
               \drawedge[curvedepth=2](3a,3){{\tt b},{\tt c}}
              \end{picture}

        \item AFN: \\
              \begin{picture}(100,37)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9,
                       loopdiam=4}
               \node[Nmarks=i, iangle=180](1)(20,20){1}
               \node(1a)(20,32){1a}
               \node[Nmarks=i, iangle=0](2)(80,20){2}
               \node(2b)(70,8){2b}
               \node(2c)(70,32){2c}
               \node[Nmarks=ir, iangle=225](3)(40,20){3}
               \node(3a)(40,32){3a}
               \node(4)(60,20){4}

               \drawedge[curvedepth=0](1a,3){\tt a}
               \drawedge[curvedepth=3, ELpos=40](2,2b){{\tt b}}
               \drawedge[curvedepth=3, ELpos=60](2b,4){{\tt b}}
               \drawedge[curvedepth=-3, ELside=r](2,2c){{\tt c}}
               \drawedge[curvedepth=-3, ELside=r](2c,4){{\tt c}}
               \drawedge[curvedepth=0](4,2){{\tt a}}
               \drawedge[curvedepth=3](2b,3){\tt b}
               \drawedge[curvedepth=-3, ELside=r](2c,3){\tt c}
               \drawedge[curvedepth=2](1,1a){\tt a}
               \drawedge[curvedepth=2](1a,1){\tt a}
               \drawedge[curvedepth=2](3,3a){\tt a}
               \drawedge[curvedepth=2, ELpos=45](3a,3){{\tt b},{\tt c}}
              \end{picture}
       \end{list}

 \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}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe o diagrama de estados de um AFN equivalente com
              apenas um estado inicial.
        \item Desenhe o diagrama de estados de um AFN equivalente com
              apenas um estado final.
       \end{list}
       No item (a), o AFN pode ter v\'arios estados finais e no item (b)
       o AFN pode ter v\'arios estados iniciais.}

       \textit{Solu\c{c}\~ao}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFN com um estado inicial: \\
              \begin{picture}(120,37)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9,
                       loopdiam=4}
               \node[Nmarks=r](1)(20,25){1}
               \node(2)(40,25){2}
               \node(3)(60,25){3}
               \node[Nmarks=r](4)(80,25){4}
               \node[Nmarks=ir, iangle=270](i)(50,8){$i$}

               \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}}

               \drawedge[curvedepth=4](i,1){{\tt 1}}
               \drawedge[curvedepth=2](i,2){{\tt 0}}
               \drawedge[curvedepth=-2, ELside=r](i,3){{\tt 0}}
               \drawedge[curvedepth=-4, ELside=r](i,4){{\tt 1}}
              \end{picture}
        \item AFN com um estado final: \\
              \begin{picture}(120,37)
               \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9,
                       loopdiam=4}
               \node[Nmarks=i, iangle=225](1)(20,25){1}
               \node(2)(40,25){2}
               \node[Nmarks=i, iangle=225](3)(60,25){3}
               \node(4)(80,25){4}
               \node[Nmarks=ir, iangle=225](f)(50,8){$f$}

               \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}}

               \drawedge[curvedepth=-4, ELside=r](1,f){{\tt 1}}
               \drawedge[curvedepth=-2, ELside=r](2,f){{\tt 0}}
               \drawedge[curvedepth=2](3,f){{\tt 1}}
               \drawedge[curvedepth=4](4,f){{\tt 0}}
              \end{picture}
       \end{list}

 \item {\footnotesize Para a linguagem reconhecida pelo AFN da quest\~ao anterior:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma gram\'atica regular que a gere.
        \item Obtenha uma express\~ao regular que a denote.
       \end{list}
       Dever\~ao ser usados os m\'etodos de obten\c{c}\~ao de gram\'atica
       regular e de express\~ao regular a partir de aut\^omatos finitos
       vistos em aula.}

       \textit{Solu\c{c}\~ao}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Gram\'atica obtida de 3(a): \\
              \begin{enumerate}
               \item[\ ] $I \,\rightarrow\, {\tt 0}D \,|\, {\tt 0}T \,|\,
                            {\tt 1}U \,|\, {\tt 1}Q \,|\, \lambda$
               \item[\ ] $U \,\rightarrow\, {\tt 0}D \,|\, {\tt 1}U \,|\,
                            \lambda$
               \item[\ ] $D \,\rightarrow\, {\tt 0}T \,|\, {\tt 0}U \,|\,
                            {\tt 1}D$
               \item[\ ] $T \,\rightarrow\, {\tt 0}T \,|\, {\tt 1}Q$
               \item[\ ] $Q \,\rightarrow\, {\tt 0}Q \,|\, {\tt 1}T \,|\,
                            \lambda$
              \end{enumerate}
        \item Acrescentando-se os estados $i$ e $f$ ao AFN original, mais
              as quatro transi\c{c}\~oes $\lambda$:
              \begin{enumerate}
               \item[\ ] $\delta(i,\lambda)=\{1,3\}$
               \item[\ ] $\delta(1,\lambda)=\{f\}$
               \item[\ ] $\delta(4,\lambda)=\{f\}$
              \end{enumerate}
              e eliminando-se os estados 1, 4, 3, 2, nesta ordem, obt\'em-se a
              express\~ao regular:
              \[1^*+(10^*1)^*10^*+1^*0(1+01^*0)^*(0+0(10^*1)10^*)\]
       \end{list}

 \item {\footnotesize Prove que $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)\not=
       n_{\tt c}(w)\}$ n\~ao \'e uma linguagem regular. ($n_s(w)$ \'e o
       n\'umero de s\'{\i}mbolos $s$ na palavra $w$.)}

       \textit{Solu\c{c}\~ao}:

       Seja $L$ a linguagem em quest\~ao e suponha que $L$ seja regular. Como
       $\overline{L}\cap L(a^*c^*)=\{{\tt a}^n{\tt c}^n\,| n\geq 0\}$,
       $L(a^*c^*)$ \'e regular e as linguagens regulares s\~ao
       fechadas sob complementa\c{c}\~ao e sob interse\c{c}\~ao, segue-se que
       $\{{\tt a}^n{\tt c}^n\,| n\geq 0\}$ \'e regular. Obt\'em-se uma
       contradi\c{c}\~ao, pois sabe-se que $\{{\tt a}^n{\tt c}^n\,| n\geq 0\}$
       n\~ao \'e regular. Logo, $L$ n\~ao \'e regular.
\end{enumerate}


\noindent {\footnotesize \textbf{Extra.} Prove que \textit{se um AFD $M$ de $k$ estados
n\~ao reconhece palavras de $k$ a $2k-1$ s\'{\i}mbolos, ent\~ao $L(M)$ \'e
finita}, e ganhe dois pontos extra! Como toda demonstra\c{c}\~ao digna do
nome, ela deve ser escrita \textit{em portugu\^es}, de cabo a rabo.}

Pela contrapositiva. Suponha que $L(M)$ seja infinita. Neste caso, $M$
reconhece palavras de $2k$ ou mais s\'{\i}mbolos. Seja, ent\~ao, uma
palavra $z\in L(M)$ de tamanho maior ou igual a $2k$ com o \textit{menor\/}
n\'umero de s\'{\i}mbolos. Pelo lema do bombeamento (a demonstra\c{c}\~ao
mostra que  a constante do lema pode ser tomada como $k$), existem $u$, $v$
e $w$ tais que $z=uvw$, $|v|>0$, $|uv|\leq k$ e $uv^iw\in L$ para todo
$i\geq 0$. Em particular, $uw\in L$. Como $|v|>0$, essa \'ultima palavra \'e
menor que $z$. Como ela n\~ao pode ser maior ou igual a $2k$ (pois $z$ \'e a
menor poss\'{\i}vel de tamanho maior ou igual a $2k$) e $|uv|\leq k$,
conclui-se que $|uw|$ \'e maior ou igual a $k$ e menor que $2k$. Assim,
existe uma palavra de $L(M)$ de $k$ a $2k-1$ s\'{\i}mbolos.

\end{document}
