\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}/Turmas Z e F: Solução do professor \hfill {08/3/2010}

\begin{enumerate}

 \item {\footnotesize Seja $\Sigma=\{{\tt 0},{\tt 1},{\tt \#}\}$. Sejam $k$ e $n$ números naturais tais que $k\leq n$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantas palavras há na linguagem $\Sigma^k$?
        \item Quantas palavras há na linguagem $(\Sigma\cup\{\lambda\})^k$?
        \item Quantas palavras de $n$ símbolos contêm exatamente $k$ ocorrências do símbolo {\tt \#}?
        \item Quantas palavras de $n$ símbolos contêm no máximo $k$ ocorrências do símbolo {\tt \#}?
       \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^k$
              palavras de $k$ símbolos.
        \item Número de palavras de zero a $k$ símbolos: $\sum_{i=0}^{k}3^i=(3^{i+1}-1)/2$.
        \item Número de posicionamentos para os $k$ {\tt \#}s: $C(n,k)$; número de sequências dos símbolos
              restantes ({\tt 0} e {\tt 1}) nas posições restantes: $2^{n-k}$. A resposta é, então, $C(n,k).2^{n-k}$.
        \item Número de palavras com zero a $k$ ocorrências de {\tt \#}: $\sum_{i=0}^{k}C(n,i).2^{n-i}$.
       \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 com no mínimo um símbolo.
        \item O conjunto das palavras em que toda ocorrência de {\tt 0} é precedida de {\tt 1}.
        \item O conjunto das palavras que cont\^em um número ímpar de {\tt 0}s seguido por um número par de {\tt 1}s.
              Ou seja, cada palavra é da forma ${\tt 0}^i{\tt 1}^p$, em que $i$ é ímpar e $p$ é par.
       \end{list}}

       \textit{Solução:}

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

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

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $P \,\rightarrow\, {\tt 0}P \,|\, {\tt 1}XX$ \\
              $X \,\rightarrow\, {\tt 0} \,|\, {\tt 1}$
        \item $P \,\rightarrow\, {\tt 0}P{\tt 0} \,|\, {\tt 1}P{\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 a},{\tt b},{\tt aa},{\tt bb}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ tem tamanho par e tem no mínimo uma ocorrência de {\tt a}$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em {\tt aa}, mas n\~ao cont\'em {\tt bb}$\}$.
       \end{list}}

       \textit{Solução:}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \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](i)(20,12){}
               \node(1)(35,19){}
               \node(2)(35,5){}
               \node(3)(50,12){}
               \node[Nmarks=r](4)(65,12){}

               \drawedge[curvedepth=0](i,1){{\tt a}}
               \drawedge[curvedepth=0, ELside=r](i,2){{\tt b}}
               \drawedge[curvedepth=0](1,3){{\tt a}}
               \drawedge[curvedepth=0,ELside=r](2,3){{\tt b}}
               \drawedge[curvedepth=6](1,4){{\tt b}}
               \drawedge[curvedepth=0](3,4){{\tt a},{\tt b}}
               \drawedge[curvedepth=-6,ELside=r](2,4){{\tt a}}
               \drawloop[loopangle=0](4){{\tt a},{\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=i](1)(20,20){}
               \node(2)(20,5){}
               \node(3)(40,20){}
               \node[Nmarks=r](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}}
               \drawedge[curvedepth=3](3,4){{\tt a},{\tt b}}
               \drawedge[curvedepth=3](4,3){{\tt a},{\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=i](1)(20,20){}
               \node(2)(20,5){}
               \node(3)(40,20){}
               \node[Nmarks=r](4)(60,20){}
               \node[Nmarks=r](5)(60,5){}

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

 \item {\footnotesize Seja $\Sigma=\{{\tt}0,{\tt 1}\}$ e:
       \begin{itemize}
        \item $X=\Sigma^*\{{\tt 1}\}$
        \item $Y=\Sigma^*\{{\tt 11}\}\Sigma^*$.
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Desenhe os diagramas de estados de AFDs que reconhe\c{c}am $X$ e $Y$. O que reconhece $X$ deve ter
              dois estados e o que reconhece $Y$ deve ter três estados.
        \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,10)\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,7){B}

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

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

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

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

               {\footnotesize
               \node[Nmarks=i](AA)(20,7){AA}
               \node(BB)(35,7){BB}
               \node(BC)(50,7){BC}
               \node(AC)(65,7){AC}
               }

               \drawloop[loopangle=90](AA){{\tt 0}}
               \drawedge[curvedepth=3](AA,BB){{\tt 1}}
               \drawedge[curvedepth=3](BB,AA){{\tt 0}}
               \drawedge[curvedepth=0](BB,BC){{\tt 1}}
               \drawloop[loopangle=90](BC){{\tt 1}}
               \drawedge[curvedepth=3](BC,AC){{\tt 0}}
               \drawedge[curvedepth=3](AC,BC){{\tt 1}}
               \drawloop[loopangle=0](AC){{\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 BB},\mbox{\footnotesize BC},\mbox{\footnotesize AC}\}$.
       \end{list}
\end{enumerate}

\end{document}
