FizzBuzz using DFA intersection

Some questions...

  1. I came up with the idea once for finite automata where some transitions represent inputs, others represent outputs. Equivalently, for finite automata where a transition represents (normally) one input and a finite automaton/regular grammar of outputs. "Equivalently" in the sense that there's an isomorphism? (sorry, losing track of some terminology), though there's one minor exception for when the first events in the grammar are outputs (the single-input-per-transition model needs a special-case epsilon). Have implementation in C++, it's nice in it's way, the two-way translation is useful because some things are easier to specify each way, but it's stupid for the application I used it for. I don't think that kind of model is original (I asked somewhere once, got an answer referring to comms protocols), so is that supported? Mainly, when dealing with one event per transition (either input or output, not both) the only difference from "conventional" finite automata was the definition of determinism. Translation between the two forms involved not-that-awkward closure algorithms and Hopcroft-style minimisation.

  2. Are the automata always deterministic? What I found in my misadventure was that allowing non-determinism was convenient. I eliminated the non-determinism (as much as possible) at key points, but even that wasn't guaranteed, and what I soon realized was that the ability to minimize DFAs and get a canonical form has it's plus side but also some unpleasant costs in terms of growth. Actually, needing a canonical form for automata was part of implementing the one-input-many-outputs form (how to get a UID for an edge transition annotated with an automaton for the outputs) now I think of it.

  3. FizzBuzz? Seriously? OK, intersection of finite automata was surprising the first time I realized it could be done, but FizzBuzz?

/r/haskell Thread Link -