\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\newcounter{conta2}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova} \hfill 10/07/2002 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turmas M e G/Solu\c c\~ao do professor}

\vspace*{1mm}
\begin{enumerate}
 \item {\footnotesize Expresse as linguagens a seguir utilizando opera\c c\~oes sobre conjuntos
       finitos de palavras de $\{\verb+0+,\verb+1+\}^*$. Considere o alfabeto
       como sendo $\{\verb+0+,\verb+1+\}$.}
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item {\footnotesize O conjunto das palavras que t\^em exatamente 10 s\'{\i}mbolos.}

                $\{\verb+0+,\verb+1+\}^{10}$

          \item {\footnotesize O conjunto das palavras que t\^em \verb+00+ como prefixo e \verb+11+
                como sufixo.}

                $\{\verb+00+\}\{\verb+0+,\verb+1+\}^*\{\verb+11+\}$

          \item{\footnotesize O conjunto das palavras em que todo \verb+0+ \'e seguido de \verb+1+.
                Exemplos: $\lambda$, \verb+111+, \verb+011+, \verb+11010111011+.}

                $\{\verb+01+,\verb+1+\}^*$

          \item {\footnotesize O conjunto das palavras que cont\^em um ou dois \verb+1+'s.}

                $\{\verb+0+\}^*\{\verb+1+\}\{\verb+0+\}^*\{\lambda,\verb+1+\}\{\verb+0+\}^*$
        \end{list}

 \item  \begin{list}{(\alph{conta})}{\usecounter{conta}}
           \item{\footnotesize  Fa\c ca uma defini\c c\~ao recursiva da linguagem
                  $\{\verb+ab+\}^*\{\lambda,\verb+b+\}\{\verb+ba+\}^*$.}

                 Seja $L$ tal linguagem $L$ pode ser definida recursivamente assim:
                 \begin{list}{(\alph{conta2})}{\usecounter{conta2}}
                  \item $\lambda\in L$ e $\verb+b+\in L$;
                  \item se $x\in L$, ent\~ao $\verb+ab+ x\in L$ e $x\verb+ba+ \in L$.
                 \end{list}

           \item {\footnotesize Construa uma gram\'atica que gere a linguagem
                  $\{\verb+ab+\}^*\{\lambda,\verb+b+\}\{\verb+ba+\}^*$.}


                 Uma gram\'atica para tal linguagem seria:
                 \begin{enumerate}
                  \item[\ ] $P\,\,\rightarrow\,\, \verb+ab+ P \,\,|\,\, P \verb+ba+
                             \,\,|\,\, \lambda \,\,|\,\, \verb+b+$.
                 \end{enumerate}


           \item {\footnotesize Em quantos passos \'e derivada uma palavra de tamanho $n$, para a
                 gram\'atica constru\'{\i}da?}

                 Uma palavra de tamanho $n$ \'e derivada em $\lfloor n/2 \rfloor + 1$ passos:
                 em $i+j$ passos deriva-se $(\verb+ab+)^i P (\verb+ba+)^j$; se a \'ultima
                 regra aplicada for $P \rightarrow \lambda$, s\~ao gastos $i+j+1$ passos;
                 e como $n=2i+2j$, $\lfloor n/2 \rfloor + 1=i+j+1$. Por outro lado, se
                 a \'ultima regra aplicada for $P\rightarrow \verb+b+$, s\~ao gastos
                 tamb\'em $i+j+1$ passos; e como $n=2i+2j+1$, $\lfloor n/2 \rfloor + 1=i+j+1$.

          \end{list}

 \item{\footnotesize  Construa aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam:}

         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item {\footnotesize $\{\lambda\}$}

                $(\{0,1\},\{\verb+0+\},\delta,0,\{0\})$, onde $\delta(0,\verb+0+)=1$
                e $\delta(1,\verb+0+)=1$.

          \item {\footnotesize O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ que cont\^em
                um ou dois \verb+1+'s.}

                $(\{0,1,2,3\},\{\verb+0+,\verb+1+\},\delta,0,\{1,2\})$, onde $\delta$ \'e:

                \hspace*{1cm}\begin{tabular}{c|cc}
                 $\delta$ & \verb+0+ & \verb+1+ \\ \hline
                        0 & 0 & 1 \\
                        1 & 1 & 2 \\
                        2 & 2 & 3 \\
                        3 & 3 & 3 \\
                \end{tabular}

          \item {\footnotesize $\{\verb+ab+\}^*\{\lambda,\verb+b+\}\{\verb+ba+\}^*$}

                $(\{1,2,3,4,5,6\},\{\verb+a+,\verb+b+\},\delta,1,\{1,3,4\})$, onde $\delta$ \'e:

                \hspace*{1cm}\begin{tabular}{c|cc}
                 $\delta$ & \verb+a+ & \verb+b+ \\ \hline
                        1 & 2 & 3 \\
                        2 & 6 & 1 \\
                        3 & 4 & 5 \\
                        4 & 6 & 5 \\
                        5 & 4 & 6 \\
                        6 & 6 & 6 \\
                \end{tabular}


          \item {\footnotesize $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, \mbox{$w$ n\~ao come\c ca com
                00 nem termina com 11}\}$}

                $(\{1,2,3,4,5,6\},\{\verb+0+,\verb+1+\},\delta,1,\{1,2,3,4\})$, onde $\delta$ \'e:

                \hspace*{1cm}\begin{tabular}{c|cc}
                 $\delta$ & \verb+0+ & \verb+1+ \\ \hline
                        1 & 2 & 3 \\
                        2 & 6 & 3 \\
                        3 & 4 & 5 \\
                        4 & 4 & 3 \\
                        5 & 4 & 5 \\
                        6 & 6 & 6 \\
                \end{tabular}

         \end{list}

 \item {\footnotesize Sejam as linguagens:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^n\verb+1+\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$
        \item $\{\verb+0+^n\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$
       \end{list}
       Mostre que a primeira n\~ao pode ser reconhecida por AFD, e que a
       segunda pode.}

 \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Suponha que $L=\{\verb+0+^n\verb+1+\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$ \'e
              reconhecida por um AFD de $k$ estados. Seja a palavra
              $z=\verb+0+^k\verb+1+\verb+0+^k\in L$. Como o prefixo $\verb+0+^k$ de $z$ tem $k$
              s\'{\i}mbolos, o AFD percorre pelo menos um ciclo no diagrama de estados do AFD para
              consum\'{\i}-lo. Suponha que a subpalavra consumida em um tal ciclo seja $v$; assim,
              seja $z=uvw$, onde $u$ \'e o prefixo antes de $v$ e $w$ o sufixo ap\'oes $v$.
              Deveria ser o caso que $uv^iw\in L$ para todo $i\geq 0$; mas
              $uv^0w\not\in L$: $uv^0w=\verb+0+^{k-|v|}\verb+1+\verb+0+^k$.
              Logo a suposi\c c\~ao de que existe AFD para $L$ \'e incorreta.
        \item Um AFD para $\{\verb+0+^n\verb+0+^n\,\,|\,\, n\in\mbox{\bf N}\}$:
              $(\{p,i\},\{\verb+0+\},\delta,p,\{p\})$, onde $\delta(p,\verb+0+)=i$
                e $\delta(i,\verb+0+)=p$.

 \end{list}

 \item{\footnotesize  Sim ou n\~ao? Por que?}

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\footnotesize Se a linguagem $L$ pode ser reconhecida por AFD, qualquer subconjunto
              de $L$ tamb\'em pode.}

              Falso. A linguagem $\Sigma^*$, para qualquer alfabeto $\Sigma$ \'e
              reconhec\'{\i}vel por AFD. E qualquer linguagem \'e subconjunto de $\Sigma^*$!

        \item {\footnotesize Para qualquer linguagem finita $L$ existe AFD que reconhece $L$.}

              Verdade. Pode-se fazer um AFD cujo diagrama de estados \'e uma \'arvore. O estado
              inicial \'e a raiz da \'arvore, e, se $a_1a_2\ldots a_n$ \'e uma palavra de $L$,
              providencia-se um caminho (de tamanho $n$) da raiz at\'e um estado final, de forma
              que $a_1a_2\ldots a_n$ seja a palavra lida no caminho.
       \end{list}

\end{enumerate}
\end{document}

