page_title: Noncommutative signal-flow graph
section_title: Finite Automata
hierarchical_section_title: Noncommutative signal-flow graph / Applications / Finite Automata
caption_attribution_description: English: automaton as signal-flow graph
context_page_description: In automata theory and control theory, branches of mathematics, theoretical computer science and systems engineering, a noncommutative signal-flow graph is a tool for modeling interconnected systems and state machines by mapping the edges of a directed graph to a ring or semiring.
  A single edge weight might represent an array of impulse responses of a complex system, or a character from an alphabet picked off the input tape of a finite automaton, while the graph might represent the flow of information or state transitions.
  As diverse as these applications are, they share much of the same underlying theory.
context_section_description: An important kind of noncommutative signal-flow graph is a finite state automaton over an alphabet .
  Serial connections correspond to the concatenation of words, which can be extended to subsets of the free monoid . For A, B 
  Parallel connections correspond to set union, which in this context is often written A+B.
  Finally, self-loops naturally correspond to the Kleene closure
  where  is the empty word. The similarity to the infinite geometric series
  is more than superficial, as expressions of this form serve as 'inversion' in this semiring.
  In this way, the subsets of  built of from finitely many of these three operations can be identified with the semiring of regular expressions.  Similarly, finite graphs whose edges are weighted by subsets of  can be identified with finite automata, though generally that theory starts with singleton sets as in the figure.
  This automaton is deterministic so we can unambiguously enumerate paths via words. Using the return loop method, path contributions are:
  path ab, has node factors (c*, ), yielding gain contribution
  path ada, has node factors (c*, c*, ), yielding gain contribution
  path ba, has node factors (c*, ), yielding gain contribution
  Thus the language accepted by this automaton (the gain of its signal-flow graph) is the sum of these terms
caption: Representation of a finite automaton as a (noncommutative) signal flow graph over a semiring.
exif: {}