I want to encode finite state machines (specifically DFAs) as output (or input) of a neural network for a supervised learning task.

Are there any ways in the literature for doing this?

I've already found some algorithms being able to extract a DFA from a recurrent neural network, but nothing about DFAs either as input or output of ANN.

  • $\begingroup$ Is the purpose to learn an unknown DFA from observation of data, or to encode a known DFA as a RNN, or something else? $\endgroup$ – Neil Slater Jul 21 '16 at 13:19
  • $\begingroup$ Mainly, to learn unknown DFA from data; but, unlike the RNN approach which "interprets" RNN as a DFA, I would yield a DFA as output of the network. $\endgroup$ – Gabrer Jul 21 '16 at 14:49
  • $\begingroup$ How much of the system do you have observed in your data? Do you have full knowledge of the state and input string at each step? If not, what do you have? $\endgroup$ – Neil Slater Jul 21 '16 at 19:36
  • $\begingroup$ I've a structurally complete set of strings with respect to target language/automaton. Then, all the needed states are "observable". $\endgroup$ – Gabrer Jul 27 '16 at 9:41
  • $\begingroup$ My knowledge about DFAs is extremely limited but you can encode it as a graph, correct? If that is the case, you could look at Graph Convolutional Neural Networks, which take a graph as input. I think the expressive power might be too limited, but it might be worth a look. $\endgroup$ – Jan van der Vegt Nov 6 '17 at 15:15

The better question might be - Why you do want to mix deep neural networks (DNN) and a finite state machine (FSM)?

There is research showing that a DNN can simulate any FSM. Since there are more frameworks for DNN and DNN can perform more tasks than FSM, it appears to be more useful just to forgo FSM altogether.

More specifically, "Neural network for synthesizing deterministic finite automata" shows how a relatively simple neural network (NN) can quickly and automatically learn the correct deterministic finite automaton (DFA).

There is a strong trend towards end-to-end DNN.


Take a look at the neural state machine by Hudson & Manning. It's non-deterministic but it is differentiable, which gives you the same kind of "black box learning power" as neural networks.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.