6
$\begingroup$

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.

$\endgroup$
6
  • $\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$ Jul 21, 2016 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, 2016 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$ Jul 21, 2016 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, 2016 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$ Nov 6, 2017 at 15:15

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ A lot of assumptions built into your answer/question. What if we require an executable output from the neural network? $\endgroup$ Jan 31 at 22:20
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

https://www.dlsi.ua.es/~mlf/nnafmc/pbook.pdf Neural Networks: Automata and Formal Models of Computation Mikel L. Forcada Universitat d’Alacant, Dept. Llenguatges i Sistemes Inform`atics, E-03071 Alacant (Spain). January 21, 2002

New contributor
Roman Mishchenko is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. - From Review $\endgroup$
    – Ethan
    Nov 30 at 23:46
  • $\begingroup$ Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    21 hours ago

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.