Pitch: Yet Another Automata Simulator (YAAS)

[davidbuzatto]

Boa tarde!

Meu nome é David Buzatto, sou professor do Instituto Federal de São Paulo (IFSP) e atualmente trabalho com várias disciplinas do curso de Bacharelado em Ciência da Computação. Dentre essas disciplinas, uma delas é a de Linguagens Formais e Autômatos, também conhecida como Teoria da Computação, entre outros nomes.

Essa é uma das disciplinas que me fascinam e, desde 2008, na época do meu mestrado, eu venho desenvolvendo pequenos simuladores para assuntos relacionados à temática das linguagens formais, além de propor algumas atividades de implementação nesse domínio na disciplina que leciono.

De fato, existem exemplos de simuladores deste tipo, sendo talvez o mais famoso deles o JFLAP (https://www.jflap.org/) que, apesar de cobrir muitos assuntos, é um pouco difícil de usar, pois não é tão intuitivo. Com isso em mente, decidi colocar minha experiência na construção desses protótipos para criar uma ferramenta mais completa e de código aberto, me auxiliando na condução da minha disciplina e permitindo que meus alunos realizem alguns testes, além de provavelmente usá-la na proposição de atividades de implementação aos alunos, onde eles poderão estender a ferramenta.

Sendo assim, apresento-lhes o YAAS, mais um simulador de autômatos! O endereço do projeto é GitHub - davidbuzatto/YAAS: Yet Another Automata Simulator (YAAS) is a prototype tool for simulating the execution of Finite Automata, Pushdown Automata and Turing Machines.. Muito do código ainda precisa ser refatorado e preparado para a continuação da implementação, mas essa versão já traz ao usuário praticamente todas as funcionalidades que envolvem a construção, simulação e a aplicação de algoritmos em Autômatos Finitos como geração de Autômatos Finitos Determinísticos a partir de Autômatos Finitos Não-Determinísticos, minimização de Autômatos Finitos Determinísticos, especificação total de funções de transição, complementação de DFAs, salvar o modelo como imagem etc. Essa versão pode ser baixada em Release v0.7.2 · davidbuzatto/YAAS · GitHub, onde são disponilizados um instalador para Windows e um arquivo .jar para quem não quiser instalar ou rodar no Linux, por exemplo.

Espero que seja interessante aos colegas! Quaisquer críticas, sugestões (e elogios, claro) são bem-vindos!

[TerraSkilll]

Boa mestre! Sempre com autômatos na cabeça

Fiquei curioso e tentei rodar aqui direto do jar, mas dá um erro:

No prompt, diz que não foi possível carregar a classe principal. Meu java é o 1.8

Abraço.

[hugokotsubo]

@TerraSkilll

No prompt, diz que não foi possível carregar a classe principal. Meu java é o 1.8

Eu rodei com Java 21, mas tem que ser com a opção -jar:

java -jar YAAS-0.7.2.jar

Com Java 8 não vai rodar mesmo, pois foi compilado com uma versão mais recente. Quando tentei rodar com Java 11, por exemplo, deu erro:

java.lang.UnsupportedClassVersionError: br/com/davidbuzatto/yaas/gui/MainWindow has been compiled by a more recent version of the Java Runtime (class file version 62.0), this version of the Java Runtime only recognizes class file versions up to 55.0

No caso, o class file version 62.0 corresponde ao Java 18. Em versões anteriores, não vai funcionar.

[hugokotsubo]

Excelente!

Parafraseando o que eu já disse em outro site:

Complementando: pra quem não sabe, Autômatos são a base teórica para muitas coisas, entre elas a construção de um compilador. Faz parte daquela “teoria chata e inútil” que os cursos caça-níquel costumam ignorar.

Ok, talvez a maioria não vá usar diretamente e nem sequer implementar um, mas não é conhecimento inútil. Saber como funcionam as entranhas te dá um entendimento maior da computação como um todo, te tornando um profissional melhor. Esse ganho é indireto e difícil de perceber no curto prazo, talvez por isso seja tão negligenciado, mais até do que a “base clássica” (algoritmos, matemática, lógica e estruturas de dados).

[TerraSkilll]

Sim, mesmo erro (UnsupportedClassVersionError) com a opção -jar. Mexo tão pouco com java ultimamente, que esses casos sempre me escapam. Vou ver se consigo usar um java mais recente.

Pro @davidbuzatto , pode ser o caso de atualizar o readme pra indicar qual a versão do java é necessária. Pra quem roda do fonte fica óbvio, mas nem tanto pra quem roda direto do jar.

Abraços.

[davidbuzatto]

Bom dia! @TerraSkilll, no release do Github está indicando Java 18. Usa o instalador, ele instala por usuário e não deixa sujeira depois se desinstalar. O instalador é feito usando jpackage, que vem no JDK. Ele já traz uma cópia do runtime mínimo para executar

Acho um assunto fascinante mesmo. Esse agora eu pretendo construir uma ferramenta completa! Estou usando para atualizar meu material de aula e para corrigir provas

[davidbuzatto]

Obrigado Hugo! Acabei de ver sua resposta lá! Nessa disciplina, logo na segunda semana eu forneço um projeto para os alunos com a implementação de parcial de um autômato finito, a estrutura de dados em si, e eles tem que implementar o método que realiza a verificação de pertinência de uma string na linguagem representada pelo autômato. No projeto eles testam se o algoritmo funciona através de testes de unidade que vão prontos tbm. Eu forço a implementação em todas as disciplinas que leciono. Acho que tem que puxar mesmo. Em. Compiladores, na primeira semana eles tem que implementar quase do zero um analisador léxico tbm, que no final das contas, tbm é um autômato finito.

[davidbuzatto]

Boa tarde! A quem puder interessar, segue release da nova versão do YAAS, mais um simulador de autômatos. Aproveito de antemão para me desculpar por possíveis duplicatas. Essa mensagem está sendo transmitida em diversos meios.

Depois de duas semanas trabalhando mais de 6 horas por dia nos meus horários vagos, acabo de lançar a versão 0.8.0 do YAAS. A principal novidade desta versão é a implementação do editor para construção de Autômatos de Pilha (Pushdown Automata) e a possibilidade de executar simulações de pertinência de strings em linguagens livres de contexto representadas pelo autômato construído. Além dessa funcionalide principal, há diversas outras novidades menores, principalmente relacionadas à qualidade de vida do usuário. A partir da versão 1.0.0 do simulador será assegurada a compatibilidade de arquivos binários gerados por ele. Por enquanto, a serialização dos modelos é atrelada à versão do simulador. Esta ferramenta tem se mostrado bastante útil na condução da disciplina de Linguagens Formais e Autômatos do curso de Bacharelado em Ciência da Computação do IFSP, câmpus São João da Boa Vista, a qual dou aula atualmente, além de também estar servindo como alternativa ao JFLAP para que os alunos consigam testar seus modelos. Quem já fez essa disciplina sabe o qual espinhoso o assunto pode ser.

A versão 0.8.0 do YAAS pode ser obtida aqui: Release v0.8.0 · davidbuzatto/YAAS · GitHub, havendo opção de download como instalador para Windows, bastante prático por sinal, ou para execução direta, o que demanda a instalação da JRE 18 ou do JDK 18 ou superior.

O próximo ciclo de desenvolvimento dará conta da implementação das Máquinas de Turing (versões 0.9.x) e, a partir dai, haverá a primeira feature freeze do projeto, para que bugs sejam resolvidos quando necessário e para o lançamento da versão 1.0.x. O processo de implementação está sendo transmitido diariamente no meu canal do YouTube (https://www.youtube.com/channel/UCtuPFOgX47mBfNoG4gXgjfA).

Obrigado!

Algumas imagens do simulador em execução:

[davidbuzatto]

Boa tarde! A quem puder interessar, segue release da primeira versão completa do YAAS, mais um simulador de autômatos. Aproveito de antemão para me desculpar por possíveis duplicatas. Essa mensagem está sendo transmitida em diversos meios.

A motivação para a criação de mais uma ferramenta para simulação de autômatos se deve à necessidade encontrada por mim, prof. David Buzatto, durante a condução da disciplina de Linguagens Formais e Autômatos, em auxiliar os alunos dessa disciplina em modelar e testar alguns modelos de computação conhecidos como Autômatos Finitos, Autômatos de Pilha e Máquinas de Turing. Durante quase dois meses foram empregadas dezenas de horas na concepção, implementação e testes do Yet Another Automata Simulator (YAAS), “mais um simulador de autômatos”. A versão v1.0.0 da ferramenta conta com as funcionalidades listadas abaixo:

Autômatos Finitos

• Suporte completo para a modelagem, teste e simulação de Autômatos Finitos Determinísticos, Não-determinísticos e Não-determinísticos com épsilon-transições;
• Criação, edição, armazenamento e armazenamento como imagem;
• Suporte para inserção de transições ausentes;
• Suporte para remoção de estados inacessíveis e inúteis;
• Conversão de Autômatos Finitos Não-determinísticos para Autômatos Finitos Determinísticos;
• Minimização de Autômatos Finitos Determinísticos;
• Operações regulares:
  • União;
  • Concatenação;
  • Estrela de Kleene;
  • Complemento;
  • Interseção.

Autômatos de Pilha

• Suporte completo para a modelagem, teste e simulação de Autômatos de Pilha Determinísticos e Não-determinísticos;
• Criação, edição, armazenamento e armazenamento como imagem;
• Conversão entre representações para aceitam por estado final para aceitação por pilha vazia e vice-versa;

Máquinas de Turing

• Suporte completo para a modelagem, teste e simulação de Máquinas e Turing Determinísticas;
• Suporte para modelagem de Máquinas e Turing Não-determinísticas;
• Criação, edição, armazenamento e armazenamento como imagem;
• Detecção automática de loops infinitos, ou seja, Máquinas de Turing que nunca param.

A versão 1.0.0 do YAAS pode ser obtida aqui: Release v1.0.0 · davidbuzatto/YAAS · GitHub, havendo opção de download como instalador para Windows, bastante prático por sinal, ou para execução direta, o que demanda a instalação da JRE 18 ou do JDK 18 ou superior. A versão instalada inclusive associa os arquivos salvos pelo simulador com a ferramenta, sendo possível abrí-los com duplo clique.

Um tutorial simples de como usar a ferramenta pode ser encontrado aqui https://youtu.be/ILxWF1mf8PY
Esse tutorial em breve será regravado com uma melhor explicação das funcionalidades.

Quaisquer sugestões e críticas são muito bem-vindos!

Obrigado!