\documentclass[11pt,a4paper]{book}

\usepackage[portuguese]{babel}
\usepackage{verbatim}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}

\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{2}^{\mbox{\underline{o}}}$ semestre de 2007 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova/Solu\c{c}\~ao do professor} \hfill 24/09/2007

\begin{enumerate}
 \item {\footnotesize Seja a gram\'atica $G=(\{A,B\},\{{\tt a},{\tt b}\},R,A)$ em que $R$ \'e
       cons\-ti\-tu\'{\i}\-do das quatro regras:
       \begin{enumerate}
        \item[\ \ \ ] $A\rightarrow {\tt a} A {\tt b}\,|\, B$
        \item[\ \ \ ] $B\rightarrow {\tt b} B \,|\, \lambda$
      \end{enumerate}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Apresente um esquema de deriva\c{c}\~ao que mostre como derivar
             qualquer palavra de $L(G)$.
       \item Descreva $L(G)$.
       \item Prove que $L(G)$ \'e ou n\~ao \'e regular.
      \end{list}}
      
      {\em Solu\c{c}\~ao\/}:
      
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item \begin{tabbing}
              xxx\= $A$ \= $\stackrel{k}{\Rightarrow} \, {\tt a}^n {\tt b}^k B {\tt b}^n$ \= \kill
              \> $A$ \> $\stackrel{n}{\Rightarrow} \, {\tt a}^n A {\tt b}^n$
                        \> ($A\rightarrow {\tt a} A {\tt b}$ $n$ vezes, $n\geq 0$) \\
              \>     \> $\Rightarrow \, {\tt a}^n B {\tt b}^n$
                        \> ($A\rightarrow B$) \\
              \>     \> $\stackrel{k}{\Rightarrow} \, {\tt a}^n {\tt b}^k B {\tt b}^n$
                        \> ($B\rightarrow {\tt b} B$ $k$ vezes, $k\geq 0$) \\
              \>     \> $\Rightarrow \, {\tt a}^n {\tt b}^k {\tt b}^n$
                        \> ($B\rightarrow \lambda$)
             \end{tabbing}
       \item $L(G)=\{{\tt a}^m{\tt b}^n \,|\, m\leq n\}$.
       \item Suponha que $L(G)$ seja regular, seja $k$ a constante mencionada no LB e
             $z={\tt a}^k{\tt b}^k$. Como $z\in L(G)$ e $|z|\geq k$, o LB diz que existem $u$, $v$ e $w$
             tais que $z=uvw$, $|uv|\leq k$, $v\not=\lambda$ e $uv^iw\in L(G)$ para todo
             $i\geq 0$. Sendo $z=uvw$ e $|uv|\leq k$, $v$ cont\'em apenas {\tt a}s, e
             sendo $v\not=\lambda$, $k+|v|>k$ e, portanto, $uv^2w={\tt a}^{k+|v|}{\tt b}^k
             \not\in L(G)$. Isso contradiz o LB. Logo, $L(G)$ n\~ao \'e regular.
      \end{list}

 \item {\footnotesize Obtenha um AFD que reconhe\c{c}a $\{{\tt 00},{\tt 11}\}^*\{{\tt 01},{\tt 10}\}^*$.}
      
      {\em Solu\c{c}\~ao\/}:
      
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(90,23)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=ir](1)(10,14){}
          \node(2)(26,26){}
          \node(3)(26,2){}
          \node[Nmarks=r](4)(42,14){}
          \node(5)(58,26){}
          \node(6)(58,2){}

          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawedge[curvedepth=2](2,1){{\tt 0}}
          \drawedge[curvedepth=2](1,3){{\tt 1}}
          \drawedge[curvedepth=2](3,1){{\tt 1}}
          \drawedge[curvedepth=0](2,4){{\tt 1}}
          \drawedge[curvedepth=0](3,4){{\tt 0}}
          \drawedge[curvedepth=2](4,5){{\tt 0}}
          \drawedge[curvedepth=2](5,4){{\tt 1}}
          \drawedge[curvedepth=2](4,6){{\tt 1}}
          \drawedge[curvedepth=2](6,4){{\tt 0}}
         \end{picture}
        }
       \end{center}

      
 \item {\footnotesize Seja o AFD com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(100,40)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(10,20){1}
          \node(2)(30,30){2}
          \node(3)(30,10){3}
          \node[Nmarks=r](4)(50,30){4}
          \node(5)(50,10){5}
          \node[Nmarks=r](6)(70,30){6}
          \node(7)(70,10){7}
          \node(8)(90,20){8}

          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
          \drawedge[curvedepth=2](2,1){{\tt 0}}
          \drawedge[curvedepth=0](2,3){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](3,4){{\tt 0}}
          \drawloop[loopangle=270](3){{\tt 1}}
          \drawedge[curvedepth=0](4,5){{\tt 0}}
          \drawedge[curvedepth=0](4,6){{\tt 1}}
          \drawloop[loopangle=270](5){{\tt 0}}
          \drawedge[curvedepth=2](5,7){{\tt 1}}
          \drawedge[curvedepth=0](6,7){{\tt 0}}
          \drawloop[loopangle=90](6){{\tt 1}}
          \drawedge[curvedepth=2](7,5){{\tt 0}}
          \drawloop[loopangle=270](7){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](8,6){{\tt 0}}
          \drawedge[curvedepth=0](8,7){{\tt 1}}
         \end{picture}
        }
       \end{center}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Obtenha o diagrama de estados de um AFD m\'{\i}nimo equivalente.
             (Denote cada estado como um conjunto de estados equivalentes.)
       \item Que linguagem \'e reconhecida pelo AFD em quest\~ao?
      \end{list}}
            
      {\em Solu\c{c}\~ao\/}:
      
       \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Inicialmente, deve-se eliminar o estado 8, inalcan\c{c}\'avel a partir do
             inicial. As parti\c{c}\~oes induzidas pela rela\c{c}\~ao de equival\^encia
             entre estados evoluem assim:
             \begin{quote}
              $S_0$: $\{1,2,3,5,7\}$ $\{4,6\}$; \\
              $S_1$: $\{1,2,5,7\}$ $\{3\}$ $\{4,6\}$; \\
              $S_2$: $\{1,2\}$ $\{5,7\}$ $\{3\}$ $\{4,6\}$; \\
              $S_3$: $\{1,2\}$ $\{5,7\}$ $\{3\}$ $\{4,6\}$.
             \end{quote}
             Diagrama de estados do AFD m\'{\i}nimo:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(90,17)
          \gasset{Nw=12, Nh=6, Nmr=4.5, loopdiam=6}

          \node[Nmarks=i](1)(10,5){$\{1,2\}$}
          \node(2)(32,5){$\{3\}$}
          \node[Nmarks=r](3)(54,5){$\{4,6\}$}
          \node(4)(76,5){$\{5,7\}$}

          \drawloop[loopangle=90](1){{\tt 0}}
          \drawedge[curvedepth=0](1,2){{\tt 1}}
          \drawloop[loopangle=90](2){{\tt 1}}
          \drawedge[curvedepth=0](2,3){{\tt 0}}
          \drawloop[loopangle=90](3){{\tt 1}}
          \drawedge[curvedepth=0](3,4){{\tt 0}}
          \drawloop[loopangle=90](4){{\tt 0},{\tt 1}}
         \end{picture}
        }
       \end{center}
       \item Linguagem: $\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*$.
      \end{list}

      
 \item {\footnotesize Seja o AFN com o seguinte diagrama de estados:
       \begin{center}
        \begin{picture}(60,15) \setlength{\unitlength}{1mm}
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i, iangle=0](i1)(50,5){$i_1$}
         \node[Nmarks=i](i0)(10,5){$i_0$}
         \node[Nmarks=r](f)(30,5){$f$}
      
         \drawedge[curvedepth=0](i0,f){{\tt 0}}
         \drawloop[loopangle=90](i0){{\tt 1}}
         \drawedge[curvedepth=0, ELside=r](i1,f){{\tt 1}}
         \drawloop[loopangle=90](i1){{\tt 0}}
        \end{picture}
       \end{center}
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item Que linguagem \'e reconhecida pelo AFN em quest\~ao?
       \item Obtenha um AFD equivalente pelo m\'etodo de constru\c{c}\~ao-de-subconjuntos.
      \end{list}}
            
      {\em Solu\c{c}\~ao\/}:
      
      \begin{list}{\alph{conta})}{\usecounter{conta}}
       \item $\{{\tt 0}\}^*\{{\tt 1}\}\cup\{{\tt 1}\}^*\{{\tt 0}\}$.
       \item AFD:
\begin{center}
  \begin{picture}(90,40) \setlength{\unitlength}{1mm}
   \gasset{Nw=12, Nh=6, Nmr=4.5, loopdiam=6}

   \node[Nmarks=i](1)(20,20){$\{i_0,i_1\}$}
   \node[Nmarks=r](2)(30,32){$\{i_1,f\}$}
   \node[Nmarks=r](3)(30,8){$\{i_0,f\}$}
   \node[Nmarks=r](6)(40,20){$\{f\}$}
   \node(4)(50,32){$\{i_1\}$}
   \node(5)(50,8){$\{i_0\}$}
   \node(7)(60,20){$\emptyset$}

   \drawedge[curvedepth=0](1,2){{\tt 0}}
   \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
   \drawedge[curvedepth=0](2,4){{\tt 0}}
   \drawedge[curvedepth=0, ELside=r](2,6){{\tt 1}}
   \drawedge[curvedepth=0, ELside=r](3,5){{\tt 1}}
   \drawedge[curvedepth=0](3,6){{\tt 0}}
   \drawedge[curvedepth=0, ELside=r](4,6){{\tt 1}}
   \drawloop[loopangle=90](4){{\tt 0}}
   \drawedge[curvedepth=0](5,6){{\tt 0}}
   \drawloop[loopangle=270](5){{\tt 1}}
   \drawedge[curvedepth=0](6,7){{\tt 0},{\tt 1}}
   \drawloop[loopangle=0](7){{\tt 0},{\tt 1}}
  \end{picture}
\end{center}
      \end{list}
      
 \item {\footnotesize Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando
       pro\-prie\-da\-des de fechamento:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 1000\}$;
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m\not=n\}$.
       \end{list}}
            
       {\em Solu\c{c}\~ao\/}:
      
      \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L=\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 1000\}$.
        
              Suponha que $L$ seja regular. A linguagem $\{{\tt 0}^n{\tt 1}^n\,|\, n<1000\}$
              \'e regular, pois \'e finita. Como as linguagens regulares s\~ao fechadas sob
              uni\~ao, ent\~ao $L\cup\{{\tt 0}^n{\tt 1}^n\,|\, n<1000\}$ \'e regular. Mas
              $L\cup\{{\tt 0}^n{\tt 1}^n\,|\, n<1000\}=\{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}$,
              que n\~ao \'e regular. Contradi\c{c}\~ao! Portanto, $L$ n\~ao \'e regular.
        \item $L=\{{\tt 0}^m{\tt 1}^n\,|\, m\not=n\}$.
        
              Suponha que $L$ seja regular. Como as linguagens regulares s\~ao fechadas sob
              complementa\c{c}\~ao, $\overline{L}$ \'e regular. Como $\{{\tt 0}\}^*\{{\tt 1}\}^*$
              tamb\'em \'e uma linguagem regular e linguagens regulares s\~ao fechadas sob
              interse\c{c}\~ao, $\overline{L}\cap\{{\tt 0}\}^*\{{\tt 1}\}^*$ deve ser
              regular. Mas, $\overline{L}\cap\{{\tt 0}\}^*\{{\tt 1}\}^*=
              \{{\tt 0}^n{\tt 1}^n\,|\, n\geq 0\}$, que n\~ao \'e regular.
              Contradi\c{c}\~ao! Portanto, $L$ n\~ao \'e regular.
       \end{list}
\end{enumerate}

\end{document}