\documentclass[11pt,a4paper]{report}

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

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

\newcounter{conta}
\newcounter{conta2}
\begin{document}
 
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2015 \\
Professor: Newton José Vieira \\
 {\bf Primeira Prova}/Solução do professor \hfill 15/9/2015

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Expresse as linguagens a seguir utilizando operações sobre \emph{conjuntos finitos} de palavras. Só podem ser
       usadas as operações: concatenação, união e fecho de Kleene.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,w\mbox{ contém no máximo dois }{\tt b}\mbox{s}\}$.
			  \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,\mbox{ a subpalavra }{\tt ab}\mbox{ ocorre um número par de vezes em }w\}$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{{\tt a}\}^*\{\lambda,{\tt b}\}\{{\tt a}\}^*\{\lambda,{\tt b}\}\{{\tt a}\}^*$.
			  \item $(\{{\tt b}\}^*\{{\tt a}\}^*\{{\tt ab}\}\{{\tt b}\}^*\{{\tt a}\}^*\{{\tt ab}\})^*\{{\tt b}\}^*\{{\tt a}\}^*$.
       \end{list}

 \item {\footnotesize Construa gramáticas para as linguagens da questão 1.}


       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $P \,\rightarrow\, ABABA$ \\
				      $A \,\rightarrow\, {\tt a}A \,|\, \lambda$ \\
				      $B \,\rightarrow\, \lambda \,|\, {\tt b}$
			  \item $P \,\rightarrow\, BA{\tt ab}BA{\tt ab}P \,|\, BA$ \\
				      $A \,\rightarrow\, {\tt a}A \,|\, \lambda$ \\
				      $B \,\rightarrow\, {\tt b}B \,|\, \lambda$

       \end{list}

 \item {\footnotesize Explique porque os problemas a seguir são decidíveis:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item Dado um AFN, determinar se ele reconhece uma linguagem finita.
			  \item Dados 3 AFDs $M_1$, $M_2$ e $M_3$, determinar se $L(M_1)-L(M_2)=L(M_3)$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item Dado um AFN $M$, determina-se um AFD $M'$ equivalente; em seguida, minimizando-se $M'$,
				      obtém-se um AFD $M''$. $L(M)$ é finita sse o diagrama de estados de $M''$, excluído um eventual
							estado de erro, não contém ciclo (todo caminho simples iniciado no estado inicial é aberto).
			  \item De $M_1$ e $M_2$ obtém-se o produto $M_p$; este, com estados finais sendo os pares $(e_1,e_2)$ tais
				      que $e_1$ é estado final de $M_1$ e $e_2$ é estado não final de $M_2$, reconhece $L(M_1)-L(M_2)$.
							Seja $M_p'$ um AFD mínimo equivalente a $Mp$ e $M_3'$ um AFD mínimo equivalente a $M_3$. Então
							$L(M_1)-L(M_2)=L(M_3)$ sse os diagramas de estado de $M_p'$ e de $M_3'$ são isomorfos (ou seja,
							são idênticos a menos dos nomes dos estados).
       \end{list}

 \item {\footnotesize Construa AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,\mbox{ a subpalavra }{\tt ab}\mbox{ ocorre um número par de vezes em }w\}$.
				\item $\{{\tt 000},{\tt 1}\}^*\{{\tt 0},{\tt 11}\}^*$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item \
				
				\mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,32)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=ir](1)(20,25){}
          \node[Nmarks=r](2)(35,25){}
          \node(3)(35,10){}
          \node(4)(20,10){}

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

			  \item \
				
				\mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,15)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=ir](1)(20,5){}
          \node[Nmarks=r](2)(35,5){}
          \node[Nmarks=r](3)(50,5){}
          \node(4)(65,5){}
          \node[Nmarks=r](5)(80,5){}

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

 \item {\footnotesize Para cada linguagem a seguir, mostre que ela é regular ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item $\{x{\tt a}x\,|\,x\in\{{\tt b},{\tt c}\}^*\}$.
			  \item $\{x\,|\,ax\in L\}$, caso $L$ seja uma linguagem regular. Aqui $a$ é um símbolo do
				      alfabeto de $L$.
       \end{list}}

       \textit{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
			  \item Sejam $L$ a linguagem em questão e $R=\{{\tt b}\}^*$. Sejam ${\tt b}^i$ e ${\tt b}^j$,
				      $i\not=j$, duas palavras arbitrárias de $R$. Tem-se que ${\tt b}^i{\tt a}{\tt b}^i\in L$
							e ${\tt b}^j{\tt a}{\tt b}^i\not\in L$. Pelo teorema da invariância à direita, $L$ não
							é regular.				      
			  \item Se $(E,\Sigma,\delta,i,F)$ é um AFD que reconhece $L$, então
				      $(E,\Sigma,\delta,\delta(i,a),F)$ é um AFD que reconhece $\{x\,|\,ax\in L\}$. Logo esta
							linguagem é regular.
       \end{list}

 \item {\footnotesize Obtenha um AFN equivalente a:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,15)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

          \drawloop[loopangle=90](1){\tt a}
          \drawedge[curvedepth=3](1,2){\tt b}
          \drawloop[loopangle=90](2){\tt b}
          \drawedge[curvedepth=3](2,3){\tt c}
          \drawloop[loopangle=90](3){\tt c}
          \drawedge[curvedepth=3](3,2){$\lambda$}
          \drawedge[curvedepth=3](2,1){$\lambda$}
         \end{picture}
        }
      \end{center}
     usando o método de obtenção de AFN a partir de AFN$\lambda$ visto em aula (ou no livro-texto).}
		 Explicite o cálculo de $\delta'(e,s)$ para cada par $(e,s)\in\{1,2,3\}\times\{{\tt a},{\tt b},
		 {\tt c}\}$ tal que $|\delta'(e,s)|>1$.

       \textit{Solução}:

        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,25)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

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

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

        $\delta'(1,{\tt b})=f\lambda(\delta(1,{\tt b}))=f\lambda(\{2\})=\{1,2\}$, \\
        $\delta'(2,{\tt b})=f\lambda(\delta(2,{\tt b}))=f\lambda(\{2\})=\{1,2\}$, \\
        $\delta'(2,{\tt c})=f\lambda(\delta(2,{\tt c}))=f\lambda(\{3\})=\{1,2,3\}$, \\
        $\delta'(3,{\tt c})=f\lambda(\delta(3,{\tt c}))=f\lambda(\{3\})=\{1,2,3\}$. \\
\end{enumerate}

\end{document}

