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,
How to constrain a finite automaton (NFA and DFA) to a tree?
graph theory;automata theory;tree;dfa;nfa
I think the easiest way of enforcing tree shape is the set of conditions$q_0$ is not in the image of $\delta$, $\delta$ is injective, and$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$.