\documentclass[12pt,a4paper]{report}

%=================================================================
\addtolength{\topmargin}{-1cm}
\addtolength{\textheight}{2cm}
%\addtolength{\evensidemargin}{-1cm}
%\addtolength{\textwidth}{1.5cm}
%=================================================================
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas re-gu-lar re-gu-la-res}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG
 
\noindent {\it Teoria de Linguagens}
 \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2002
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Prova}/{\em Solu\c c\~ao do professor}

\vspace*{3mm}

\begin{enumerate}

 \item {\footnotesize Descreva cada linguagem abaixo {\em em portugu\^es coloquial\/},
       supondo que o alfabeto delas \'e $\{0,1\}$. Por exemplo: $\{0,1\}^*\{1\}\{0,1\}$:
       {\em Conjunto das palavras cujo pen\'ultimo s\'{\i}mbolo \'e 1\/}.}

       \begin{enumerate}
        \item[(a)] $\{0\}\{0,1\}^*\cup\{0,1\}^*\{1\}$: {\em Conjunto das palavras
              iniciadas em 0 ou terminadas em 1.}

        \item[(b)] $(\{0,1\}\{0,1\}\{0,1\})^*\cap(\{0,1\}^*\{1\})$: {\em Conjunto das palavras
              terminadas em 1 com tamanho m\'ultiplo de 3.}

       \end{enumerate}

 \item {\footnotesize  Obtenha gram\'aticas que gerem as linguagens a seguir.}

       \begin{enumerate}
        \item[(a)] $\{0,1\}^*\{01\}\{11\}^*$.

             \vspace*{1mm}
             \begin{enumerate}
              \item[\ ] $P \,\,\rightarrow\,\, 0 P \,\,|\,\, 1 P \,\,|\,\, 0 1 A$
              \item[\ ] $A \,\,\rightarrow\,\, 1 1 A \,\,|\,\, \lambda$
             \end{enumerate}

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

             \vspace*{1mm}
             \begin{enumerate}
              \item[\ ] $P \,\,\rightarrow\,\, a A \,\,|\,\, b P \,\,|\,\, c P \,\,|\,\, c$
              \item[\ ] $A \,\,\rightarrow\,\, a A \,\,|\,\, b B \,\,|\,\, c P \,\,|\,\, c$
              \item[\ ] $B \,\,\rightarrow\,\, a A \,\,|\,\, b P \,\,|\,\, c$
             \end{enumerate}

       \end{enumerate}

 \item {\footnotesize Construa aut\^omatos finitos determin\'{\i}sticos (AFD's) para
       reconhecer as linguagens abaixo, de alfabeto $\{0,1\}$:}

       \begin{enumerate}
        \item[(a)] {\footnotesize O conjunto das palavras cujo pen\'ultimo s\'{\i}mbolo \'e 1. Cada
               palavra tem tamanho maior do que 1.}

               \vspace*{1mm}
               $(\{00,01,10,11\},\{0,1\},\delta,00,\{10,11\})$, onde $\delta$ \'e:

               \begin{tabular}{c|cc}
                $\delta$ &  0 &  1 \\ \hline
                      00 & 00 & 01 \\
                      01 & 10 & 11 \\
                      10 & 00 & 01 \\
                      11 & 10 & 11
               \end{tabular}

        \item[(b)] {\footnotesize $\{w\in\{0,1\}^*\,\,|\,\,\mbox{ toda subpalavra de $w$ de tamanho
                   3 tem 0's e 1's}\}$. Se $|w|<3$, $w$ deve ser reconhecida.}

               \vspace*{1mm}
               $(\{\lambda,10,01,00,11,e\},\{0,1\},\delta,\lambda,\{\lambda,10,01,00,11\})$,
               onde $\delta$ \'e:

               \begin{tabular}{c|cc}
                $\delta$  &  0 &  1 \\ \hline
                $\lambda$ & 10 & 01 \\
                       10 & 00 & 01 \\
                       01 & 10 & 11 \\
                       00 & $e$ & 01 \\
                       11 & 10 &  $e$ \\
                      $e$ & $e$ &  $e$
               \end{tabular}

       \end{enumerate}

 \item {\footnotesize 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)] {\footnotesize Que linguagens s\~ao reconhecidas por $M_1$ e $M_2$?}

                   \vspace*{1mm}
                   $L(M_1)= (\{0,1\}\{0,1\})^*\{1\}$

                   \vspace*{1mm}
                   $L(M_2)= \{1\}^*\{0\}\{0,1\}^*$

        \item[(b)]{\footnotesize Usando produto de aut\^omatos, determine AFD's que
               reconhe\c am $L(M_1)\cup L(M_2)$
               e $L(M_1)\cap L(M_2)$. Especifique apenas uma fun\c c\~ao de transi\c c\~ao
               (usando tabela ou grafo) e explicite os estados finais para cada caso.}

             \vspace*{1mm}
             Em ambos os casos tem-se a seguinte fun\c c\~ao de transi\c c\~ao:

               \begin{tabular}{c|cc}
                $\delta$ & 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}

            Estados finais para {\bf uni\~ao\/}: $\{[i_1,n],[i_1,s],[i_0,s],[p,s]\}$.

            Estados finais para {\bf interse\c c\~ao\/}: $\{[i_1,s]\}$.
       \end{enumerate}

 \item {\footnotesize Construa aut\^omatos finitos n\~ao de\-ter\-mi\-n\'{\i}s\-ti\-cos que
       reconhe\c cam as linguagens a\-bai\-xo, de alfabeto $\{a,b,c\}$.}

       \begin{enumerate}
        \item[(a)] {\footnotesize O conjunto das palavras em que o \'ultimo s\'{\i}mbolo
              tenha ocorrido antes.
              Cada palavra tem pelo menos 2 s\'{\i}mbolos.}

             \vspace*{1mm}
               $(\{\lambda,a,b,c,f\},\{a,b,c\},\delta,\{\lambda\},\{f\})$, onde $\delta$ \'e:

               \begin{tabular}{c|ccc}
                $\delta$  &            $a$  &            $b$  &  $c$  \\ \hline
                $\lambda$ & $\{\lambda,a\}$ & $\{\lambda,b\}$ & $\{\lambda,c\}$ \\
                      $a$ &         $\{f\}$ &         $\{a\}$ &         $\{a\}$ \\
                      $b$ &         $\{b\}$ &         $\{f\}$ &         $\{b\}$ \\
                      $c$ &         $\{c\}$ &         $\{c\}$ &         $\{f\}$ \\
                      $f$ &         $\{\}$ &         $\{\}$ &         $\{\}$
               \end{tabular}

        \item[(b)] {\footnotesize O conjunto das palavras em que o \'ultimo s\'{\i}mbolo
               {\em n\~ao\/} tenha ocorrido antes. Cada palavra tem pelo menos 1 s\'{\i}mbolo.}

             \vspace*{1mm}
               $(\{a,b,c,f\},\{a,b,c\},\delta,\{a,b,c\},\{f\})$, onde $\delta$ \'e:

               \begin{tabular}{c|ccc}
                $\delta$  &            $a$  &            $b$  &  $c$  \\ \hline
                      $a$ &         $\{f\}$ &         $\{a\}$ &         $\{a\}$ \\
                      $b$ &         $\{b\}$ &         $\{f\}$ &         $\{b\}$ \\
                      $c$ &         $\{c\}$ &         $\{c\}$ &         $\{f\}$ \\
                      $f$ &         $\{\}$ &         $\{\}$ &         $\{\}$
                \end{tabular}
       \end{enumerate}

\end{enumerate}

\vspace*{5mm}
\noindent{\bf Extra:} Seja a linguagem $L$ definida {\em recursivamente\/} assim:
\begin{enumerate}
 \item $\lambda\in L$;
 \item se $x\in L$, ent\~ao $xb\in L$ e $axb\in L$.
\end{enumerate}
Toda palavra de $L$ tem a forma $a^mb^k$, onde $m\leq k$.

\vspace*{2mm}
\noindent{\em Prova\/}:

\vspace*{1mm}
Por indu\c c\~ao forte sobre o tamanho da palavra. Tem-se, por (a), que $\lambda\in L$. E
$\lambda=a^0b^0$. Suponha, como hip\'ostese de indu\c c\~ao, que toda palavra $w$ de $L$ tem
a forma $a^mb^k$, onde $m\leq k$, se $|w|\leq n$. Basta, ent\~ao, provar que o mesmo
resultado vale se $|w|= n+1$. Seja, ent\~ao, uma palavra $w$ de $L$ de tamanho $n+1$. Como
$|w|>0$, por (b) $w$ \'e da forma $xb$ ou $axb$, onde $x\in L$.
Em qualquer destes dois casos, $|x|\leq n$. Assim, pela hip\'otese de indu\c c\~ao,
$x$ tem a forma $a^mb^k$, onde $m\leq k$. Portanto, $w$ \'e da forma $a^mb^{k+1}$ ou
$a^{m+1}b^{k+1}$, mantendo a forma requerida.

\end{document}
 


