3 ms·
From automata theory, you might know that nondeterministic automata are represented by a set of states. Deterministic automata are always in a specific state,
by pkal 1y ago
From automata theory, you might know that nondeterministic automata are represented by a set of states. Deterministic automata are always in a specific state, while nondeterministic ones are in multiple at once. Lists are used for non-determinism in Haskell the same way as a set, mainly because they are easier to implement. But the total order that a list induces over a set is not that relevant.
- ryandv 1y agoThat's right, and you see this directly reflected in the "types" of the transition functions for DFAs and NFAs, respectively [0] [1]: δ : Q × E ⟶ Q δ : Q × E ⟶ P(Q) ... where Q denotes the set of the automaton's states, E its alphabet of input symbols, and P the power set operation. Deterministic automata arrive at a definite, single state drawn from Q, while non-deterministic automata may arrive at a set (~list) of possible states, when given a current state from Q and next input symbol from E. [0] https://en.wikipedia.org/wiki/Deterministic_finite_automaton https://en.wikipedia.org/wiki/Deterministic_finite_automaton [1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...