\documentclass[11pt,a4paper]{article}

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

\newcounter{conta}
\newcounter{conta2}
\pagestyle{empty}

\begin{document}
 
\vspace*{15mm}
\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 2009 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova}/Solu\c{c}\~ao do professor \hfill 21/09/2009

\vspace*{1mm}
\begin{enumerate}
 \item {\footnotesize Seja o alfabeto $\Sigma=\{{\tt 0},{\tt 1}\}$ e as linguagens
       $A=\Sigma^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\Sigma^*$ e $B=\Sigma\{{\tt 0}\}\Sigma^*$. Usando uma
       express\~ao obtida a partir de \textit{conjuntos finitos} e opera\c{c}\~oes dentre \textit{uni\~ao},
       \textit{concatena\c{c}\~ao} e \textit{fecho de Kleene}, expresse:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\overline{A}$.
        \item $\overline{B}$.
        \item $B-A$.
       \end{list}}

       \textit{Solu\c{c}\~ao}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\overline{A}=\{{\tt 1}\}^*\{\lambda,{\tt 0}\}\{{\tt 1}\}^*$.
        \item $\overline{B}=\{\lambda,{\tt 0},{\tt 1}\}\cup\Sigma\{{\tt 1}\}\Sigma^*$.
        \item $B-A=\{{\tt 10}\}\{{\tt 1}\}^*$.
       \end{list}
 \item {\footnotesize Seja a linguagem $L$ assim definida, recursivamente:
       \begin{itemize}
        \item $\lambda,{\tt 0},{\tt 1}\in L$;
        \item se $x\in L$ ent\~ao ${\tt 0}x{\tt 0},{\tt 1}x{\tt 1}\in L$.
       \end{itemize}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Fa\c{c}a uma gram\'atica que gere $L$.
        \item Fa\c{c}a uma gram\'atica que gere $\overline{L}$.
        \item Prove que $L$ \'e ou que n\~ao \'e regular.
       \end{list}}

       \textit{Solu\c{c}\~ao}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $P\,\rightarrow\, {\tt 0}P{\tt 0} \,|\, {\tt 1}P{\tt 1} \,|\, \lambda \,|\, {\tt 0} \,|\, {\tt 1}$
        \item $P\,\rightarrow\, {\tt 0}P{\tt 0} \,|\, {\tt 1}P{\tt 1} \,|\, {\tt 0}X{\tt 1} \,|\, {\tt 1}X{\tt 0}$ \\
              $X\,\rightarrow\, {\tt 0}X \,|\, {\tt 1}X \,|\, \lambda$
        \item Usando o lema do bombeamento (LB):
              \begin{quote}
               Suponha que $L$ \'e regular. Seja $k$ a contante mencionada no LB e $z={\tt 0}^k{\tt 1}{\tt 0}^k$.
               Sejam ainda $u$, $v$ e $w$ tais que $z=uvw$, $|uv|\leq k$ e $v\not=\lambda$.
               De acordo com o LB deve-se ter $uv^iw\in L$ para $i\geq 0$. Mas, j\'a que $v$ s\'o tem
               {\tt 0}s, pois $|uv|\leq k$, e tem no m\'{\i}nimo um {\tt 0}, pois $v\not=\lambda$,
               $uv^2w={\tt 0}^{k+|v|}{\tt 1}{\tt 0}^k\not\in L$. Portanto, $L$ n\~ao \'e regular.
              \end{quote}

              Usando propriedades de fecho:
              \begin{quote}
               Suponha que $L$ \'e regular. Como a classe das linguagens regulares \'e fechada sob interse\c{c}\~ao,
               segue-se que $L\cap\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*$ deve ser regular. Mas,
               $L\cap\{{\tt 0}\}^*\{{\tt 1}\}\{{\tt 0}\}^*=\{{\tt 0}^n{\tt 1}{\tt 0}^n\,|\, n\geq 0\}$, que n\~ao \'e
               regular. Portanto, $L$ n\~ao \'e regular. 
              \end{quote}

       \end{list}
 \item {\footnotesize Encontre um AFD que reconhe\c{c}a $\{{00},{1}\}^*\{{0},{11}\}^*$.}

       \textit{Solu\c{c}\~ao}:
 
        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,10)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=ir](A)(20,5){}
          \node[Nmarks=r](B)(40,5){}
          \node(C)(60,5){}
          \node[Nmarks=r](D)(80,5){D}

          \drawedge[curvedepth=3](A,B){{\tt 0}}
          \drawloop[loopangle=90](A){{\tt 1}}
          \drawedge[curvedepth=3](B,A){{\tt 0}}
          \drawedge[curvedepth=0](B,C){{\tt 1}}
          \drawedge[curvedepth=3](C,D){{\tt 1}}
          \drawedge[curvedepth=3](D,C){{\tt 1}}
          \drawloop[loopangle=90](D){{\tt 0}}
         \end{picture}
        }

 \item {\footnotesize Partindo do AFN$\lambda$ a seguir, obtenha um AFD equivalente. Dever\'a ficar claro o
       m\'etodo utilizado para elimina\c{c}\~ao das transi\c{c}\~oes $\lambda$.

        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,25)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=i](A)(20,20){A}
          \node(B)(40,20){B}
          \node(C)(20,5){C}
          \node[Nmarks=r](D)(40,5){D}

          \drawedge[curvedepth=0](A,B){$\lambda$}
          \drawedge[curvedepth=3](A,C){{\tt 0}}
          \drawedge[curvedepth=3](B,D){{\tt 1}}
          \drawedge[curvedepth=3](C,A){{\tt 1}}
          \drawedge[curvedepth=0](C,D){$\lambda$}
          \drawedge[curvedepth=3](D,B){{\tt 0}}
         \end{picture}
        }}

       \textit{Solu\c{c}\~ao}:

        Um AFN equivalente \'e tal que $I'=f\lambda(\{\mbox{A}\})=\{\mbox{A},\mbox{B}\}$ e sua fun\c{c}\~ao
        de transi\c{c}\~ao \'e calculada assim:
        \begin{quote}
         $\delta'(\mbox{A},{\tt 0})=f\lambda(\delta(\mbox{A},{\tt 0}))=f\lambda(\{\mbox{C}\})
              =\{\mbox{C},\mbox{D}\}$; \\
         $\delta'(\mbox{C},{\tt 1})=f\lambda(\delta(\mbox{C},{\tt 1}))=f\lambda(\{\mbox{A}\})
              =\{\mbox{A},\mbox{B}\}$; \\
         $\delta'(X,a)=\delta(X,a)$ para o resto.
        \end{quote}
        Tem-se, ent\~ao, o AFN:

        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,25)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=i](A)(20,20){A}
          \node[Nmarks=r](D)(40,20){D}
          \node(C)(20,5){C}
          \node[Nmarks=i, iangle=0](B)(40,5){B}

          \drawedge[curvedepth=0](A,D){${\tt 0}$}
          \drawedge[curvedepth=3](A,C){{\tt 0}}
          \drawedge[curvedepth=3](B,D){{\tt 1}}
          \drawedge[curvedepth=3](C,A){{\tt 1}}
          \drawedge[curvedepth=0](C,B){{\tt 1}}
          \drawedge[curvedepth=3](D,B){{\tt 0}}
         \end{picture}
        }

        Aplicando-se o m\'etodo da contru\c{c}\~ao-de-subconjuntos obt\'em-se o AFD:

        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,25)
          \gasset{Nw=10, Nh=6, Nmr=5, loopdiam=6}

          \node[Nmarks=i](A)(20,20){$\{$A,B$\}$}
          \node[Nmarks=r](D)(40,20){$\{$D$\}$}
          \node(C)(20,5){$\{$C,D$\}$}
          \node(B)(40,5){$\{$B$\}$}

          \drawedge[curvedepth=0](A,D){${\tt 1}$}
          \drawedge[curvedepth=3](A,C){{\tt 0}}
          \drawedge[curvedepth=3](B,D){{\tt 1}}
          \drawedge[curvedepth=3](C,A){{\tt 1}}
          \drawedge[curvedepth=0](C,B){{\tt 0}}
          \drawedge[curvedepth=3](D,B){{\tt 0}}
         \end{picture}
        }

 \item {\footnotesize Sejam $L_1=\{{0}^n \,|\, n \mbox{ \'e um n\'umero primo}\}$ e $L_2=\{{\tt 0}\}^k\{{\tt 0}\}^*$, onde
       $k$ \'e uma constante. Para cada linguagem a seguir, mostre que ela \'e regular ou que n\~ao \'e:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$.
        \item $L_1\cap L_2$.
        \item $L_1\cup L_2$.
       \end{list}}

       \textit{Solu\c{c}\~ao}:

       Sabe-se que $L_1$ n\~ao \'e regular (provado usando-se o lema do bombeamento); e $L_2$ \'e regular
       (um AFD que a aceite \'e trivial).
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L_3=L_1-L_2$ \'e regular. \\
              $L_3=\{{0}^n \,|\, n<k \mbox{ e }n \mbox{ \'e um n\'umero primo}\}$. Como este conjunto
              \'e \textit{finito}, \'e regular.
        \item $L_4=L_1\cap L_2=$ n\~ao \'e regular. \\
              Se $L_4=\{{0}^n \,|\, n\geq k \mbox{ e }n \mbox{ \'e um n\'umero primo}\}$ fosse regular,
              $L_4\cup L_3$ tamb\'em seria, pois as linguagens regulares s\~ao fechadas sob uni\~ao. Mas,
              $L_4\cup L_3=L_1$, que n\~ao \'e regular.
        \item $L_1\cup L_2$ \'e regular. \\
              Como $L_1\cup L_2=L_3\cup L_2$, $L_3$ e $L_2$ s\~ao regulares, segue-se por fechamento sob
              uni\~ao que $L_1\cup L_2$ \'e regular.
       \end{list}
\end{enumerate}

\end{document}
