\documentclass[12pt, a4paper]{report}
 
\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Prof.: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Prova/Solu\c c\~ao do professor}

\begin{enumerate} \footnotesize
 \item Descreva mais formalmente (usando conjuntos, concatena\c c\~ao, fecho de Kleene, etc.)
       as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras de tamanho maior que zero.

                   {\em Resposta\/}: $\{0,1\}^+$.

        \item[(b)] O conjunto das palavras que cont\^em a subpalavra 001.

                   {\em Resposta\/}: $\{0,1\}^*\{001\}\{0,1\}^*$.

        \item[(c)] O conjunto das palavras de tamanho \'{\i}mpar terminadas em 1.

                   {\em Resposta\/}: $(\{0,1\}\{0,1\})^*\{1\}$.

        \item[(d)] O conjunto das palavras com n\'umero par de 0's ou \'{\i}mpar de 1's (ou ambos).

                   {\em Resposta\/}:
                   $\{1\}^*(\{0\}\{1\}^*\{0\}\{1\}^*)^*\cup\{0\}^*\{1\}\{0\}^*(\{1\}\{0\}^*\{1\}\{0\}^*)^*$.

        \item[(e)] O conjunto das palavras de tamanho par cuja primeira metade seja id\^entica
                   \`a segunda.

                   {\em Resposta\/}: $\{ww\,\,|\,\, w\in\{0,1\}^*\}$.

       \end{enumerate}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{a^nb^n\,\,|\,\, n\in\mbox{\bf N}\}$.

                   {\em Resposta\/}:

                   \begin{tabular}{ccl}
                    $P$ & $\rightarrow$ & $a P b \,\,|\,\, \lambda$
                   \end{tabular}

        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ de tamanho \'{\i}mpar terminadas em 1.

                   {\em Resposta\/}:

                   \begin{tabular}{ccl}
                     $P$ & $\rightarrow$ & $0 I \,\,|\,\, 1 I \,\,|\,\, 1$ \\
                     $I$ & $\rightarrow$ & $0 P \,\,|\,\, 1 P$ \\
                   \end{tabular}

        \item[(c)] $\{w\in\{a,b\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em a subpalavra $aa$}\}$.

                   {\em Resposta\/}:

                   \begin{tabular}{ccl}
                     $P$ & $\rightarrow$ & $a A \,\,|\,\, b P \,\,|\,\, \lambda$ \\
                     $A$ & $\rightarrow$ & $b P \,\,|\,\, \lambda$ \\
                   \end{tabular}

        \item[(d)] $\{ww^R\,\,|\,\, w\in\{a,b\}^*\}$.

                   {\em Resposta\/}:

                   \begin{tabular}{ccl}
                     $P$ & $\rightarrow$ & $a P a \,\,|\,\, b P b \,\,|\,\, \lambda$
                   \end{tabular}

       \end{enumerate}

 \item Construa aut\^omatos finitos determin\'{\i}sticos para:
       \begin{enumerate}
        \item[(a)] $\emptyset$.

                   {\em Resposta\/}: $(\{0\},\Sigma,\emptyset,0,\emptyset)$, qualquer que seja $\Sigma$.

        \item[(b)] O conjunto das palavras sobre $\{0,1\}$ de tamanho \'{\i}mpar terminadas em 1.

                   {\em Resposta\/}: $(\{p,i_0,i_1\},\{0,1\},\delta,p,\{i_1\})$, onde $\delta$ \'e dada por:
                   \begin{center}
                   \begin{tabular}{c|cc}
                    $\delta$ & 0 & 1 \\ \hline
                       $p$   & $i_0$ & $i_1$ \\
                       $i_0$ & $p$ & $p$ \\
                       $i_1$ & $p$ & $p$ \\
                   \end{tabular}
                   \end{center}

        \item[(c)] $\{w\in\{a,b\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em a subpalavra $aa$}\}$.

                   {\em Resposta\/}: $(\{\lambda,\mbox{\em a\/},\mbox{\em aa\/}\},\{a,b\},\delta,\lambda,\{\lambda,
                   \mbox{\em a\/}\})$, onde $\delta$ \'e dada por:
                   \begin{center}
                   \begin{tabular}{c|cc}
                    $\delta$ & $a$ & $b$ \\ \hline
                       $\lambda$ & {\em a} & $\lambda$ \\
                       {\em a}  & {\em aa} & $\lambda$ \\
                       {\em aa} & {\em aa} & {\em aa}
                   \end{tabular}
                   \end{center}

        \item[(d)] $\{01\}^*\{10\}^*$.

                   {\em Resposta\/}: $(\{A,B,C,D,E\},\{0,1\},\delta,A,\{A,D\})$, onde $\delta$ \'e dada por:
                   \begin{center}
                   \begin{tabular}{c|cc}
                    $\delta$ & 0 & 1 \\ \hline
                       $A$ & $B$ & $C$ \\
                       $B$ & $E$ & $A$ \\
                       $C$ & $D$ & $E$ \\
                       $D$ & $E$ & $C$ \\
                       $E$ & $E$ & $E$
                   \end{tabular}
                   \end{center}

       \end{enumerate}

 \item Sim ou n\~ao? Por que?
       \begin{enumerate}
        \item[(a)] Seja $J$ o conjunto de todos os programas escritos na linguagem Java que tenham, no
                   m\'aximo, $10^{10^{10}}$ caracteres. Existe um AFD que reconhece $J$.

                   {\em Resposta\/}: Sim. Qualquer linguagem finita pode ser reconhecida por AFD.

        \item[(b)] Existe algoritmo que determina se $L(M)=\emptyset$ para quaquer AFD $M$.

                   {\em Resposta\/}: Sim. Aplicando-se o algoritmo de minimiza\c c\~ao, se for
                   obtido um AFD com um \'unico estado e este n\~ao for estado final (como no item
                   {\em a\/} da quest\~ao 3), $L(M)=\emptyset$; caso contr\'ario, $L(M)\not=\emptyset$.

        \item[(c)] Se um AFD $M$ reconhece uma palavra de tamanho igual ao n\'umero de estados de $M$,
                   ent\~ao $L(M)$ \'e infinita.

                   {\em Resposta\/}: Sim. Seja $k$ o n\'umero de estados de $M$. Se $M$ reconhece uma
                   palavra $w$ de tamanho $k$, o caminho percorrido no diagrama de estados de $M$ tem
                   $k+1$ estados. Assim, algum estado \'e repetido no caminho, o que implica que
                   o caminho tem um ciclo. Isto, por sua vez, implica que $w$ \'e da forma $xyz$,
                   onde $y$ \'e a subpalavra correspondente ao ciclo. Como o ciclo pode ser percorrido
                   quantas vezes se queira, tem-se que $xy^iz\in L(M)$ para todo $i\in\mbox{\bf N}$.
                   Logo $L(M)$ \'e infinita.

        \item[(d)] Suponha que existam AFD's para as linguagens $A$, $B$ e $C$. \'E poss\'{\i}vel
                   construir um AFD que reconhe\c ca $A-(B-C)$. (Lembre-se que $A-B=A\cap\overline{B}$.)

                   {\em Resposta\/}: Sim. Observe que $A-(B-C)=A\cap\overline{B-C}=
                   A\cap\overline{B\cap\overline{C}}=A\cap(\overline{B}\cup C)$. Como existe AFD para
                   $B$, existe AFD para $\overline{B}$. Como existem AFD's para $\overline{B}$ e para
                   $C$, existe AFD para $\overline{B}\cup C$. Finalmente, como existem AFD's para
                   $A$ e para $\overline{B}\cup C$, existe AFD para $A\cap(\overline{B}\cup C)$.
                   Conclus\~ao: existe AFD para $A-(B-C)$.

       \end{enumerate}
\end{enumerate}

\end{document}
 
