In this section we first define several variations of the finite automata distinguished by the properties of the transition function.

Definition 15 (Finite automata). Let A = ( Q, T, q₀, δ, F ). It is a finite automaton (recognizer), where Q is the finite set of (inner) states, T is the input (or tape) alphabet, q₀ ∈ Q is the initial state, F ⊆ Q is the set of final (or accepting) states and δ is the transition function as follows.

One can observe, that the second variation is a special case of the first one (not having λ-transitions). The third variation is a special case of the second one having sets with at most one element as images of the transition function, while the fourth case is more specific allowing sets exactly with one element.

One can imagine a finite automaton as a machine equipped with an input tape. The machine works on a discrete time scale. At every point of time the machine is in one of its states, then it reads the next letter on the tape (the letter under the reading head), or maybe nothing (in the first variations), and then, according to the transition function (depending on the actual state and the letter being read, if any) it goes to a/the next state. It may happen in some variations that there is no transition defined for the actual state and letter, then the machine gets stuck and cannot continue its run.

There are two widely used ways to present automata: by Cayley tables or by graphs. When an automaton is given by a Cayley table, then the 0th line and the 0th column of the table are reserved for the states and for the alphabet, respectively (and it is marked in the 0th element of the 0th row). In some cases it is more convenient to put the states in the 0th row, while in some cases it is a better choice to put the alphabet there. We will look at both possibilities. The initial state should be the first among the states (it is advisable to mark it by a → sign also). The final states should also be marked, they should be circled. The transition function is written into the table: the elements of the set δ(q,a) are written (if any) in the field of the column and row marked by the state q and by the letter a. In the case when λ-transitions are also allowed, then the 0th row or the column (that contains the symbols of the alphabet) should be extended by the empty word (λ) also. Then λ-transitions can also be indicated in the table.

Automata can also be defined in a graphical way: let the vertices (nodes, that are drawn as circles in this case) of a graph represent the states of the automaton (we may write the names of the states into the circles). The initial state is marked by an arrow going to it not from a node. The accepting states are marked by double circles. The labeled arcs (edges) of the graph represent the transitions of the automaton. If p ∈ δ (q,a) for some p,q ∈ Q, a ∈ T ∪ {λ}, then there is an edge from the circle representing state q to the circle representing state p and this edge is labeled by a. (Note that our graph concept is wider here than the usual digraph concept, since it allows multiple edges connecting two states, in most cases these multiple edges are drawn as normal edges having more than 1 labels.)

In this way, implicitly, the alphabet is also given by the graph (only those letters are used in the automaton which appear as labels on the edges).

In order to provide even more clarification, we present an example. We describe the same nondeterministic automaton both by a table and by a graph.

Example 21. Let an automaton be defined by the following Cayley table:

Figure 2.2. shows the graph representation of the same automaton.

2.2. ábra - The graph of the automaton of Example 21.

These automata are used to accept words, and thus, languages:

Definition 16. (Language accepted by finite automaton). Let A = (Q, T, q₀, δ, F) be an automaton and w ∈ T^* be an input word. We say that w is accepted by A if there is a run of the automaton, i.e., there is an alternating sequence q₀ t₁ q₁ ... q_k-1 t_k q_k of states and transitions, that starts with the initial state q₀, (q_i ∈ Q for every i, they are not necessarily distinct, e.g., q_i = q_j is allowed even if i ≠ j) and for every of its transition t_i of the sequence

where a₁... a_k = w, and q_k ∈ F. This run is called an accepting run.

All words that A accepts form L(A), the language accepted (or recognized) by the automaton A.

Example 22. Let A be the automaton drawn in the next animations. We show a non-accepting run of a non-deterministic automaton A (with λ-transitions) in Animation 3.

Animation 3.

However the word 1100 is accepted by A, since it has also an accepting run that is shown in Animation 4.

Animation 4.

These finite automata are also called finite-state acceptors or Rabin-Scott automata. Let us see the language class(es) that can be accepted by these automata.

Two automata are equivalent if they accept the same language.

We have defined four types of finite automata and by the definition it seems that the latter ones are more restricted than the former ones. However, it turns out that all four versions characterize the same language class:

Theorem 4. For every finite automaton there is an equivalent (completely defined) deterministic finite automaton.

Proof. The proof is constructive. Let A = (Q, T, q₀, δ, F) be a nondeterministic finite automaton (allowing λ-transitions). Let us define, first, the λ-closure of an arbitrary set q' of states.

Since Q is finite, there is a value k such that U_k (q') = U_k+1 (q'), let us denote this set by U(q'). Practically, this set contains all the states that can be reached starting from a state of q' by only λ-transitions.

Now we are ready to construct the automaton A' = (Q', T, U (q₀), δ', F'), where Q' = 2^Q, F' ⊂ Q' includes every element q' ∈ Q' such that q' ∩ F ≠ ∅. The transition function δ' is defined as follows: for any a ∈ T and q' ∈ Q'. Actually while this can be done for all subsets of Q, subsets which cannot be reached by transitions from U (q₀) by δ' can be deleted (these useless states are not needed).

One can observe that A' is a completely defined deterministic automaton. Also, every run of A has an equivalent run of A', in fact, A' simulates every possible run of A on the input at the same time. Conversely, if A' has an accepting run, then A also has at least one accepting run for the same input. Therefore, A and A' accept the same language, consequently they are equivalent.

QED

Our previous proof gives an algorithm for the ''determinization'' of any finite automaton having only states reachable from the initial state as we will see it in details in Example 23. Note that even if we deleted these useless states, the automaton may not be minimal in the sense that the same language can be accepted by a completely defined deterministic finite automaton having less number of states than our automaton.

Example 23. Let a nondeterministic automaton be defined by the following Cayley table (note that in this algorithm the rows refer to the states of the automaton and the columns to the letters of the alphabet, and in this automaton λ-transitions are allowed):

We start with the λ-closure of the initial state U (q₀) = {q₀}. This set will count as the initial state of the new automaton: let it be in the first row of the table of this new automaton. Let us see which sets of states can be obtained from this set by using the letters of the alphabet:

Let us write these two sets in the second and third row of the table. Now let us see what sets of states can be reached from these sets. First, let us see the set {q₀, q₁, q₂}.

Since this latter set is not in the table yet, it is added to the fourth row. Now let us see the set {q₂}.

Since both of these two sets are already in the table we do not need to add a new row. Finally, let us analyse the set {q₁,q₂} (that is the last row of the table).

These sets are in the table. So the table is filled. The initial state of the new deterministic automaton is {q₀}. The final states are: {q₀, q₁, q₂}, {q₂}, and {q₁, q₂}. The next table shows the resulting deterministic finite automaton:

Example 24. Animation 5. shows an example how to obtain a completely defined deterministic automaton that is equivalent to the original nondeterministic automaton.

Animation 5.

Let A = (Q, T, q₀, δ, F) be a deterministic finite automaton such that each of its states is reachable from its initial state (there are no useless states). Then we can construct the minimal deterministic finite automaton that is equivalent to A in the following way:

Let us divide the set of states into two groups obtaining the classification C₁ = {F, Q\F}. (We denote the class where state q is by C₁[q].)

Then, for i > 1 the classification C_i is obtained from C_i-1: the states p and q are in the same class by C_i if and only if they are in the same class by C_i-1 and for every a ∈ T they behave similarly: δ (p,a) and δ (q,a) are in the same class by C_i.

Set Q is finite and, therefore, there is a classification C_m such that it is the same as C_m+1.

Then, we can define the minimal completely defined deterministic automaton that is equivalent to A: its states are the groups of the classification C_m, the initial state is the group containing the initial state of the original automaton, the final states are those groups that are formed from final states of the original automaton, formally:

where δ_Cm(C_m [q], a) = C_m [δ (q,a)] for every C_m [q] ∈ C_m, a ∈ T and F_Cm = {C_m [q]∣q ∈ F}.

It may happen that there are some words w ∈ T^* that are not prefixes of any words of a regular language L. Then, the minimal completely defined deterministic automaton contains a sink state, that is the state where the word w and other words with the same property lead the automaton. When we want to have a minimal deterministic finite automaton for these languages, allowing partial (not completely defined) finite automata, then we may delete this sink state (with the transitions into it) by decreasing the number of the states by one.

Let us see yet another example. When applying the minimization algorithm it is more convenient to put the states to the 0th row of the table and the letters of the alphabet to the 0th column of the table.

Example 25. Let the deterministic automaton A be given as follows:

Give a minimal deterministic automaton that is equivalent to A.

Solution:

Before applying the algorithm we must check which states can be reached from the initial state: from q₀ one can reach the states q₀, q₂, q₁, q₃, q₅, q₄. Observe that the automaton cannot enter state q₆, therefore, this state (column) is deleted. The task is to minimize the automaton

by the algorithm. When we perform the first classification of the states C₁ = {Q₁, Q₂} by separating the accepting and non-accepting states: Q₁ = {q₂, q₄, q₅}, Q₂ = {q₀, q₁, q₃} then we have:

Then C₂ = {Q₁₁, Q₁₂, Q₂₁, Q₂₂} with Q₁₁ = {q₂, q₅}, Q₁₂ = {q₄}, Q₂₁ = {q₀, q₁}, Q₂₂ = {q₃}. Then according to this classification we have

Since C₃ = C₂ we have the solution, the minimal deterministic finite automaton equivalent to A:

We conclude this subsection by a set of exercises.

Exercise 17. Give a finite automaton that accepts the language of words that contain the consecutive substring baab over the alphabet {a,b}.

Exercise 18. Let the automaton A be given in a Cayley table as follows:

Draw the graph of A. What is the type of A (e.g., nondeterministic with allowed λ-transitions)?

Exercise 19. The graph of the automaton A is given in Figure 2.3.

2.3. ábra - The graph of the automaton of Exercise 19.

Describe A by utilizing a Cayley table. What is the type of A (e.g., deterministic with partially defined transition function)? What is the language that A recognizes?

Exercise 20. Let a nondeterministic automaton with λ-transitions, A, be defined by the following Cayley table:

Give a completely defined deterministic automaton that is equivalent to A.

Exercise 21. Let a nondeterministic automaton A be defined by the following table:

Give a completely defined deterministic automaton that accepts the same language as A.

Exercise 22. Let a nondeterministic automaton A be defined by the graph shown in Figure 2.4.

2.4. ábra - The graph of the automaton of Exercise 22.

Give a completely defined deterministic automaton that accepts the same language as A.

Exercise 23. Let the deterministic automaton A be given as follows:

Give a minimal deterministic automaton that is equivalent to A.

Exercise 24. Let the deterministic automaton A be given by the following table.

Give a minimal deterministic automaton that is equivalent to A. (Hint: check first which states can be reached from the initial state.)

Exercise 25. Let a nondeterministic automaton A be defined by the graph shown in Figure 2.5.

2.5. ábra - The graph of the automaton of Exercise 25.

Give a minimal deterministic automaton that is equivalent to A.

2.3.1. Synthesis and Analysis of Finite Automata

Now we are going to show that exactly the class of regular languages can be described with the help of the finite automata. First we show that every regular language (type 3 language) can be accepted by finite automata.

Theorem 5. Every language generated by a regular grammar is accepted by a finite automaton.

Proof. The proof is constructive. Let G = (N, T, S, P) be a regular grammar in normal form. Then, let the finite automaton

A = (Q, T, q₀, δ,F)

be defined as follows:

let Q = N ∪ {F'} (where F' ∉ N),

q₀ = S.

Let the transition function δ be defined by the elements of P: let B ∈ δ (A,a) if A → aB ∈ P; and let F' ∈ δ (A,a) if A → a ∈ P. Further, let the set of accepting states be {F'} if S →λ is not in P and let F = {F',S} if S → λ ∈ P.

One can see that the successful derivations in the grammar and the accepting runs of the automaton have a one-to-one correspondence.

QED.

Example 26. Let

G = ({S, A, B, C}, {a, b, c}, S,

{  S → abbA,
   S → baaB,
   S → λ,
   A → aS,
   A → aC,
   B → bC,
   C → aS,
   C → cc  
}) 

generating the language L(G). Give a finite automaton that accepts the language L(G).

Solution:

First we must exclude the rules containing more than 1 terminals, as we did in the proof of Theorem 2. In this way the grammar

G' =({S, A, B, C, X₁, X₂, X₃, X₄, X₅}, {a, b, c}, S,

{  S → aX1,
   X1 → bX2,
   X2 → bA,
   S → bX3,
   X3 → aX4,
   X4 → aB,
   S → λ,
   A → aS,
   A → aC,
   B → bC,
   C → aS,
   C → cX5,
   X5 → c
}) 

can be obtained. Then, we can draw the graph of automaton A as it can be seen in Figure 2.6.

2.6. ábra - The graph of the automaton of Example 26.

Now we are going to show that the class of finite automata cannot accept more languages than the class that can be described by regular expressions.

Theorem 6. Every language accepted by a finite automaton can be described by a regular expression.

Proof. The proof is constructive. We present an algorithm that shows how one can construct a regular expression from a finite automaton. We can restrict ourselves to deterministic finite automaton, since we have already seen that they are equivalent to the nondeterministic finite automata. Let the states of a deterministic finite automaton be 1,2,... for the sake of simplicity, i.e., let A = ({1,... n}, T, 1, δ, F) be given. Let denote the regular expression that describes the language accepted by the automaton ({1,...,k} ∪ {i,j}, T, i, δ', {j}), where δ' is the restriction of δ containing only transitions from the set {i} ∪ {1,...,k} to the set {1,...,k} ∪ {j} (1 ≤ i,j ≤ n, 0 ≤ k ≤ n and 1,..., 0 means the empty set).

Then, describes the regular language that is given by direct transition(s) from state i to j. Therefore, gives the language {λ} ∪ {a∣δ (i,a) = i} (this language contains the empty word and possibly some one-letter-long words, i.e., it is described by a basic regular expression or finite union of basic regular expressions).

Further, describes the language {a∣δ (i,a) = j} if i ≠ j (it can contain some one-letter-long words). These regular expressions can easily be obtained and proven to describe the languages mentioned.

Now we use induction on the upper index:

for 1 ≤ k ≤ n. This expression can be seen intuitively: starting from state i we could reach state j by using the first k states in our path, either without using state k (the part refers to this case) or by a path reaching state , and then reaching it arbitrarily many times (including 0 times: , and finally reaching state j from state

Finally, gives a regular expression that describes exactly the language accepted by A. In this way it is constructively proven that for any finite automaton one can construct a regular expression that describes the language accepted by the automaton.

QED.

Example 27. Let the Cayley table of automaton A be given as follows:

T Q	→q1	⊂q2⊃	⊂q3⊃
a	q2	q3	q1
b	q3	q2	-

Describe the accepted language L(A) by a regular expression.

Solution:

Let us describe the regular expressions for i,j ∈ {1,2,3} by using the transitions of A.

Now by using the inductive step we compute for i,j ∈ {1,2,3}.

• 

• 

• 

• 

• 

• 

• 

• 

• 

Now we can continue by computing the expressions

• 

• 

• 

• 

• 

• 

• 

• 

• 

To describe L(A) we need Let us compute it:

• 

• 

Thus, the regular expression

(ab^*a + b)(aab^*a + ab)^* aab^* + ab^* + (ab^*a + b)(aab^*a + ab)^* = (ab^*a + b)(aab^*a + ab)^* (λ + aab^*) + aab^*

describes L(A). The problem is solved.

Now we have proven that the three concepts we have discussed in this chapter, the regular grammars, regular expressions and finite automata are equivalent in the sense that each of them characterize exactly the class of regular languages (see Figure 2.7).

2.7. ábra - The equivalence of the three types of descriptions (type-3 grammars, regular expressions and finite automata) of the regular languages.

The aim of the analysis of a finite automaton is the task to describe the accepted language in another way, usually, by regular expressions. The synthesis of a finite automaton is the construction of the automaton that accepts a regular language that is usually given by a regular expression. Kleene has proven the equivalence of finite automata and regular expressions.

The minimization algorithm is very important, since the minimal, completely defined, deterministic finite automaton is (the only known) unique identification of a regular language. In this way, we can decide if two regular languages (given by regular expressions, grammars or automata) coincide or not.

We close this subsection by a set of exercises.

Exercise 26. Let

G = ({S, A, B}, {0,1}, S,

{  S → 000A,
   S → 111B,
   A → λ,
   A → 0S,
   A → 11,
   B → 1S,
   B → 000 
}) 

generating language L(G). Give a finite automaton that accepts language L(G). (Hint: first transform the grammar to normal form.)

Exercise 27. Let

G = ({S, A, B, C}, {a,b}, S,

{  S → aaaA,
   S → bbB,
   S → C,
   A → S,
   A → baB,
   A → ba,
   B → S,
   B → C,
   B → b,
   B → λ,
   C → B,
   C → aA
}) 

generating language L(G). Give a finite automaton that accepts language L(G).

Exercise 28. Let

G = ({S, A, B}, {a, b, c}, S,

{  S → abA,
   S → bccS,
   A → bS,
   A → c,
   A → B,
   B → S,
   B → aA, 
   B → bcc,
   B → λ
}) 

generating language L(G). Give a finite automaton that accepts language L(G).

Exercise 29. Let the automaton A be defined by the following table:

T Q	→q1	q2	⊂q3⊃
0	q1	q3	q3
1	q2	q2	q1

Give a regular expression that describes the language accepted by automaton A.

Exercise 30. Let automaton A, accepting language L(A), be defined by the Cayley table:

T Q	→⊂q1⊃	q2	⊂q3⊃
a	q1	q3	-
b	-	q2	q1
c	q2	q2	-

Give a regular expression that describes language L(A).

Exercise 31. Let automaton A be as it is shown in Figure 2.8. Give a regular expression that defines the same language as A.

2.8. ábra - The graph of the automaton of Exercise 31.

2.3.2. The Word Problem

The word problem is to decide whether any given word w belongs to a given regular language (or not). This can be done very efficiently by using a deterministic finite automaton that accepts the given language. (Such an automaton can be constructed from a regular expression, first by Theorem 3. and then/or from a grammar by Theorem 5. and then/or from a nondeterministic finite automaton by Theorem 4.) Reading the word w can be done by ∣w∣ steps, and then, if the automaton accepts w, i.e., it arrived at an accepting state in this run, then w is an element of the language. Otherwise, (if there were some undefined transitions and the automaton gets stuck, or by reading the word finally a non accepting state is reached) w does not belong to the given regular language. The decision on an input word of length n is done in at most n steps, therefore, this is a real time algorithm (i.e., linear time algorithm with coefficient 1). There is no faster algorithm that can read the input, so the word problem for regular languages can be solved very efficiently.

Exercise 32. Let automaton A be given as it can be seen in Figure 2.9.

2.9. ábra - The graph of the automaton of Exercise 32.

Decide whether the words

   abab, 
   baba, 
   aaaabbb, 
   bbbaaaab, 
   baabaabaabb and 
   aaaabbbababaaa are in L(A). 

Exercise 33. Let the nondeterministic automaton A be defined by the Cayley table:

Q T	0	1	λ
→q0	q1, q4	q5	q2
q1	q3	q1, q4	-
q2	q1	q2	-
⊂q3⊃	-	-	q2
q4	-	q4	-
⊂q5⊃	q5	q5	q0

Decide which of the words 0011, 0101, 0110, 01110010, 100, 1011110 belong to the accepted language of A.

Exercise 34. Let

G = ({S, A, B}, {a, b, c}, S,

{  S → abcS,
   S → bcA,
   S → acB,
   A → aS,
   A → a,
   B → bS,
   B → bcc,
   S → ccc
}) 

be a regular grammar. Decide which of the following words can be generated by G:

   abcccc, 
   acbcc, 
   acbbacbccc,
   bca, 
   bcacacc, 
   bcaabcacbcc, 
   ccc, 
   cccacbc.

Exercise 35. Given the regular language

a^* + (a+b)^*baba (a+b)^*),

decide if the following words are in the described language or not:

   aaaaa, 
   aaabaa, 
   ababa, 
   abbabaaba.