\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 Primeira Prova/Solu\c{c}\~ao do professor}

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

 \item {\footnotesize Sejam $A=\{{\tt a}\}$ e $B=\{{\tt bb}\}$. Quantas palavras de $n$
       s\'{\i}mbolos, para cada $n\geq 0$, h\'a em:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $A^*B$?
        \item $AB^*$?
        \item $A^*B^*$?
       \end{list}}

       {\it Solu\c{c}\~ao\/}: Chamando de $p(n)$ o n\'umero de palavras de $n$
       s\'{\i}mbolos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $p(0)=p(1)=0$; $p(n)=1$ para $n\geq 2$.
        \item $p(n)=0$ se $n$ \'e par; $p(n)=1$ se $n$ \'e \'{\i}mpar.
        \item $p(n)=\lfloor n/2\rfloor+1$.
       \end{list}

 \item {\footnotesize Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 00},{\tt 11}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,$ o n\'umero de {\tt 0}s em $w$ \'e
              \'{\i}mpar$\}$.
        \item $\{wxw^R\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{\tt c\}^*\}$.
       \end{list}}

       {\it Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P\,\rightarrow\,{\tt 0}P \,|\, {\tt 1}P \,|\, {\tt 00}
                               \,|\,{\tt 11}$
        \item $P\,\rightarrow\,{\tt 0}I \,|\, {\tt 1}P$ \\
              $I\,\rightarrow\,{\tt 0}P \,|\, {\tt 1}I \,|\, \lambda$
        \item $P\,\rightarrow\,{\tt a}P{\tt a} \,|\, {\tt b}P{\tt b}
                               \,|\, {\tt C}$ \\
              $C\,\rightarrow\,{\tt c}C \,|\, \lambda$

       \end{list}

 \item {\footnotesize Construa AFDs que reconhe\c cam
       as linguagens a seguir. Apresente apenas os diagramas de estados.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt ab}\}^*\{{\tt aba}\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ a subpalavra {\tt abc}
               ocorre um n\'umero \'{\i}mpar de vezes em $w\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em o mesmo s\'{\i}mbolo
              em todas as posi\c{c}\~oes \'{\i}mpares$\}$. Considere que o primeiro
              s\'{\i}mbolo da palavra est\'a na posi\c{c}\~ao 1, o segundo na
              posi\c{c}\~ao 2 etc.
       \end{list}}

       {\it Solu\c{c}\~ao\/}:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,15)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=4, fillcolor=Gray, fillgray=0.9}

               \node[Nmarks=i](1)(20,5){}
               \node(2)(40,5){}
               \node(3)(60,5){}
               \node[Nmarks=r](4)(80,5){}

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

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(140,35)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=4, fillcolor=Gray, fillgray=0.9}

               \node[Nmarks=i](1)(20,15){}
               \node(2)(40,15){}
               \node(3)(60,15){}
               \node[Nmarks=r](4)(80,15){}
               \node[Nmarks=r](5)(100,15){}
               \node[Nmarks=r](6)(120,15){}

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

               \drawedge[curvedepth=3](4,5){{\tt a}}
               \drawloop[loopangle=270](4){{\tt b},{\tt c}}
               \drawedge[curvedepth=3](5,4){{\tt c}}
               \drawedge[curvedepth=3](5,6){{\tt b}}
               \drawloop[loopangle=270](5){{\tt a}}
               \drawedge[curvedepth=3](6,5){{\tt a}}
               \drawedge[curvedepth=12](6,4){{\tt b}}
               \drawedge[curvedepth=-20, ELside=r](6,1){{\tt c}}
              \end{picture}
             } \\
        \item  \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(100,35)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=4, fillcolor=Gray, fillgray=0.9}

               \node[Nmarks=ir](1)(20,15){}
               \node[Nmarks=r](2)(35,25){}
               \node[Nmarks=r](3)(55,25){}
               \node[Nmarks=r](4)(35,5){}
               \node[Nmarks=r](5)(55,5){}

               \drawedge[curvedepth=0](1,2){{\tt 0}}
               \drawedge[curvedepth=0](1,4){{\tt 1}}
               \drawedge[curvedepth=4](2,3){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=4](3,2){{\tt 0}}
               \drawedge[curvedepth=4](4,5){{\tt 0},{\tt 1}}
               \drawedge[curvedepth=4](5,4){{\tt 1}}
              \end{picture}
             } \\

       \end{list}

 \item {\footnotesize Sejam os AFDs $M_1$ e $M_2$ com os diagramas de estado mostrados
       a seguir.

       \begin{picture}(100,40)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \put(10,30){\makebox(0,0){$M_1$:}}
        \node[Nmarks=i, iangle=180](a)(30,30){a}
        \node[Nmarks=r](b)(50,30){b}
        \node(c)(70,30){c}

        \put(10,10){\makebox(0,0){$M_2$:}}
        \node[Nmarks=ir, iangle=180](1)(30,10){1}
        \node(2)(50,10){2}

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

       Observe que o diagrama de $M_1$ \'e o simplificado.
       Obtenha o diagrama de estados do produto de $M_1$ e $M_2$. Explicite
       quais seriam os estados finais para um AFD que reconhe\c{c}a:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $L(M_1)\cup L(M_2)$.
        \item $L(M_1)\cap L(M_2)$.
       \end{list}}

       {\it Solu\c{c}\~ao\/}: Seja $e$ o estado de erro de $M_1$. O diagrama
       de estados para o produto seria:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(100,40)\setlength{\unitlength}{1mm}
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=4, fillcolor=Gray, fillgray=0.9}

         \node(e2)(20,25){$e2$}
         \node[Nmarks=i](a1)(40,25){$a1$}
         \node(b2)(60,25){$b2$}
         \node(c1)(80,25){$c1$}
         \node(e1)(40,5){$e1$}
         \node(a2)(60,5){$a2$}
         \node(b1)(80,5){$b1$}

         \drawedge[curvedepth=0](a1,b2){{\tt 0}}
         \drawedge[curvedepth=0](a1,e1){{\tt 1}}
         \drawedge[curvedepth=4](a2,b2){{\tt 0}}
         \drawedge[curvedepth=0](a2,e1){{\tt 1}}
         \drawedge[curvedepth=0](b1,a2){{\tt 0}}
         \drawedge[curvedepth=4](b1,c1){{\tt 1}}
         \drawedge[curvedepth=4](b2,a2){{\tt 0}}
         \drawedge[curvedepth=0](b2,c1){{\tt 1}}
         \drawedge[curvedepth=4](c1,b1){{\tt 1}}
         \drawedge[curvedepth=-10,ELside=r](c1,e2){{\tt 0}}
         \drawedge[curvedepth=3](e1,e2){{\tt 0}}
         \drawloop[loopangle=270](e1){{\tt 1}}
         \drawedge[curvedepth=3](e2,e1){{\tt 1}}
         \drawloop[loopangle=180](e2){{\tt 0}}
        \end{picture}
       } \\

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{a1,b1,b2,c1,e1\}$.
        \item $\{b1\}$.
       \end{list}

 \item {\footnotesize A diferen\c{c}a sim\'etrica de duas linguagens $A$ e $B$ \'e
       $C=(A\cup B)-(A\cap B)$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Explique como obter um AFD $M_3$, a partir de AFDs $M_1$ e
              $M_2$, que reconhe\c{c}a a diferen\c{c}a sim\'etrica de 
              $L(M_1)$ e $L(M_2)$.
        \item \'E poss\'{\i}vel saber se $L(M_1)=L(M_2)$, analisando-se o
              AFD $M_3$. Como?
       \end{list}}

       {\it Solu\c{c}\~ao\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Sejam $E_i$ e $F_i$ o conjunto de estados e o conjunto de estados
              finais do AFD $M_i$. Basta obter o produto de $M_1$ e $M_2$ e fazer
              $F_3=(F_1\times E_2\cup E_1\times F_2)-F_1\times F_2$.
        \item $L(M_1)=L(M_2)$ se, e somente se, nenhum estado de $F_3$ (se
              $F_3\not=\emptyset$)\'e alcan\c{c}\'avel a partir do estado
              inicial de $M_3$, j\'a que $L(M_1)=L(M_2)$ se, e somente se,
              $L(M_3)=\emptyset$.
       \end{list}
\end{enumerate}

\end{document}

\noindent \textbf{Extra.} {\footnotesize Demonstre qualquer uma das respostas da primeira
quest\~ao, usando indu\c{c}\~ao matem\'atica, e ganhe um ponto extra!}

       {\it Solu\c{c}\~ao\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $p(0)=p(1)=0$; $p(n)=1$ para $n\geq 2$.

              Como a menor palavra de $A^*B$ \'e {\tt bb}, segue-se que
              $p(0)=p(1)=0$. Ser\'a mostrado, por indu\c{c}\~ao, que
              $p(n)=1$ para $n\geq 2$. Como a menor palavra de $A^*B$
              \'e {\tt bb} e n\~ao existe outra de dois s\'{\i}mbolos,
              $p(2)=1$. Seja $n\geq 2$ arbitr\'ario. Suponha, como
              hip\'otese de indu\c{c}\~ao que $p(n)=1$. Neste caso,
              como ${\tt a}^{n-2}{\tt bb}\in A^*B$ e
              $|{\tt a}^{n-2}{\tt bb}|=n$,  ${\tt a}^{n-2}{\tt bb}$
              \'e a \'unica palavra de $n$ s\'{\i}mbolos de $A^*B$. Assim,
              pela defini\c{c}\~ao de fecho de Kleene, j\'a que
              $A=\{{\tt a}\}$, s\'o existe a palavra
              ${\tt a}^{n-2}{\tt a}{\tt bb}={\tt a}^{n-1}{\tt bb}$
              de $n+1$ s\'{\i}mbolos em $A^*B$. Ou seja, $p(n+1)=1$.

        \item $p(n)=0$ se $n$ \'e par; $p(n)=1$ se $n$ \'e \'{\i}mpar.

              Suponha, como hip\'otese de indu\c{c}\~ao (forte) que
              para $k< n$, $p(k)=0$, se $k$ \'e par, e $p(k)=1$ se $k$
              \'e \'{\i}mpar. Tem-se dois casos a considerar:
              \begin{enumerate}
               \item $n$ \'e par. Se $n=0$, como a menor palavra de
                     $AB^*$ \'e {\tt a}, segue-se que $p(n)=0$. Se $n>1$,
                     como $n-1$ \'e \'{\i}mpar, $p(n-1)=1$, pela hip\'otese
                     de indu\c{c}\~ao. Uma palavra de mais s\'{\i}mbolos
                     s\'o \'e conseguida concatenando-se ${\tt bb}\in B$
                     \`a palavra de $n-1$ s\'{\i}mbolos. Logo, n\~ao h\'a
                     palavras com $n$ s\'{\i}mbolos.
               \item $n$ \'e \'{\i}mpar. Se $n=1$, como a menor palavra de
                     $AB^*$ \'e {\tt a} e n\~ao h\'a outra com o mesmo n\'umero
                     de s\'{\i}mbolos, $p(n)=1$. Se $n>2$,
                     como $n-1$ \'e par, $p(n-1)=0$ e $p(n-2)=1$, pela
                     hip\'otese de indu\c{c}\~ao. Uma palavra de mais
                     s\'{\i}mbolos s\'o \'e conseguida concatenando-se
                     ${\tt bb}\in B$ \`a palavra de $n-2$ s\'{\i}mbolos.
                     Logo, $p(n)=1$.
              \end{enumerate}

        \item $p(n)=\lfloor n/2\rfloor+1$.
       \end{list}

\end{document}
