<p>I think the easiest way of enforcing tree shape is the set of conditions</p>

<ol>
<li>$q_0$ is not in the image of $\delta$, </li>
<li>$\delta$ is injective, and</li>
<li>$M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable.</li>
</ol>

<p>Then we can prove (by induction) that for any state $q$ there is a unique path from $q_0$ to $q$.</p>

CC BY-SA 3.0
2015-11-25T08:14:09.650Z
How would I notate the image of $\delta$? Would I write: $\forall q \in Q, \forall a \in \Sigma, q_0 \notin \delta^{-1}(q,a)$
Kate F
CC BY-SA 3.0
2015-11-25T11:30:40.813Z
Nearly: $\forall q\in Q,\forall a\in\Sigma,\delta(q,a)\neq q_0$. Alternatively, define the transition function to be $\delta:Q\times\Sigma\to(Q\setminus\{q_0\})$.
Klaus Draeger
CC BY-SA 3.0
2015-11-25T13:59:05.950Z
Thanks! Both those make sense. Meanwhile I think there's a problem with your set of conditions: Although you constrain $\delta$ to be injective, doesn't that permit transitions in both directions, back up the tree as well as down - e.g. from a leaf node to a parent?
Kate F
CC BY-SA 3.0
2015-11-25T14:02:21.340Z
That would mean that the affected state $q$ has two incoming transitions - one belonging to the path $q_0\to\dots\to q$, and the other from further down in the tree. This contradicts injectivity.
Klaus Draeger
CC BY-SA 3.0
2015-11-25T14:17:53.550Z
I see! So if I were to define this tree entirely with transitions in the other direction (all pointing towards $q_0$), then $\delta$ would need to not be injective; would it instead be "many to one"? And I think I would replace condition (1) with $\forall a \in \Sigma, \exists q \in Q\ (\delta(q, a) = q_0)$
Kate F
CC BY-SA 3.0
2015-11-27T01:30:46.987Z
@KateF As I understand this, condition (1) simply identifies the root of the tree, whereas (2,3) without (1) provide the tree shape. If you want to dispense with (1), start with (2,3), then take just the subtree rooted at $q_0$.
Lawrence
CC BY-SA 3.0
2015-11-27T06:33:13.030Z
For transitions towards $q_0$, you want the "reversed" versions of the conditions: (1) $\delta(q_0,a)$ undefined for all $a$; (2) For each other $q$, there is exactly one $a$ such that $\delta(q,a)$ is defined (i.e. a unique parent); (3) $M$ is connected, in this case meaning that for any $q_1,q_2$ there are words $w_1,w_2$ with $\delta(q_1,w_1)=\delta(q_2,w_2)$.
Klaus Draeger
CC BY-SA 3.0
2015-11-24T20:55:37.750Z
2015-11-24T20:55:37.750Z
Klaus Draeger
<p>Another idea, inspired by the pump lemma, would be to just say that there exists a maximum size N on words in the language, with N &lt; |Q|. if there was a cycle, then you could repeat the cycle indefinitely and have a word of arbitrary size ; if you can't, then there's no cycle and your automata is a tree.</p>

CC BY-SA 3.0
2015-11-24T20:01:29.457Z
I really love this!
Kate F
CC BY-SA 3.0
2015-11-26T23:41:12.910Z
Same mistake as I made: not every acyclic graph is a tree.
reinierpost
CC BY-SA 3.0
2015-11-24T19:55:53.373Z
2015-11-24T19:55:53.373Z
unautre
<p>Such a constraint cannot be expressed within (what is normally considered to be) a transition function for a DFA or NFA, where transitions are specified in terms of triples $(\operatorname{from-state},\operatorname{input-symbol},\operatorname{to-state})$. </p>

<p>Hence they are 'local' to the 'from' state, carrying no information about the path from prior states. Nothing can therefore prevent $\operatorname{to-state}$ pointing back to some previously-encountered state.</p>

<p>One possible alternative would be to use <a href="https://en.wikipedia.org/wiki/Augmented_transition_network" rel="nofollow">augmented transition networks</a>, which can:</p>

<ul>
<li><p>Use registers to record prior state</p></li>
<li><p>Have arbitrary guard conditions associated with transitions.</p></li>
</ul>

CC BY-SA 3.0
2015-11-24T13:22:34.507Z
I don't follow. Surely I could constrain the possible functions however I like? For example, I could write "where $\delta$ may only map to states which have an outgoing edge" or some other similarly arbitrary qualifier.  
  
I think the set of your triples (which are not present in my question) would be a state transition matrix, and that's one concrete implementation for the $\delta$ function. My question is about constraining all $\delta$ functions.
Kate F
CC BY-SA 3.0
2015-11-24T13:31:10.883Z
The notion of 'transition as local rule' is effectively part of the definition of DFA/NFA. Under these circumstances, the triple formulation uniquely defines the implementation.


Why do you need to encode this constraint in the transition function? If your interest is in generating constrained FSA, then you can just have the generating procedure obey the required constraint.


Of course, nothing prevents you from coming up with a more general formulation, it just wouldn't correspond to what is usually thought of as a DFA.
NietzscheanAI
CC BY-SA 3.0
2015-11-24T13:38:47.697Z
Your (set of) triples defines one concrete implementation for $\delta$, not $\delta$ in general. I'm interested in $\delta$ in general.
Kate F
CC BY-SA 3.0
2015-11-24T13:42:09.773Z
As defined above $\delta$ is a function of $Q$ and $\Sigma$, which are effectively sets of labels. It is not a function of the (potentially partially constructed) state of the FSA itself.
NietzscheanAI
CC BY-SA 3.0
2015-11-24T13:44:06.827Z
The very best you might be able to do is to try and encode the information you need to make a decision about valid/invalid target states into $Q$ and $\Sigma$ e.g. via Goedel numbering or some such scheme. It's not clear to me whether this is possible, but even if it was it seems a very roundabout method of achieving something that is much easier at the level of FSA generation.
NietzscheanAI
CC BY-SA 3.0
2015-11-24T13:57:35.153Z
I think we're talking about quite different things.
Kate F
CC BY-SA 3.0
2015-11-24T13:59:01.107Z
I'm talking about the definition given above, where $\delta$ cannot be some arbitrary function: it can only be defined in terms of the symbols of the alphabet and state indices. If you add some further context about why you want the constraint to be encoded within $\delta$ itself (as opposed to being imposed externally when the transition matrix is generated), it might be possible to suggest alternatives.
NietzscheanAI
CC BY-SA 3.0
2015-11-24T13:07:24.053Z
2015-11-24T13:46:24.457Z
2015-11-24T13:46:24.457Z
NietzscheanAI
<p>The easiest way I can think of is to define the constraint in terms of some ordering on the states.  For instance: say a $\delta$ is only valid if it respects some total ordering $&lt;$ on $Q$, i.e. only relates elements $p, q \in Q$ for which $p &lt; q$.</p>

<p>As the comments point out, that does not suffice: all DAGs meet this criterion, not just trees.</p>

<p>So instead, associate ordered <em>intervals</em> with states: say a $\delta$ is only valid if there exists a function $f: Q \rightarrow I\!\!N^2$ such that</p>

<ul>
<li>if $\delta$ relates elements $p, q \in Q$, then $f(q)$ is in $f(p)$</li>
<li>if $\delta$ relates elements $p, q_1$ and $p, q_2 \in Q$, then $f(q_1)$ and $f(q_2)$ are disjoint</li>
</ul>

<p>I believe this is only satisfied by trees or forests.
If you really want a tree, you also need to require connectedness: e.g.:</p>

<ul>
<li>only one element exists to which $\delta$ relates no elements</li>
</ul>

<p><em>I should really withdraw this answer until it comes with a proof ...</em></p>

CC BY-SA 3.0
2015-11-24T14:48:52.600Z
Couldn't an equivalent relation be expressed in terms of $\delta(\delta(q, a_1), a_2)$ rather than defining ordering between states? This way the ordering would be implicit in multiple applications.
Kate F
CC BY-SA 3.0
2015-11-24T16:25:44.057Z
I would like to upvote this, but I don't have the reputation for it :(
Kate F
CC BY-SA 3.0
2015-11-24T20:52:24.033Z
This condition actually allows DAGs, rather than just trees (if $q_0<q_1<q_2$, you can still have $\delta(q_0,a)=q_1,\delta(q_0,b)=q_2,\delta(q_1,a)=q_2$)
Klaus Draeger
CC BY-SA 3.0
2015-11-25T08:04:41.657Z
@KlausDraeger Thank you for the example! I hadn't understood the problem with this approach until then.
Kate F
CC BY-SA 3.0
2015-11-25T10:59:24.193Z
True ... I'll fix or remove this answer when I have time.
reinierpost
CC BY-SA 3.0
2015-11-25T13:47:34.773Z
See the comments of ThomasS and Klaus Draeger, which point out that to avoid DAGs the non-root states should have indegree 1 (the transition relation should be injective function) and the indegree of the root should be 0 (the root should not be in the image of the transition relation).
András Salamon
CC BY-SA 3.0
2015-11-26T19:48:52.537Z
True, but that should be a separate answer, I think.
reinierpost
CC BY-SA 3.0
2015-11-24T14:42:31.453Z
2015-11-29T19:34:16.533Z
2015-11-29T19:34:16.533Z
reinierpost
<p>With much help from @unautre (quelqun_dautre on freenode's ##cs):</p>

<blockquote>
  <p>There exists a total order relation on Q, where $q_0$
  (initial state of the automata) is the minimum, and
  for all x, y in Q, a in sigma, y = delta(x, a) => x &lt; y<br>
  ($\implies$ is implication)</p>
</blockquote>

<p>Where $y = \delta(x,a)$ would be for a DFA, but would be $y \in \delta(x,a)$ for an NFA, since $\delta$ would produce a <em>set</em> of states for any given symbol.</p>

<p>In maths notation:
$$
\forall x, y \in Q, \forall a \in \Sigma, y \in \delta(x, a) \implies x
&lt; y
$$</p>

<p>I would possibly write $q_1$ and $q_2$ for $x$ and $y$, except I think that might be confusing with respect to $q_0$, the start state.</p>

CC BY-SA 3.0
2015-11-27T19:45:44.107Z
Klaus Draeger remarks that this allows DAGs,
reinierpost
CC BY-SA 3.0
2015-11-24T19:51:09.140Z
2015-11-24T19:51:09.140Z
Kate F
<p>I have a finite automaton by the standard model Hopcroft &amp; Ullman define:
$$
M = (Q, \Sigma, \delta, q_0, F)
$$</p>

<p>Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such that $\delta(q, a)$ is a state for each state $q \in Q$, the set of all states, and input symbol $a \in \Sigma$, the alphabet. That allows for $\delta$ to map to any element of $Q$. So that's a graph, although it's not described using the usual $G = (V, E)$ notation.</p>

<p>Without specifying any particular definition for $\delta$, I'd like to be able to write the constraint that $\delta$ may only define transitions which form a tree. How can that be expressed?</p>

<p>My thought is that I might say that $\delta$ must be recursive somehow (to give a tree shape), but I'm not sure how to go about that.</p>

<p>Thank you,</p>

CC BY-SA 3.0
2015-11-24T12:23:52.030Z
A tree is a graph containing no cycles as subgraphs.  So you could forbid a cycle of transitions.  But this then seems closer to a decision tree than an automaton?
András Salamon
CC BY-SA 3.0
2015-11-24T12:26:55.390Z
@AndrásSalamon Do you know how I might express a cycle in terms of the $\delta$ transition function? By induction, perhaps?
Kate F
CC BY-SA 3.0
2015-11-24T14:10:16.200Z
Graph constructions don't readily lend themselves to induction (since there is no natural ordering on nodes or edges). Below is a paper which made some progress in this area by highlighting a designated vertex. This might possibly serve as a starting point for your desired induction scheme:
https://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf
NietzscheanAI
CC BY-SA 3.0
2015-11-24T14:16:53.363Z
I'm very interested in DFA's whose state diagrams are shaped like tree's (excluding the dead state) or other graph theoretic structures.  What was your motivation for asking this question?  :)
Michael Wehar
CC BY-SA 3.0
2015-11-24T14:26:56.547Z
@MichaelWehar I've a lexical analyser which uses a trie for its internal representation, and I'd like to model that. I'm also gluing together chunks of NFA into a tree (much as one might construct NFA fragments from a regular expression). If you're interested in that sort of thing, perhaps we could chat about it!
Kate F
CC BY-SA 3.0
2015-11-24T14:58:20.203Z
It seems like you are asking your automaton to be a trie: https://en.wikipedia.org/wiki/Trie
Sylvain
CC BY-SA 3.0
2015-11-24T15:01:06.863Z
@Sylvain It would be a trie, yes.
Kate F
CC BY-SA 3.0
2015-11-24T16:15:42.727Z
@KateF Cool!  I'm interested.  Feel free to shoot me an email and we can set-up a time to talk.  :)
Michael Wehar
CC BY-SA 3.0
2015-11-24T16:21:44.750Z
@Sylvain It's worth noting that the some notions of tree-shaped DFA allow for the merging of branches.  For example, a branch for the word "care" and a branch for the word "cane" could possibly be merged into a single branch ca{n,r}e where edges are labeled with sets of characters.  Is this a common practice for tries?
Michael Wehar
CC BY-SA 3.0
2015-11-24T16:24:12.350Z
Indeed you could merge the tails of the branches of a trie - as when minimizing a DFA, for example. But I'm not asking about that with my question here.
Kate F
CC BY-SA 3.0
2015-11-24T20:20:16.233Z
@MichaelWehar I'm told this merging of suffixes is more properly termed "compression".
Kate F
CC BY-SA 3.0
2015-11-24T20:30:00.320Z
I must be missing something - is the condition you are looking for not simply that $\delta$ is injective?
Klaus Draeger
CC BY-SA 3.0
2015-11-24T20:36:19.550Z
@KlausDraeger Per my understanding, that's not enough - because a cycle may be longer than one state transitioning to itself. $q_0 \rightarrow q_1 \rightarrow q_0$
Kate F
CC BY-SA 3.0
2015-11-24T20:39:04.323Z
Correct, you need the additional condition that $q_0$ is not in the image of $\delta$. That should do it, though.
Klaus Draeger
CC BY-SA 3.0
2015-11-24T20:42:10.473Z
@KlausDraeger I don't know enough to confirm that. But if you think it's suitable, could you write it as an answer so I can see how you'd express it, please?
Kate F
CC BY-SA 3.0
2015-11-25T06:34:41.247Z
Well, a DFA in the strict sense (with delta being a function) can not yield a tree: from each vertex there is an outgoing edge and, since the vertex set is finite, there must be cycles.
If you allow partial functions, I'd suggest to combine the order idea of reinierpost with an additional condition. That is,
- each state should only have edges to a larger state wrt <, and
- each state should have in-degree 1. Besides the root, which has 0.
Thomas S
CC BY-SA 3.0
2015-11-25T17:52:25.343Z
@KateF Yep.  Hmm, well it seems there are a few different ways to compress tries.  I wonder if there is a unique name (other than compressed) for tries with merged branches.
Michael Wehar
CC BY-SA 3.0
2015-11-25T17:53:46.257Z
@ThomasS Is it appropriate to say that ignoring the dead state, it forms a tree directed from root to leaves?
Michael Wehar
CC BY-SA 3.0
2015-11-25T18:32:42.913Z
Sure, that makes sense.
Thomas S
CC BY-SA 3.0
2015-12-01T07:28:10.233Z
In what sense is this an actual question? If you want to constrain the state-transition graph to be a tree, why not just say that it is a tree?
David Eppstein
CC BY-SA 3.0
2015-12-01T14:23:14.103Z
@DavidEppstein My question is how that can be said, formally, in terms of predicates on M.
Kate F
<graph-theory><automata-theory><tree><dfa><nfa>
How to constrain a finite automaton (NFA and DFA) to a tree?
Kate F
# How to constrain a finite automaton (NFA and DFA) to a tree?

(Asked by: username_0 on 2015-11-24)

I have a finite automaton by the standard model Hopcroft & Ullman define:
$$
M = (Q, \Sigma, \delta, q\_0, F)
$$

Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such that $\delta(q, a)$ is a state for each state $q \in Q$, the set of all states, and input symbol $a \in \Sigma$, the alphabet. That allows for $\delta$ to map to any element of $Q$. So that's a graph, although it's not described using the usual $G = (V, E)$ notation.

Without specifying any particular definition for $\delta$, I'd like to be able to write the constraint that $\delta$ may only define transitions which form a tree. How can that be expressed?

My thought is that I might say that $\delta$ must be recursive somehow (to give a tree shape), but I'm not sure how to go about that.

Thank you,

**Tags:** graph-theory, automata-theory, tree, dfa, nfa
> **Comments:**
> **username_1**: A tree is a graph containing no cycles as subgraphs.  So you could forbid a cycle of transitions.  But this then seems closer to a decision tree than an automaton?  
> **username_0**: @AndrásSalamon Do you know how I might express a cycle in terms of the $\delta$ transition function? By induction, perhaps?  
> **username_2**: Graph constructions don't readily lend themselves to induction (since there is no natural ordering on nodes or edges). Below is a paper which made some progress in this area by highlighting a designated vertex. This might possibly serve as a starting point for your desired induction scheme: https://web.engr.oregonstate.edu/~erwig/papers/InductiveGraphs_JFP01.pdf  
> **username_3**: I'm very interested in DFA's whose state diagrams are shaped like tree's (excluding the dead state) or other graph theoretic structures.  What was your motivation for asking this question?  :)  
> **username_0**: @MichaelWehar I've a lexical analyser which uses a trie for its internal representation, and I'd like to model that. I'm also gluing together chunks of NFA into a tree (much as one might construct NFA fragments from a regular expression). If you're interested in that sort of thing, perhaps we could chat about it!  
> **username_4**: It seems like you are asking your automaton to be a trie: https://en.wikipedia.org/wiki/Trie  
> **username_0**: @Sylvain It would be a trie, yes.  
> **username_3**: @KateF Cool!  I'm interested.  Feel free to shoot me an email and we can set-up a time to talk.  :)  
> **username_3**: @Sylvain It's worth noting that the some notions of tree-shaped DFA allow for the merging of branches.  For example, a branch for the word "care" and a branch for the word "cane" could possibly be merged into a single branch ca{n,r}e where edges are labeled with sets of characters.  Is this a common practice for tries?  
> **username_0**: Indeed you could merge the tails of the branches of a trie - as when minimizing a DFA, for example. But I'm not asking about that with my question here.  
> **username_0**: @MichaelWehar I'm told this merging of suffixes is more properly termed "compression".  
> **username_5**: I must be missing something - is the condition you are looking for not simply that $\delta$ is injective?  
> **username_0**: @KlausDraeger Per my understanding, that's not enough - because a cycle may be longer than one state transitioning to itself. $q_0 \rightarrow q_1 \rightarrow q_0$  
> **username_5**: Correct, you need the additional condition that $q_0$ is not in the image of $\delta$. That should do it, though.  
> **username_0**: @KlausDraeger I don't know enough to confirm that. But if you think it's suitable, could you write it as an answer so I can see how you'd express it, please?  
> **username_6**: Well, a DFA in the strict sense (with delta being a function) can not yield a tree: from each vertex there is an outgoing edge and, since the vertex set is finite, there must be cycles. If you allow partial functions, I'd suggest to combine the order idea of reinierpost with an additional condition. That is, - each state should only have edges to a larger state wrt <, and - each state should have in-degree 1. Besides the root, which has 0.  
> **username_3**: @KateF Yep.  Hmm, well it seems there are a few different ways to compress tries.  I wonder if there is a unique name (other than compressed) for tries with merged branches.  
> **username_3**: @ThomasS Is it appropriate to say that ignoring the dead state, it forms a tree directed from root to leaves?  
> **username_6**: Sure, that makes sense.  
> **username_7**: In what sense is this an actual question? If you want to constrain the state-transition graph to be a tree, why not just say that it is a tree?  
> **username_0**: @DavidEppstein My question is how that can be said, formally, in terms of predicates on M.  

---

## 5 answers

### Answer by username_5 on 2015-11-24. Score: 3 | Accepted answer

I think the easiest way of enforcing tree shape is the set of conditions

1. $q\_0$ is not in the image of $\delta$,
2. $\delta$ is injective, and
3. $M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable.

Then we can prove (by induction) that for any state $q$ there is a unique path from $q\_0$ to $q$.

> **Comments:**
> **username_0**: How would I notate the image of $\delta$? Would I write: $\forall q \in Q, \forall a \in \Sigma, q_0 \notin \delta^{-1}(q,a)$  
> **username_5**: Nearly: $\forall q\in Q,\forall a\in\Sigma,\delta(q,a)\neq q_0$. Alternatively, define the transition function to be $\delta:Q\times\Sigma\to(Q\setminus\{q_0\})$.  
> **username_0**: Thanks! Both those make sense. Meanwhile I think there's a problem with your set of conditions: Although you constrain $\delta$ to be injective, doesn't that permit transitions in both directions, back up the tree as well as down - e.g. from a leaf node to a parent?  
> **username_5**: That would mean that the affected state $q$ has two incoming transitions - one belonging to the path $q_0\to\dots\to q$, and the other from further down in the tree. This contradicts injectivity.  
> **username_0**: I see! So if I were to define this tree entirely with transitions in the other direction (all pointing towards $q_0$), then $\delta$ would need to not be injective; would it instead be "many to one"? And I think I would replace condition (1) with $\forall a \in \Sigma, \exists q \in Q\ (\delta(q, a) = q_0)$  
> **username_8**: @KateF As I understand this, condition (1) simply identifies the root of the tree, whereas (2,3) without (1) provide the tree shape. If you want to dispense with (1), start with (2,3), then take just the subtree rooted at $q_0$.  
> **username_5**: For transitions towards $q_0$, you want the "reversed" versions of the conditions: (1) $\delta(q_0,a)$ undefined for all $a$; (2) For each other $q$, there is exactly one $a$ such that $\delta(q,a)$ is defined (i.e. a unique parent); (3) $M$ is connected, in this case meaning that for any $q_1,q_2$ there are words $w_1,w_2$ with $\delta(q_1,w_1)=\delta(q_2,w_2)$.  

---

### Answer by username_9 on 2015-11-24. Score: 1

Another idea, inspired by the pump lemma, would be to just say that there exists a maximum size N on words in the language, with N < |Q|. if there was a cycle, then you could repeat the cycle indefinitely and have a word of arbitrary size ; if you can't, then there's no cycle and your automata is a tree.

> **Comments:**
> **username_0**: I really love this!  
> **username_10**: Same mistake as I made: not every acyclic graph is a tree.  

---

### Answer by username_2 on 2015-11-24. Score: 1

Such a constraint cannot be expressed within (what is normally considered to be) a transition function for a DFA or NFA, where transitions are specified in terms of triples $(\operatorname{from-state},\operatorname{input-symbol},\operatorname{to-state})$.

Hence they are 'local' to the 'from' state, carrying no information about the path from prior states. Nothing can therefore prevent $\operatorname{to-state}$ pointing back to some previously-encountered state.

One possible alternative would be to use [augmented transition networks](https://en.wikipedia.org/wiki/Augmented_transition_network), which can:

* Use registers to record prior state
* Have arbitrary guard conditions associated with transitions.

> **Comments:**
> **username_0**: I don't follow. Surely I could constrain the possible functions however I like? For example, I could write "where $\delta$ may only map to states which have an outgoing edge" or some other similarly arbitrary qualifier.      I think the set of your triples (which are not present in my question) would be a state transition matrix, and that's one concrete implementation for the $\delta$ function. My question is about constraining all $\delta$ functions.  
> **username_2**: The notion of 'transition as local rule' is effectively part of the definition of DFA/NFA. Under these circumstances, the triple formulation uniquely defines the implementation.   Why do you need to encode this constraint in the transition function? If your interest is in generating constrained FSA, then you can just have the generating procedure obey the required constraint.   Of course, nothing prevents you from coming up with a more general formulation, it just wouldn't correspond to what is usually thought of as a DFA.  
> **username_0**: Your (set of) triples defines one concrete implementation for $\delta$, not $\delta$ in general. I'm interested in $\delta$ in general.  
> **username_2**: As defined above $\delta$ is a function of $Q$ and $\Sigma$, which are effectively sets of labels. It is not a function of the (potentially partially constructed) state of the FSA itself.  
> **username_2**: The very best you might be able to do is to try and encode the information you need to make a decision about valid/invalid target states into $Q$ and $\Sigma$ e.g. via Goedel numbering or some such scheme. It's not clear to me whether this is possible, but even if it was it seems a very roundabout method of achieving something that is much easier at the level of FSA generation.  
> **username_0**: I think we're talking about quite different things.  
> **username_2**: I'm talking about the definition given above, where $\delta$ cannot be some arbitrary function: it can only be defined in terms of the symbols of the alphabet and state indices. If you add some further context about why you want the constraint to be encoded within $\delta$ itself (as opposed to being imposed externally when the transition matrix is generated), it might be possible to suggest alternatives.  

---

### Answer by username_10 on 2015-11-24. Score: 1

The easiest way I can think of is to define the constraint in terms of some ordering on the states. For instance: say a $\delta$ is only valid if it respects some total ordering $<$ on $Q$, i.e. only relates elements $p, q \in Q$ for which $p < q$.

As the comments point out, that does not suffice: all DAGs meet this criterion, not just trees.

So instead, associate ordered *intervals* with states: say a $\delta$ is only valid if there exists a function $f: Q \rightarrow I\!\!N^2$ such that

* if $\delta$ relates elements $p, q \in Q$, then $f(q)$ is in $f(p)$
* if $\delta$ relates elements $p, q\_1$ and $p, q\_2 \in Q$, then $f(q\_1)$ and $f(q\_2)$ are disjoint

I believe this is only satisfied by trees or forests.
If you really want a tree, you also need to require connectedness: e.g.:

* only one element exists to which $\delta$ relates no elements

*I should really withdraw this answer until it comes with a proof ...*

> **Comments:**
> **username_0**: Couldn't an equivalent relation be expressed in terms of $\delta(\delta(q, a_1), a_2)$ rather than defining ordering between states? This way the ordering would be implicit in multiple applications.  
> **username_0**: I would like to upvote this, but I don't have the reputation for it :(  
> **username_5**: This condition actually allows DAGs, rather than just trees (if $q_0<q_1<q_2$, you can still have $\delta(q_0,a)=q_1,\delta(q_0,b)=q_2,\delta(q_1,a)=q_2$)  
> **username_0**: @KlausDraeger Thank you for the example! I hadn't understood the problem with this approach until then.  
> **username_10**: True ... I'll fix or remove this answer when I have time.  
> **username_1**: See the comments of ThomasS and Klaus Draeger, which point out that to avoid DAGs the non-root states should have indegree 1 (the transition relation should be injective function) and the indegree of the root should be 0 (the root should not be in the image of the transition relation).  
> **username_10**: True, but that should be a separate answer, I think.  

---

### Answer by username_0 on 2015-11-24. Score: -1

With much help from @unautre (quelqun\_dautre on freenode's ##cs):

> There exists a total order relation on Q, where $q\_0$
> (initial state of the automata) is the minimum, and
> for all x, y in Q, a in sigma, y = delta(x, a) => x < y  
> ($\implies$ is implication)

Where $y = \delta(x,a)$ would be for a DFA, but would be $y \in \delta(x,a)$ for an NFA, since $\delta$ would produce a *set* of states for any given symbol.

In maths notation:
$$
\forall x, y \in Q, \forall a \in \Sigma, y \in \delta(x, a) \implies x
< y
$$

I would possibly write $q\_1$ and $q\_2$ for $x$ and $y$, except I think that might be confusing with respect to $q\_0$, the start state.

> **Comments:**
> **username_10**: Klaus Draeger remarks that this allows DAGs,  

---

