undefined | Better HN

0 pointspkal8mo ago0 comments

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.

0 comments

ryandv8mo ago

That'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

[1] https://en.wikipedia.org/wiki/Nondeterministic_finite_automa...

j / k navigate · click thread line to collapse