3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This gives the shortest string(s) accepted. $\endgroup$ – vonbrand Jun 20 '14 at 14:37
  • 1
    $\begingroup$ If you mean that there is no string in the language that is shorter than a string in the ones we generate, that is not necessarily the case. There could be a cycle that gives many string shorter than one on a long path. $\endgroup$ – gardenhead Jun 20 '14 at 21:04
3
$\begingroup$

A way to generate strings accepted by a given DFA is to start at the initial state, and follow a random transition out of the current state at each step, recording the symbol(s) that would give this transition. Output the result each time you reach a final state, backtrack when you hit a dead state. Collect a few strings each run, and start over to get another path through the DFA.

I'd minimize the DFA beforehand to make this more efficient.

$\endgroup$
3
$\begingroup$

Another way to think of the process described in the other answers is as follows:

  1. Convert the DFA into a Regular Grammar (use the one that puts the nonterminal on the right, for convenience)
  2. Assign $L_0 = \{S\}$ where $S$ is the start symbol for your grammar.
  3. Iteratively compute $L_{i+1}$ from $L_i$. All sentences in $L_i$ will end with a single nonterminal; they are of the form $\alpha X$ where $\alpha$ consists only of terminals (maybe empty). Now, for each $\alpha X \in L_i$, consider all $\alpha \beta$ where your grammar has a production of the form $X \rightarrow \beta$. If $\alpha \beta$ consists only of terminals, it's a string in the language accepted by the DFA; otherwise, it belongs in $L_{i+1}$. If $L_{i}$ is ever empty, then your DFA accepts a finite language.

This might be a bit more natural, since grammars are typically thought of as generating languages anyway (whereas automata are usually thought of as recognizing or accepting strings).

$\endgroup$

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.