\documentclass[11pt,a4paper]{article}

\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 2008 \\
\noindent Professor: Newton Jos\'{e} Vieira \\
\noindent {\bf Primeira Prova}/Solu\c{c}\~ao do professor \hfill 17/09/2008

\vspace*{1mm}
\begin{enumerate}
 \item {\footnotesize Seja o alfabeto $\Sigma=\{{\tt 0},{\tt 1}\}$ e as linguagens $A=\Sigma\{{\tt 1}\}\Sigma^*$
       e $B=\Sigma^*\{{\tt 1}\}$. Para cada linguagem a seguir, enuncie em portugu\^es uma
       condi\c{c}\~ao necess\'aria e suficiente para que uma palavra perten\c{c}a \`a mesma,
       deixando impl\'{\i}cito que a palavra cont\'em apenas {\tt 0}s e {\tt 1}s, e iniciando
       com o n\'umero m\'{\i}nimo de s\'{\i}mbolos que ela tem. Por exemplo, uma condi\c{c}\~ao necess\'aria
       e suficiente para que uma palavra perten\c{c}a a $B\cap (\Sigma\Sigma)^*$ \'e: \emph{tem no
       m\'{\i}nimo dois s\'{\i}mbolos, tamanho par e termina em {\tt 1}}.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item $AB$.
        \item $A\cap B$.
        \item $A-B$.
        \item $B-A$.
       \end{list}}

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

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Tem no m\'{\i}nimo tr\^es s\'{\i}mbolos, o segundo \'e {\tt 1} e o \'ultimo \'e {\tt 1}.
        \item Tem no m\'{\i}nimo dois s\'{\i}mbolos, o segundo \'e {\tt 1} e o \'ultimo \'e {\tt 1}.
        \item Tem no m\'{\i}nimo tr\^es s\'{\i}mbolos, o segundo \'e {\tt 1} e o \'ultimo \'e {\tt 0}.
        \item Tem no m\'{\i}nimo um s\'{\i}mbolo, o segundo, se existe, \'e {\tt 0} e o \'ultimo \'e {\tt 1}.
       \end{list}

 \item {\footnotesize Seja a linguagem $L=\{{\tt a}^n{\tt b}^i{\tt c}^j\,|\,i+j=n\}$.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Prove que $L$ n\~ao \'e regular.
        \item Fa\c{c}a uma gram\'atica $G$ que gere $L$.
        \item Mostre, por meio de um esquema de deriva\c{c}\~ao, que toda palavra da forma
              ${\tt a}^n{\tt b}^i{\tt c}^j$, para $i+j=n$, \'e gerada por $G$.
       \end{list}}

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

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Suponha que $L$ seja regular. Ent\~ao, como $\{{\tt a}\}^*\{{\tt b}^*\}$ \'e regular e as
              linguagens regulares s\~ao fechadas sob interse\c{c}\~ao, $L\cap\{{\tt a}\}^*\{{\tt b}^*\}$
              deve ser regular. Mas $L\cap\{{\tt a}\}^*\{{\tt b}^*\}=\{{\tt a}^n{\tt b}^n\,|\, n\geq 0\}$, que
              n\~ao \'e regular. Contradi\c{c}\~ao! Portanto, $L$ n\~ao \'e regular.
        \item $P\,\rightarrow\,{\tt a}P{\tt c} \,|\, B$ \\
              $B\,\rightarrow\,{\tt a}B{\tt b} \,|\, \lambda$
        \item \begin{tabbing}
               $P$ \=$\Rightarrow\,{\tt a}^{j+i}B{\tt b}^i{\tt c}^j$xx\= \kill
               $P$ \>$\stackrel{j}{\Rightarrow}\,{\tt a}^jP{\tt c}^j$ 
                                                \> ($P\rightarrow {\tt a}P{\tt c}$, $j$ vezes, $j\geq 0$) \\
                   \>$\Rightarrow\,{\tt a}^jB{\tt c}^j$ 
                                                \> ($P\rightarrow B$) \\
                   \>$\stackrel{i}{\Rightarrow}\,{\tt a}^{j+i}B{\tt b}^i{\tt c}^j$ 
                                                \> ($B\rightarrow {\tt a}B{\tt b}$, $i$ vezes, $i\geq 0$) \\
                   \>$\Rightarrow\,{\tt a}^{j+i}{\tt b}^i{\tt c}^j$ 
                                                \> ($B\rightarrow \lambda$)
              \end{tabbing}
       \end{list}

 \item {\footnotesize Seja $L_1=\{{\tt 01},{\tt 10}\}^*$ e $L_2=\{{\tt 01}\}\{{\tt 0},{\tt 1}\}^*\{{\tt 10}\}$.
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Construa o diagrama de estados de um AFD $M_1$ que reconhe\c{c}a $L_1$.
        \item Construa o diagrama de estados de um AFD $M_2$ que reconhe\c{c}a $L_2$.
        \item Como um AFD que reconhe\c{c}a $L_1-L_2$ pode ser constru\'{\i}do a partir de $M_1$ e
              $M_2$? Fa\c{c}a refer\^encia a algum m\'etodo visto no curso e descreva em detalhes
              apenas o conjunto de estados, o estado inicial e os estados finais de tal AFD
              (n\~ao \'e preciso especificar as transi\c{c}\~oes).
       \end{list}}

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

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

          \node[Nmarks=ir](1)(20,14){1}
          \node(2)(36,25){2}
          \node(3)(36,3){3}
          \node(4)(52,14){4}

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

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

          \node[Nmarks=i](1)(20,20){1}
          \node(2)(36,20){2}
          \node(3)(52,20){3}
          \node(4)(68,20){4}
          \node[Nmarks=r](5)(84,20){5}
          \node(6)(28,5){6}

          \drawedge[curvedepth=0](1,2){{\tt 0}}
          \drawedge[curvedepth=0,ELside=r](1,6){{\tt 1}}
          \drawedge[curvedepth=0](2,3){{\tt 1}}
          \drawedge[curvedepth=0](2,6){{\tt 0}}
          \drawloop[loopangle=270](3){{\tt 0}}
          \drawedge[curvedepth=0](3,4){{\tt 1}}
          \drawloop[loopangle=270](4){{\tt 1}}
          \drawedge[curvedepth=2](4,5){{\tt 0}}
          \drawedge[curvedepth=2](5,4){{\tt 1}}
          \drawedge[curvedepth=-8,ELside=r](5,3){{\tt 0}}
          \drawloop[loopangle=0](6){{\tt 0},{\tt 1}}
         \end{picture}
        }

        \item Faz-se o produto de $M_1$ e $M_2$ e toma-se como
              \begin{itemize}
               \item estados: $\{1,2,3,4\}\times\{1,2,3,4,5,6\}$;
               \item estado inicial: $[1,1]$; e
               \item estados finais: $\{1\}\times\{1,2,3,4,6\}$.
              \end{itemize}
       \end{list}

 \item {\footnotesize Construa um AFN (sem transi\c{c}\~oes $\lambda$) que reconhe\c{c}a $X\{{\tt 01}\}^*$, sendo
       \[X=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\eta(w) \mbox{ mod } 3 = 1\}\] onde $\eta(w)$
       \'e o n\'umero representado por $w$ na base 2.}

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

         \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(90,30)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](0)(20,20){0}
          \node(1)(36,20){1}
          \node(2)(52,20){2}
          \node[Nmarks=r](3)(52,4){3}
          \node(4)(68,4){4}

          \drawloop[loopangle=90](0){{\tt 0}}
          \drawedge[curvedepth=2](0,1){{\tt 1}}
          \drawedge[curvedepth=2](1,0){{\tt 1}}
          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawloop[loopangle=90](2){{\tt 1}}
          \drawedge[curvedepth=2](2,1){{\tt 0}}
          \drawedge[curvedepth=-6, ELside=r](0,3){{\tt 1}}
          \drawedge[curvedepth=0](2,3){{\tt 0}}
          \drawedge[curvedepth=2, Nmarks=r](3,4){{\tt 0}}
          \drawedge[curvedepth=2](4,3){{\tt 1}}
         \end{picture}
        }

 
 \item {\footnotesize Responda sim ou n\~ao, justificando sua resposta:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Para toda linguagem regular existe um AFN (sem transi\c{c}\~oes $\lambda$) com um
              \'unico estado final. 
        \item Para qualquer linguagem $L$, regular ou n\~ao, existem linguagens regulares $R_I$
              e $R_S$ tais que $R_I\subseteq L\subseteq R_S$.
        \item Se $L$ for n\~ao regular, $F\subseteq L$ e $F$ finita, $L-F$ pode ser regular ou n\~ao.
        \item O problema de determinar se uma linguagem regular, cujo alfabeto \'e $\Sigma$,
              cont\'em alguma palavra com a ocorr\^encia de todos os s\'{\i}mbolos de $\Sigma$
              \'e decid\'{\i}vel.
       \end{list}}

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

       \begin{list}{\alph{conta})}{\usecounter{conta}}
        \item Sim. Seja $M=(E,\Sigma,\delta,I,F)$ um AFN com $|F|>1$. Um AFN equivalente com um estado
              final seria $(E\cup\{f\},\Sigma,\delta',I',\{f\})$, em que (a) $I'=I$ se $I\cap F=\emptyset$,
              e $I'=I\cup\{f\}$ se $I\cap F\not=\emptyset$, e (b) $\delta'(e,a)=\delta(e,a)$ se
              $\delta(e,a)\cap F=\emptyset$, e  $\delta'(e,a)=\delta(e,a)\cup\{f\}$ se
              $\delta(e,a)\cap F\not=\emptyset$.
        \item Sim. $\emptyset\subseteq L\subseteq \Sigma^*$.
        \item N\~ao. Suponnha $L$ n\~ao regular, $F\subseteq L$ e $F$ finita. Se $L-F$ fosse
              regular, como $F$ \'e finita, $(L-F)\cup F$ seria regular. Mas $(L-F)\cup F=L$, pois
              $F\subseteq L$. Contradi\c{c}\~ao. Portanto, $L-F$ n\~ao pode ser regular se
              $L$ for n\~ao regular, $F\subseteq L$ e $F$ finita.
        \item Sim. Dado um AFD que reconhe\c{c}a a linguagem, basta testar as palavras que ocasionem a
              passagem por algum ciclo do mesmo no m\'aximo uma vez e que tenham ocorr\^encias de todos
              os s\'{\i}mbolos de $\Sigma$. Evidentemente, o conjunto de tais palavras \'e finito.
       \end{list}

\end{enumerate}

\end{document}
