Directional Graph Vs. State machine

Question

What is the difference between a Directed Graph and an end state machine in computer science / software development?

Answer 1

Directional graphs have many different applications in computer science, including, for example, software analysis and visualization. A directed graph is a pair: many nodes and many edges, that is, depending on the area of ​​the application, you can interpret the nodes and edges as you like. For example, in nodes of final states, nodes will be interpreted as states and edges as transitions. In social networks, nodes will represent people and territories - “each other” relationships between them.

In addition, the state machine is not limited to the directed graph itself. Finite state machines must also include the initial state and many final states. Finally, transitions in machines with a final state are associated with letters / words from the corresponding alphabet, which is not necessarily the case for oriented graphs in general.

Answer 2

Directional graphs are an ordered pair:

• set of nodes N and
• a binary relation through N

Labeled oriented graphs additionally contain annotations (marking functions) on nodes and edges. These are syntax constructs, i.e. The semantics associated with these annotations are not part of the labels themselves, but rather the interpretation that we will attribute to them, depending on the context. (see also multidigraph ).

The definition of a converter is discussed in this answer . This is a tuple that includes nodes, edges, input alphabet, output alphabet, set of initial states and marking functions: edges with input letters and states (Moore) or edges (Mealy) with output letters.

Thus, a directed graph is a data structure that does not correspond to the representation of the finite machine. On the contrary, a labeled directed graph is a data structure that can represent a finite state machine (although algebraically they are different structures, although it is more technical).

Note that a “set of initial states” can be equivalently described by a function that designates states as initial or not, so a digraph equipped with enough marking functions is enough to describe a final state machine.