Trabalho Prático 1 de Fundamentos Teóricos da Computação: Simulação de AFDs - Autômatos Finitos Determinísticos
O código deste repositório representa o primeiro trabalho prático da disciplina de Fundamentos Teóricos da Computação. Seu intuito é simular as funções e propriedades de autômatos finitos determinísticos (AFDs), como minimização, equivalência e produto - com as operações de união, interseção e diferença.
A seguir, serão apresentadas as funções principais dos algoritmos presentes neste trabalho.
O trabalho permite importar arquivos de AFDs diretamente do programa JFLAP no formato XML (.jff, no caso do software) para maior facilidade de utilização. A biblioteca Tkinter é usada para abrir uma janela de diálogo para a escolha do arquivo.
O usuário pode importar quantos autômatos desejar, uma vez que eles ficam armazenados em memória em um dicionário que relaciona seus nomes (que o usuário dá) com as classes montadas pelo programa no momento da importação. Dessa forma, para qualquer operação que se deseja fazer, basta digitar o nome do autômato dentro do algoritmo, e ele será usado.
Depois de realizar as funcionalidades com o autômato, o usuário pode salvá-lo em seu computador como um arquivo JFLAP para posterior utilização e visualização. Essa funcionalidade também utiliza a biblioteca Tkinter para a janela de seleção de arquivos.
A minimização de um AFD é o processo de diminuir a quantidade de estados necessários para processar uma cadeia de caracteres sem alterar o seu funcionamento. Dessa forma, o autômato minimizado aceitará e rejeitará as mesmas cadeias de caracteres que seu original. O processo de minimização de um autômato no programa ocorre da seguinte forma: a. Encontrar os estados alcançáveis: se um estado não é alcançável a partir do estado final, ele não faz diferença para o funcionamento do autômato, logo, pode ser retirado sem maiores problemas.
b. Encontrar estados não equivalentes: este processo utiliza do teorema de Myhill-Nerode (link nos próximos tópicos), no qual é possível identificar os estados que não são equivalentes dentro do autômato.
c. Agrupar estados equivalentes: ainda no mesmo teorema, agrupamos os estados equivalentes seguindo o seguinte pensamento: esse processo é a formação de "estados minimizados" (grupos) a partir dos estados originais do AFD. Inicialmente, cada estado original forma seu próprio estado minimizado. Depois, quando descobrimos que dois estados são equivalentes (não pertencendo ao conjunto de estados não equivalentes anteriormente descoberto), unimos seus estados minimizados correspondentes. Se o estado
d. Construir o AFD minimizado: com os grupos de estados equivalentes em mãos, simplesmente construímos um dicionário que relaciona um estado para o representante do seu grupo (o com o primeiro nome na ordem alfabética). Assim, os novos estados do AFD mínimo excluirão os demais estados do grupo de equivalentes. Para as transições, substituímos cada estado pelo representante de seu grupo, bem como acontece com o estado inicial e os estados finais. Dessa forma, retornamos o autômato montado e minimizado.
O autômato minimizado pode substituir o original ou ser salvo com o nome automático [nome-original]-min, dependendo da escolha do usuário.
A união de dois AFDs é dada pelo seguinte: [nome-afd1]-uni-[nome-afd2].
A interseção de dois AFDs é dada pelo seguinte: [nome-afd1]-int-[nome-afd2].
A diferença de dois AFDs é dada pelo seguinte: [nome-afd1]-dif-[nome-afd2].
O complemento de um AFD é feito quando atribuímos o status de final aos estados que não são, e tiramos esse atributo dos estados que são. No programa, o usuário pode escolher se o autômato complementado será atribuído a um novo autômato ou se substituirá o original. Caso um novo AFD seja gerado, ele terá o nome automático de [nome-original]-comp.
O programa testa se dois AFDs são equivalentes ou não retornando True ou False para cada um dos casos, respectivamente. As condições para que dois autômatos sejam equivalentes são as seguintes:
a. Os alfabetos precisam ser iguais;
b. Se o estado inicial de um deles for final, o estado inicial do outro necessariamente precisa ser final também.
c. Para qualquer par de estados gerado a partir dos estados iniciais de dois autômatos na forma
O programa também consegue identificar quais grupos de estados são equivalentes dentro de um autômato. Isso acontece usando basicamente usando o teorema de Myhill-Nerode, o método da tabela que é usado no processo de minimização de autômatos finitos determinísticos. Fonte: https://www.youtube.com/watch?v=UiXkJUTkp44 Ao usar essa função, ela retorna algo parecido com o seguinte:
O seguinte conjunto de estados é equivalente: q11, q14
O seguinte conjunto de estados é equivalente: q1, q5, q6, q8
Mas, atenção, essa função não vai juntar os estados equivalentes em um só. Isso é cargo da função de minimização, que também utiliza do mesmo teorema em seu funcionamento.
Dado pelo menos um autômato importado no sistema, será possível visualizar todos os AFDs disponíveis no programa. O resultado será parecido com o a seguir:
1. a-impar
2. b-impar
Dado pelo menos um autômato importado no sistema, será possível visualizar seus estados, alfabeto, transições, estado inicial e estados finais dentro do programa. Basta selecioná-lo e aparecerá um resultado parecido com o a seguir:
AFD(
estados: ['q0', 'q1']
alfabeto: ['a', 'b']
transicoes:
('q0', 'b') -> q0
('q1', 'b') -> q1
('q0', 'a') -> q1
('q1', 'a') -> q0
estado_inicial: q0
estados_finais: ['q1']
)
Caso seja necessária uma nova instância de certo autômato, basta copiá-lo que haverá uma cópia independente do original, nomeada automaticamente como [nome-original]-copia.
Para um determinado autômato escolhido, o programa verificará se a cadeia termina em um estado de aceitação (estado final), se sim, a cadeia é aceita, caso contrário, não.
Desenvolvido com ❤️ para o professor Walace.