<p>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:
<a href="https://dl.dropboxusercontent.com/u/3198145/rand-dfa.pdf" rel="nofollow">https://dl.dropboxusercontent.com/u/3198145/rand-dfa.pdf</a></p>

<p>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.</p>

CC BY-SA 3.0
2016-05-02T06:41:11.570Z
Thank you for your answer. What I am asking for is slightly different than "classical automaton" of finite state machines; It's Extended finite state machine and for this kind of automaton we can not directly test reachability because it's a difficult problem and it produces Space State Explosion. I am not demanding uniform distribution but only covering a large space and if there are some well known examples of EFSM I am very interested. Notice also that the number of states is expected to be not very large ( approximately 100)
Elaqqad
CC BY-SA 3.0
2016-05-02T07:08:26.667Z
I see. If reachability is a hard problem then indeed my proposed solution doesn't work.
Aryeh
CC BY-SA 3.0
2016-05-02T07:38:56.017Z
Unfortunately yes, and what I am thinking of is using some well defined examples and parametrize them like logic circuits or counters. Another idea is to extract them from existing programs. But I don't really know if any of this will work
Elaqqad
CC BY-SA 3.0
2016-05-01T14:42:25.610Z
2016-05-01T14:42:25.610Z
Aryeh
<p>This is related to my academic project</p>

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

<ul>
<li>$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.</li>
<li>$S$ is the set of states </li>
<li><p>$T\subseteq S\times S \times G\times A$ the set of transitions, a transition $t=(s_1,s_2,g,a)$ means :</p>

<ul>
<li>$s_1$ the source state</li>
<li>$s_2$ the target state</li>
<li><p>$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\}$.</p></li>
<li><p>$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.</p></li>
</ul></li>
</ul>

<p>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}$</p>

<p>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$</p>

<p>The guards  are represented by expressions over the set of the variables $I$</p>

<p><strong>What I am  able to do :</strong> 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)</p>

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

<p>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</p>

<p>Any other ideas to do  tests  with Extended State Machines?
Thanks</p>

<p><strong>Edit 29/04/2016</strong></p>

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

<blockquote>
  <p><strong>Question 2:</strong> what are some well known random Extended State Machines for which every state is reachable.</p>
</blockquote>

<p>The purpose of my project is to test the efficiency of an algorithm </p>

CC BY-SA 3.0
2016-04-05T14:44:25.043Z
I don't understand how could I improve my question?
Elaqqad
CC BY-SA 4.0
2020-07-09T09:38:46.607Z
Are you still interested in this question, or did you find a solution to it? I am interested in a similar problem.
Konchog
CC BY-SA 4.0
2020-07-09T21:12:50.110Z
Sorry, It has been years ago, and if I remember correctly, I did not succeed in finding a solution
Elaqqad
<automata-theory><randomness>
How to generate Extended Finite State Machines Randomly with some properties?
Elaqqad
# How to generate Extended Finite State Machines Randomly with some properties?

(Asked by: username_0 on 2016-04-05)

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

**Tags:** automata-theory, randomness
> **Comments:**
> **username_0**: I don't understand how could I improve my question?  
> **username_1**: Are you still interested in this question, or did you find a solution to it? I am interested in a similar problem.  
> **username_0**: Sorry, It has been years ago, and if I remember correctly, I did not succeed in finding a solution  

---

## 1 answers

### Answer by username_2 on 2016-05-01. Score: 1

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.

> **Comments:**
> **username_0**: Thank you for your answer. What I am asking for is slightly different than "classical automaton" of finite state machines; It's Extended finite state machine and for this kind of automaton we can not directly test reachability because it's a difficult problem and it produces Space State Explosion. I am not demanding uniform distribution but only covering a large space and if there are some well known examples of EFSM I am very interested. Notice also that the number of states is expected to be not very large ( approximately 100)  
> **username_2**: I see. If reachability is a hard problem then indeed my proposed solution doesn't work.  
> **username_0**: Unfortunately yes, and what I am thinking of is using some well defined examples and parametrize them like logic circuits or counters. Another idea is to extract them from existing programs. But I don't really know if any of this will work  

---

