search

leonbohn / automata

MIT License
4 stars 0 forks source link

Alternative Generation of Random Transition Systems #57

Closed fesemeyer closed 3 months ago

fesemeyer commented 3 months ago

Add some functions to randomly generate transition systems, automata and words.

The implemented algorithm for generating transition systems takes a size n and adds that many states. Afterwards, edges are randomly drawn. Note that there can be unreachable states.

Based on this algorithm there are functions generate_random_dba and generate_random_dpa for DBA and DPA respectively. The acceptance conditions are drawn uniformly.

Note that as of now, if there are unreachable states, they remain in the generated automaton because the function remove_state() from the Shrinkable trait is not yet implemented for LinkedListTransitionSystem.

The algorithm for drawing finite words takes min and max lengths, uniformly draws a random length from that range and afterwards generates a word of that length by uniformly drawing symbols from the universe of the alphabet. Omega words work equivalently by drawing the spoke and the cycle which are finite words.

leonbohn commented 3 months ago

I have added the methods trim and trim_from to the Sproutable trait. The random generation methods now also return a transition system of type DTS, which is guaranteed to implement Sproutable which means we can also remove unreachable traits.