Enhancing Regular Language Parsing: NFA to DFA, State Minimization, and Optimization Algorithms

[vaishakhRaveendran]

Description:

We propose the following enhancements to improve the efficiency of regular language processing:

• NFA to DFA Conversion: Implement the subset construction algorithm to convert Non-deterministic Finite Automata (NFA) to Deterministic Finite Automata (DFA).

• DFA State Minimization: Add an algorithm to minimize DFA states by merging equivalent states, producing a more efficient automaton.

• Optimization Algorithms:

  • Forward Reachability: Determine the set of states reachable from the initial state and remove unreachable states.
  • Co-reachability: Identify states that can reach a final state and eliminate non-contributing states.

---

[blenderskool]

@vaishakhRaveendran How would the forward reachability changes be different from the current implementation?

[vaishakhRaveendran]

We're planning to use a breadth-first search (BFS) starting from the initial state 'S' to explore all the reachable nodes in the finite automaton. Yes, it is kind of similar to the current implementation. It's an experiment we're trying out. We've noticed it can be a lot faster with parallelization for larger graphs. We're aiming to build this if we can.

[blenderskool]

@vaishakhRaveendran Sure, do take a shot at it. I would recommend exploring the BFS approach if you have time. Other enhancements are actual extensions to the project, while this may just be a performance improvement. Also, do measure the computation times before / after the forward reachability changes.