REPOSITORY CODING · MEDIUM
Repair future-sensitive DFA minimization
States with the same immediate acceptance can still be separated by a future suffix. Propagate distinguishability through transition targets until no pair changes.
Language automataFinite automaton workbench
Work through a real codebase.
Choose an environment, investigate the existing implementation and use the tests to check your change. Sign in to open a workspace; execution and Ono usage follow your plan’s allowances.
Task requirements and environments
C++ · 55 minute session
- Analyze an epsilon-NFA with 1..12 states, a start state, accepting state IDs, up to 80 edges and a unique alphabet of at most six lowercase ASCII single-character symbols. A null edge symbol is epsilon. Validate all references and input words (at most 30 words, each at most 64 symbols).
- Compute epsilon closure to a fixed point and determinize reachable subsets in sorted-symbol breadth-first order, retaining the empty subset as a rejecting sink whenever reachable. Reject expansions above 128 DFA states with state-limit. A subset accepts if any member accepts.
- Return word membership, membership in the complement over exactly the declared alphabet, and the number of states in the minimal reachable complete DFA. Empty alphabets and empty words are supported.
- If other is supplied, require the same alphabet and compare languages by a breadth-first product traversal. Return equivalent plus the shortest, lexicographically smallest distinguishing witness, or null when equivalent; an empty-string witness is distinct from null. No external libraries or services implement the automaton algorithms.