vyaakaran icon indicating copy to clipboard operation
vyaakaran copied to clipboard

Published 20 hours ago • verified publisher icon blenderskool

Improve the efficiency of regular grammar processing

Open riya461 opened this issue 6 months ago • 4 comments

Description:

This PR addresses the issue #21 and issue #2 raised. We made the following enhancements to improve the efficiency of regular language processing.

Changes made:

NFA to DFA Conversion:

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

DFA State Minimization:

  • Implemented Hopcroft for reducing the number of states in a deterministic finite automaton (DFA) while maintaining its language recognition capabilities.

Optimization Algorithms:

  • Co-reachability: Identify states that can reach a final state and eliminate non-contributing states.
  • Cyclic Dependency: Add method to detect and raise a warning for cyclic dependencies.

riya461 avatar Jul 28 '24 12:07 riya461