# How to generate Extended Finite State Machines Randomly with some properties?

This is related to my academic project

An extended finite state machine is a tuple $SM=(I,S,T)$ (simplified):

• $I$ is the set of identifiers and it's divided into two sets Inputs and outputs, for simplification we will just consider boolean variables. Let $\sigma$ be the evaluation function $\sigma :I \to \{0,1\}$ which associate to very identifier its value, And let $\Sigma$ be the set of all evaluations.
• $S$ is the set of states
• $T\subseteq S\times S \times G\times A$ the set of transitions, a transition $t=(s_1,s_2,g,a)$ means :

• $s_1$ the source state
• $s_2$ the target state
• $g$ the guard,which is usual expressed in the guard language and here we can just consider it as its semantic $g:\Sigma \to \{0,1\}$ where $g(\sigma)$ is an element of $\{0,1\}$.

• $a$ is usually expressed in the action language, and we will here identify it with its semantic $a:\Sigma \to \Sigma$ where $f(\sigma)$ is another evaluation function.

Now a configuration of the state machine $SM$ is a tuple $(s_i,\sigma)$ where $s_i$ is the current state and the $\sigma$ the current evaluation function. A run of the machine is : $$(\sigma_0,s_0)\to(\sigma_1,s_{1})\to (\sigma_2,s_2)\to \cdots (\sigma_k,s_k)\to(\sigma_{k+1},s_{k+1})\to \cdots$$ where for every $k$ we have $(s_k,s_{k+1},g,a)$ is a transition and $g(\sigma_k)=1$ (meaning true) and $a(\sigma_k)=\sigma_{k+1}$

Example of action : we denote an action by $Rep(a)=[e_1,\cdots,e_n]$ where $e_i$ is a boolean expression over the variables in $I=[o_1,\cdots,o_n,i_1,\cdots ,i_k]$ where $i_j$ are the inputs of the system and are determined by the environment. And from this representation of the action we can have $a(\sigma)(x)=e_j(\sigma)$ if $x=o_j$ and $a(\sigma)(x)=i_j$ if $x=i_j$

The guards are represented by expressions over the set of the variables $I$

What I am able to do : I was able to generate some boolean expressions that are valid or satisfiable using either well known examples, or using the threshold density of boolean formulas. Hence I am able to generate the guards and the actions (which are random, and have some properties like satisfiable or valid)

Question : how could I generate a random Extended State machine with the property that: Every state is reachable and every transition can be executed

you can use that fact that I am able to generate a formula that evaluates to $1$ or $0$ and I can generate a satisfiable or unsatisfiable formula

Any other ideas to do tests with Extended State Machines? Thanks

Edit 29/04/2016

As my question is either not very clear or difficult; I have an alternative question:

Question 2: what are some well known random Extended State Machines for which every state is reachable.

The purpose of my project is to test the efficiency of an algorithm

• I don't understand how could I improve my question? Commented Apr 5, 2016 at 14:44
• Are you still interested in this question, or did you find a solution to it? I am interested in a similar problem. Commented Jul 9, 2020 at 9:38
• Sorry, It has been years ago, and if I remember correctly, I did not succeed in finding a solution Commented Jul 9, 2020 at 21:12

You can generate a random automaton naively (i.e., every state sends a directed edge uniformly at random to every other state, including itself) and then remove the unreachable states. If you start with $n$ states, you will end up with roughly $cn$ states (where $c$ is explicitly computable), and this is tighly concentrated: https://dl.dropboxusercontent.com/u/3198145/rand-dfa.pdf
Thus, if your goal is $n$ states, start with, say, $n/c$ states, generate a random automaton, and remove unreachable states. Note that this process does not sample uniformly from all $n$-state automata, but you didn't ask for a uniform distribution. See also references in that linked paper for generating random automata with various properties.