\documentclass[12pt, a4paper]{report}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\pagestyle{empty}

\newcounter{conta}
\newcounter{conta2}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2004 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Primeira Prova/Solu\c c\~ao} \hfill 16/09/2004

\begin{enumerate}\footnotesize

 \item Para cada um dos casos abaixo, encontre exemplos de linguagens $A$ e $B$
       sobre $\{{\tt a},{\tt b}\}$ que satisfa\c cam a condi\c c\~ao apresentada:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $|AB|\not=|A|\times|B|$. ($|A|$ \'e o n\'umero de palavras de $A$.)

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

              $A=\{\lambda,{\tt a}\}$, $B=\{\lambda,{\tt a}\}$. Neste caso:

              $AB=\{\lambda, {\tt a},{\tt aa}\}$, que tem 3 palavras, e
              $|A|\times|B|= 2\times 2=4$.

        \item $(A\cup B)^*\not=A^*\cup B^*$.

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

              $A=\{{\tt a}\}$, $B=\{{\tt b}\}$. Neste caso:

              $(A\cup B)^*=\{{\tt a},{\tt b}\}^*$ e $A^*\cup B^*=\{{\tt a}\}^*
               \cup\{{\tt b}\}^*$.

        \item $A\not\subseteq B$ e $B\not\subseteq A$ e $(A\cup B)^*=A^*\cup B^*$.

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

              $A=\{{\tt a}\}$, $B=\{\lambda\}$. Neste caso:

              $(A\cup B)^*=A^*\cup B^*=\{{\tt a}\}^*$.
       \end{list}

 \item Descreva as linguagens abaixo, todas sobre o alfabeto $\{{\tt 0},{\tt 1}\}$,
       usando conjuntos finitos e \underline{apenas} as opera\c c\~oes:
       concatena\c c\~ao, uni\~ao, interse\c c\~ao e/ou fecho de Kleene.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras com um n\'umero par de {\tt 0}'s.

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

              $(\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\})^*\{{\tt 1}\}^*$.

        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ come\c ca com {\tt 0} e
              cont\'em {\tt 11}$\}$.

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

              $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 11}\}\{{\tt 0},{\tt 1}\}^*$.

        \item $\{{\tt 0}y\,|\,y\in\{{\tt 0},{\tt 1}\}^*$ e $y$ n\~ao
              cont\'em {\tt 11}$\}$.

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

              $\{{\tt 0}\}\{{\tt 0},{\tt 10}\}^*\{{\tt 1},\lambda\}$.

       \end{list}

 \item Sobre gram\'aticas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada pela gram\'atica $G$ definida a seguir?

              $G=(\{P,A,B\},\{{\tt a},{\tt b},{\tt c}\},R,P)$.
               \begin{enumerate}
                \item[$R$:] $P\,\rightarrow\,B A B$
                \item[\ ]   $A\,\rightarrow\,{\tt a} A {\tt a} \,|\, \lambda$
                \item[\ ]   $B\,\rightarrow\,{\tt a} B {\tt a} \,|\, {\tt b} B {\tt b}
                                             \,|\, {\tt c}$
               \end{enumerate}

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

              $L(G)=\{x{\tt c}x^R{\tt a}^{2n}y{\tt c}y^R\,|\,x,y\in\{{\tt a},{\tt b}\}^*
                      \mbox{ e } n\geq 0\}$.

        \item Obtenha uma gram\'atica que gere o conjunto das palavras sobre
              $\{{\tt a},{\tt b},{\tt c}\}$ que n\~ao contenham {\tt ab} como
              subpalavra.

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

              $G=(\{P,A\},\{{\tt a},{\tt b},{\tt c}\},R,P)$.
               \begin{enumerate}
                \item[$R$:] $P\,\rightarrow\, {\tt a}A \,|\, {\tt b}P \,|\, {\tt c}P \,|\,
                              \lambda$
                \item[\ ]   $A\,\rightarrow\,{\tt a} A  \,|\, {\tt c}P \,|\, \lambda$
               \end{enumerate}
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para as linguagens
       a seguir. Apresente apenas o \underline{diagrama de estados} de cada AFD
       (pode ser no estilo simplificado).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01}\}^*\{{\tt 1},{\tt 10}\}^*$.

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

              \begin{center}
              \begin{picture}(190,85) \footnotesize
               \put(10,70){\vector(1,0){10}}
               \put(30,70){\oval(20,20){\makebox(0,0){$1$}}}
               \put(30,70){\oval(17,17)}
               \put(40,70){\vector(1,0){50}}
               \put(65,73){\makebox(0,0)[b]{{\tt 1}}}

               \put(35,62){\vector(0,-1){44}}
               \put(38,40){\makebox(0,0)[l]{{\tt 0}}}
               \put(25,18){\vector(0,1){44}}
               \put(22,40){\makebox(0,0)[r]{{\tt 1}}}
               \put(30,10){\oval(20,20){\makebox(0,0){$4$}}}

               \put(100,70){\oval(20,20){\makebox(0,0){$2$}}}
               \put(100,70){\oval(17,17)}
               \put(108,75){\vector(1,0){54}}
               \put(135,78){\makebox(0,0)[b]{{\tt 0}}}
               \put(162,65){\vector(-1,0){54}}
               \put(135,62){\makebox(0,0)[t]{{\tt 1}}}
               \put(105,62){\line(0,-1){10}}
               \put(100,52){\oval(10,10)[b]}
               \put(100,44){\makebox(0,0)[t]{{\tt 1}}}
               \put(95,52){\vector(0,1){10}}

               \put(170,70){\oval(20,20){\makebox(0,0){$3$}}}
               \put(170,70){\oval(17,17)}

              \end{picture}
              \end{center}

        \item $\{{\tt 0}y\,|\,y\in\{{\tt 0},{\tt 1}\}^*$ e $y$ n\~ao
              cont\'em {\tt 11}$\}$.

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

              \begin{center}
              \begin{picture}(190,55) \footnotesize
               \put(10,40){\vector(1,0){10}}
               \put(30,40){\oval(20,20){\makebox(0,0){$1$}}}
               \put(40,40){\vector(1,0){50}}
               \put(65,43){\makebox(0,0)[b]{{\tt 0}}}

               \put(100,40){\oval(20,20){\makebox(0,0){$2$}}}
               \put(100,40){\oval(17,17)}
               \put(108,45){\vector(1,0){54}}
               \put(135,48){\makebox(0,0)[b]{{\tt 1}}}
               \put(162,35){\vector(-1,0){54}}
               \put(135,32){\makebox(0,0)[t]{{\tt 0}}}
               \put(105,32){\line(0,-1){10}}
               \put(100,22){\oval(10,10)[b]}
               \put(100,14){\makebox(0,0)[t]{{\tt 0}}}
               \put(95,22){\vector(0,1){10}}

               \put(170,40){\oval(20,20){\makebox(0,0){$3$}}}
               \put(170,40){\oval(17,17)}

              \end{picture}
              \end{center}


        \item O complemento da linguagem do item (b).

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

              \begin{center}
              \begin{picture}(190,85) \footnotesize
               \put(10,70){\vector(1,0){10}}
               \put(30,70){\oval(20,20){\makebox(0,0){$1$}}}
               \put(30,70){\oval(17,17)}
               \put(40,70){\vector(1,0){50}}
               \put(65,73){\makebox(0,0)[b]{{\tt 0}}}

               \put(30,60){\vector(0,-1){40}}
               \put(33,40){\makebox(0,0)[l]{{\tt 1}}}
               \put(30,10){\oval(20,20){\makebox(0,0){$4$}}}
               \put(30,10){\oval(17,17)}
               \put(22,5){\line(-1,0){10}}
               \put(12,10){\oval(10,10)[l]}
               \put(4,10){\makebox(0,0)[r]{{\tt 0},{\tt 1}}}
               \put(12,15){\vector(1,0){10}}

               \put(100,70){\oval(20,20){\makebox(0,0){$2$}}}
               \put(108,75){\vector(1,0){54}}
               \put(135,78){\makebox(0,0)[b]{{\tt 1}}}
               \put(162,65){\vector(-1,0){54}}
               \put(135,62){\makebox(0,0)[t]{{\tt 0}}}
               \put(105,62){\line(0,-1){10}}
               \put(100,52){\oval(10,10)[b]}
               \put(100,44){\makebox(0,0)[t]{{\tt 0}}}
               \put(95,52){\vector(0,1){10}}

               \put(170,70){\oval(20,20){\makebox(0,0){$3$}}}
               \put(170,60){\line(0,-1){45}}
               \put(173,40){\makebox(0,0)[l]{{\tt 1}}}
               \put(165,15){\oval(10,10)[rb]}
               \put(165,10){\vector(-1,0){125}}
             

              \end{picture}
              \end{center}

       \end{list}

 \item Seja um AFD $M=(\{i,e,f,\ldots\},\{{\tt 0},{\tt 1}\},\delta,i,\{f\})$ e
       suponha que $\hat{\delta}(i,x)=e$, $\hat{\delta}(e,y)=e$ e
       $\hat{\delta}(e,z)=f$, onde $\hat{\delta}$ \'e a fun\c c\~ao de transi\c c\~ao
       estendida para $M$. Explique porque:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $xz\in L(M)$.

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

              Tem-se: $\hat{\delta}(i,xz)=\hat{\delta}(\hat{\delta}(i,x),z)$. Como
              $\hat{\delta}(i,x)=e$, segue-se que  $\hat{\delta}(i,xz)=\hat{\delta}(e,z)$.
              E como $\hat{\delta}(e,z)=f$, segue-se que $\hat{\delta}(i,xz)=f$. Como $f$
              \'e um estado final de $M$, $xz\in L(M)$.

        \item $xyyz\in L(M)$.

              Tem-se: $\hat{\delta}(i,xyyz)=\hat{\delta}(\hat{\delta}(i,x),yyz)$. Como
              $\hat{\delta}(i,x)=e$, segue-se que $\hat{\delta}(i,xyyz)=\hat{\delta}(e,yyz)$.
              Como $\hat{\delta}(e,y)=e$, segue-se que
              $\hat{\delta}(e,yyz)=\hat{\delta}(e,yz)=\hat{\delta}(e,z)$. Finalmente, como
              $\hat{\delta}(e,z)=f$, segue-se que $\hat{\delta}(i,xyyz)=f$. Como $f$
              \'e um estado final de $M$, $xyyz\in L(M)$.

        \item $L(M)$ \'e infinita.

              Pelo racioc\'{\i}nio acima, para todo $n\geq 0$, \[\hat{\delta}(i,xy^nz)=
              \hat{\delta}(\hat{\delta}(i,x),y^nz)=\hat{\delta}(e,y^nz)=\hat{\delta}(e,y^{n-1}z)
              =\cdots=\hat{\delta}(e,z)=f\mbox{.}\]
              Assim, $xy^nz\in L(M)$ para todo $n\geq 0$. Logo, $L(M)$ \'e infinita.
              
       \end{list}
\end{enumerate}

\end{document}

