automaton (original) (raw)
An automaton is a semiautomaton with two types of special states: starting states, and final states. Specifically, an automaton A is is a five-tuple (S,Σ,δ,I,F), where
- (S,Σ,δ) is a semiautomaton,
- a non-empty set I⊆S of starting states, and
- a set F⊆S of final states or terminating states.
A triple (s,a,t) is called a transition if t∈δ(s,a), and is written s⟶at. The set δ(s,a) may contain more than one element (or none at all), which is why an automaton is also said to be non-deterministic. If on the other hand δ(s,a) is a singleton for every (s,a), and I is a singleton, then A is said to be deterministic
. In a deterministic automaton, δ can be viewed as a function from S×Σ to S.
If S and Σ are both finite, then A is called a finite-state automaton, or FSA for short.
The state diagram
GA of a finite-state automaton A is constructed as if A is being treated as a semiautomaton. In addition
, a vertex corresponding to a starting state has an incoming arrow without a source, and a vertex corresponding to a final state has an outgoing arrow without a destination (alternatively, it may be represented by a double circle). This is illustrated in the following example:
Let A be given by S={σ,s,t}, where σ is the starting state, and t the final state, Σ={a,b}, with the transition function given by the following table
| Title | automaton |
|---|---|
| Canonical name | Automaton |
| Date of creation | 2013-03-22 12:26:34 |
| Last modified on | 2013-03-22 12:26:34 |
| Owner | CWoo (3771) |
| Last modified by | CWoo (3771) |
| Numerical id | 42 |
| Author | CWoo (3771) |
| Entry type | Definition |
| Classification | msc 03D05 |
| Classification | msc 68Q45 |
| Synonym | next-state function |
| Synonym | terminating state |
| Synonym | FSA |
| Synonym | start state |
| Synonym | recognizer |
| Related topic | DeterministicFiniteAutomaton |
| Related topic | NonDeterministicFiniteAutomaton |
| Related topic | PushdownAutomaton |
| Related topic | Semiautomaton |
| Defines | finite-state automaton |
| Defines | transition function |
| Defines | starting state |
| Defines | final state |
| Defines | configuration |
| Defines | acceptor |
| Defines | automata |
| Defines | deterministic automaton |
| \@unrecurse |