Finite-state machine

A finite-state machine (or finite automaton) is a model of computation for a primitive computer. It consists of several states and several transitions, and it can accept or reject a string it is given.

Example

Informally, we describe a finite-state machine using a state diagram:

The automaton is made up of states; in the picture there are three round states q₀, q₁ and q₂. Between these states there are transitions, which are the arrows. The automaton must also have a start state, which is the state q₀. The start state is often drawn with an arrow pointing into it that does not come from any state. The automaton also typically has an accepting state, which we draw with a double outline, so in the picture it is the state q₂.

An automaton built like this accepts certain strings. We feed strings into the automaton and it tries to accept them. If it accepts a string, the automaton answers YES; if it does not, it answers NO. Our automaton tries to accept strings made of the letters “a, b, c”, so we can try to accept the string “abbc”.

We start in the start state q₀ and the input is the string “abbc”. From here we follow the arrows.

We go through the string in the usual way, from left to right, so the first symbol we take is “a”. The arrow for the input “a” goes to the state q₁, so we move there and remove the symbol “a” from the string. The input is now the string “bbc”:

The arrow for the input “b” points back to the node q₁. Again we remove the first letter and the input is the string “bc”. Again we stay in the state q₁. Finally the input is the string “c”. From the state q₁ the arrow for the input “c” sends us to the state q₂.

We have used up all the letters of the input string and we are in the state q₂, which is an accepting state. So this finite automaton accepts the string “abbc”.

If we were not in an accepting state at the end, the automaton would not accept the string. Likewise, the automaton would not accept the string if we had nowhere to go in some state. For example, for the input “ab” we would get to the state q₁ and end up there – the automaton does not accept such a string. If we tested the string “aabbc”, we would again be out of luck, because from the state q₁ there is no arrow for the letter “a”.

A finite-state machine is therefore used to recognise a set of strings. In practice we could use an automaton, for example, to find out whether a given input string is a valid email address.

Definition of a finite automaton

We have to formalise the previous intuitive idea of what a finite automaton is, so that we can work with automata further and more easily.

We say that a finite (deterministic) automaton is a quintuple ⟨Q, Σ, δ, q₀, F⟩, where

• Q is a finite set of states,
• Σ (capital sigma) is the alphabet (a finite set of symbols/letters),
• δ: Q × Σ ⟶ Q is the transition function,
• q₀ ∈ Q is the start state,
• F ⊆ Q is the set of accepting states.

Returning to the previous automaton,

we can say that the set of states Q contains three states, Q = {q₀, q₁, q₂}. The alphabet Σ contains the letters from which we can build the strings that the automaton will accept or reject. Here it is probably the alphabet Σ= {a, b, c}, but it can also be any superset of it. The start state q₀ is the state q₀; nothing changes there. The set of accepting states in this automaton has only one state, F = {q₂}.

By the transition function we mean those three arrows with letters. If the notation δ: Q × Σ ⟶ Q confuses you, it just means that δ is a function (or perhaps better, a mapping) that takes two arguments: a state from Q and a letter from Σ. When the function is called, it returns a new state. We could define our transition function with a table like this:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

So if we call δ(q₁, c), we apply the third row and the function answers with the state q₂ – just like the diagram. If we are in the state q₁ and the input is the letter “c”, we get to the state q₂. Before we define formally what it means for an automaton to accept a string, we will use the intuitive understanding of this concept and look at some more examples.

More examples

1. Construct an automaton that works over the binary alphabet, that is Σ= {0, 1}, and accepts only strings that end with a one. For example, it accepts the strings 1, 01, 000001, 0101011.

   

   Our automaton has two states – the start state q₀ and the accepting state q₁. Whenever the input is the digit 1, we move to the accepting state q₁ and stay there. Conversely, if the input is the digit 0, we move to the non-accepting state q₀ and also stay there.

2. Construct an automaton over the binary alphabet that accepts only strings whose first letter is different from the last letter.

   

   In the very first step the automaton splits into two “sub-automata”. If the string starts with a zero, the automaton enters the left part and stays there; if it starts with a one, it moves to the right part. After that it is straightforward: if we are in the left part and the input is 1, we move to an accepting state and stay there. If the input is 0, we move to the state q₁, which is not accepting.

   Unlike the previous automata, this automaton has several accepting states, that is F = {q₃, q₄}.

3. Construct an automaton over the binary alphabet that accepts only strings that do not contain two zeros in a row.

   

   This automaton is interesting for two reasons. The first is that it accepts the empty string. We can try to feed the empty string into an automaton, and the automaton accepts it if the start state is also an accepting state, which is what happened with this automaton. Since the empty string is a string that does not contain two zeros in a row, that is correct. The other interesting thing is that all the states of this automaton are accepting. The only case in which the automaton would not accept a string is when there is no transition out of a state. That happens in the state q₁, which has no transition for 0, because then the string would contain two zeros in a row.

4. Construct an automaton over the alphabet {-,+,.,0,1,…,9} that accepts only strings that represent a number. That means either an integer such as 2, 548, 98263, or a decimal number such as 5584.48, 3.14, each also in a negative version with a minus sign (-2, -548, -3.14) and with an explicit plus sign (+2, +548, +3.14). At the same time we must be able to write the number 0.123 as just .123 (without the zero at the start), including with both signs. We introduce a helper notation: instead of listing ten transitions for the ten digits, we will use the symbol N.

   

5. Construct an automaton over the binary alphabet that accepts only strings of the form 0ⁿ1ⁿ, which means the strings start with a certain number of zeros, followed by the same number of ones. Examples of such strings are 0011, 00001111, 01.

   Such an automaton cannot be built, because we have no way to “remember” the number of zeros. We would have to create several “sub-automata”, as in the second example, but there would have to be infinitely many of these “sub-automata”, one for each value of n.

Formalisation of an automaton's computation

We have already formally defined a finite automaton itself. Next we must define what such an automaton actually does, that is, we define the computation of an automaton.

Configuration of an automaton: we say that a pair ⟨q, w⟩ ∈ Q × Σ^∗ is a configuration of the automaton, where q is the current state the automaton is in and w is the part of the string not yet read. Σ^∗ denotes the closure of the alphabet Σ, the set of all strings that can be built from the letters of the alphabet Σ. The closure also contains the empty string, which we denote ε.

If we have an automaton ⟨Q, Σ, δ, q₀, F⟩ and we are trying to accept a string w, the automaton is in the initial configuration ⟨q₀, w⟩. If we return to the automaton

and want to accept the string w = abbc, the initial configuration will be ⟨q₀, abbc⟩.

We define a computation step as a relation ↦ between the sets (Q × Σ^∗) × (Q × Σ^∗), that is, between configurations of the automaton. Let w = w₀w₁… w_n be the part of the string w not yet read. Then we say that the pairs ⟨q₁, w₀w₁… w_n⟩ and ⟨q₂, w₁… w_n⟩ are in the relation ↦, which we write as

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

if and only if δ(q₁, w₀) = q₂. Returning to our example, the initial configuration is ⟨q₀, abbc⟩. From the diagram we see that for the input “a” we can move to the state q₁. We can therefore write

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

because δ(q₀, a) = q₁. This is one computation step – we looked at which state we should go to for the given input (= the first letter of the part of the string not yet read), moved there and removed the first letter from the unread part of the string. This gave us a new configuration.

The reflexive and transitive closure of the computation step relation is denoted ↦ ^∗. So if we write K₁ ↦ ^∗ K₂, where K₁, K₂ are configurations of the automaton, it means that from the configuration K₁ we can get to the configuration K₂ through several computation steps, that is, there is a finite sequence of configurations such that:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

For example, in our automaton ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, because after two computation steps we are left with the string “bc” and we stay in the state q₁. That is, this sequence of configurations exists:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

The automaton accepts the string w if and only if there exists q_f ∈ F such that $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ This means that the automaton accepts the string w if and only if there is a sequence of computation steps such that at the end of the sequence we have read the whole string and are in an accepting state of the automaton. That we have read the whole string is expressed by the empty string ε in the place of the string in the configuration. Our automaton accepts the string abbc, because this sequence of configurations exists:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

and the state q₂ is an accepting state, q₂ ∈ F.

The language accepted by an automaton is the set of all strings the automaton accepts. We denote the language of an automaton A by L(A). Then L(A) ⊆ Σ^∗ and

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }|A\text{ accepts the string }w\}$$

A regular language is a language that is accepted by some finite automaton.

Two finite automata are equivalent if they accept the same language. That is, automata A₁ and A₂ are equivalent if L(A₁) = L(A₂).

Sources

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools