Main content:

In this chapter, we will study a type of “abstract machine” called a finite automaton. They are tools for guessing a fairly simple class of languages ​​called the regular language class. First, two forms of finite automaton will be presented, respectively, and it will be shown that they are equivalent in terms of language recognition. We will then refer to regular expressions, another means of defining languages, and again we will see that the class of languages ​​accepted by finite automaton is the class of regular languages. . The next part of the chapter will deal with the relationship between automaton and regular expressions; using symbols for languages. At the end of this chapter, some specific applications of finite automaton will be presented.

Watching: What is Automata

Achievable targets:

By the end of this chapter, students should have mastered:

The concept of a finite automaton, its components, its forms and the fundamental difference between the two.

The equivalent conversion method from deterministic to non-deterministic form and vice versa.

Write regular expressions; notation regularization for set of regular languages.

Relationship between finite automaton and regular expression.

Draw a state transition diagram (deterministic or non-deterministic) from a regular expression.

Find other practical applications from the finite automaton model.

Basic knowledge:

In order to absorb the content of this chapter well, students need to have some relevant knowledge about graph theory, circuit theory; understand basic concepts of computer architecture; using some common text editor…

References :

John E. Hopcroft, Jeffrey D.Ullman – Introduction to Automata Theory, Languages ​​and Computation – Addison – Wesley Publishing Company, Inc – 1979 (Chapter 2: Finite Automata and Regular Expressions).

Phan Thi Tuoi – Translator – Education Publishing House – 1986 (Chapter 3: Analysis; vocabulary).

J.A.Garcia and S.Moral- Theory of Finite Automata :

Donald R. Biggar – Regular Expression Matching Using Finite Automata:


In computer science, one can find many wallets; finite state systems, and the theory of finite automaton is a useful design tool for these systems. For example, a switching system such as a control unit in a computer. A switch consists of a finite number of input gates, each of which has two values ​​of 0 or 1. These input values ​​define two different voltage levels at the output port. Each state of a switched network with any n ports will be an instance of 2n assignments of 0s and 1s to different ports. Switches are designed in this way, so they can be viewed as finite state systems. Commonly used programs, such as text editors or parsers; lexicons in computer compilers; are also designed as finite state systems. Wallet; For example, a lexical analyzer scans all lines of a computer program to find a group of strings of characters corresponding to a variable name, constant, keyword, etc. For this, the lexical analyzer needs to remember a finite amount of information such as the characters that begin to form key sequences. The theory of finite automaton is often used for the design of efficient string processing tools.

READ MORE  Apartment For Rent In Vinhomes West Point Hanoi, Vinhome Westpoint

Computer; can also be viewed as a finite state system. The current state of the central processing unit, internal memory, and auxiliary storage devices at any given time is one of a very large and finite number of states. The human brain is also a finite state system, because the number of neurons, or neurons, is limited, at most 235.

The most important reason for the study of finite-state systems is the naturalness of the concept and its wide applicability in many practical fields. Finite automata (FA) are divided into two types: deterministic (DFA) and non-deterministic (NFA). Both types of finite automaton have the ability to identify correct, correct, regular sets. A deterministic finite automaton is more readily linguistically identifiable than a nondeterministic finite automaton, but is instead normally of size; its size is larger than that of the equivalent non-deterministic finite automaton.

Deterministic Finite Automata (DFA)

A deterministic finite automaton (DFA) – referred to as FA – consists of a finite set of states and a set of state-to-state transitions on input symbols selected from a set of certain letter Σ. Each input symbol has exactly one transition out of each state (possibly back to itself). A state, usually denoted q0, is called the starting state (the automaton start state). Some states are designed as termination or acceptance states.

A directed graph, called a transition diagram, corresponds to a DFA as follows: the vertices of the graph are the the status of the DFA; if there is a transition from state q to state p on input a, then there is an arc a transition from state q to state p in the transition diagram. DFA accepts a sequence x if there exists a sequence of corresponding transitions per symbol of x leading from the start state to one of the end states.

For example, the transition diagram of a DFA is shown in Figure 3.1. The start state q0 is indicated by an arrow labeled “Start”. There is only one termination state, also q0 in this case, indicated by two circles. This automaton accepts all sequences of 0s and 1s with zeros and ones being even numbers.

READ MORE  What is an Associate Professor?

Giving; Example 3.1:

Figure 3.1 – Transition diagram of a DFA

One thing to note, the DFA uses each of its states to hold only a portion of the sequence of 0s and 1s, not an actual number, so the DFA needs to use a finite number of states.

See also: What is the upper class – What is the English upper class


Formally we define a finite automaton as a set of five components (Q, Σ, δ, q0, F), where :

. Q is a finite set of states.

. Σ is a finite set of input letters.

. δ is a transfer function mapping from Q × Σ → Q, i.e. δ(q, a) is a state given by the transition from state q on input symbol a.

. q0 ∈ Q is the starting state

. F ⊆ Q is the set of termination states.

We draw the DFA as a finite controller, for each state in Q, the DFA reads a sequence of symbols a from Σ written on tape (as shown in the figure).

Figure 3.2 – Description of a DFA

During a transition, the DFA in state q reads input symbol a on the tape, transitions to the state determined by the transfer function δ(q, a), and then shifts the reader to the right one character. If δ(q, a) goes to one of the termination states, the DFA accepts the string written on the input tape;a before the reader, but does not include the character at the position; reader just moved to. In case the reader has translated to the end of the string on tape, the DFA will accept the entire string on tape.

Extended state transition function

To be able to formally describe the behavior of a DFA on a string, we extend the transfer function δ to apply to a state on the string rather than a state per symbol. We define the transfer function δ as a mapping from Q × Σ* → Q with the meaning that δ(q, w) is the state DFA moves from state q on the string w. Formally, we define:

d (q, ε) = q δ (q, wa) = δ(δ (q, w), a), for all strings w and the input symbol a.

READ MORE  Cultural Movement of the Renaissance

Some notation conventions:

Q is the set of states. The symbols q and p (with or without index) are states, q0 is the starting state. Σ is the input alphabet. Symbols a, b (with or without subscript) and digits are input symbols. δ is the transfer function. F is the set of termination states. w, x, y and z (with or without subscript) are input symbol sequences.

Languages ​​accepted by DFA

A string w is accepted by a finite automaton M (Q, Σ, δ, q0, F) if δ(q0, w) = p with p ∈ F. Language accepted by M, denoted L(M) is the set:

Giving; Example 3.2: Consider the transfer diagram in Figure 3.1. According to the formal concept, we have a DFA defined by M (Q, Σ, δ, q0, F) with Q = {q0, q1, q2, q3}, Σ = {0, 1}, F = {q0 } and the transfer function δ as follows:

Suppose the string w = 110101 is entered into M.

We have δ(q0, 1) = q1 and δ(q1, 1) = q0 , so δ(q0, 11) = δ(δ(q0,1),1) = δ(q1, 1) = q0.

Continuing δ(q0, 0) = q2, so δ(q0, 110) = δ(δ(q0, 11), 0) = q2.

Continuing we have (q0, 1101) = q3, δ(q0, 11010) = q1

And finally δ(q0, 110101) = q0 ∈ F.

(Or d(q0, 110101) = d(q1, 10101) = d(q0, 0101) = d(q2, 101) = d(q3, 01) = d(q1, 1) = q0 ∈ F)

So 110101 belongs to L(M). We can prove that L(M) is the set of all strings with even numbers of 0s and even numbers of 1s.

According to the above description of the DFA, we can see that the transition table can also be used to describe the state transitions of a finite automaton. In the transfer function table, the row contains the states of the automaton state set and the column is the input alphabetic symbols. The transfer function table suggests a data structure to describe a finite automaton, and also shows that the operation of DFA can be easily simulated through a computer program; for example, using a computer program. loop structure.

See also: What is Extend

Algorithm to simulate the operation of a DFA

Comment :

In general, we see that the set Q of DFA represents the storage states of automaton in the process of language recognition, and thus the storage capacity of automaton is finite. On the other hand, the transfer function d is a total and univalued function, so the automaton’s transitions are always uniquely determined. It is because of these two characteristics that the DFA described above is called a deterministic finite automaton.