# How to constrain a finite automaton (NFA and DFA) to a tree?

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,

• 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? Nov 24 '15 at 12:23
• @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! Nov 24 '15 at 14:26
• It seems like you are asking your automaton to be a trie: en.wikipedia.org/wiki/Trie Nov 24 '15 at 14:58
• 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. Nov 24 '15 at 16:24
• 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. Nov 25 '15 at 6:34

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$.

• 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)$ Nov 25 '15 at 8:14
• 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\})$. Nov 25 '15 at 11:30
• 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. Nov 25 '15 at 14:02
• @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$. Nov 27 '15 at 1:30
• 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)$. Nov 27 '15 at 6:33

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, which can:

• Use registers to record prior state

• Have arbitrary guard conditions associated with transitions.

• 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. Nov 24 '15 at 13:22
• 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. Nov 24 '15 at 13:31
• Your (set of) triples defines one concrete implementation for $\delta$, not $\delta$ in general. I'm interested in $\delta$ in general. Nov 24 '15 at 13:38
• 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. Nov 24 '15 at 13:42
• 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. Nov 24 '15 at 13:44

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.

• I really love this! Nov 24 '15 at 20:01
• Same mistake as I made: not every acyclic graph is a tree. Nov 26 '15 at 23:41

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

• 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. Nov 24 '15 at 14:48
• I would like to upvote this, but I don't have the reputation for it :( Nov 24 '15 at 16:25
• 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$) Nov 24 '15 at 20:52
• @KlausDraeger Thank you for the example! I hadn't understood the problem with this approach until then. Nov 25 '15 at 8:04
• True ... I'll fix or remove this answer when I have time. Nov 25 '15 at 10:59

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.

• Klaus Draeger remarks that this allows DAGs, Nov 27 '15 at 19:45