HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

generate possible inputs valid for automata

Submitted by: @import:stackexchange-cs··
0
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.

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.