Example FSA
finite state automaton Model {
S [initial] -- a ----> T [final]
T -- a;b --> S
}
Syntax FSA
Finite State Automata are a graph-like structure and the discussion about syntax of graphs applies. The syntax of a finite state automaton always starts with finite state automaton <name> {. It ends with a closing curly bracket }. The core of the description of the FSA is in the form of transitions S -- a --> T. Transitions are labelled with symbols from the alphabet of the FSA (a in the example). A transition without a symbol represents an $\epsilon$ transition. A transition can be labelled with multiple symbols separated by commas, for example S -- a, b, # --> T. This is a short-hand notation for a transition for each of the symbols. In this case, # can be used for an $\epsilon$ transition.
Symbol names are combinations of letters, numbers and the underscore character _ that start with a letter. Additionally, arbitrary symbol names can be written by enclosing the name with single or double quotation marks.
State names follow the same requirements, but have the additional possibility of using tuple-like (such as (S,T)) or set-like (such as {S,t}) notation. These can also be mixed arbitrarily, recursively, so that ({A,B},{X,Y}) is also a valid state name. It is important to note that in the set-like notation, state names are still compared literally {A,B} is not the same as {B,A}
States can have different annotations to denote if the state is an initial state or a final (accepting) state. For example, S [initial; final] denotes that S is both an initial state and a final state. Annotations are separated by semicolon ;. final can be abbreviated to f. initial can be abbreviated to i and the enclosing square brackets are optional, so S f;i is also valid. Annotations do not need to be repeated every time a state is mentioned, but can be added anywhere.
Generalized acceptance conditions can be specified by adding a label after the final label, e.g., S final[A], T final[A,B] defines two acceptance sets A = {S,T} and B = {T}. If the model has additional final states that are not labelled with a named acceptance set, then those states together also form a separate acceptance set.
Occasionally there is a need to add states to an FSA that have no adjacent transitions. In that case, unconnected states can be added by adding the keyword states at the end of the description followed by a list of states (possibly including annotations), such as in the following model.
finite state automaton A {
S --> T
states U V W f;i
}