Our finite state automata can be thought of as machines with a restricted stack, one we are only allowed to pop symbols off of. Initially this stack contains the input, with the first symbol at the top of the stack and the last symbol at the bottom.
We could, if we wanted to, consider finite state automata which have a write-only stack rather than a read-only stack, i.e. ones which we can push symbols onto but can pop symbols off of. These have no input but have an output, i.e the final state of the stack, where can conventionally agree that the top of the stack is the last output symbol and the bottom is the first.
It’s reasonable to ask which languages can be the set of outputs for such a finite state automaton. If we restrict to deterministic finite state automata then the answer is totally uninteresting, since these could only ever generate one list. If we allow non-deterministic finite state automata then the answer is once again the regular languages, so we have yet another characterisation of these languages.
We could even consider a generalisation of finite state automata with
two stacks, one read-only stack for the input and one write-only stack
for the output. These are generally called transducers. The other types
of finite state automata can be considered as special cases of the
transducer. You can, for example, consider the read-only automata from
the earlier chapter as ones which read the input and produce as output a
single special symbol, either accept or
reject, depending on whether we end up in an accepting or
rejecting state. It’s easy to generalise this to a classifier, a machine
which produces output from a finite set of options, not just two. In
fact this essentially is the job of a lexical analyser and a lexical
analyser can be implemented by such an automaton, a special case of the
transducer.