0

I have implemented a simple Scanner-Generator, which runs properly in all situations.

It's not a code issue, but a question about how to optimize DFA. Minimization for one Accept Node using the Hopcroft's algorithm and Accept Nodes for accepting the same rule worked well, but the algorithm did not minimize the DFA with several different Accept Nodes. For example, if you create a DFA that accepts two "if", "[a-z][a-z0-9]*", and then run Hopcroft's algorithm, the unique Accept Node disappears. Of course, each node was grouped into different groups from the beginning.

I would like to know how to minimize this type of DFA. I would like you to answer even if there is no way to solve these minimization problems.

My Code: https://github.com/rollrat/compiler-compiler

rollrat
  • 151
  • 13
  • 1
    If I understand it correctly, you want Hopcroft's algorithm to yield exactly one accepting state? A minimum DFA does not necessarily have only one accepting state. For example, the minimum complete DFA for the language `L={a, aa}` has four states, two of which are accepting. There's no way around that. – Welbog May 06 '19 at 13:11
  • @Welbog No, No. I just want a way to create a more minimized DFA. It does not need to be abbreviated as one for different Accept Node groups. I just asked if there are other minimization algorithms because of the abbreviated problem using the Hopcroft's Algorithm like this picture. https://imgur.com/a/HVfUeFt The "else" Accept Node has disappeared completely. – rollrat May 07 '19 at 02:39

0 Answers0