snippetMinor
generate possible inputs valid for automata
Viewed 0 times
inputsautomatapossiblegenerateforvalid
Problem
I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not.
Can we do the reverse ?
I am looking for solution which generates few possible inputs (not all) accepted by automata(NFA/DFA).
One of the Brute-force approach can be to randomly select inputs and validate with automata if passes then consider those as desired .
But really don't want that . What really am i looking for here, can we use automata itself for produce possible inputs which are accepted by automata.
Any approach also would be helpful.
Can we do the reverse ?
I am looking for solution which generates few possible inputs (not all) accepted by automata(NFA/DFA).
One of the Brute-force approach can be to randomly select inputs and validate with automata if passes then consider those as desired .
But really don't want that . What really am i looking for here, can we use automata itself for produce possible inputs which are accepted by automata.
Any approach also would be helpful.
Solution
Just do a BFS from the start state, and at every node keep track of what transitions you took to get there. Obviously this will only generate a finite number of words, as it doesn't follow cycles.
Context
StackExchange Computer Science Q#27858, answer score: 6
Revisions (0)
No revisions yet.