\documentclass[11pt,a4paper]{article}

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

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

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

\begin{document}
 
\vspace*{13mm}
\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 2010 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova}/Solução do professor \hfill 09/09/2010

\begin{enumerate}
 \item {\footnotesize Sejam as linguagens $L_1=\{{\tt 1}\}^*\{\lambda,{\tt 0}\}\{{\tt 1}\}^*$ e $L_2=\{{\tt 01},{\tt 1}\}^*$.
       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{L_1}$.
        \item $L_1\cap L_2$.
        \item $L_2-L_1$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 1}\}^*\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*$.
        \item $\{{\tt 1}\}^*\{\lambda,{\tt 01}\}\{{\tt 1}\}^*$.
        \item $\{{\tt 1}\}^*\{{\tt 01}\}\{{\tt 1}\}^*\{{\tt 01}\}\{{\tt 01},{\tt 1}\}^*$.
       \end{list}
 \item {\footnotesize Seja a gramática $G=(\{A,B\},\{{\tt 0},{\tt 1}\},R,A)$ em que $R$ tem apenas as regras:
       \begin{enumerate}
        \item[\ ] $A\,\rightarrow\, {\tt 0}A{\tt 1} \,|\, B$
        \item[\ ] $B\,\rightarrow\, {\tt 1}B{\tt 0} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item O que é $L(G)$?
        \item Fa\c{c}a uma gram\'atica que gere $\overline{L(G)}$.
        \item Prove que $L(G)$ n\~ao \'e regular.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $L(G)=\{{\tt 0}^n{\tt 1}^k{\tt 0}^k{\tt 1}^n \,|\, n,k\geq 0\}$.
        \item Gramática que gera $\overline{L(G)}$:
              \begin{enumerate}
               \item[\ ] $A \,\rightarrow\, {\tt 0}A{\tt 1} \,|\, {\tt 1}B{\tt 0} \,|\, D$
               \item[\ ] $B \,\rightarrow\, {\tt 1}B{\tt 0} \,|\, C$
               \item[\ ] $C \,\rightarrow\, {\tt 0}X{\tt 1} \,|\, D$
               \item[\ ] $D \,\rightarrow\, {\tt 0}X{\tt 0} \,|\, {\tt 1}X{\tt 1} \,|\, {\tt 0} \,|\, {\tt 1}$
               \item[\ ] $X \,\rightarrow\, {\tt 0}X \,|\, {\tt 1}X \,|\, \lambda$
              \end{enumerate}
        \item $L(G)\cap\{{\tt 0}\}^*\{{\tt 1}\}^*=\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$. Como
              $\{{\tt 0}\}^*\{{\tt 1}\}^*$ \'e regular e as linguagens regulares são fechadas sob interseção,
              $L(G)$ não pode ser regular, já que $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}$ não é.
       \end{list}

 \item {\footnotesize Encontre AFDs que reconhe\c{c}am as linguagens:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 01},{\tt 1}\}^*$.
        \item O complemento da linguagem anterior.
        \item $\{{\tt 01},{\tt 1}\}^*\cap\{{\tt 00},{\tt 01},{\tt 10},{\tt 11}\}^*$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item \ 
        
        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,10)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=6}

          \node[Nmarks=ir](1)(20,5){1}
          \node(2)(40,5){2}

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

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

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

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

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

          \node[Nmarks=ir](1p)(20,20){1p}
          \node(2i)(40,20){2i}
          \node(1i)(20,5){1i}
          \node(2p)(40,5){2p}

          \drawedge[curvedepth=3](1p,2i){{\tt 0}}
          \drawedge[curvedepth=3](1p,1i){{\tt 1}}
          \drawedge[curvedepth=3](2i,1p){{\tt 1}}
          \drawedge[curvedepth=3](1i,1p){{\tt 1}}
          \drawedge[curvedepth=3](1i,2p){{\tt 0}}
          \drawedge[curvedepth=3](2p,1i){{\tt 1}}
         \end{picture}
        }
       \end{list}


 \item {\footnotesize Seja o seguinte AFN$\lambda$:

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

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

          \drawloop(1){${\tt a}$}
          \drawedge[curvedepth=0](1,3){$\lambda$}
          \drawloop(2){${\tt c}$}
          \drawedge[curvedepth=0](2,3){{\tt c}}
          \drawedge[curvedepth=0](2,4){$\lambda$}
          \drawloop(3){${\tt b}$}
          \drawloop(4){${\tt a}$}
         \end{picture}
        }
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Obtenha um AFN equivalente pela eliminação das transições $\lambda$. Dever\'a ficar claro
              o \underline{m\'etodo} utilizado para elimina\c{c}\~ao das transi\c{c}\~oes $\lambda$.
        \item Obtenha um AFD equivalente ao AFN. Dever\'a ficar claro o \underline{m\'etodo} utilizado. 
       \end{list}}

       \textit{Solução}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item \ 
        
        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,30)
          \gasset{Nw=5, Nh=5, Nmr=2.5, loopdiam=4}

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

          \drawloop(1){${\tt a}$}
          \drawedge[curvedepth=0](1,3){${\tt a}$}
          \drawloop(2){${\tt c}$}
          \drawedge[curvedepth=0](2,3){{\tt c}}
          \drawedge[curvedepth=0](2,4){${\tt c}$}
          \drawloop(3){${\tt b}$}
          \drawloop(4){${\tt a}$}
         \end{picture}
        }

        \item \ 
        
        \mbox{\setlength{\unitlength}{1mm} \footnotesize
         \begin{picture}(90,40)
          \gasset{Nw=10, Nh=5, Nmr=7.5, loopdiam=4}

          \node[Nmarks=ir](1234)(20,35){1234}
          \node[Nmarks=r](134)(40,35){134}
          \node[Nmarks=r](234)(20,20){234}
          \node[Nmarks=r](3)(40,20){3}
          \node[Nmarks=r](4)(20,5){4}

          \drawedge[curvedepth=0](1234,134){${\tt a}$}
          \drawedge[curvedepth=0](1234,3){{\tt b}}
          \drawedge[curvedepth=0](1234,234){${\tt c}$}
          \drawloop[loopangle=0](134){${\tt a}$}
          \drawedge[curvedepth=0](134,3){${\tt b}$}
          \drawloop[loopangle=0](3){${\tt b}$}
          \drawloop[loopangle=180](234){${\tt c}$}
          \drawedge[curvedepth=0](234,4){${\tt a}$}
          \drawedge[curvedepth=0](234,3){${\tt b}$}
          \drawloop[loopangle=180](4){${\tt a}$}
         \end{picture}
        }
       \end{list}

 \item {\footnotesize Mostre que:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item se $L$ não é uma linguagem regular, então $\overline{L}$ também não é.
        \item Se $L_1$ e $L_2$ são linguagens regulares, então $\{w\in L_1\cup L_2 \,|\, w\not\in L_1 \mbox{ ou }
              w\not\in L_2\}$ também é.
        \item Para todo AFN existe AFN equivalente com um único estado final.
       \end{list}}

       \textit{Solução}:

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Suponha que $\overline{L}$ seja regular. Então, como a classe das linguagens regulares é fechada sob
              complementação, $\overline{\overline{L}}=L$ é regular. Portanto, se $L$ não é regular,
              $\overline{L}$ também não é regular.
        \item A linguagem em questão é $L=(L_1\cup L_2)\cap(\overline{L_1}\cup\overline{L_2})$. Como a classe das
              linguagens regulares é fechada sob complementação, união e interseção, conclui-se que se $L_1$ e $L_2$
              são regulares, então $L$ é regular.
        \item Seja um AFN $(E,\Sigma,\delta,I,F)$. Um AFN equivalente com um único estado final é
              $(E\cup\{f\},\Sigma,\delta',I',\{f\})$, em que:
              \begin{itemize}
               \item $f\not\in E$;
               \item Para todo $e\in E$ e $a\in\Sigma$:
                    $\delta'(e,a)=\left\{\begin{array}{ll} \delta(e,a)\cup\{f\}, & \mbox{se }
                                                                \delta(e,a)\cap F\not=\emptyset \\
                                                  \delta(e,a), & \mbox{caso contrário;} \end{array} \right.$
               \item $I'=\left\{\begin{array}{ll} I\cup\{f\}, & \mbox{se } I\cap F\not=\emptyset \\
                                                  I, & \mbox{caso contrário.} \end{array} \right.$
              \end{itemize}
       \end{list}
\end{enumerate}

\end{document}
