computability – What is the difference between the transition graph and the transition generalization graph in finite automata?

A transition graph (TG) is a set of the following elements:

  • A finite number of states, of which at least one is the starting state and (possibly) a set of final states.
  • A finite set of input letters () from which input strings are formed.
  • A finite set of transitions that shows how to go from one state to another by reading specified substrings of input letters, or even the null string ().

Meanwhile, a generalized transition graph (GTG) is a set of the following:

  • A finite number of states, of which at least one is the starting state and (possibly) a set of final states.
  • A finite set of input letters () from which input strings are formed.
  • Directed edges linking state pairs and tagged with regular expressions.

TGs and GTGs provide certain relaxations, that is, there may be more than one path for a certain chain or, otherwise, there may be no path for a certain chain. This property generates non-determinism and can also help differentiate TGs and GTGs from finite automata.