\documentclass[11pt, a4paper]{report}

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

\begin{document}

\vspace*{10mm}
\noindent {\it Fundamentos da Teoria da Computação}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova}/Turma W: Solução do professor \hfill {08/3/2010}

\begin{enumerate}

 \item {\footnotesize Seja $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantas palavras sobre $\Sigma$ existem com exatamente $n$ símbolos?
        \item Quantas palavras sobre $\Sigma$ existem com no máximo $n$ símbolos?
        \item Quantas subpalavras contém uma palavra de $n$ símbolos, \underline{no mínimo}?
        \item Quantas subpalavras contém uma palavra de $n$ símbolos, \underline{no máximo}?
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Cada símbolo da palavra pode ser {\tt 0}, {\tt 1} ou {\tt \#} (3 opções). Logo, existem $3^n$
              palavras de $n$ símbolos.
        \item Número de palavras de zero a $n$ símbolos: $\sum_{i=0}^{n}3^i=(3^{n+1}-1)/2$.
        \item Uma palavra de $n$ símbolos tem o número mínimo de subpalavras se todos os seus símbolos são
              idênticos. Neste caso, ela tem $n+1$ subpalavras.
        \item Uma palavra de $n$ símbolos tem no máximo $C(n-1+2,2)+1=[(n+1)n/2]+1$ subpalavras.
              ($C(n-1+2,2)$ é o número de multiconjuntos de dois elementos tomados de um conjunto de $n$ elementos.)
       \end{list}

 \item {\footnotesize Descreva as linguagens a seguir, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando apenas conjuntos finitos, opera\c c\~oes sobre conjuntos,
       concatena\c c\~ao e fecho de Kleene. Procure obter uma descri\c c\~ao bem
       concisa.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras iniciadas com {\tt 0} e de tamanho ímpar.
        \item O conjunto das palavras em que cada ocorrência de {\tt 0} é seguida de pelo menos dois
              {\tt 1}s consecutivos.
        \item O conjunto das palavras que cont\^em um número par de {\tt 0}s (e qualquer número de {\tt 1}s).
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}\}(\{{\tt 0},{\tt 1}\}\{{\tt 0},{\tt 1}\})^*$.
        \item $\{{\tt 1},{\tt 011}\}^*$.
        \item $(\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\cup\{{\tt 1}\})^*$.
       \end{list}

 \item {\footnotesize  Obtenha gram\'aticas para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 010}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w=w^R\}$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, {\tt 0}P \,|\, {\tt 1}P \,|\, {\tt 010}$
        \item $P \,\rightarrow\, {\tt 0}P{\tt 0} \,|\, {\tt 1}P{\tt 1} \,|\, {\tt 0} \,|\, {\tt 1} \,|\, \lambda$.
       \end{list}

 \item {\footnotesize  Construa AFDs que reconhe\c cam as linguagens a seguir.
       Apresente apenas os diagramas de estados (que podem ser simplificados).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a},{\tt b}\}^*\{{\tt aba}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em pelo menos um {\tt a} e cont\'em número par de {\tt b}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, w$ n\~ao cont\'em {\tt ab} nem {\tt bc}$\}$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item  \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,10)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=i](1)(20,7){}
               \node(2)(35,7){}
               \node(3)(50,7){}
               \node[Nmarks=r](4)(65,7){}

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

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

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

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

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,20)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \node[Nmarks=ir](1)(20,20){}
               \node[Nmarks=r](2)(30,5){}
               \node[Nmarks=r](3)(40,20){}

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

 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $X=\{{\tt 1}\}\Sigma^*$
        \item $Y=\Sigma^*\{{\tt 11}\}$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $X$ e $Y$. Eles devem três estados cada um.
        \item Obtenha o diagrama de estados para o produto dos dois AFDs.
        \item Diga quais s\~ao os estados finais para os AFDs que reconhecem $X\cap Y$ e $X\cup Y$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,16)\setlength{\unitlength}{1mm}
               \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

               \put(10,7){\makebox(0,0)[r]{$M_X$:}}
               \put(60,7){\makebox(0,0)[r]{$M_Y$:}}

               {\footnotesize
               \node[Nmarks=i](A)(20,7){A}
               \node[Nmarks=r](B)(35,12){B}
               \node(C)(35,2){C}

               \node[Nmarks=i](a)(70,7){A}
               \node(b)(85,7){B}
               \node[Nmarks=r](c)(100,7){C}
               }

               \drawedge[curvedepth=0](A,B){{\tt 1}}
               \drawedge[curvedepth=0](A,C){{\tt 0}}
               \drawloop[loopangle=0](B){{\tt 0},{\tt 1}}
               \drawloop[loopangle=0](C){{\tt 0},{\tt 1}}

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

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,30)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

               {\footnotesize
               \node[Nmarks=i](AA)(30,25){AA}
               \node(BB)(50,30){BB}
               \node(BC)(65,30){BC}
               \node(CA)(20,15){CA}
               \node(BA)(50,20){BA}
               \node(CB)(20,5){CB}
               \node(CC)(35,5){CC}
               }

               \drawedge[curvedepth=0](AA,BB){{\tt 1}}
               \drawedge[curvedepth=0](AA,CA){{\tt 0}}
               \drawedge[curvedepth=0](BB,BC){{\tt 1}}
               \drawedge[curvedepth=2](BB,BA){{\tt 0}}
               \drawloop[loopangle=0](BC){{\tt 1}}
               \drawedge[curvedepth=3](BC,BA){{\tt 0}}
               \drawloop[loopangle=180](CA){{\tt 0}}
               \drawedge[curvedepth=2](CA,CB){{\tt 1}}
               \drawloop[loopangle=270](BA){{\tt 0}}
               \drawedge[curvedepth=2](BA,BB){{\tt 1}}
               \drawedge[curvedepth=2](CB,CA){{\tt 0}}
               \drawedge[curvedepth=0](CB,CC){{\tt 1}}
               \drawloop[loopangle=0](CC){{\tt 1}}
               \drawedge[curvedepth=-3,ELside=r](CC,CA){{\tt 0}}
              \end{picture}
             } \\

        \item Estados finais para AFD que reconhece $X\cap Y$: $\{\mbox{\footnotesize BC}\}$. \\
              Estados finais para AFD que reconhece $X\cup Y$: $\{\mbox{\footnotesize BA},\mbox{\footnotesize BB},\mbox{\footnotesize BC},\mbox{\footnotesize CC}\}$.
       \end{list}
\end{enumerate}

\end{document}

