\documentclass[12pt, a4paper]{report}

\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{1cm}
\newcounter{conta}
\pagestyle{empty}
\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{2}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Prova} \hfill 23/01/02

\begin{enumerate} \footnotesize
 \item Descreva, em portugu\^es coloquial, as seguintes linguagens sobre o alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] $\{0\}\{0,1\}^*\cup\{0,1\}^*\{1\}$
        \item[(b)] $\{0,1\}^*\{01\}\{11\}^*$
       \end{enumerate}
       [Exemplo: $\{0,1\}^*\{1\}\{0,1\}$ \'e {\em o conjunto das palavras cujo pen\'ultimo
                 s\'{\i}mbolo \'e 1\/}.]

       {\em Solu\c c\~ao\/}:
       \begin{enumerate}
        \item[(a)] Conjunto das palavras que come\c cam com 0 ou terminam com 1.
        \item[(b)] Conjunto das palavras que terminam com 0 seguido de um n\'umero \'{\i}mpar
                   de 1's consecutivos.
       \end{enumerate}

 \item Obtenha gram\'aticas para as seguintes linguagens:
       \begin{enumerate}
        \item[(a)] $\{w\in\{a,b,c\}^*\,\,|\,\, w \mbox{ n\~ao cont\'em a subpalavra $cba$}\}$.
        \item[(b)] $\{ww^R\,\,|\,\, w\in\{a,b\}^* \mbox{ e $w$ cont\'em pelo menos um $a$
                   e um $b$}\}$.
       \end{enumerate}

       {\em Solu\c c\~ao\/}:
       \begin{enumerate}
        \item[(a)] $P\rightarrow aP \,\,|\,\, bP \,\,|\,\, cA \,\,|\,\, \lambda$ \\
                   $A\rightarrow aP \,\,|\,\, bB \,\,|\,\, cA \,\,|\,\, \lambda$ \\
                   $B\rightarrow bP \,\,|\,\, cA \,\,|\,\, \lambda$
        \item[(b)] $P\rightarrow aAa \,\,|\,\, bBb$ \\
                   $A\rightarrow aAa \,\,|\,\, bXb$ \\
                   $B\rightarrow aXa \,\,|\,\, bBb$ \\
                   $X\rightarrow aXa \,\,|\,\, bXb \,\,|\,\, \lambda$
       \end{enumerate}

 \item Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para reconhecer as seguintes
       linguagens de alfabeto $\{0,1\}$:
       \begin{enumerate}
        \item[(a)] O conjunto das palavras cujo pen\'ultimo s\'{\i}mbolo \'e 1.
        \item[(b)] $\{w010\,\,|\,\, w\in\{0,1\}^*\}$.
        \item[(c)] $(\{1\}\cup\{0\}\{1\}^*\{0\})^*$.
       \end{enumerate}

       {\em Solu\c c\~ao\/}:
       \begin{enumerate}
        \item[(a)] $(\{\mbox{00},\mbox{01},\mbox{10},\mbox{11}\},\{0,1\},\delta,\mbox{00},
                    \{\mbox{10},\mbox{11}\})$, onde $\delta$ \'e dada por:

                   \begin{tabular}{c|cc}
                    $\delta$ & 0 & 1 \\ \hline
                    00 & 00 & 01 \\
                    01 & 10 & 11 \\
                    10 & 00 & 01 \\
                    11 & 10 & 11
                   \end{tabular}
        \item[(b)] $(\{\lambda,\mbox{0},\mbox{01},\mbox{010}\},\{0,1\},\delta,\lambda,
                    \{\mbox{010}\})$, onde $\delta$ \'e dada por:

                   \begin{tabular}{c|cc}
                    $\delta$ & 0 & 1 \\ \hline
                    $\lambda$ & 0 & $\lambda$ \\
                    0 & 0 & 01 \\
                    01 & 010 & $\lambda$ \\
                    010 & 0 & 01
                   \end{tabular}

        \item[(c)] $(\{p,i\},\{0,1\},\delta,p,\{p\})$, onde $\delta$ \'e dada por:

                   \begin{tabular}{c|cc}
                    $\delta$ & 0 & 1 \\ \hline
                    $p$ & $i$ & $p$ \\
                    $i$ & $p$ & $i$
                   \end{tabular}
       \end{enumerate}

 \item Sejam os AFD's a seguir:
       \begin{enumerate}
        \item[$M_1$:] $(\{p,i_0,i_1\},\{0,1\},\delta_1,p,\{i_1\})$, onde $\delta_1$ \'e dada por:\

                      \begin{tabular}{c|cc}
                       $\delta$ & 0 & 1 \\ \hline
                           $p$  & $i_0$ & $i_1$ \\
                         $i_0$  & $p$ & $p$ \\
                         $i_1$  & $p$ & $p$
                      \end{tabular}
        \item[$M_2$:] $(\{n,s\},\{0,1\},\delta_2,n,\{s\})$, onde $\delta_2$ \'e dada por:

                      \begin{tabular}{c|cc}
                       $\delta$ & 0 & 1 \\ \hline
                           $n$  & $s$ & $n$ \\
                           $s$  & $s$ & $s$
                      \end{tabular}
       \end{enumerate}

       \begin{enumerate}
        \item[(a)] Que linguagens s\~ao reconhecidas por $M_1$ e $M_2$?
        \item[(b)] Usando produto de aut\^omatos, construa AFD's para $L(M_1)\cup L(M_2)$ e
                   $L(M_1)\cap L(M_2)$.
        \item[(c)] Minimize os AFD's obtidos em (b).
       \end{enumerate}

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

       \begin{enumerate}
        \item[(a)] $L(M_1)$: conjunto das palavras de tamanho \'{\i}mpar terminadas em 1.

                   $L(M_1)$: conjunto das palavras que cont\^em pelo menos um 0.

        \item[(b)] AFD para $L(M_1)\cup L(M_2)$: $(E_3,\{0,1\},\delta_3,[p,n],F_3)$, onde:
                   \begin{itemize}
                    \item $E_3=\{p,i_0,i_1\}\times\{n,s\}$;
                    \item $F_3=\{[i_1,n],[i_1,s],[i_0,s],[p,s]\}$; e
                    \item $\delta_3$ \'e dada por:

                          \begin{tabular}{c|cc}
                           $\delta_3$ & 0 & 1 \\ \hline
                           $[p,n]$  & $[i_0,s]$ & $[i_1,n]$ \\
                           $[i_0,s]$ & $[p,s]$ & $[p,s]$ \\
                           $[i_1,n]$ & $[p,s]$ & $[p,n]$ \\
                           $[p,s]$  & $[i_0,s]$ & $[i_1,s]$ \\
                           $[i_1,s]$ & $[p,s]$ & $[p,s]$
                      \end{tabular}
                   \end{itemize}

                   AFD para $L(M_1)\cap L(M_2)$: o mesmo que o anterior, mas com:
                   \begin{itemize}
                    \item $F_3=\{[i_1,s]\}$.
                   \end{itemize}

        \item[(c)] Para $L(M_1)\cup L(M_2)$, na minimiza\c c\~ao os estados $[i_0,s]$, $[p,s]$
                   e $[i_1,s]$ ficam na mesma classe de equival\^encia. Assim, o AFD m\'{\i}nimo
                   fica com 3 estados; a fun\c c\~ao de transi\c c\~ao fica assim:

                   \begin{tabular}{c|cc}
                    $\delta_3$ & 0 & 1 \\ \hline
                    $\{[p,n]\}$   & $\{[i_0,s],[p,s],[i_1,s]\}$ & $\{[i_1,n]\}$ \\
                    $\{[i_1,n]\}$ & $\{[i_0,s],[p,s],[i_1,s]\}$ & $\{[p,n]\}$  \\
                    $\{[i_0,s],[p,s],[i_1,s]\}$ & $\{[i_0,s],[p,s],[i_1,s]\}$ &
                           $\{[i_0,s],[p,s],[i_1,s]\}$
                   \end{tabular}

                   O estado inicial \'e $\{[p,n]\}$ e os outros dois s\~ao finais. O AFD
                   para $L(M_1)\cap L(M_2)$, j\'a \'e m\'{\i}nimo.
       \end{enumerate}
\end{enumerate}

\end{document}
 
