search

flapjs / FLAPJS-WebApp

An intuitive web app to help you explore and construct formal languages and automata with real-time analysis and error checking.
https://flapjs.github.io/FLAPJS-WebApp
MIT License
13 stars 8 forks source link

DFA Minimization #2

Closed moreheadm closed 5 years ago

moreheadm commented 5 years ago

I talked to Professor Minnes on Friday and she said that I could contribute to FlapJS by writing DFA minimization and equivalence code. What exactly needs to done on this front? I've notice that the option to optimize equivalent states seems to be currently (purposely?) disabled in the UI. I've also looked at the code in src/app/machine/util/minimizeFSA.js, and it seems like the algorithm there should work, although it is slightly different from the one suggested by Wikipedia.

What exactly has to be done to get this working? Is it just a matter of fixing bugs in the algorithm and re-enabling the UI option, or is it slightly more involved?

-Max

andykuo1 commented 5 years ago

That is amazing. Sadly, minimizeFSA and equalFSA is not completely implemented. However, we are currently working on fixing equalFSA (now EqualFSA.js under fsa2), but have no immediate plans yet for minimizeFSA. Since we have refactored much of the FSA code, these functions would probably benefit more from a complete rewrite than fixing its current issues. Please email me if you have further questions.