print · source · login   

Finite Automata

A finite automaton is a finite state machine in which certain states are identified as accepting. The language accepted by a finite automataton consists of the labels of all the paths from an initial state to an accepting state.

Formal definition



In the DOT format, accepting states are denoted by a double circle, following the standard convention. For instance, the dot encoding for the Toy DFA benchmark is:

  digraph g {
  __start0 [label="" shape="none"]
  s1 [shape="doublecircle" label="s1"]
  s2 [shape="circle" label="s2"]
  __start0 -> s1
  s1 -> s2[label="0"]
  s1 -> s1[label="1"]
  s2 -> s1[label="0"]
  s2 -> s2[label="1"]