Good day. We have a finite automaton F1, for example,
.
We need to get automaton F2 that accepts strings like accepted by F1, but symbols may be in different order. Clearly, there may be large number of combinations, factorials will be here. And we have a sample, for example,
abcde, bacde, baced.
As you can see, it is not random strings, there is some structure. How to learn F2 from given sample? There are existing techniques and algorithms for that specific case (not common grammar and automata learning algorithms without additional information)? What is the automaton should be in my example and what will it be if we add
abced
to sample?
There is a standard way to do this, though it is unlikely to give you the most efficient result.
First create a non-deterministic finite automaton to recognise the finite language you want. This could consist of one "piece" like the one you have shown for each word - so, for your first question, three pieces: the states in the second would be labelled $b,a,c,d,e$ and in the third $b,a,c,e,d$. All of the "left hand ends" would be initial states. Then there is a standard algorithm for converting the NDFA to a DFA. It begins by taking each state of the DFA to be a set of states from the NDFA. The rest should not be hard to find online.