-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathRelFinal.tex
1888 lines (1395 loc) · 139 KB
/
RelFinal.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
%% abtex2-modelo-trabalho-academico.tex, v-1.9.5 laurocesar
%% Copyright 2012-2015 by abnTeX2 group at http://www.abntex.net.br/
%%
%% This work may be distributed and/or modified under the
%% conditions of the LaTeX Project Public License, either version 1.3
%% of this license or (at your option) any later version.
%% The latest version of this license is in
%% http://www.latex-project.org/lppl.txt
%% and version 1.3 or later is part of all distributions of LaTeX
%% version 2005/12/01 or later.
%%
%% This work has the LPPL maintenance status `maintained'.
%%
%% The Current Maintainer of this work is the abnTeX2 team, led
%% by Lauro César Araujo. Further information are available on
%% http://www.abntex.net.br/
%%
%% This work consists of the files abntex2-modelo-trabalho-academico.tex,
%% abntex2-modelo-include-comandos and abntex2-modelo-references.bib
%%
% ------------------------------------------------------------------------
% ------------------------------------------------------------------------
% abnTeX2: Modelo de Trabalho Academico (tese de doutorado, dissertacao de
% mestrado e trabalhos monograficos em geral) em conformidade com
% ABNT NBR 14724:2011: Informacao e documentacao - Trabalhos academicos -
% Apresentacao
% ------------------------------------------------------------------------
% ------------------------------------------------------------------------
\documentclass[
% -- opções da classe memoir --
12pt, % tamanho da fonte
%openright, % capítulos começam em pág ímpar (insere página vazia caso preciso)
openany,
%twoside, % para impressão em verso e anverso. Oposto a oneside
oneside,
%titlepage,
a4paper, % tamanho do papel.
% -- opções da classe abntex2 --
%chapter=TITLE, % títulos de capítulos convertidos em letras maiúsculas
%section=TITLE, % títulos de seções convertidos em letras maiúsculas
%subsection=TITLE, % títulos de subseções convertidos em letras maiúsculas
%subsubsection=TITLE,% títulos de subsubseções convertidos em letras maiúsculas
% -- opções do pacote babel --
english, % idioma adicional para hifenização
brazil % o último idioma é o principal do documento
]{abntex2}
% ---
% Pacotes básicos
% ---
\usepackage{lmodern} % Usa a fonte Latin Modern
\usepackage[T1]{fontenc} % Selecao de codigos de fonte.
\usepackage[utf8]{inputenc} % Codificacao do documento (conversão automática dos acentos)
\usepackage{lastpage} % Usado pela Ficha catalográfica
\usepackage{indentfirst} % Indenta o primeiro parágrafo de cada seção.
\usepackage{color} % Controle das cores
\usepackage{graphicx} % Inclusão de gráficos
\usepackage{microtype} % para melhorias de justificação
% ---
% MEUS PACKAGES
\usepackage[brazil]{babel}
\usepackage[utf8]{inputenc}
%\usepackage[T1]{fontenc}
%\pagestyle{plain}
\usepackage{amsfonts,amssymb,amsmath,textcomp,amsthm}
%\setlength{\parindent}{1cm}
%\usepackage{indentfirst}
%\usepackage{ae}
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{float}
%\usepackage{bm}
\usepackage[table]{xcolor}
\usepackage{multirow}
\usepackage{pdfpages}
\usepackage{url}
\usepackage{hyperref}
%\usepackage[dvipdfmx]{graphicx} %\usepackage{bmpsize}
%\use{enumerate}
\graphicspath{{figuras/}}
\usepackage{algorithmic}
\usepackage[portuguese, linesnumbered, ruled, lined, vlined, boxed]{algorithm2e}
\usepackage{wrapfig}
%\restylefloat{figure}
\usepackage{caption}
\usepackage{subcaption}
%\usepackage{ragged2e}
%\usepackage[utf8x]{inputenc}
\usepackage{textcomp}
\usepackage{etoolbox}
\makeatletter
\patchcmd{\chapter}{\if@openright\cleardoublepage\else\clearpage\fi}{}{}{}
\makeatother
%\newenvironment{packed_enum}{
%\begin{enumerate}
% \setlength{\itemsep}{1pt}
% \setlength{\parskip}{0pt}
% \setlength{\parsep}{0pt}
%}{\end{enumerate}}
%
%
%\newenvironment{packed_itemize}{
%\begin{itemize}
% \setlength{\itemsep}{1pt}
% \setlength{\parskip}{0pt}
% \setlength{\parsep}{0pt}
%}{\end{itemize}}
%\usepackage{enumerate}
%\usepackage{paralist}
\usepackage[demo]{rotating}
% ---
% Pacotes adicionais, usados apenas no âmbito do Modelo Canônico do abnteX2
% ---
%%%\usepackage{lipsum} % para geração de dummy text
% ---
% ---
% Pacotes de citações
% ---
\usepackage[brazilian,hyperpageref]{backref} % Paginas com as citações na bibl
\usepackage[alf]{abntex2cite} % Citações padrão ABNT
% ---
% CONFIGURAÇÕES DE PACOTES
% ---
% ---
% Configurações do pacote backref
% Usado sem a opção hyperpageref de backref
\renewcommand{\backrefpagesname}{Citado na(s) página(s):~}
% Texto padrão antes do número das páginas
\renewcommand{\backref}{}
% Define os textos da citação
\renewcommand*{\backrefalt}[4]{
\ifcase #1 %
Nenhuma citação no texto.%
\or
Citado na página #2.%
\else
Citado #1 vezes nas páginas #2.%
\fi}%
% ---
% ---
% Informações de dados para CAPA e FOLHA DE ROSTO
% ---
\titulo{Um sistema para auxiliar na \\ aprendizagem da disciplina \\ Linguagens Formais e Autômatos}
\autor{Rafael Cardoso da Silva}
\local{Santo André - SP, Brasil}
\data{2016}
\orientador{Prof. Daniel M. Martin}
%\coorientador{Equipe \abnTeX}
\instituicao{%
Universidade Federal do ABC
\par
Bacharelado em Ciências da Computação}
\tipotrabalho{Iniciação Cientifica}
% O preambulo deve conter o tipo do trabalho, o objetivo,
% o nome da instituição e a área de concentração
\preambulo{Relatório final apresentado ao Programa de Iniciação Científica da Universidade Federal do ABC.}
%{Modelo canônico de trabalho monográfico acadêmico em conformidade com as normas ABNT apresentado à comunidade de usuários \LaTeX.}
% ---
% ---
% Configurações de aparência do PDF final
% alterando o aspecto da cor azul
\definecolor{blue}{RGB}{41,5,195}
% informações do PDF
\makeatletter
\hypersetup{
%pagebackref=true,
pdftitle={Um sistema para auxiliar na aprendizagem da disciplina Linguagens Formais e Autômatos},
pdfauthor={Rafael Cardoso da Silva},
%pdfsubject={\imprimirpreambulo},
pdfcreator={LaTeX with abnTeX2},
pdfkeywords={autômato finito}{equivalência de autômatos}{minimização de autômato}{programação para web},
colorlinks=false, % false: boxed links; true: colored links
linkcolor=blue, % color of internal links
citecolor=blue, % color of links to bibliography
filecolor=magenta, % color of file links
urlcolor=blue,
bookmarksdepth=4
}
\makeatother
% ---
% ---
% Espaçamentos entre linhas e parágrafos
% ---
% O tamanho do parágrafo é dado por:
\setlength{\parindent}{1.3cm}
% Controle do espaçamento entre um parágrafo e outro:
\setlength{\parskip}{0.2cm} % tente também \onelineskip
% ---
% compila o indice
% ---
\makeindex
% ---
% ----
% Início do documento
% ----
\begin{document}
% Seleciona o idioma do documento (conforme pacotes do babel)
%\selectlanguage{english}
\selectlanguage{brazil}
% Retira espaço extra obsoleto entre as frases.
\frenchspacing
% ----------------------------------------------------------
% ELEMENTOS PRÉ-TEXTUAIS
% ----------------------------------------------------------
% \pretextual
%% CAPA DO IC
\includepdf[pages={1}]{caparelatorio.pdf}
% ---
% Capa
% ---
\imprimircapa
% ---
% ---
% Folha de rosto
% (o * indica que haverá a ficha bibliográfica)
% ---
\imprimirfolhaderosto
% ---
% ---
% Inserir a ficha bibliografica
% ---
% Isto é um exemplo de Ficha Catalográfica, ou ``Dados internacionais de
% catalogação-na-publicação''. Você pode utilizar este modelo como referência.
% Porém, provavelmente a biblioteca da sua universidade lhe fornecerá um PDF
% com a ficha catalográfica definitiva após a defesa do trabalho. Quando estiver
% com o documento, salve-o como PDF no diretório do seu projeto e substitua todo
% o conteúdo de implementação deste arquivo pelo comando abaixo:
%
% \begin{fichacatalografica}
% \includepdf{fig_ficha_catalografica.pdf}
% \end{fichacatalografica}
%\begin{fichacatalografica}
% \sffamily
% \vspace*{\fill} % Posição vertical
% \begin{center} % Minipage Centralizado
% \fbox{\begin{minipage}[c][8cm]{13.5cm} % Largura
% \small
% \imprimirautor
% %Sobrenome, Nome do autor
%
% \hspace{0.5cm} \imprimirtitulo / \imprimirautor. --
% \imprimirlocal, \imprimirdata-
%
% \hspace{0.5cm} \pageref{LastPage} p. : il. (algumas color.) ; 30 cm.\\
%
% \hspace{0.5cm} \imprimirorientadorRotulo~\imprimirorientador\\
%
% \hspace{0.5cm}
% \parbox[t]{\textwidth}{\imprimirtipotrabalho~--~\imprimirinstituicao,
% \imprimirdata.}\\
%
% \hspace{0.5cm}
% 1. Palavra-chave1.
% 2. Palavra-chave2.
% 2. Palavra-chave3.
% I. Orientador.
% II. Universidade xxx.
% III. Faculdade de xxx.
% IV. Título
% \end{minipage}}
% \end{center}
%\end{fichacatalografica}
% ---
% ---
% RESUMOS
% ---
% resumo em português
\setlength{\absparsep}{18pt} % ajusta o espaçamento dos parágrafos do resumo
\begin{resumo}
Resolver exercícios é fundamental para um aluno fixar os conceitos apresentados em aula. Por outro lado, ter seus exercícios corrigidos também é muito importante, para que ele possa avaliar o seu aprendizado. Na UFABC, a disciplina de Linguagens Formais e Autômatos contempla vários exercícios que admitem infinitas respostas, o que torna a correção deles praticamente impossível, principalmente quando as turmas são grandes. O objetivo deste projeto foi a criação e implementação de um sistema para aplicação e correção automática de exercícios envolvendo autômatos finitos determinísticos. Através do estudo de métodos e algoritmos presentes na literatura, foi possível implementar o teste de equivalência entre o autômato-resposta do aluno e o autômato-gabarito previamente armazenado no banco de dados. Ao final do projeto, o sistema foi usado em caráter experimental numa turma da UFABC da disciplina de Linguagens Formais e Autômatos, afim de testar a sua qualidade. E ao final da disciplina, a nota que os alunos obtiverem ao revolver os exercícios do sistema ajudarão a compor o conceito final de cada um na disciplina.
\textbf{Palavras-chave}: autômato finito, equivalência de autômatos, minimização de autômato, programação para web
\end{resumo}
% resumo em inglês
%\begin{resumo}[Abstract]
% \begin{otherlanguage*}{english}
% This is the english abstract.
%
% \vspace{\onelineskip}
%
% \noindent
% \textbf{Keywords}: latex. abntex. text editoration.
% \end{otherlanguage*}
%\end{resumo}
% ---
% ---
% inserir lista de ilustrações
% ---
%%%%%\pdfbookmark[0]{\listfigurename}{lof}
%%%%%\listoffigures*
%%%%%\cleardoublepage
% ---
% ---
% inserir lista de tabelas
% ---
%%%%%\pdfbookmark[0]{\listtablename}{lot}
%%%%%\listoftables*
%%%%%\cleardoublepage
% ---
% ---
% inserir lista de abreviaturas e siglas
% ---
%\begin{siglas}
% \item[ABNT] Associação Brasileira de Normas Técnicas
% \item[abnTeX] ABsurdas Normas para TeX
%\end{siglas}
% ---
% ---
% inserir lista de símbolos
% ---
%\begin{simbolos}
% \item[$ \Gamma $] Letra grega Gama
% \item[$ \Lambda $] Lambda
% \item[$ \zeta $] Letra grega minúscula zeta
% \item[$ \in $] Pertence
%\end{simbolos}
% ---
% ---
% inserir o sumario
% ---
%\let\clearpage\relax
\pdfbookmark{\contentsname}{toc} %[0]
\tableofcontents*
\cleardoublepage
%\let\clearpage\relax
% ---
% ----------------------------------------------------------
% ELEMENTOS TEXTUAIS
% ----------------------------------------------------------
\textual
% ----------------------------------------------------------
% Introdução (exemplo de capítulo sem numeração, mas presente no Sumário)
% ----------------------------------------------------------
%\let\clearpage\relax
\chapter[Introdução]{Introdução}
%\addcontentsline{toc}{chapter}{Introdução}
%\section{Introdução}
%\addcontentsline{toc}{section}{Introdução}
% ----------------------------------------------------------
Resolução de exercícios é uma atividade fundamental para que um aluno possa praticar o que foi apresentado em aula. A correção dos exercícios também é importante para que o aluno possa avaliar seu aprendizado. Para turmas grandes, torna-se inviável corrigir rapidamente todos os exercícios propostos e devolvê-los em tempo hábil aos alunos. Na disciplina MC3106 – Linguagens Formais e Autômatos – vários exercícios da parte inicial da disciplina pedem como resposta um autômato finito determinístico. Tais exercícios são particularmente trabalhosos de se corrigir porque cada um deles admite infinitas respostas corretas e, por esse motivo, sua correção se torna exaustiva para o monitor ou docente responsável.
Com o intuito de agilizar essa tarefa, este projeto propõe o desenvolvimento de um sistema web que permita ao aluno inserir seu autômato-resposta por meio de uma interface intuitiva e fácil de ser utilizada e obter um \emph{feedback} quase que imediatamente, um tempo drasticamente reduzido se comparado à correção manual. Acreditamos que um sistema como esse será de grande valia para o aprendizado dos alunos. Por outro lado, para o docente responsável, facilitará o processo de composição do conceito final na disciplina de Linguagens Formais e Autômatos.
Além do estudo de autômatos e linguagens regulares, a disciplina de Linguagens Formais e Autômatos trata de linguagens não-regulares, em especial das que podem ser descritas por gramáticas livres de contexto (GLC). Nesta segunda parte da disciplina, é também comum a ocorrência de exercícios que pedem, como resposta, uma gramática livre de contexto para descrever uma linguagem livre de contexto. Automatizar a correção deste tipo de exercício é impossível pois o problema geral de se determinar se duas gramáticas livres de contexto descrevem a mesma linguagem é um problema indecidível~\cite{sipser}. Por outro lado, diversos tópicos em linguagens livres de contexto podem ser examinados de maneira automática, incluindo a equivalência de certas subclasses de gramáticas livres de contexto~\cite{nijholt}, a transformação de uma gramática livre de contexto qualquer para a Forma Normal de Chomsky (FNC), a busca da árvore de derivação para um texto segundo uma GLC na FNC, problemas de \emph{parsing} em geral.
%Se houver tempo, acreditamos que seria interessante agregar ao sistema alguns scripts de correção automática para classes de exercícios envolvendo gramáticas livres de contexto.
\clearpage
\chapter[O Principal Problema]{O Principal Problema}
Um \emph{autômato finito determinístico} (também chamado de AFD ou máquina de estados) consiste de um conjunto de estados não vazio $Q$, um alfabeto $\Sigma$, um estado inicial $s \in Q$, um conjunto de estados de aceitação $F \subseteq Q$ e uma função de transição $\delta \colon Q \times \Sigma \rightarrow Q$. É comum estender a função de transição para uma função $\hat{\delta} \colon Q \times \Sigma^* \rightarrow Q$ definida indutivamente por
\begin{alineas}%[(i)]
\item[(i)] $\hat{\delta}(q, \varepsilon) = q$ para todo estado $q \in Q$;
\item[(ii)] $\hat{\delta}(q, \sigma) = \delta(q, \sigma)$ para todo estado $q \in Q$ e símbolo $\sigma \in \Sigma$;
\item[(iii)] $\hat{\delta}(q, \sigma_1 \cdots \sigma_k) = \delta(\hat{\delta}(q, \sigma_1 \cdots \sigma_{k-1}), \sigma_k)$ para todo estado $q \in Q$ e símbolos $\sigma_1, \dots, \sigma_k \in \Sigma$.
\end{alineas}
Todo autômato pode ser representado por um diagrama de estados. Considere o diagrama da Figura~\ref{fig:aut01} abaixo.
\begin{figure}[H]
\vspace{-0.5cm}
\centering
\includegraphics[scale=0.75]{aut01.png}
\vspace{-0.5cm}
\caption{Um autômato $M_1$.}
\label{fig:aut01}
\vspace{-0.5cm}
\end{figure}
No autômato da Figura~\ref{fig:aut01}, temos $Q = \{S_1, S_2\}$, $\Sigma = \{a, b\}$, $s = S_1$, $F = \{S_1\}$ e a função de transição é dada pela tabela a seguir.
\begin{table}[H]
\centering
\begin{tabular}[H]{c|c c}
$\delta$ & \textbf{\texttt{a}} & \textbf{\texttt{b}} \\
\hline
$S_1$ & $S_2$ & $S_1$ \\
$S_2$ & $S_1$ & $S_2$
\end{tabular}
\caption{Tabela de transições do $M_1$.}
\label{tab:tabTransicoesM1}
\vspace{-0.5cm}
\end{table}
Nesse exemplo, se o AFD $M_1$ é alimentado com a palavra \textbf{\texttt{aabab}}, ele irá começar no estado $S_1$ e irá percorrer os estados $S_2$, $S_1$, $S_1$, $S_2$, $S_2$ nesta ordem, e irá rejeitar a palavra dada (pois o último estado $S_2 \not\in F$). Se, para uma outra palavra $w$, a simulação tivesse terminado em $S_1$ (que pertence a $F$) diríamos que o autômato aceita a palavra $w$. Mais formalmente, se $M_1 = (Q, \Sigma, \delta, s, F)$ é um autômato finito determinístico, dizemos que $M_1$ \emph{aceita} $w$ se $\hat{\delta}(s, w) \in F$ e que $M_1$ \emph{rejeita} $w$ caso contrário.
A \emph{linguagem reconhecida} por um autômato $M_1 = (Q, \Sigma, \delta, s, F)$ é o conjunto de palavras que são aceitas por esse autômato, ou seja, é definida pelo conjunto \[ L(M_1) = \{w \in \Sigma^* \colon \hat{\delta}(s, w) \in F \}. \] No exemplo da Figura~\ref{fig:aut01} acima, a linguagem reconhecida por por $M_1$ é $L(M_1) = \{w \in \Sigma^* : w \text{ tem número par de símbolos } \mathtt{a}\}$.
% É comum estender a função de transição para uma função $\hat{\delta} \colon Q
% \times \Sigma^* \rightarrow Q$ definida indutivamente por
% \begin{enumerate}[(i)]
% \item $\hat{\delta}(q, \sigma) = \delta(q, \sigma)$ para todo estado $q \in Q$ e símbolo $\sigma \in \Sigma$;
% \item $\hat{\delta}(q, \sigma_1 \cdots \sigma_k) = \delta(\hat{\delta}(q, \sigma_1 \cdots \sigma_{k-1}), \sigma_k)$ para todo estado $q \in Q$ e símbolos $\sigma_1, \dots, \sigma_k \in \Sigma$.
% \end{enumerate}
\bigskip
Vários tipos de exercícios pedem por uma resposta que é um autômato. Por exemplo:
\begin{alineas}%[(i)]
\item[(i)] construir um autômato que reconheça a linguagem regular
dada por um certo conjunto de palavras descrito matematicamente;
\item[(ii)] transformar um autômato finito não determinístico num
determinístico equivalente;
\item[(iii)] criar um autômato que reconheça a mesma linguagem
descrita por uma expressão regular dada;
\item[(iv)] construir o menor autômato finito determinístico
que reconheça uma certa linguagem regular.
\end{alineas}
Cada um destes tipos de exercícios possui centenas de casos particulares que os alunos podem fazer para praticar os conceitos de autômatos abordados na disciplina. Tais exercícios podem, por exemplo, ser encontrados abundantemente no livro \textit{Introdução à Teoria da Computação} de M. Sipser~\cite{sipser}. Outras referências importantes da disciplina que possuem exercícios semelhantes são~\cite{ullman} e~\cite{linz}. Em todos os casos acima, contudo, há uma infinidade de respostas corretas para cada exercício. Por exemplo, considere o diagrama abaixo.
\begin{figure}[H]
\vspace{-0.5cm}
\centering
\includegraphics[scale=.65]{aut02.png}
\vspace{-0.5cm}
\caption{Um autômato $M_2$.}
\label{fig:aut02}
\vspace{-0.5cm}
\end{figure}
Apesar de visivelmente maior e mais complexo que $M_1$, este autômato reconhece a mesma linguagem que o autômato $M_1$ da Figura~\ref{fig:aut01}. É possível demonstrar que, para cada linguagem regular, existem infinitos autômatos que a reconhecem. Como decidir então se o autômato-resposta dado por um aluno reconhece a linguagem pedida? No caso do sistema que iremos desenvolver isso se reduz ao seguinte problema:
\bigskip
\noindent \textbf{Problema:} Decidir se dois autômatos finitos determinísticos reconhecem a mesma linguagem.
%\newpage
\clearpage
\chapter[Métodos para resolver o problema da equivalência]{Métodos para resolver o problema da equivalência}
Determinar se dois autômatos finitos e determinísticos reconhecem linguagens diferentes é um problema bem resolvido. A ideia fundamental é tentar encontrar uma palavra $w$ que é aceita por um autômato e rejeitada pelo outro. Se tal palavra puder ser encontrada, então as linguagens reconhecidas por esses autômatos são distintas. Caso tal palavra não exista, os autômatos reconhecem a mesma linguagem.
Mais formalmente, dizemos que dois estados $q_1$ e $q_2$ (no mesmo autômato ou não) são \emph{equivalentes} se, para toda palavra $w \in \Sigma^*$ vale que $\hat{\delta}(q_1, w) \in F$ se e somente se $\hat{\delta}(q_2, w) \in F$, caso contrário $q_1$ e $q_2$ sao chamados distinguíveis. Dois autômatos serão, portanto, equivalentes se e somente se seus respectivos estados iniciais forem equivalentes no sentido que acabamos de definir.
Esse problema está intimamente relacionado com o problema de minimização de autômatos finitos determinísticos. Os primeiros algoritmos desenvolvidos para testar a equivalência de autômatos resolviam também o problema da minimização. Eles apareceram em~\cite{huffman} e~\cite{moore} e podem ser implementados sem muito esforço em tempo $O(n^4)$, onde $n$ é o número total de estados. O algoritmo mais eficiente conhecido para minimização de autômatos~\cite{hopcroft} executa em tempo $O(n \log{}n)$. Posteriormente Hopcroft e Karp~\cite{hopcroft_karp} desenvolveram um algoritmo linear para testar a equivalência de autômatos.
\section{Minimização de Moore}
%[ULLMAN pag. 154 – 4.4 Equivalence and Minimization of Automata (pdf 168)]
Nessa seção vamos investigar um algoritmo de minimização de autômato finito determinístico, mais especificamente o algoritmo de Minimização de Moore~\cite{moore} e discultido no~\cite{ullman}.
Para facilitar a compreensão utilizaremos como exemplo o autômato $M_2$ da Figura~\ref{fig:aut02}. Queremos determinar se $M_2$ é equivalente ao autômato $M_1$ da Figura~\ref{fig:aut01}.
O autômato $M_2$ é representado pela quíntupla $M_2 = (Q, \Sigma, \delta, s, F)$, onde temos $Q = \{S_1, S_2, S_3, S_4\}$, $\Sigma = \{a, b\}$, $s = S_1$, $F = \{S_1, S_4\}$ e a função de transição é dada pela tabela a seguir.
%__|__a__b_
%S1| S2 S1
%S2| S4 S2
%S3| S1 S3
%S4| S3 S1
\begin{table}[H]
\centering
\begin{tabular}[H]{c|c c}
$\delta$ & \textbf{\texttt{a}} & \textbf{\texttt{b}}\\
\hline
$S_1$ & $S_2$ & $S_1$ \\
$S_2$ & $S_4$ & $S_2$ \\
$S_3$ & $S_1$ & $S_3$ \\
$S_4$ & $S_3$ & $S_1$ \\
\end{tabular}
\caption{Tabela de transição do $M_2$.}
\vspace{-0.5cm}
\end{table}
Note que a definição de estados equivalentes na seção anterior não se traduz imediatamente em um algoritmo, pois não é possível testar se $\hat{\delta}(p, w) \in F$ para todas as palavras $w \in \Sigma^*$
No entanto, podemos desenvolver um algoritmo para determinar a equivalência entre estados $p$ e $q$ baseando-se no seguinte lema:
\newtheorem{lemma}{Lema}
\begin{lemma}
\label{lemma01}
Se $r = \delta(q,\sigma)$ e $s = \delta(p,\sigma)$ e se $r$ e $s$ são distinguíveis, então $p$ e $q$ são distinguíveis.
\end{lemma}
%\noindent\textbf{\textit{Base.}} Se $p$ é um estado de aceitação e $q$ é um estado de não aceitação, então o par $\{p,q\}$ é distinguível.
\begin{proof}[\textbf{Prova}]
%Temos os estados $p$ e $q$ que ao entrar com o simbolo $\sigma$, teremos $r = \delta(q,\sigma)$ e $s = \delta(p,\sigma)$ na qual sabemos que $r$ e $s$ são distinguíveis. Então o par $p$ e $q$ também é distinguível, pois para este lema faça sentido
Por hipótese deve haver uma palavra $w$ que distingue $r$ de $s$, ou seja, exatamente um dos estados $\hat{\delta}(r, w)$ e $\hat{\delta}(s, w)$ é de aceitação. Então a palavra $\sigma w$ distingui $p$ de $q$, já que $\{\hat{\delta}(p, \sigma w), \hat{\delta}(q, \sigma w)\}$ é o mesmo par de estados que $\{\hat{\delta}(r, w), \hat{\delta}(s, w)\}$.
\end{proof}
% \textcolor{blue}{\textbf{[LIVRO ULLMAN pag 155]}}\\
%\textcolor{blue}{\textbf{FALAR DO PROCESSO}} ( O lema 1 é só um principio que norteia o processo )
A partir do Lema acima podemos elaborar um processo para investigar quais são os pares de estados que são distinguíveis. Para qualquer par de estados, eles são distinguíveis se constatar que um simbolo do alfabeto aplicado na função $\delta$, em cada estado deste par, resulta em um par de estados que já estão distinguidos. E também ter como premissa que se num par de estados, um destes estados é de aceitação e o outro não, então estes estados são distinguidos com a palavra vazia, denotada por $\varepsilon$.
Entendido o processo de como verificar se um par de estados são distinguíveis, podemos ver o pseudo código, que realiza as verificações para todos os possíveis pares, logo a baixo.\\
\vspace{-0.5cm}
\begin{algorithm}[H]
\label{alg01}
\caption{Acha Pares Distinguíveis pela Minimização de Moore}
\Entrada{$Q, \Sigma, \delta, F$}
\Saida{Tabela de distinguibilidade }
\Inicio{
\ParaCada{ $p \in Q$ }{
\ParaCada{ $q \in Q$ }{
$D\{p,q\} \gets \emptyset$
}
}
\ParaCada{ $p \in F$ }{
\ParaCada{ $q \in Q \backslash F$ }{
$D\{p,q\} \gets$ x
}
}
distinguiu{\_}algo $\gets$ verdadeiro\\
\Enqto{distinguiu{\_}algo}{
distinguiu{\_}algo $\gets$ falso\\
\ParaCada{ $p \in Q$ }{
\ParaCada{ $q \in Q$ }{
\Se{$D\{p,q\} = \emptyset$}{
\ParaCada{ $\sigma \in \Sigma$ }{
\Se{$D\{\delta(p,\sigma), \delta(q, \sigma)\} \neq \emptyset$}{
$D\{p,q\} \gets$ x \\ %\sigma $\\
distinguiu{\_}algo $\leftarrow$ verdadeiro\\
}
}
}
}
}
}
\Retorna{D}
}
\end{algorithm}
Ao analisarmos este pseudo código de algoritmo de minimização vemos que este recebe como entrada o conjunto de estados $Q$, o alfabeto $\Sigma$, a tabela de transição $\delta$ e o conjunto de estados finais $F$ de um autômato.
E contamos com o apoio de uma matriz quadrada simétrica $D$ de dimensão $|Q|\times|Q|$, cujas células abaixo da diagonal principal serão utilizadas para representar todos os pares de estados possíveis. Inicialmente, $D$ será inicializada com valores vazios. Ao longo da execução do algoritmo, se um par for distinguido, então atribuiremos o simbolo “x” à célula correspondente a este par. Logo em seguida, preenchemos as células dos pares trivialmente distinguíveis, ou seja, pares que consistem de um estado final e um não final.
Então iniciam-se as rodadas de verificação, onde percorre-se $D$ e para cada par $\{p, q\}$ com valor vazio, o algoritmo testa para cada carácter $\sigma$ do conjunto $\Sigma$, se o par $\{p, q\}$ se torna distinguível pelo caractere $\sigma$, considerando $\hat{\delta}(p, w)$ e $\hat{\delta}(q, w)$ em vista do Lema~\ref{lemma01}.
Além disto, com o apoio da variável booleana $distinguiu{\_}algo$, utilizada para marcar se houve uma alteração em $D$, verificamos que as rodadas somente cessarão se, na mesma rodada, nenhum ``x'' é adicionado na tabela de distinguibilidade, concluindo assim que não existem mais pares à ser distinguídos. Retornando, ao fim, a tabela de distinguibilidade.
Concluímos que não pode haver mais de $O(n^2)$ verificações em uma rodada, assim certamente o limite superior para o número de verificações é $O(n^4)$, visto que o pior caso é atingido quando somente um único par de estados é distinguido por rodada, causando $O(n^2)$ rodadas com $O(n^2)$ verificações em cada, onde $n$ é o tamanho do conjunto~$Q$.
Então, para solucionamos o nosso problema de verificar se dois autômatos são equivalentes, podemos considerar um terceiro autômato que é a união disjunta dos dois autômatos dados e executamos o algoritmo acima sobre a união. E, ao final, apenas verificamos se a posição na tabela que representa o par de estados iniciais encontra-se vazia.
%se os estados iniciais dos dois autômatos se encontram equivalente na tabela de distinguibilidade retornada pelo método.
Para o nosso exemplo, ao unirmos o $M_1$ com o $M_2$, obtemos a seguinte tabela de transição. Mas com a nomenclatura dos estados de $M_2$ mapeados de $\{S_1, S_2, S_3, S_4\}$ para $\{S_3, S_4, S_5, S_6\}$.
% _|_a_b
% 1| 2 1
% 2| 1 2
% 3| 4 3
% 4| 6 4
% 5| 3 5
% 6| 5 3
\begin{table}[H]
\centering
\begin{tabular}[H]{c|c c}
$\delta$ & \textbf{\texttt{a}} & \textbf{\texttt{b}} \\
\hline
$S_1$ & $S_2$ & $S_1$ \\
$S_2$ & $S_1$ & $S_2$ \\
$S_3$ & $S_4$ & $S_3$ \\
$S_4$ & $S_6$ & $S_4$ \\
$S_5$ & $S_3$ & $S_5$ \\
$S_6$ & $S_5$ & $S_3$ \\
\end{tabular}
\caption{Tabela de Transição dos autômatos $M_1$ e $M_2$ unidos.}
\vspace{-0.5cm}
\end{table}
E ao executar o algoritmos de equivalência, obteremos a seguinte tabela de distinguibilidade.
%2| #
%3| - #
%4| # - #
%5| # - # -
%6|_-__#__-__#__#_
% 1 2 3 4 5
\begin{table}[H]
\centering
\begin{tabular}{c c c c c c}
\cline{2-2}
$S_2$ & \multicolumn{1}{|c|}{x} \\
\cline{2-3}
$S_3$ & \multicolumn{1}{|c|}{ } & \multicolumn{1}{c|}{x} \\
\cline{2-4}
$S_4$ & \multicolumn{1}{|c|}{x} & \multicolumn{1}{c|}{ } & \multicolumn{1}{c|}{x} \\
\cline{2-5}
$S_5$ & \multicolumn{1}{|c|}{x} & \multicolumn{1}{c|}{ } & \multicolumn{1}{c|}{x} & \multicolumn{1}{c|}{ } \\
\cline{2-6}
$S_6$ & \multicolumn{1}{|c|}{ } & \multicolumn{1}{c|}{x} & \multicolumn{1}{c|}{ } & \multicolumn{1}{c|}{x} & \multicolumn{1}{c|}{x} \\
\cline{2-6}
& $S_1$ & $S_2$ & $S_3$ & $S_4$ & $S_5$ \\
\end{tabular}
\caption{Tabela de distinguibilidade dos autômatos $M_1$ e $M_2$ unidos.}
\vspace{-0.5cm}
\end{table}
Basta agora verificar se a posição da matriz $D$ correspondente ao par de estados iniciais está com o seu valor vazio, o que indica que os estados iniciais são equivalentes. Neste caso, os autômatos $M_1$ e $M_2$ são equivalentes.
%\subsection {Detalhes de Implementação do Algoritmo de Minimização}
% Como visto na seção anterior, o que faz o Algoritmo~\ref{alg01} estar sobrecarregado é o fato de que, em todas as rodadas, ele procura pelo próximo par de estados que ainda não foi distinguido, que é feito pelas linhas 11, 12 e 13 do pseudo-código anterior. Assim, uma solução possível para melhorar a eficiência do algoritmo seria manter informações extras na memória de modo que, ao realizar uma verificação da distinguibilidade de um par, ele já deve ter conhecimento de qual é o próximo par à ser checado.
%
% Intuitivamente, se faz necessário o uso de uma estrutura de dados para abrigar os índices das células desta matriz $D$, que representam um par. E esta estrutura de dados terá como regra de inserção e remoção de elementos no formato de que o primeiro a entrar será o primeiro a sair, ou seja, uma fila. Então todos os elementos que estiverem contidos nesta fila, obrigatoriamente ainda não foram distinguidos.
%
% Temos então que fazer algumas alterações no código do Algoritmo~\ref{alg01}. Anteriormente à linha 9, em que se dá o inicio das rodadas de verificação, devemos inserir na fila todos os pares que não foram trivialmente distintos e ao final adicionamos um elemento chave, que tem a função de marcar o final de uma rodada.
%
% A seguir inicia-se as rodadas de verificação, em que será removido um a um os elementos da fila e verificamos primeiramente se este elemento se trata do elemento chave. Se sim, com o auxilio da variável booleana $distinguiu{\_}algo$, verificaremos se foi distinguido algum par de estados durante a rodada. Se não houve um novo par distinguido, então encerra-se as rodadas, caso contrario inserimos o elemento chave de volta a fila.
%
% Mas caso não seja o elemento chave, tentamos verificar se o par que este elemento representa pode ser distinguido para todas os símbolos de $\Sigma$ conforme o Lema~\ref{lemma01}. E se aquele par for distinguível, marcamos a celula de $D$ como distinguido. Se e somente se o par não for distinguido, ele será novamente inserido na fila, para que na próxima rodada o torne a verificar.
%
% Assim ao final das rodadas de verificação, os elementos contido na fila serão os representantes dos pares indistinguíveis.
%
% Com esta estratégia, conseguiremos eliminar as verificações dos pares que já foram distinguidos durante as rodadas que o algoritmo executa. Utilizando mais memória para armazenar esta estrutura de dado que auxilia na verificação, mas proporcionando uma melhora significativa no desempenho do Algoritmo~\ref{alg01}.
\subsection {Recuperação de Palavra}
Este sistema de apoio a aprendizagem tem como objetivo o rápido feedback sobre a resposta submetida pelo usuário. Com a ajuda do Algoritmo~\ref{alg01} conseguimos verificar se o autômato-resposta é equivalente ao autômato-gabarito perfeitamente. Mas, caso o Algoritmo~\ref{alg01} retornar que não são equivalentes, então se faz necessário de uma dica ao usuário para que ele tome conhecimento de seu erro. Esta dica será uma palavra $w \in \Sigma^*$, que distingue o estado inicial do autômato-resposta submetido do estado inicial do autômato-gabarito, e ao ser percorrida pelo usuário, permite encontrar o erro cometido em sua resposta.
Então é necessária a implementação de um algoritmo que descubra qual é essa palavra que distingue os dois autômatos. Para que seja possível encontrar a palavra desejada é necessário modificar o Algoritmo~\ref{alg01}, para que ele não somente descubra quais pares de estados são distinguíveis, mas também guarde os símbolos iniciais das palavras que as distinguem. Isso pode ser feiro alterando-se apenas as linhas 7 e 16 do Algoritmo~\ref{alg01} como indicado a seguir:
\begin{alineas}%[(i)]
\item[7.] $ D\{p,q\} \gets \varepsilon $
\item[16.] $ D\{p,q\} \gets \sigma $
\end{alineas}
%Previamente temos que fazer uma alteração na matriz $D$, em que ao invés de receber o simbolo “x”, atribuiremos agora o simbolo $\sigma \in \Sigma$ que os distinguiu, mais especificamente na linha 7 e 16 do Algoritmo~\ref{alg01}.
Então supondo que $D\{p,q\} \neq \emptyset$, temos o seguinte pseudo código.
\begin{algorithm}[H]
\caption{Acha a palavra que distingui os dois autômatos}
\label{alg02}
\Entrada{$ D, \delta, \{p_0, q_0\}$}
\Saida{ w }
\Inicio{
$ w \gets \varepsilon $\\
$ \{p, q\} \gets \{p_0, q_0\} $ \\
$ \sigma \gets D(\{p, q\}) $\\
\Enqto{$\sigma \neq \varepsilon$} {
$ w \gets w \cdot \sigma $\\
$ \{p, q\} \gets \{\delta(p, \sigma), \delta(q, \sigma)\} $\\
$ \sigma \gets D(\{p, q\}) $
}
\Retorna{ w }
}
\end{algorithm}
O algoritmo recebe como entrada $D$, $\delta$ e $\{p_0, q_0\}$, que é a tabela de distinguibilidade gerado pelo Algoritmo~\ref{alg01} com as modificações sugeridas acima, a tabela de transição dos autômatos unidos e o par de estados iniciais dos autômatos, respectivamente.
O Algoritmo~\ref{alg02} irá coletando os símbolos contidos em células especificas de $D$ e unindo-os ao conjunto $w$. Inciando pelo par $\{p_0, q_0\}$, descobrindo o simbolo que os distinguem e atribuindo a $\sigma$. E enquanto não encontrar o simbolo $\sigma$ com o valor $\varepsilon$, unirá ao conjunto $w$ o simbolo $\sigma$, em seguida descobre o próximo par de estados que o simbolo $\sigma$ levará utilizando a tabela de transição, ou seja, o novo par será $\{\delta(p, \sigma), \delta(q, \sigma)\}$, e por ultimo descobre qual é o simbolo que distinguiu este próximo par de estados.
%Para finalizar, faz uma ultima verificação se o conjunto $palavra$ esta vazio, se caso positivo então incluímos o simbolo $\varepsilon$ em $palavra$.
Então será retornado o a palavra $w$, que é a palavra que distinguiu os dois autômatos que estávamos procurando.
%\newpage
\section {Equivalência em Tempo Linear}
A maioria dos algoritmos para teste de equivalência de autômatos finitos determinísticos na literatura tem crescimento assintótico proporcional ao quadrado do número de estados~\cite{ullman}. Um algoritmo desenvolvido por Hopcroft e Karp~\cite{hoka71}, para este mesmo fim, tem complexidade de $O(n \log{}^* n)$, onde $n$ é o número de estados. Nesta seção estudaremos este algoritmo. %Então estudaremos este algoritmo nesta seção.
Mas antes temos que entender a estrutura de dados utilizada para armazenar conjuntos disjuntos, conhecida popularmente como \textit{Union-Find}, que será fundamental para o método de equivalência de Hopcroft e Karp.
\subsection {A Estrutura Union-Find}
Para o método que veremos na seção seguinte, envolve o agrupamento de elementos em uma coleção de conjuntos disjuntos\footnote{São quando os conjuntos não tem elementos em comum, ou seja, suas interseções é o conjunto vazio.}, e há uma estrutura de dados que atende este requisito~\cite{cormen} e admite duas operações que será vital para a implementação do algoritmo de equivalência em tempo linear. %\footnote{Conjuntos disjuntos são quando a cada dois conjuntos, a sua interseção é o conjunto vazio.}
%A primeira operação é o FIND, que basicamente tem a função de dado um elemento no parâmetro, encontrar a qual conjunto este elemento pertence. A segunda operação é o MERGE, que tem a função de fundir os dois conjuntos em um. Adiante iremos aprofundar melhor em seus detalhes.~\cite{cormen}
Na estrutura de dados de conjuntos disjuntos guarda-se um coleção de elementos disjuntos. Onde cada conjunto é identificado por um representante, que será um de seus elementos, não importando na maioria dos casos qual seja este elemento, somente que será sempre ele que atenderá quando for procurado o representante daquele conjunto.
Para se criar um conjunto utiliza-se a função \texttt{MAKE-SET($x$)}, que aloca um conjunto contendo um elemento $x$ na memória, este elemento será o representante deste conjunto, e claro $x$ não deverá estar presente em nenhum outro conjunto.
A operação \texttt{FIND($x$)} basicamente tem a função de dado um elemento $x$, encontrar a qual conjunto este elemento pertence, retornando o seu elemento representante.
A outra operação é o \texttt{MERGE($x$, $y$)}, que tem a função de fundir os dois conjuntos que os elementos $x$ e $y$ pertencem em somente um na coleção.
Há mais de um modo de implementar esta estrutura, usando listas ligadas ou até lista de árvores, por exemplo.
Com a lista ligada, temos o primeiro elemento de cada lista sendo o representante, e cada objeto desta lista tem um ponteiro para o próximo objeto e um ponteiro direto para o representante. Deste modo facilita a operação \texttt{FIND} por ter um ponteiro direto para o representante. Mas para o \texttt{MERGE}, não basta somente o ultimo objeto do primeiro conjunto apontar para o inicio do segundo conjunto, há a necessidade de atualizar o ponteiro para o novo representante de todos os elementos do segundo conjunto. Causando um aumento na complexidade do algoritmo.
Já se utilizarmos uma estrutura de árvore, em que cada elemento será um objeto que representa um nó na árvore. Então este nó somente basta ter um ponteiro para seu nó pai, e o representante será aquele que apontar para ele mesmo. A operação \texttt{MERGE} se torna mais simples, mas o ponteiro da raiz do segundo apontar para a raiz do primeiro conjunto. Já o \texttt{FIND} terá que percorrer a partir do pais deste elemento, todos os pais de seus ancestrais, até encontrar a raiz, que é o representante deste conjunto. Isso pode se tornar custoso caso a altura da árvore seja muito grande, por isso uma otimização da estrutura se faz necessária, utilizando um método de compactação do caminho até a raiz.
Cada implementação tem a sua particularidade e a escolha depende de seu uso, para o Algoritmo de Hopcroft e Karp, será implementada como modo de árvores, que discutiremos e analisaremos melhor nas seções seguintes.
Para ilustrar melhor esta estrutura, temos o seguinte exemplo:
\begin{alineas}
\item[$\bullet$]
Criamos uma coleção de conjuntos disjuntos $\Psi = \{S_1, S_2, S_3, S_4, S_5\}$, onde para cada conjunto $S_i$ temos o elemento $i$ contido nele e este será o representante do conjunto disjunto. Criando $\{ \{\underline{1}\}, \{\underline{2}\}, \{\underline{3}\}, \{\underline{4}\}, \{\underline{5}\}\}$. Os elementos sublinhados caracteriza o representantes daquele conjunto.
\begin{figure}[!ht]
\centering
\vspace{-0.3cm}
\includegraphics[scale=0.4]{unionFind_exemplo1.png}
\vspace{-0.5cm}
\end{figure}
\item[$\bullet$]
\texttt{MERGE(2, 3)} resulta em $\{ \{\underline{1}\}, \{2, \underline{3}\}, \{\underline{4}\}, \{\underline{5}\}\}$.
\begin{figure}[H]
\centering
\vspace{-0.3cm}
\includegraphics[scale=0.4]{unionFind_exemplo2.png}
\vspace{-0.5cm}
\end{figure}
\item[$\bullet$]
\texttt{MERGE(5, 4)} resultado em $\{ \{\underline{1}\}, \{2, \underline{3}\}, \{\underline{4}, 5\}\}$.
\begin{figure}[H]
\centering
\vspace{-0.3cm}
\includegraphics[scale=0.4]{unionFind_exemplo3.png}
\vspace{-0.5cm}
\end{figure}
\item[$\bullet$]
\texttt{FIND(2)} será retornado o elemento \texttt{3}.
\item[$\bullet$]
\texttt{FIND(3)} será retornado o elemento \texttt{3}.
\end{alineas}
\subsection {Algoritmo de Hopcroft e Karp}
Nesta seção estudaremos o algoritmo de Hopcroft e Karp para o teste de equivalência em tempo linear~\cite{hoka71}. O algoritmo utilizas-se da estrutura de dados pilha e uma estrutura de dados popularizada como Union-Find para armazenar conjuntos disjuntos~\cite{cormen}. Em especial esta última estrutura de dados tem fundamental importância no algoritmo para testar a equivalência dos autômatos, pois armazenará no mesmo conjunto os estados que são equivalentes.
Vejamos a seguir o algoritmo.
\begin{algorithm}[H]
\caption{Teste de Equivalência de Hopcroft e Karp}
\label{alg03}
\Entrada{$ Q, \delta, \{p_0, q_0\}$}
\Saida{ Conjuntos disjuntos }
\Inicio{
conjuntos.INIT($|Q|$) \\
conjuntos.MERGE($p_0, q_0$) \\
pilha.empilha($\{p_0, q_0\}$) \\
\Enqto{pilha $\neq \emptyset$} {
$\{p, q\} \gets$ pilha.desempilha() \\
\ParaCada{$\sigma \in \Sigma$} {
$r \gets$ conjuntos.FIND( $\delta(p, \sigma)$ ) \\
$s \gets$ conjuntos.FIND( $\delta(q, \sigma)$ ) \\
\Se{$r \neq s$} {
conjuntos.MERGE($r, s$) \\
pilha.empilha($\{r, s\}$) \\
}
}
}
\Retorna{conjuntos}
}
\end{algorithm}
A estrutura de dados Union-Find armazena conjuntos disjuntos na memória, e deseja-se executar essencialmente duas operações: MERGE($i, j$), une o conjunto $i$ ao conjunto $j$, e FIND($i$) busca o conjunto ao qual pertence o elemento $i$.
O algoritmo inicia-se criando a estrutura de dados Union-Find, que atribuímos o nome de $conjuntos$, e terá o tamanho igual ao tamanho do conjunto $Q$, que é novamente a união dos dois autômatos que queremos testar sua equivalência. Assim a estrutura conterá $|Q|$ conjuntos e em cada um contendo um único elemento que corresponde a um estado de $Q$, e cada conjunto é denominado pelo nome do elemento que é o representante daquele conjunto. Ou seja, cada estado de $Q$ está em seu próprio conjunto, sendo ele mesmo o representante e nome deste conjunto.
Realizaremos a primeira fusão, entre os conjunto $p_0$ e $q_0$, pois supomos que se os autômatos são equivalentes, então seus estados iniciais também deverão ser equivalentes. EM seguida utilizaremos uma estrutura de dados de Pilha para armazenar o par destes dois estado iniciais.
Assim inicia-se as verificações até que esta pilha esteja vazia. Primeiro desempilhamos um par da pilha e atribuímos a variáveis $\{p,q\}$. Então para cada simbolo $\sigma$ do alfabeto $\Sigma$ será feito algumas etapas. Buscamos qual é o conjunto que contém o estado que foi levado pela função de transição $\delta$ ao entrar com o simbolo $\sigma$ e denominaremos estes de $r$ e $s$. E verificaremos se $r \neq s$, ou seja, se o conjunto $r$ é diferente do conjunto $s$. Se sim, então uniremos estes dois conjuntos e empilhamos o par $\{r, s\}$ na pilha.
Assim o algoritmo somete terminará ao analisar todos os estados para todas as letras do alfabeto, retornando ao final o $conjuntos$.
Então para constatar a equivalência, basta examinar em cada conjunto $q$ da lista de conjuntos disjuntos se $q \subset F$ ou $q \subset Q \backslash F$. Ou seja, os dois autômatos são equivalentes se, e somente se em nenhum conjunto da lista há estados de aceitação e de não aceitação no mesmo conjunto.
Os passos das linhas 2, 3, 4 e a verificação final desta lista, são executadas em uma quantidade limitada por uma constante de tempo $n$, onde $n$ é o número de estados de $Q$.
Já o tempo de execução da interações da linha 5 até a 12, tem o tempo limitado pelo número de vezes que os pares são removidos da pilha. Que por sua vez, o número de pares retirados da pilha é limitado por $n$, pois cada vez que um par é inserido na pilha, dois conjuntos são fundidos, assim o número total de conjuntos é diminuído em um. Desde a inicialização, são definidos $n$ conjuntos e no máximo $n-1$ pares são colocados na pilha.
Então o tempo de execução deste algoritmo para testar a equivalência de dois autômatos finitos é delimitados por uma constante vezes o produto do tamanho do alfabeto pelo o número de estados, ou seja, $O(c \times |\Sigma| \times |Q|)$.
Mas como utilizamos a estrutura de dados Union-Find temos o consumo de tempo limitados superiormente por $O(n \log^* n)$.
%A função FIND tem em si uma otimização da estrutura, que acarreta em um tempo de $O(\log n)$ no pior caso, e esta função dentro do Algoritmo~\ref{alg03} é executada $n$ vezes, assim faz o algoritmo ser limitado superiormente por $O(n \log n)$. Veremos mais detalhes desta estrutura na seção seguinte.
\subsection {Detalhes de Implementação do Algoritmo de Teste de Equivalência} %{Detalhes de Implementação do Algoritmo de Teste de Equivalência de Hopcroft e Karp }
O algoritmo utiliza-se de duas estruturas de dados, uma pilha para armazenar o próximo par a ser analisado e o Union-Find para armazenar conjuntos disjuntos.
A pilha utilizada na implementação é a oferecida pela biblioteca padrão da linguagem. Já o conjunto disjunto pode ser simplificada, pois sua utilização neste algoritmo, a estrutura de dados não necessita ter alocação de memória dinâmica. Logo, para sua implementação basta a alocação de um único vetor sequencial de tamanho igual ao passado por parâmetro no método INIT. Para isto, os atributos padrão destra estrutura de dados serão simplificados, provendo assim uma economia de memória.
Cada índice deste vetor, representará um elemento a ser agrupado em conjuntos, que por sua vez representa um estado da união dos dois autômatos. O valor daquele elemento no vetor representará o seu pai. E quando este valor apontar para si mesmo, significa que este elemento é o elemento raiz, também chamados de representante do conjunto que ele está contido. O atributo \textit{rank} não se fará necessário para esta implementação simplificada. Esta estrutura se assemelhará a uma árvore, em que cada elemento há somente o ponteiro para seu pai.
Assim com esta estrutura, podemos implementar somente os métodos necessários para manipular os conjuntos disjuntos que o algoritmo necessita.
Os passos para a implementação da função MERGE serão as seguintes: recebido dois índices por parâmetro, buscamos os conjuntos que os contêm com auxilio da função FIND e por fim fazemos o primeiro conjunto ser subconjunto do segundo, ou seja, a raiz do primeiro terá seu valor apontando para a raiz do segundo conjunto.
Já o método FIND, recebe um elemento por parâmetro, e retorna o índice do elemento raiz (o representante) do conjunto que contem o elemento passado como parâmetro.
% Já o método FIND, recebe um elemento por parâmetro, e verificar se ele é a raiz, ou seja, se o valor aponta para ele mesmo, se sim este é a raiz e nome do conjunto, e retornando-o. Se não, haverá uma busca em profundidade em seu parente recursivamente, ao encontra a raiz, será devolvida seu valor e atribuído este valor ao valor do elemento. Forçando assim que o elemento e todos seus parentes até atingir a raiz agora apontam diretamente para a raiz. Esta otimização da estrutura garante uma compactação do caminho até a raiz.
Para testar a equivalência de dois autômatos, inicialmente supomos que eles são equivalentes, logo os seus estados iniciais são equivalentes. Por conta disto acontece a primeira chamada do método MERGE para o par $\{p_0, q_0\}$ correspondente ao par de estados inciais dos dois autômatos. E assim inicia-se as verificações até que não haja mais conjuntos a serem unidos.
Há ainda a possibilidade de otimizar este código, pois ao final da execução do algoritmo, temos que verificar todos os conjuntos resultantes da estrutura de dados Union-Find. Se durante a execução do Algoritmo~\ref{alg03} for haver uma união de conjuntos, basta verificarmos cada um dos representantes se um é estado de aceitação e o outro não. Então comprovando que aqueles dois autômatos não são equivalentes, não necessitando terminar todas as interações para verificar todos os conjuntos somente ao final. Então se encontrado uma união heterogênea, o algoritmo deve cessar. E acontecerá esta verificação anteriormente as linhas 3 e 11 do Algoritmo~\ref{alg03} nos conjuntos que pretendem ser unidos.
%Mas se fizermos a verificação antes da chamada do método MERGE, nas linas 3 e 11, se os dois conjuntos pretendentes a união são heterogêneo a respeito de serem todos estados de aceitação ou não, podemos terminar a execução ali mesmo, pois já resultaria que os dois autômatos não são equivalentes.
\subsection {Recuperação de Palavra}
Para poder encontrar uma palavra que demonstre a distinção dos dois autômatos, a partir da otimização proposta na seção anterior, facilmente percebemos que, se o algoritmo for terminado por tentar unir dois conjuntos heterogêneos, então exite uma palavra que os distingue. Basta agora recuperar esta palavra, e para isto temos que recuperar todas as uniões que foram efetuadas até o momento do término.
%Sabemos que se houve uma união de conjuntos, então houve a insertação do próximo par na pilha.
Uma possível solução, que foi implementada, é que a cada união de conjuntos devemos guardar em uma nova pilha as informações a respeito desta união. Então armazenamos a tupla $\{p, q, \sigma, r, s\}$, que basicamente são as variáveis daquela interação, onde $p$ e $q$ é o par que estava sendo verificado pelo simbolo $\sigma$, que causou a união do par $r$ e $s$.
%que anteriormente a verificação, se é possível a união, inserimos um par nesta pilha histórico e anexo a ele, qual foi o par anterior e qual o simbolo que possibilitou a união dos conjuntos. Ou seja, inserimos o conjunto $\{p, q, r, s, \sigma\}$.
Então no Algoritmo~\ref{alg03}, basta acrescentar a instrução de empilhar esta tupla na pilha, que chamaremos de \emph{pHist}, após as linhas: 3 e 11.
No pseudo código a seguir veremos a implementação da recuperação desta palavra.
\begin{algorithm}[H]
\caption{Recuperação da palavra que os distinguem}
\label{alg04}
\Entrada{$ pHist $}
\Saida{ $ w $ }
\Inicio{
$w \gets \varepsilon $ \\
\Enqto{$pHist \neq \emptyset$}{
$\{p, q, \sigma, r, s\} \gets $pHist.desempilha() \\
$w \gets \sigma \cdot w$ \\
\Enqto{$(pHist.topo().r \neq p) ~ | ~ (pHist.topo().s \neq q)$}{ %(pHist \neq \emptyset) ~\&~
pHist.desempilha() \\
}
}
\Retorna{w}
}
\end{algorithm}
Assim teremos uma pilha com o histórico das uniões. Então se o Algoritmo~\ref{alg03} terminou por ter encontrado uma união não desejada, basta agora ir retirando os elementos desta pilha histórico até esvaziar, adicionando à variável $w$ o simbolo que causou a união. E por fim encontrar o par de estados que uniu este par sucessor, dispensando os elementos que não estamos procuramos.
Poderíamos abstrair melhor este algoritmo como se a cada verificação a partir da raiz ($\{p_0, q_0\}$) no Algoritmo~\ref{alg03} fosse uma busca em profundidade, que se interrompida em algum ponto, então o caminho de volta até a raiz a partir deste ponto, recolhendo os símbolos associada a cada união, forma a palavra que distinguiu os dois autômatos.
%a recuperação da palavra seria um
\section{Escolha do Melhor Método}
Após implementar e analisar cada algoritmo que discutimos até aqui, devemos escolher qual deles deve ser incluído no sistema. Ambos cumprem a tarefa de verificar a equivalência entre dois autômatos, e ambos são capazes de recuperar a palavra que diferencia um autômato do outro, no caso de eles não serem equivalentes.
Claramente o algoritmo de teste de equivalência de Hopcroft e Karp se destaca comparado ao método de minimização de Moore, pelo fato dele ter complexidade linear, o que possibilita atingir um maior desempenho, que é uma característica desejável para o sistema.
\chapter[O sistema] {O sistema}
%Não podemos negar que a internet está difundida na sociedade: ela está em todos os lugares, tanto em computadores como em televisores e em celulares.
A plataforma que desenvolvemos possibilita uma experiência de uso semelhante ao de um aplicativo para \textit{desktop}, mas não necessita de instaladores e não depende de um sistema operacional especifico como os programas tradicionais.
Uma aplicação web é um sistema que possibilita a intercomunicação entre um cliente e um servidor via internet. O cliente é um navegador, que exibe uma interface gráfica e proporciona uma interação com o usuário. Já o processamento fica ao encargo de um servidor HTTP\footnote{Abreviação para \textit{Hypertext Transfer Protocol}, em português Protocolo de Transferência de Hipertexto, é um protocolo base para a comunicação de dados da \textit{World Wide Web}.}. Este servidor tem a função de receber requisições e devolver respostas ao cliente. E o cliente exibe as informações ao usuário e solicita recursos a este servidor conforme o usuário interage com o navegador.
Assim este sistema se torna muito prático e acessível para o aluno poder praticar o conceito aprendido em aula. Então, o objetivo deste projeto é que, por meio de um navegador de internet, o aluno responda a questões e obtenha um retorno praticamente imediato do servidor que analisará sua resposta. Por este motivo foi utilizada a plataforma web para desenvolver este sistema.
No próximo capítulo será documentado todo o processo de desenvolvimento deste sistema. Discutiremos os requisitos e analisaremos as melhores estratégias para projetar e implementar este sistema de apoio na aprendizagem da disciplina de Linguagens Formais e Autômatos. Também discutiremos o conceito do juiz, que tem um papel fundamental neste sistema: o de julgar a equivalência entre autômato-resposta do aluno e o autômato-gabarito, utilizando o algoritmo anteriormente escolhido.
Mas, primeiramente, é necessário viabilizar um requisito de extrema importância para este projeto, de como será coletado o autômato-resposta do aluno.
\section{Interface de entrada da resposta}
Inicialmente, os exercícios que o sistema vai atender têm como resposta um autômato finito determinístico. Então, há a necessidade do uso de algum tipo de formulário, ou método, que receba esta resposta. Este autômato-resposta poderia ser descrito matematicamente, como definimos anteriormente, mas não seria dinâmico nem intuitivo para o aluno.
Então, a adoção de um método intuitivo e com interação gráfica se torna um requisito essencial deste sistema, e acarreta no aumento da complexidade deste projeto.
Um Autômato Finito Determinístico, que também pode ser chamado de Máquina de Estado Finito Determinístico, é uma máquina de estados que aceita ou rejeita cadeias de símbolos. E cada cadeia, ao ser processada, faz com que o autômato percorra uma sequência de passos determinadas unicamente pela palavra lida.
Esta máquina de estados pode ser representada por um diagrama de estados, constituída por círculos com borda duplas ou simples que correspondem, respectivamente, aos estados de aceitação ou de não aceitação. Um indicador para o estado inicial. E as regras de transições são retratadas como ligações direcionais entre dois estados quaisquer, ou seja, setas com um simbolo associado ligando dois estados.
Após uma pequena pesquisa na internet, encontramos a \textit{Finite State Machine Designer}, uma ferramenta para construção de máquinas de estados finitos desenvolvida por Evan Wallace~\cite{evan}, como vemos abaixo. Ela tem como objetivo facilitar a confecção de diagramas de máquinas de estados e a possibilidade de exportar o diagrama criado para diversos formatos, proporcionando uma grande praticidade.
\begin{figure}[H]
\centering
\includegraphics[scale=0.8]{fsm_page.png} %0.7
\caption{Construtor de máquinas de estados.}
\label{fig:evan01}
\end{figure}
Esta ferramenta utiliza o elemento \textit{CANVAS}\footnote{Um elemento do HTML para exibir gráficos em uma página web.} do \textit{HTML5}\footnote{HTML5 (\textit{Hypertext Markup Language}, versão 5) é uma linguagem para estruturação e apresentação de conteúdo para a web.}, onde objetos são desenhados por meio de um \textit{JavaScript}\footnote{Linguagem de programação para páginas HTML e web, executada pelo navegador do cliente.}. Então, como esta ferramenta requer somente um navegador que suporte o elemento \textit{CANVAS}, ela é a ferramenta perfeita para ser utilizada na hora que os usuários do sistema (principalmente os alunos) precisarem fornecer o diagrama de um autômato. Como esta ferramenta tem licença MIT~\cite{mit}, qualquer pessoa pode usar, copiar, modificar, mesclar, publicar, distribuir, sublicenciar e vender como bem entender.
Esta ferramenta tem estas características e pode ser usada para:
\begin{alineas}
\item[$\bullet$] Criar estados com duplo clique em uma área em branco;
\item[$\bullet$] Criar transições com a tecla \textit{shift} e o clicar e arrastar do \textit{mouse};
\item[$\bullet$] Arrastar um objeto com o clicar e arrastar do \textit{mouse};
\item[$\bullet$] Deletar um objeto selecionado clicando a tecla \textit{delete};
\item[$\bullet$] Tornar um estado em aceitação, ou não, com um duplo clique sobre ele;
\item[$\bullet$] Subscrever números com “$\_$”, do seguinte modo “$S\_0$” para obter “$S_0$”;
\item[$\bullet$] Escrever letras gregas do seguinte modo “$\backslash$beta” para obter “$\beta$”;
\item[$\bullet$] Exportar para PNG, SVG e \LaTeX\xspace a máquina de estados;
\item[$\bullet$] Manipular os objetos desta máquina de estados em memória;
\item[$\bullet$] Desenhar os objetos no elemento \textit{CANVAS} do \textit{HTML5};
\item[$\bullet$] Salvar e recuperar automaticamente o diagrama no armazenamento local do navegador;
\end{alineas}
O código fonte está disponível no repositório pessoal do Evan Wallace\footnote{Disponível em: \url{https://github.com/evanw/fsm}.}. Para este projeto precisaremos modificar o código para atender alguns requisitos do sistema. Dentre as funções destacadas acima, somente as funções de exportar, de salvamento e recuperação automática, de inserção de letras gregas e subscrito não nos interessa inicialmente. E, para este sistema, foi necessário a adição de funções extras, tais como: a verificação da correta confecção de um autômato finito determinístico e a extração de sua descrição matemática que para ser enviada ao juiz.
Desenvolvemos assim uma especialização da ferramenta \textit{Finite State Machine Designer}, que possibilita a construção e verificação de autômatos finitos determinísticos, a qual demos o nome de \textbf{DFAdesigner}. Abreviação de \textit{Deterministic Finite Automaton Designer}, ou em português, Construtor de Autômato Finito Determinístico.
\chapter[Desenvolvendo o sistema] {Desenvolvendo o sistema}
Neste capítulo são documentados as etapas do desenvolvimento do sistema web. Definimos os objetivos e requisitos a partir do contexto, para assim analisar e projetar este sistema, para assim, finalmente, implementa-lo e testa-lo.
O sistema pode ser acessado por dois tipos de usuários: Aluno e Professor, que desempenham papeis diferentes no sistema. O aluno é o discente matriculado na disciplina e o professor é o docente que ministra aquela turma.
O objetivo principal deste sistema é a aplicação de listas de exercícios aos alunos de uma turma. E desta maneira, o sistema deve possibilitar também todo o gerenciamento destas aplicações.
Um exercício nada mais é do que uma questão, constituída de um título, um enunciado e um autômato-gabarito que apresenta uma resposta correta. Questões ordenadas compõem uma lista, cada questão pode estar presente em diversas listas.
Uma turma é formada por alunos e está subordinada a um professor, e nela são aplicadas listas de questões. Na aplicação de uma lista, é definida uma data e hora limite para o envio da solução do aluno. Um aluno pode fazer parte de mais de uma turma (por exemplo, no caso dele vir a refazer a disciplina).
Então o professor deve gerenciar todas as turmas, listas e questões criadas por ele. E também o sistema pode suportar mais de um professor, no caso da disciplina ser ofertada por professores diferentes no mesmo período ou em períodos distintos.
Já a administração de todos os usuários, como alunos ou outros professores, fica ao encargo de todos os professores. %Visto a possibilidade de um aluno fazer parte de diferentes turmas, criados por diferentes professores.
Além de alunos e professores, há também um terceiro componente deste sistema, que denominaremos de Juiz, que tem a função de corrigir instantaneamente uma submissão. Ao longo deste capítulo, será melhor detalhado cada componente e seus relacionamentos.
\section{Modelo de Processo}
Para o desenvolvimento deste projeto, foi utilizado o processo de desenvolvimento RAD\footnote{Abreviação de \textit{Rapid Application Development}, em português, Desenvolvimento de Aplicação Rápida.}, que é um modelo de processo de software incremental, que enfatiza um ciclo de desenvolvimento curto. Esse modelo permitiu o desenvolvimento rápido do projeto, que demorou 90 dias. Isso só foi possível porque houve muita reutilização de componentes no projeto, o que garantiu uma padronização tanto na aparência final do sistema, quanto da implementação de seus módulos, visto que o gerenciamento das Questões, Listas, Turmas e Usuários é praticamente igual.