The Finite state machine reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Finite state machine

In computer science, a finite-state machine (FSM) or finite-state automaton (FSA) is an abstract machine that has only a finite, constant amount of memory. The internal statess of the machine carry no further structure. This kind of model is very widely used in the study of computation and languages.

Table of contents

1 Overview 2 Formal definitions 2.1 Deterministic finite automaton 2.2 Non-deterministic finite automaton 2.3 Generalized non-deterministic finite automaton 3 Examples of FSMs 3.4 Deterministic finite state machine 4 Optimization and Canonicalisation 5 Computational power 6 Representation 7 Implementation 8 Tools 9 See also 10 References 11 External links

Overview

It can be conceptualised as a directed graph. There are a finitely many states, and each state has transitions to states. There is an input string that determines which transition is followed (some transitions may be from a state to itself). Finite state machines are studied in automata theory, a subfield of theoretical computer science.

There are several types of finite state machines:

Acceptors produce a "yes" or "no" answer to the input; they either accept the input or do not. Recognizers categorise the input. Transducers are used to generate an output from a given input.

Finite automata may operate on languages of finite words (the standard case), infinite words (Rabin automata, Büchi automata), or various types of trees (tree automata), to name the most important cases.

A further distinction is between deterministic and non-deterministic automata. In deterministic automata, for each state there is at most one transition for each possible input. In non-deterministic automata, there can be more than one transition from a given state for a given possible input. Non-deterministic automata are usually implemented by converting them to deterministic automata—in the worst case, the generated deterministic automaton is exponentially bigger than the non-deterministic automaton (although it can usually be substantially optimised).

The standard acceptance condition for non-deterministic automata requires that some computation accepts the input. Alternating automata also provide a dual notion, where for acceptance all non-deterministic computations must accept.

Apart from theory, finite state machines occur also in hardware circuits, where the input, the state and the output are bit vectors of fixed size (Moore machines and Mealy machines).

Mealy machines have actions (outputs) associated with transitions and Moore machines have actions associated with states.

Formal definitions

Deterministic finite automaton

Formally, a deterministic finite automaton (DFA) is a 5-tuple: (S, Σ, T, s, A)

• a finite set called the alphabet (Σ)
• a finite set of states (S)
• a transition function (T : S × Σ → S).
• a start state (s ∈ S)
• a set of accept states (A ⊆ S)

The machine starts in the start state and reads in a string of symbols from its alphabet. It uses the transition function T to determine the next state using the current state and the symbol just read. If, when it has finished reading, it is in an accepting state, it is said to accept the string, otherwise it is said to reject the string. The set of strings it accepts form a language, which is the language the DFA recognises.

Formally, the definition of computation of a finite automata is given. Let M = (S, Σ, T, s, A) be a finite automata, and X = x₁x₂ ... x_n be a string over the alphabet Σ. M accepts the string X if a sequence of states, r₀,r₁, ..., r_n, exists in S with the following conditions:

1. r₀ = s
2. T(r_i, x_i+1) = r_i+1, for i = 0, ..., n-1
3. r_n ⊆ A.

Condition 1 says that the machine starts in the start state, s. The second condition says that given each character of X, the machine will transition from state to state as ruled by the transition function, T. The last condition says that the machine accepts if the last input of X causes the machine to be in one of the accepting states.

Non-deterministic finite automaton

A non-deterministic finite automaton (NFA) is a 5-tuple: (S, Σ, T, s, A)

• a finite set of alphabet (Σ)
• a finite set of states (S)
• a transition function (T : S × (Σ ∪{ε}) → P(S)).
• a start state (s ∈ S)
• a set of accept states (A ⊆ S)

Where P(S) is the power set of S and ε is the empty string.

The machine starts in the start state and reads in a string of symbols from its alphabet. It uses the transition relation T to determine the next state(s) using the current state and the symbol just read or the empty string. If, when it has finished reading, it is in an accepting state, it is said to accept the string, otherwise it is said to reject the string. The set of strings it accepts form a language, which is the language the NFA recognises.

Every NFA has an equivalent DFA. Therefore it is possible to convert and existing NFA to DFA for the purpose of implementing a simpler machine.

Generalized non-deterministic finite automaton

A generalized non-deterministic finite automaton (GNFA) is a 5-tuple: (S, Σ, T, s, a)

• S is a finite set of states
• Σ is a finite set of symbols
• T : (S -{a}) × (S - {s}) → R
• s ∈ S is the start state
• a ∈ S is the accept state

Where R is the collection of all regular expressions over the alphabet Σ.

A DFA or NFA can easily be converted into a GNFA and then the GNFA can be easily converted into a regular expression by reducing the number of states until S = {s, a}.

Examples of FSMs

Deterministic finite state machine

The following example explains a deterministic finite state machine (M) with a binary alphabet, which determines if the input contains an even number of 0s.

M = (S, Σ, T, s, A)

• Σ = {0, 1}
• S = {S₁, S₂}
• s = S₁
• A = {S₁}
• The transition function T is visualised by the directed graph shown on the right, and defined as follows:
  • T(S₁, 0) = S₂
  • T(S₁, 1) = S₁
  • T(S₂, 0) = S₁
  • T(S₂, 1) = S₂

Simply put, the state S₁ represents that there has been an even number of 0s in the input so far, while S₂ signifies an odd number. A 1 in the input does not change the state of the automaton. When the input ends, the state will show whether the input contained an even number of 0s or not.

Optimization and Canonicalisation

The problem of optimizing an FSM (finding the machine with the least number of states that performs the same function) is decidable, unlike the same problem for more computationally powerful machines. Furthermore, it is possible to construct a canonical version of any FSM, in order to test for equality. Both of these problems can be solved using a colouring algorithm.

Computational power

FSMs can only recognize regular languages, and hence they are less computationally powerful than Turing machines - there are decidable problems that are not computable using a FSM.

For each non-deterministic FSM a deterministic FSM of equal computational power can be constructed with an algorithm.

Representation

A FSM may be represented using a state transition table or a state diagram. This is a diagram consisting of circles to represent states and directed line segments to represent transitions between those states.

Implementation

A finite state machine can be implemented in software with a state transition matrix.

1. in some cases a sparse matrix implemented with linked lists or
2. a huge switch-statement for detecting the internal state and then individual switch statements for decoding the input symbol

In hardware a FSM may be built from a programmable logic device.

Tools

1. AT&T FSM Library™
2. AutoFSM
3. Bandera
4. Covered
5. Exorciser
6. Finite State Kernel Creator
7. Finite State Machine Editor
8. Finite State Machine Explorer
9. FSMGenerator
10. jrexx-Lab
11. Kara
12. Nunni FSM Generator
13. Petrify
14. Qfsm
15. Ragel
16. WhatOS

See also

• Petri net
• Simulation
• State chart
• Marvin Minsky
• Automata analyzer
• Coverage analysis
• Transition system
• Protocol development

References

• Tiziano Villa: Synthesis of Finite State Machines: Functional Optimization, Kluwer Academic Publishers, ISBN 0792398424
• Tiziano Villa: Synthesis of Finite State Machines: Logic Optimization, Kluwer Academic Publishers, ISBN 0792398920

External links

• Description from the Free On-Line Dictionary of Computing
• Citations from CiteSeer

This is the "Finite state machine" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.