Finite automaton

A finite automaton (English: finite state machine or finite automaton) is a computational model of a primitive computer that consists of several states and several transitions, and that can accept or reject a passed word.

Example

We informally describe a finite automaton using a state diagram that describes the finite automaton:

The automaton is made up of states, in the figure there are three round states q₀, q₁ and q₂. Between these states there are transitions, these are the arrows. Furthermore, there must be an initial state in the automaton, that is the state q₀. The initial state is often shown by pointing an arrow to it, which does not come from any state. Then there is typically a final state in the automaton, this is shown by a double line, so in the picture it is the state q₂.

The automaton constructed in this way receives some words. So we put some words into the automaton, the automaton tries to accept these words. If it accepts them, the automaton answers YES, if it does not accept them, it answers NO. Our automaton tries to accept words that consist of the letters "a, b, c", so we can try to accept the word "abbc".

We start in the initial state q₀ and the input is the word "abbc". Next, we follow the arrow keys.

We'll go through the word classically from left to right, that is, we'll take the symbol "a" first. The arrow for input "a" goes to the state q₁, so we go there and remove the symbol "a" from the word. In the input we have the word "bbc":

The arrow for input "b" goes back to node q₁. Again, we remove the first letter and have the word "bc" as input. Again, we remain in the q₁ state. Finally, we have the word "c" on the input. From the q₁ state, the arrow for input "c" sends us to the q₂ state.

We have already used up all the letters from the input word and are in the state q₂, which is the end state. This finite automaton thus accepts the word "abbc".

If we were not in the receiving state at the end, the automaton would not accept the word. Similarly, the automaton would not accept the word if we were in some state with nowhere to go. For example, to enter "ab", we would be in the q₁ state and we would end up there - the automaton does not accept that word. If we tested the word "aabbc", we would be out of luck again because there is no arrow leading from the q₁ state for the letter "a".

So the final automaton is used to recognize some set of words. In practice, we could use the automaton, for example, to determine whether a given input word is a valid email.

Definition of a finite automaton

We need to formalize the previous intuitive notion of what a finite automaton is in order to work further and better with automata.

We will say that a finite (deterministic) automaton is a quintuple $\left<Q, \Sigma, \delta, q_0, F\right>$, where

• Q is a finite set of states,
• $\Sigma$ (big sigma) is an alphabet (finite set of symbols/letters),
• $\delta: Q \times \Sigma\longrightarrow Q$ is the transition function,
• q₀ ∈ Q is the initial state,
• F ⊆ Q is the set of final (receiving) states.

Returning to the previous automaton,

we can say that there are three states in the set of states Q Q = {q₀, q₁, q₂} . The alphabet $\Sigma$ contains letters from which we can compose words that the automaton will then accept or reject. Here, it is likely to be the alphabet $\Sigma=\left\{a, b, c\right\}$, but it can be any superset. The initial state of q₀ is the state of q₀, nothing changes that. The set of end states has only one state in this automaton F = {q₂}.

The transition function is then the three arrows with letters. If you're confused by the $\delta: Q \times \Sigma\longrightarrow Q$ marking , it just means that δ is a function (perhaps better a view) that takes two parameters: the state from Q and the letter from $\Sigma$. When the function is called, it returns a new state. We could define our transition function with a table as follows:

$$ \begin{array}{cc|c} Q&\Sigma&\rightarrow Q\\\hline 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 line and the function responds with the state q₂ - just like the diagram. If we are in the state q₁ and the input is the letter "c", we get the state q₂. Before we formally define what it means for an automaton to accept a word, let's use our intuitive understanding of this concept to show some more examples.

Other examples

1. Create an automaton that operates over a binary alphabet, i.e., $\Sigma=\left\{0,1\right\}$, and only accepts words that end in one. For example, it accepts the words 1, 01, 000001, 0101011.

   

   Our automaton has two states - the initial q₀ and the final q₁. Whenever we have the digit 1 as input, we go to the ending state q₁ and stay in it. Conversely, if the input is a digit 0, we go to the non-terminal state q₀ and stay in that state as well.

2. Construct an automaton over a binary alphabet that accepts only words whose starting letter is different from the ending letter.

   

   The automaton splits into two "sub-automata" in the very first step. If the word 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. Then it's classic, if we're in the left part and there's a 1 in the input, it moves to the end state and stays there already. If it's at input 0, we move to the state q₁, which is not the end state.

   Unlike the previous automata, this automaton has multiple end states, i.e. F = {q₃, q₄}.

3. Construct an automaton over a binary alphabet that only accepts words that do not contain two consecutive zeros.

   

   This automaton is interesting for two reasons: the first is that it accepts empty words. We can try to put an empty word into the automaton and the automaton will accept it if the initial state is also the final state, which is what happened with this automaton. Since an empty word is a word that doesn't contain two zeros in a row, that's the right thing to do. Another interesting thing is that this automaton has all end states. Thus, the only time the automaton would not accept a word is if there was no transition from the state. This happens in the state q₁, which has no transition for 0, because then the word would contain two zeros in a row.

4. Construct an automaton over the alphabet {-,+,.,0,1,...,9} that only accepts words that represent a number. That is, either an integer such as 2, 548, 98263, or a decimal such as 5584.48, 3.14, and both with a version for a negative number with a minus sign of -2, -548, -3.14, and also with an explicit plus sign, i.e. +2, +548, +3.14. At the same time, we need to be able to write the number 0.123 as just .123 (without the leading zero), and including both signs. We'll introduce a notation where, instead of writing out ten transitions for ten digits, we use the symbol N.

   

5. Construct an automaton over the binary alphabet that will only accept words that are of the form 0ⁿ1ⁿ, which means that the words have a certain number of zeros at the beginning followed by an equal number of ones. Examples of such words are 0011, 00001111, 01.

   We cannot build such an automaton because we are unable to "remember" the number of zeros anywhere. We would have to create several "sub-automata", like in the second example, but there would have to be infinitely many of these "sub-automata", one for each value of n.

Formalizing the calculation of the automaton

We have already formally defined the finite automaton itself. Next, we still need to define what such an automaton actually does, i.e. we define the computation of the automaton.

Configuration of the automaton: We say that the pair $\left<q, w\right> \in Q \times \Sigma^\ast$ is the configuration of the automaton, where q is the current state the automaton is in and w is the unread part of the word. $\Sigma^\ast$ denotes the closure of the alphabet $\Sigma$, the set of all words that can be put together from the letters of the alphabet $\Sigma$. The closure includes the empty word, which we denote by $\varepsilon$.

If we have an automaton $\left<Q, \Sigma, \delta, q_0, F\right>$ and we try to accept the word w, then the automaton is in the initial configuration <q₀, w>. If we go back to the automaton

and we try to accept the word w = abbc, then the initial configuration is <q₀, abbc>.

We definethe computation step as a relation $\mapsto$ between the sets $(Q\times\Sigma^\ast)\times(Q\times\Sigma^\ast)$, i.e., between the configurations of the automaton. Let w = w₀w₁… w_n represent the unread part of the word w. Then we say that the pairs <q₁, w₀w₁… w_n> and <q₂, w₁… w_n> are in the session $\mapsto$, written as

$$ \left<q_1, w_0w_1\dots w_n\right> \mapsto \left<q_2, w_1\dots w_n\right>, $$

just if δ(q₁, w₀) = q₂. Returning to our example, the initial configuration is <q₀, abbc>. From the diagram, we can see that for input "a" we can move to the state q₁. So we can write

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right>, $$

because δ(q₀, a) = q₁ applies. By doing this, we have performed one step of the calculation - we have looked at what state we should go to for a given input (= the first letter of the unread part of the word), moved there and removed the first letter from the unread part of the word. This gave us a new configuration.

We denote thereflexive and transitive closure of the session step of the computation by $\mapsto^\ast$. Thus, if we write $K_1 \mapsto^\ast K_2$, where K₁, K₂ are the configurations of the automaton, this means that we can get from the configuration K₁ to the configuration K₂, or there is a finite sequence of configurations such that:

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

For example, in our automaton, $\left<q_0, abbc\right> \mapsto^\ast \left<q_1,bc\right>$, because if we perform two steps of computation, we will be left with the word "bc" and remain in the state q₁. That is, there is this sequence of configurations:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> $$

The automaton accepts the word w if and only if there exists a q_f ∈ F such that $$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>$$ That is, the automaton accepts the word w if and only if there exists some sequence of computation steps such that at the end of this sequence we have read the whole word and are in the end state of the automaton. That we have read the whole word is expressed by the fact that it is in the configuration in place of the word $\varepsilon$, which is an empty word. Our automaton accepts the word abbc because this sequence of configurations exists:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> \mapsto \left<q_1, c\right> \mapsto \left<q_2, \varepsilon\right> $$

and the state q₂ is the end state, q₂ ∈ F.

The language accepted by the automaton is the set of all words that the automaton accepts. We will denote the language of the automaton A as L(A). Thus, $L(A) \subseteq \Sigma^\ast$ and

$$ L(A) = \left\{w \in \Sigma^\ast,|,A \mbox{ accepts the word } w\right\} $$

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, the automata A₁ and A₂ are equivalent if L(A₁) = L(A₂) holds.

Resources

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