\documentclass[12pt,a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

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

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

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize (3 pontos) Seja $L=\{\lambda,{\tt 0},{\tt 1}\}$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
				\item Que linguagem é $L^n$ para $n\geq 0$?
				\item Quantas palavras tem $L^n$ para $n\geq 0$?
       \end{list}}


       \emph{Solução}:
			  \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
				\item $L^n=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, 0\leq |w|\leq n\}$
				\item $\sum_{k=0}^n2^k=2^{n+1}-1$
       \end{list}
 \item {\footnotesize (4 pontos) Expresse as linguagens a seguir utilizando operações sobre \emph{conjuntos finitos} de palavras de
       $\{{\tt 0},{\tt 1}\}^*$. Use apenas os operadores de \emph{união}, \emph{concatenação} e \emph{fecho
			 de Kleene}. Considere o alfabeto como sendo $\{{\tt 0},{\tt 1}\}$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item o conjunto das palavras que contêm pelo menos um {\tt 0} \textbf{e} um {\tt 1};
        \item o conjunto das palavras  de $\{{\tt 0}\}^*\{{\tt 1}\}^*$ de tamanho par.
       \end{list}}

       \emph{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{{\tt 0},{\tt 1}\}^*\{{\tt 01},{\tt 10}\}\{{\tt 0},{\tt 1}\}^*$
        \item $\{{\tt 00}\}^*\{\lambda,{\tt 01}\}\{{\tt 11}\}^*$
       \end{list}
 \item {\footnotesize (4 pontos) Seja a gramática $G=(\{P,A,B\},\{{\tt a},{\tt b}\},R,P)$ em que $R$ tem as regras:
       \begin{enumerate}
        \item[\ \ \ ] $P\rightarrow AB$
        \item[\ \ \ ] $A\rightarrow {\tt a} A \,|\, \lambda$
        \item[\ \ \ ] $B\rightarrow {\tt a} B {\tt b} \,|\, \lambda$
       \end{enumerate}
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item Que linguagem é $L(G)$?
			  \item Apresente um esquema de derivação que mostre como gerar qualquer palavra de $L(G)$.
       \end{list}}

       \emph{Solução}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $L(G)=\{{\tt a}^n{\tt b}^k\,|\, n\geq k\}$
			  \item \begin{tabbing}
				       $B$ \=$\,\Rightarrow\,xxxxxxxx$\= \kill
							 $P$ \>$\,\Rightarrow\, AB$     \> ($P\,\rightarrow\, AB$) \\
							     \>$\,\stackrel{n}{\Rightarrow}\, {\tt a}^nAB$ \> ($A\,\rightarrow\, {\tt a}A$ $n$ vezes, $n\geq 0$) \\
							     \>$\,\Rightarrow\, {\tt a}^nB$ \> ($A\,\rightarrow\, \lambda$) \\
							     \>$\,\stackrel{k}{\Rightarrow}\, {\tt a}^{n+k}B{\tt b}^k$ \> ($B\,\rightarrow\, {\tt a}B{\tt b}$ $k$ vezes, $k\geq 0$) \\
							     \>$\,\Rightarrow\, {\tt a}^{n+k}{\tt b}^k$ \> ($B\,\rightarrow\, \lambda$)
							\end{tabbing}
       \end{list}
 \item {\footnotesize (3 pontos) Minimize o AFD com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(100,40)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(10,30){1}
          \node[Nmarks=r](2)(10,10){2}
          \node(3)(30,30){3}
          \node(4)(50,30){4}
          \node(5)(30,10){5}
          \node[Nmarks=r](6)(50,10){6}

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

       \emph{Solução}: \\
			 Evolução das partições do conjunto de estados:
       \begin{enumerate}
        \item[\ ] \begin{tabular}{cl}
                   $S_0$: & $\{2,6\},\{1,3,4,5\}$ \\
                   $S_1$: & $\{2,6\},\{1,5\},\{3,4\}$ \\
                   $S_2$: & $\{2,6\},\{1,5\},\{3,4\}$
                  \end{tabular}
       \end{enumerate}
       AFD mínimo: $(\{15,26,34\},\delta,15,\{26\})$, em que $\delta$ é:
      \begin{center}
       \begin{tabular}{r|cc}
        $\delta$ & {\tt 0} & {\tt 1} \\ \hline
               $15$ & $26$ & $34$ \\
               $26$ & $26$ & $34$ \\
               $34$ & $15$ & $34$ \\
       \end{tabular}
      \end{center}

 \item {\footnotesize (4 pontos: 1,1,2) Encontre AFDs que reconheçam as linguagens:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{{\tt 01},{\tt 1}\}^*$.
        \item O complemento da linguagem anterior.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\mbox{$w$ tem número ímpar de {\tt 0}s e não tem {\tt 0}s
				      consecutivos}\}$.
       \end{list}}

       \emph{Solução}:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \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){3}

          \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}
              \begin{picture}(120,10)\setlength{\unitlength}{1mm}
               \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

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

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

 \item {\footnotesize (3 pontos) Encontre um AFD equivalente ao AFN:
       \begin{center}
       \begin{picture}(65,30)
        \gasset{Nw=6, Nh=6, Nmr=3, %fillcolor=Gray,
				        fillgray=0.9, loopdiam=4}

%        \put(30,0){\makebox(0,0){\textbf{(b) AFN 2.}}}
        \node[Nmarks=i, iangle=180](1)(10,15){1}
        \node(2)(25,25){2}
        \node[Nmarks=i, iangle=225](3)(25,5){3}
        \node[Nmarks=ir, iangle=0](4)(40,15){4}

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

       \emph{Solução}: \ 

              \mbox{\setlength{\unitlength}{1mm}
              \begin{picture}(120,13)(-10,0)
               \gasset{Nw=9, Nh=6, Nmr=7.5, ELdist=0.5, loopdiam=5, fillgray=0.9}

               \node[Nmarks=ir](134)(20,8){134}
               \node[Nmarks=r](124)(40,10){124}
               \node(12)(60,8){12}

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


	\item {\footnotesize (3 pontos) Obtenha um AFN que reconheça $\{{\tt bab}\}^*\{{\tt aa},{\tt b}\}^*$. \emph{Sugestão}: Construa
	      um AFN$\lambda$ e, em seguida, retire a(s) transição(ões) $\lambda$.}

      \emph{Solução}: \ 

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

        \put(0,20){\makebox(0,0)[l]{AFN$\lambda$:}}
        \node[Nmarks=i](1)(30,30){1}
        \node(2)(20,10){2}
        \node(3)(40,10){3}
        \node[Nmarks=r](4)(50,30){4}
        \node(5)(50,10){5}

        \drawedge[curvedepth=0](1,2){\tt b}
        \drawedge[curvedepth=0](1,4){$\lambda$}
        \drawedge[curvedepth=0](2,3){\tt a}
        \drawedge[curvedepth=0](3,1){\tt b}
        \drawloop[loopangle=90](4){\tt b}
        \drawedge[curvedepth=3](4,5){\tt a}
        \drawedge[curvedepth=3](5,4){\tt a}
       \end{picture}
       \begin{picture}(60,40)
        \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

        \put(0,20){\makebox(0,0)[l]{AFN:}}
        \node[Nmarks=i](1)(30,30){1}
        \node(2)(20,10){2}
        \node(3)(40,10){3}
        \node[Nmarks=ir](4)(50,30){4}
        \node(5)(50,10){5}

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

\end{enumerate}

\end{document}
