1
Chương 2
AUTOMATA HỮU HẠN VÀ
NGÔN NGỮ CHÍNH QUI
2
1.Automata hữu hạn
1.1 Giới thiệu phi hình thức về automata hữu hạn
1.2 Automata hữu hạn đơn định
1.3 Automata hữu hạn không đơn định
1.4 Automata hữu hạn với phép truyền rỗng
2. Ngôn ngữ và biểu thức chính qui
2.1 Biểu thức chính qui
2.2 Chuyển đổi giữa biểu thức chính qui và
automata hữu hạn
2.3 Các luật đại số cho biểu thức chính qui
2.4 Ngôn ngữ chính qui
3
Automata hữu hạn (Finite automata)
Lớp ngôn ngữ “Ngôn ngữ chính qui”, được đoán
nhận bởi máy ảo, gọi tên là “automata hữu hạn”.
 Automata hữu hạn đơn định (
Deterministic Finite
Automata – DFA
 Automata hữu hạn không đơn định (Nondeterministic
Finite Automata – NFA)
 Automata hữu hạn không đơn định, chấp nhận
phép truyền rỗng (ε-NFA)
4
Giới thiệu phi hình thức về automata hữu hạn
 Một bài toán trong automata là nhận diện chuỗi w
có thuộc về ngôn ngữ L hay không.

 Không nhớ chuỗi con.
 Nhớ số lượng ký số 0 và số lượng ký số 1 đã
được đọc. Có 4 trường hợp.
8
even
even
Start
even
odd
odd
even
odd
odd
0
0
0
0
1
1
1
1
9
Ví dụ: L = {w  {0, 1}* | w kết thúc bằng ký số 1 và
không chứa chuỗi con 00}
TH 1
: Đã biết chuỗi w chứa chuỗi con 00.
TH 2
: chuỗi 00 chưa xuất hiện.
TH 2.1
: Ký hiệu cuối là 0. Nếu ký hiệu kế tiếp là:

: hàm truyền.
4. q
0
: trạng thái bắt đầu, q
0
 Q.
5. F: tập các trạng thái kết thúc/chấp nhận, F  Q.
12
Ví dụ: Mô tả DFA chấp nhận ngôn ngữ L:
L = {w | w = x01y và chuỗi x, y  {0, 1}*}
Bảng chữ cái của ngôn ngữ L này là:  = {0, 1}.
DFA A cần phải nhớ:
TH 1
: Đã thấy 01. Chấp nhận tất cả những ký hiệu
nhập còn lại.
TH 2
: Chưa thấy 01
TH 2.1
: Ký hiệu nhập gần nhất là 0. Nếu ký hiệu
kế tiếp là:
1: Xem như A đã gặp 01  TH 1.
0: Dừng lại ở TH 2.1.
TH 2.2
: Ký hiệu nhập gần nhất là 1. Nếu ký hiệu
kế tiếp là:
1: Dừng lại ở TH 2.2.
0: Chuyển sang TH 2.1
13
Mỗi trường hợp TH1, TH 2.1, TH 2.2 có thể được
biểu diễn bởi một trạng thái.


(q
2
, 1) = q
1
.
TH 1 được thể hiện bởi trạng thái chấp nhận q
1
.
 Hàm truyền trên q
1
:

(q
1
, 0) = q
1
và

(q
1
, 1) = q
1
.
Như vậy, Q = {q
0
, q
1
, q
2

15
Sơ đồ truyền
Sơ đồ truyền cho DFA A = (Q, ,

, q
0
, F) là một
đồ thị được định nghĩa như sau:
 Mỗi trạng thái trong Q là một nút.
 Nếu p, q  Q, a . Giả sử

(q, a) = p. Khi đó,
sơ đồ truyền có cung nối nút q đến nút p và gán
nhãn a.
 Luôn có 1 mũi tên chỉ vào trạng thái bắt đầu q
0
,
gán nhãn Start.
 Những nút mô tả trạng thái chấp nhận ( F) có 2
vòng tròn đồng tâm. Những nút còn lại chỉ chứa
1 vòng tròn.
16
Bảng truyền
Biểu diễn các hàm truyền trên một bảng.
- Dòng của bảng tương ứng với trạng thái.
- Các cột là những ký hiệu nhập trong tập .
- Trạng thái bắt đầu được đánh dấu bởi mũi tên ().
- Trạng thái kết thúc được đánh dấu bởi dấu sao (*).
17
Hàm truyền mở rộng (DFA)

Có 4 trường hợp.
 q
0
là tt bắt đầu cũng như tt kết thúc.
 DFA A của ngôn ngữ L là:
A = ({q
0
, q
1
, q
2
, q
3
}, {0, 1},

, q
0
, {q
0
})
20
Sơ đồ truyền
Bảng truyền
q
2
q
1
q
3
q

1
0
0
0
Start
21
Ngôn ngữ của DFA
Định nghĩa:
Ngôn ngữ L(A) của DFA A = (Q, ,

, q
0
, F) được
xác định bởi:
L(A) = {w |

^(q
0
, w)  F }

Nếu ngôn ngữ L là L(A) của DFA A nào đó, ta nói,
L là ngôn ngữ chính qui.
22
Automata hữu hạn không đơn định (NFA)
 Automaton kiểu NFA sẽ có thể thuộc về một vài
trạng thái cùng một lúc.
 NFA cũng chấp nhận ngôn ngữ chính qui, giống
như DFA.
 NFA thường cô đọng và dễ thiết kế hơn DFA.
Có thể chuyển đổi từ NFA sang DFA.

0
q
0
q
0
q
0
q
1
q
1
q
1
q
2
q
2
(dừng)
(dừng)
00101
Các trạng thái
hiện hành
q
0
q
0
26
Định nghĩa: NFA A là (Q, ,

, q

{q
2
}Øq
1
{q
0
}{q
0
, q
1
}
 q
0
10
28
Hàm truyền mở rộng (NFA)
Hàm truyền mở rộng được định nghĩa bằng qui
nạp
 Bước cơ sở:

^(q, ε) = q.
 Bước qui nạp: Giả sử chuỗi w có dạng xa
29
Ngôn ngữ của NFA
Một NFA chấp nhận chuỗi w nếu một/một số
luồng xuất phát từ trạng thái bắt đầu và đạt đến
trạng thái chấp nhận với điều kiện chuỗi w được
xử lý hoàn toàn.
Gọi NFA A là (Q, ,



),(
ˆ
0
wq

),(
ˆ
0
wq

31
 Ba phát biểu trên giúp xác định trạng thái của A
trước khi đọc ký hiệu nhập kế tiếp.
 Việc chứng minh 3 phát biểu trên đảm bảo rằng
ngôn ngữ của NFA này là tập các chuỗi ký tự kết
thúc bởi 01.
 Sử dụng chứng minh qui nạp tương hỗ.
32
Bước cơ sở: Nếu |w| = 0 thì w = ε.
33
Bước qui nạp: Cho rằng w = xa, với a là ký hiệu
nhập 0 hoặc 1.
34
 (If) Nếu w kết thúc bởi 0, có nghĩa là a = 0.
Chứng minh q
1


^(q

 Xây dựng NFA thường dễ dàng hơn.
 Trong thực tế, số trạng thái của DFA xấp xỉ NFA,
nhưng thường thì có nhiều hàm truyền hơn.
 Trong trường hợp xấu nhất, nếu cùng chấp
nhận một ngôn ngữ: NFA có n trạng thái thì DFA
có 2
n
trạng thái.
37
Kiến tạo tập con
 Để chứng minh DFA chấp nhận mọi ngôn ngữ
mà NFA chấp nhận, cần sử dụng kỹ thuật “Kiến
tạo tập con”.
 Từ NFA N = (Q
N
, ,

N
, q
0
, F
N
), dùng “Kiến tạo
tập con” để xây dựng DFA D = (Q
D
, ,

D
, q
0


39
Ví dụ: Gọi NFA N là automaton chấp nhận chuỗi
kết thúc bởi 01. Vì Q
N
= {q
0
, q
1
, q
2
} nên “kiến tạo
tập con” sản sinh ra DFA có 2
3
= 8 trạng thái.
{q
0
, q
2
}{q
0
, q
1
}*{q
0
, q
1
, q
2
}

}
ØØ*{q
2
}
{q
2
}Ø{q
1
}
{q
0
}{q
0
, q
1
}
 {q
0
}
ØØØ
10
40
Gọi A = Ø, B = {q
0
}, C = {q
1
}, Z = {q
2
}, E = {q
0

 Bước cơ sở: Tập con chứa trạng thái bắt đầu
của N.
 Bước qui nạp: Giả sử R là tập các trạng thái có
thể truy xuất.
42
{q
0
} {q
0
, q
1
} {q
0
, q
2
}
Start
1
01
1
0
0
43
Chứng minh hình thức vai trò của “Kiến tạo tập con”
 DFA D vừa được xây dựng sẽ chấp nhận chuỗi
nhập w nếu D đi vào trạng thái kết thúc sau khi
đọc hết w.
 Mỗi trạng thái chấp nhận của DFA là một tập
hợp chứa ít nhất một trạng thái chấp nhận của
NFA.

Trước hết, cần chứng minh bằng qui nạp đẳng
thức sau:
),(
ˆ
)},({
ˆ
00
wqwq
ND


45
 Bước cơ sở: Giả sử |w| = 0 thì w = ε.
 Bước qui nạp: Gọi |w| = n + 1.
46
→ L(D) = L(N).
“Kiến tạo tập con”, theo một hướng khác:


k
i
iNkD
apappp
1
21
),()},,,,({



47