\documentclass[11pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\vspace*{20mm}
\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}/DINTER
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova}/Solução do professor \hfill 08/10/2010

\begin{enumerate}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item AFD: \mbox{\setlength{\unitlength}{1mm}
                    \begin{picture}(100,10)(0,4)
                     \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=4}

                     \node[Nmarks=i](1)(10,5){}
                     \node[Nmarks=r](2)(25,5){}

                     \drawedge[curvedepth=0](1,2){\tt 1}
                     \drawloop[loopangle=0](2){\tt 0,1}
                    \end{picture}
                   } \\

              ER: $1(0+1)^*$
        \item AFD: \mbox{\setlength{\unitlength}{1mm}
                    \begin{picture}(100,10)(0,4)
                     \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=4}

                     \node[Nmarks=i](1)(10,5){}
                     \node(2)(25,5){}
                     \node[Nmarks=r](3)(40,5){}

                     \drawedge[curvedepth=0](1,2){\tt 0,1}
                     \drawedge[curvedepth=0](2,3){\tt 1}
                     \drawloop[loopangle=0](3){\tt 0,1}
                    \end{picture}
                   } \\

              ER: $(0+1)1(0+1)^*$
        \item AFD: \mbox{\setlength{\unitlength}{1mm}
                    \begin{picture}(100,10)(0,4)
                     \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=4}

                     \node[Nmarks=ir](1)(10,5){}
                     \node[Nmarks=r](2)(25,5){}
                     \node[Nmarks=r](3)(40,5){}

                     \drawedge[curvedepth=0](1,2){\tt 0,1}
                     \drawedge[curvedepth=0](2,3){\tt 0}
                     \drawloop[loopangle=0](3){\tt 0,1}
                    \end{picture}
                   } \\

              ER: $\lambda+0+1+(0+1)0(0+1)^*$
        \item AFD: \mbox{\setlength{\unitlength}{1mm}
                    \begin{picture}(100,10)(0,4)
                     \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=4}

                     \node[Nmarks=i](1)(10,5){}
                     \node(2)(25,5){}
                     \node[Nmarks=r](3)(40,5){}

                     \drawedge[curvedepth=0](1,2){\tt 1}
                     \drawedge[curvedepth=0](2,3){\tt 1}
                     \drawloop[loopangle=0](3){\tt 0,1}
                    \end{picture}
                   } \\

              ER: $11(0+1)^*$
        \item AFD: \mbox{\setlength{\unitlength}{1mm}
                    \begin{picture}(100,10)(0,4)
                     \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=4}

                     \node[Nmarks=i](1)(10,5){}
                     \node[Nmarks=r](2)(25,5){}
                     \node[Nmarks=r](3)(40,5){}

                     \drawedge[curvedepth=0](1,2){\tt 1}
                     \drawedge[curvedepth=0](2,3){\tt 0}
                     \drawloop[loopangle=0](3){\tt 0,1}
                    \end{picture}
                   } \\

              ER: $1+10(0+1)^*$
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \begin{tabbing}
               $A$ \= $\,\Rightarrow\, {\tt 0}{\tt 0}^nB{\tt 1}^n$ \= \kill
               $A$ \> $\,\Rightarrow\, {\tt 0}B$ \> ($A \,\rightarrow\, {\tt 0} B$) \\
                   \> $\,\Rightarrow\, {\tt 0}{\tt 0}^nB{\tt 1}^n$ \> ($B \,\rightarrow\, A {\tt 1}$ e 
                                           $A \,\rightarrow\, {\tt 0}B$, $n\geq 0$ vezes cada uma) \\
                   \> $\,\Rightarrow\, {\tt 0}^{n+1}{\tt 1}^n$ \> ($B \,\rightarrow\, \lambda$)
              \end{tabbing}
        \item $L(G)=\{{\tt 0}^{n+1}{\tt 1}^n\,|\, n\geq 0\}$.
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item  $a_1=a_2$ e $b_1=b_2$.

               \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,28)
                \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=5}

                \node[Nmarks=i](1)(20,13){}
                \node(2)(35,23){}
                \node(3)(35,3){}
                \node(4)(50,13){}
                \node(5)(65,23){}
                \node(6)(65,3){}
                \node[Nmarks=r](7)(80,13){}

                \drawedge(1,2){\tt 0}
                \drawedge(1,3){\tt 1}
                \drawedge(2,4){\tt 0}
                \drawedge(3,4){\tt 1}
                \drawedge(4,5){\tt 0}
                \drawedge(4,6){\tt 1}
                \drawedge(5,7){\tt 0}
                \drawedge(6,7){\tt 1}
        \end{picture}
       } \\
    
        \item  $a_1a_2=b_2b_1$.

               \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,53)
                \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=3}

                \node[Nmarks=i](1)(20,28){}
                \node(2)(35,43){}
                \node(3)(35,13){}
                \node(4)(50,53){}
                \node(5)(50,33){}
                \node(6)(50,23){}
                \node(7)(50,3){}
                \node(8)(65,43){}
                \node(9)(65,13){}
                \node[Nmarks=r](10)(80,28){}

                \drawloop[loopangle=90](4){\tt 0,1}
                \drawloop[loopangle=90](5){\tt 0,1}
                \drawloop[loopangle=270](6){\tt 0,1}
                \drawloop[loopangle=270](7){\tt 0,1}
                \drawedge(1,2){\tt 0}
                \drawedge(1,3){\tt 1}
                \drawedge(2,4){\tt 0}
                \drawedge(2,5){\tt 1}
                \drawedge(3,6){\tt 0}
                \drawedge(3,7){\tt 1}
                \drawedge(4,8){\tt 0}
                \drawedge(5,8){\tt 1}
                \drawedge(6,9){\tt 0}
                \drawedge(7,9){\tt 1}
                \drawedge(8,10){\tt 0}
                \drawedge(9,10){\tt 1}
        \end{picture}
       } \\

        \item  $a_1a_2=b_1b_2$.

               \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,63)
                \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=3}

                \node[Nmarks=i](1)(20,28){}
                \node(2)(35,43){}
                \node(3)(35,13){}
                \node(4)(50,53){}
                \node(5)(50,33){}
                \node(6)(50,23){}
                \node(7)(50,3){}
                \node(8)(65,43){}
                \node(9)(65,13){}
                \node[Nmarks=r](10)(80,28){}

                \drawloop[loopangle=90](4){\tt 0,1}
                \drawloop[loopangle=90](5){\tt 0,1}
                \drawloop[loopangle=270](6){\tt 0,1}
                \drawloop[loopangle=270](7){\tt 0,1}
                \drawedge(1,2){\tt 0}
                \drawedge(1,3){\tt 1}
                \drawedge(2,4){\tt 0}
                \drawedge(2,5){\tt 1}
                \drawedge(3,6){\tt 0}
                \drawedge(3,7){\tt 1}
                \drawedge(4,8){\tt 0}
                \drawedge(5,9){\tt 0}
                \drawedge(6,8){\tt 1}
                \drawedge(7,9){\tt 1}
                \drawedge(8,10){\tt 0}
                \drawedge(9,10){\tt 1}
        \end{picture}
       } \\

       \end{list}

 \item \ 
 
       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,33)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=5}

         \node[Nmarks=i](1)(20,20){1}
         \node[Nmarks=i](2)(35,5){2}
         \node[Nmarks=ir, iangle=0](3)(50,20){3}

         \drawloop[loopangle=90](1){{\tt a}}
         \drawedge(1,2){\tt a}
         \drawedge(1,3){\tt a,b}
         \drawloop[loopangle=270](2){{\tt c}}
         \drawedge(2,3){\tt c}
         \drawloop[loopangle=90](3){{\tt b}}
        \end{picture}
       } \\

 \item \ 
 
        \mbox{\setlength{\unitlength}{1mm}
               \begin{picture}(120,33)
                \gasset{Nw=7, Nh=5, Nmr=2.5, loopdiam=5}

                \node[Nmarks=i](12)(20,13){12}
                \node[Nmarks=r](13)(35,23){13}
                \node[Nmarks=r](23)(35,3){23}
                \node(1)(55,23){1}
                \node(2)(55,3){2}

                \drawedge(12,13){\tt a}
                \drawedge(12,23){\tt b}
                \drawloop[loopangle=90](13){\tt a}
                \drawloop[loopangle=270](23){\tt b}
                \drawedge[curvedepth=2](13,1){\tt c}
                \drawedge[curvedepth=0,ELpos=30,ELside=r](13,2){\tt d}
                \drawedge[curvedepth=0,ELpos=30](23,1){\tt c}
                \drawedge[curvedepth=2](23,2){\tt d}
                \drawedge[curvedepth=2](1,13){\tt a}
                \drawedge[curvedepth=2](2,23){\tt b}
        \end{picture}
       } \\
 

 \item Seja $L=\{x\#y \,|\, x,y\in\{{\tt 0},{\tt 1}\}^+ \mbox{ e } \eta(x) \leq \eta(y)\}$.
 
       Suponha que $L$ seja regular. Seja $k$ a constante do lema do bombeamento e $z={\tt 1}^k\#{\tt 1}^k$.
       Sejam $u$, $v$ e $w$ tais que $z=uvw$, $|uv|\leq k$ e $v\not=\lambda$. Sendo $z=uvw$ e $|uv|\leq k$, segue-se
       que $v$ é uma subpalavra do prefixo de $k$ {\tt 1}s e, assim, $uv^2w={\tt 1}^{k+|v|}\#{\tt 1}^k$. Como $|v|>0$,
       $\eta({\tt 1}^{k+|v|})>\eta({\tt 1}^{k})$, visto que $\eta({\tt 1}^{k+|v|})=\eta({\tt 1}^{k})+
       \eta({\tt 1}^{|v|}).2^k$. Logo, $uv^2w\not\in L$, o que contradiz o lema do bombeamento. Portanto, $L$ não é
       regular.
\end{enumerate}

\end{document}
