REPOSITORY CODING · HARD
Repair comparison identities and witness order
Language comparison loses product states and sometimes returns the wrong tie-breaking witness. Preserve ordered state pairs and traverse symbols lexically in the breadth-first search.
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++ · 80 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.