\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 11/07/2002 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turma A/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 de 5 a 10 s\'{\i}mbolos.}

                $\{\verb+0+,\verb+1+\}^5\{\lambda,\verb+0+,\verb+1+\}^5$

          \item {\footnotesize O conjunto das palavras que n\~ao tenham \verb+00+ como subpalavra,
                nem \verb+11+. Exemplos: $\lambda$, \verb+0+, \verb+01+,
                \verb+10+, \verb+101+.}

                $\{\verb+01+\}^*\{\lambda,\verb+0+\}\cup\{\verb+10+\}^*\{\lambda,\verb+1+\}$


          \item {\footnotesize O conjunto das palavras em que as posi\c c\~oes \'{\i}mpares s\'o
                t\^em \verb+1+'s.
                Exemplos: $\lambda$, \verb+101+, \verb+111+, \verb+1010111011+.}

                $(\{\verb+1+\}\{\verb+0+,\verb+1+\})^*\{\lambda,\verb+1+\}$

          \item {\footnotesize O conjunto das palavras de tamanho m\'ultiplo de 3 terminadas em
                \verb+11+.}

                $(\{\verb+0+,\verb+1+\}^3)^*\{\verb+0+,\verb+1+\}\{\verb+11+\}$

        \end{list}

 \item {\footnotesize Seja a gram\'atica $G=(\{P,A,B,D\},\{\verb+0+,\verb+1+,\#\},R,P)$, onde $R$ \'e:
       \begin{enumerate}
        \item[\ ] $P \,\,\rightarrow\,\, A \# B$
        \item[\ ] $A \,\,\rightarrow\,\, D D A \,\,|\,\, \lambda$
        \item[\ ] $B \,\,\rightarrow\,\, B \verb+1+ \,\,|\,\, \lambda$
        \item[\ ] $D \,\,\rightarrow\,\, \verb+0+ \,\,|\,\, \verb+1+$
       \end{enumerate}}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item {\footnotesize Que linguagem \'e gerada por $G$?}

              $(\{\verb+0+,\verb+1+\}\{\verb+0+,\verb+1+\})^*\#\{\verb+1+\}^*$


        \item {\footnotesize Construa uma gram\'atica que gere $L(G)$, por\'em sem usar regra
              com o lado direito igual a $\lambda$.}

       \begin{enumerate}
        \item[\ ] $P \,\,\rightarrow\,\, A \# B \,\,|\,\, \# B  \,\,|\,\, A \# \,\,|\,\, \#$
        \item[\ ] $A \,\,\rightarrow\,\, D D A \,\,|\,\, D D$
        \item[\ ] $B \,\,\rightarrow\,\, B \verb+1+ \,\,|\,\, \verb+1+$
        \item[\ ] $D \,\,\rightarrow\,\, \verb+0+ \,\,|\,\, \verb+1+$
       \end{enumerate}

        \item Para uma das gram\'aticas, determine quantos passos s\~ao necess\'arios
              para derivar uma palavra de tamanho $n$.

              Para a gram\'atica $G$, s\~ao necess\'arios na gera\c c\~ao de uma palavra $x\#y$:
              \begin{itemize}
               \item 1 passo na aplica\c c\~ao da regra $P \rightarrow A \# B$;
               \item $3|x|/2+1$ passos para gerar $x$: $|x|/2$ aplica\c c\~oes de
                     $A \rightarrow D D A$,
                     $|x|$ de  $D \rightarrow \verb+0+ \,\,|\,\, \verb+1+$ e 1 de $A \rightarrow
                     \lambda$;
               \item $|y|+1$ passos para gerar $y$: $|y|$ aplica\c c\~oes de
                     $B \rightarrow B \verb+1+$ e 1 de $B \rightarrow \lambda$.
              \end{itemize}
              Assim, s\~ao necess\'arios $3|x|/2+|y|+3$ passos.
       \end{list}

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

         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item {\footnotesize $\{\verb+0+\}$}

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

          \item {\footnotesize O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ de tamanho
                \'{\i}mpar e terminadas em \verb+1+.}

                $(\{p,i0,i1\},\{\verb+0+,\verb+1+\},\delta,p,\{i1\})$, onde $\delta$ \'e:

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

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

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

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

          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w| \mbox{ mod } 3=0 
                \mbox{ e } w \mbox{ n\~ao cont\'em }\verb+00+\}$

                $(\{r_01,r_00,r_11,r_10,r_21,r_20,e\},\{\verb+0+,\verb+1+\},\delta,r_01,
                \{r_01,r_00\})$, onde $\delta$ \'e:

                \hspace*{1cm}\begin{tabular}{c|cc}
                 $\delta$ & \verb+0+ & \verb+1+ \\ \hline
                       $r_01$ & $r_10$ & $r_11$ \\
                       $r_00$ & $e$    & $r_11$ \\
                       $r_11$ & $r_20$ & $r_21$ \\
                       $r_10$ & $e$    & $r_21$ \\
                       $r_21$ & $r_00$ & $r_01$ \\
                       $r_20$ & $e$    & $r_01$ \\
                          $e$ & $e$    & $e$ \\
                \end{tabular}

         \end{list}

 \item {\footnotesize Sejam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^m\verb+1+\verb+0+^n\,\,|\,\, m<n\}$
        \item $\{\verb+0+^n\verb+00+^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{conta2})}{\usecounter{conta2}}
        \item Suponha que $L=\{\verb+0+^m\verb+1+\verb+0+^n\,\,|\,\, m<n\}$ \'e
              reconhecida por um AFD de $k$ estados. Seja a palavra
              $z=\verb+0+^k\verb+1+\verb+0+^{k+1}\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\'os $v$. Deveria ser o caso que $uv^iw\in L$ para todo $i\geq 0$; mas
              $uv^2w\not\in L$: $uv^2w=\verb+0+^{k+|v|}\verb+1+\verb+0+^k$ e
              $k+|v|\geq k$.
              Logo a suposi\c c\~ao de que existe AFD para $L$ \'e incorreta.

        \item Um AFD para $\{\verb+0+^n\verb+00+^n\,\,|\,\, n\in\mbox{\bf N}\}$:
              $(\{p,i\},\{\verb+0+\},\delta,p,\{i\})$, 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$ n\~ao pode ser reconhecida por AFD e
              $L\subseteq X$, $X$ n\~ao pode ser reconhecida por AFD.}

              Falso. Qualquer linguagem sobre $\Sigma$ \'e subconjunto de $\Sigma^*$, e
              $\Sigma^*$ pode ser reconhecida por AFD.

        \item {\footnotesize Para qualquer AFD $M$ existe um AFD $N$ tal que $L(M)=L(N)$ e $N$
              tem apenas 1 estado final.}

              Falso. Para a linguagem $\{\lambda,\verb+a+\}$ n\~ao existe AFD com apenas 1
              estado final.

       \end{list}

\end{enumerate}
\end{document}

