REPOSITORY CODING · MEDIUM
Repair transitive epsilon closure
An empty word should reach accepting states through multiple epsilon edges, including cycles. Compute the complete closure before and after consuming each symbol.
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.