1
Chương 3
BIỂU THỨC CHÍNH QUI VÀ
NGÔN NGỮ CHÍNH QUI
2
1. Biểu thức chính qui
1.1 Toán tử của biểu thức chính qui
1.2 Xây dựng biểu thức chính qui
1.3 Độ ưu tiên của các toán tử
2. Định lý của Kleene
2.1 Chuyển FA sang biểu thức chính qui
2.2 Chuyển biểu thức chính qui sang FA
2.3 Định lý Kleen
3. Những luật đại số trên biểu thức chính qui
3.1 Kết hợp và giao hoán
3.2 Đồng nhất thức và giá trị triệt tiêu
3.3 Những luật phân phối
3.4 Luật bất biến giá trị
3.5 Các luật trên biể
u thức chính qui
3.6 Kiểm tra luật đại số trên biểu thức chính qui
3
Biểu thức chính qui
(Regular Expression - RE)
 FA là những máy ảo nhận dạng ngôn ngữ, trong
khi RE mô tả ngôn ngữ như biểu thức đại số
 Ứng dụng:
1. Các lệnh tìm kiếm chuỗi

2. Các bộ phát sinh bộ phân tích từ vựng.
4

0
 L
1
 L
2
 …
Chú ý
:
Ø* = {ε}, vì Ø
0
= {ε}, Ø
n
= Ø (n  1)
7
Xây dựng biểu thức chính qui
 Dạng cơ sở của biểu thức đại số là hằng số
và/hoặc biến. Những biểu thức phức tạp hơn
được xây dựng bằng cách áp dụng các toán tử
trên những biểu thức đã được xây dựng.
 RE cũng được xây dựng tương tự
 Nếu RE E là hợp lệ thì tồn tại ngôn ngữ L(E) mà
E biểu diễn.
8
Bước qui nạp: Gồm 4 phần
1. Hằng ε và Ø là RE
2. Nếu a là một ký hiệu bất kỳ thì a là RE:
Bước cơ sở: Bao gồm 2 phần:
 Nếu E và F là RE thì E + F là RE:
 Nếu E và F là RE thì EF là RE:
 Nếu E là RE thì E* là RE:

 01* + 1: Tương đương với biểu thức (0(1*)) + 1
 (01)* + 1:
 01
+
:
14
Định lý của Kleene
 Về cơ bản, RE dùng để mô tả ngôn ngữ, còn FA
dùng để nhận dạng ngôn ngữ.
 FA và RE cùng chấp nhận lớp “ngôn ngữ chính
qui”
1. Ngôn ngữ được định nghĩa bởi DFA, NFA
hay ε–NFA
2. Ngôn ngữ được định nghĩa bởi RE
15
X  Y: lớp ngôn ngữ được chấp nhận bởi X sẽ
được chấp nhận bởi Y.
RE DFA
ε–NFA NFA
Tính tương đương giữa RE, DFA, ε–NFA và NFA.
16
Từ DFA đến RE: Khái niệm
 Xây dựng RE chấp nhận ngôn ngữ của DFA khá
phức tạp.
 RE sẽ mô tả tập các chuỗi mà mỗi ký hiệu trong
chuỗi là nhãn một đường truyền trong sơ đồ
truyền của DFA.
17
RE xây dựng từ DFA thông qua qui nạp:
 Bước cơ sở: Xây dựng các RE đơn giản

21
Nếu i ≠ j:
Kiểm tra sự tồn tại phép truyền từ trạng thái i
sang trạng thái j trên DFA A.
22
Nếu i = j:
-Nếu tồn tại đường truyền
-Nếu không tồn tại đường truyền
23
Bước qui nạp: Giả sử tồn tại đường truyền từ
trạng thái i sang j với điều kiện mọi trạng thái bên
trong được đánh số  k.
1. Đường truyền đi qua trạng thái k ít nhất một lần.
24
ikkkj
)1( k
ik
R
*)1(
)(
k
kk
R
)1( k
kj
R
Chú ý: Nếu đường truyền đi qua trạng thái k một
lần thì chỉ tồn tại 2 đoạn
25
Tập của các nhãn trên mọi đường truyền chính là

Dựa trên định lý 3.1, Bước cơ sở xây dựng các RE sau:
R
11
(0)
= ε + 1
R
12
(0)
= 0
R
21
(0)
= Ø
R
22
(0)
= ε + 0 + 1
29
Bước qui nạp: Xây dựng các RE phức tạp hơn.
Luật xây dựng R
ij
(1)
dựa vào Định lý 3.1:
30
(ε + 0 + 1) + Ø(ε + 1)*0 R
22
(1)
Ø+ Ø(ε + 1)*(ε + 1) R
21
(1)

1* + 1*0(ε + 0 + 1)*ØR
11
(2)
Rút gọnThay thế trực tiếp
33
Cuối cùng, RE tương đương với DFA là hội của tất
cả các RE thỏa:
(a)
(b)
R
12
(2)
= 1*0(0 + 1)*.
 Đây là RE mô tả những chuỗi 0, 1 chứa ít nhất
một số 0.
34
Chuyển DFA sang RE bằng loại bỏ trạng thái
 Phương pháp xây dựng RE: Loại bỏ trạng thái.
Giả sử tồn tại đường truyền: q → s → p.
Hủy s

 Nhãn của một đường truyền là nối của các RE (nhãn)
dọc theo từng cung truyền.
 Với FA có nhãn cung truyền là RE thì ngôn ngữ của
nó là hợp tất cả các đi từ
trạng thái đến trạng thái
35
S
q
1

trạng thái s.
q
1
q
k
p
1
p
m
R
11
+ Q
1
S
*
P
1
R
km
+ Q
k
S
*
P
m
R
k1
+ Q
k
S

Cần chuyển NFA sang automaton có nhãn là RE.
A B
C D
Start
0 + 1
0 + 1 0 + 11
A B
C D
Start
0, 1
0, 1 0, 11
40
Loại bỏ trạng thái B:
A và C lần lượt là trạng thái trước và sau của B.
A
C D
Start
0 + 1
1(0 + 1) 0 + 1
41
Loại bỏ trạng thái C:
A
D
Start
0 + 1
1(0 + 1)(0 + 1)
→ Mô tả chuỗi 0/1, có số 1 tại vị trí thứ ba tính từ
cuối.
42
Loại bỏ trạng thái D:

Bước qui nạp:
Giả thiết qui nạp
: Phát biểu của định lý là đúng đối
với RE thành phần gần nhất của RE đang xét.

Có 4 trường hợp xảy ra:
47
1. Hội R + S của 2 RE thành phần R và S.
Ngôn ngữ của FA trong hình (a) là:
ε
εε
εR
S
(a)
48
2. NốiRS của 2 RE thành phần R và S.
 Những đường truyền được chấp nhận bởi
automaton (b) sẽ có nhãn là chuỗi
R S
ε (b)
49
3. Bao đóng R* của RE thành phần R
i. Đi trực tiếp
Đường truyền chấp nhận chuỗi
ii. Từ trạng thái bắt đầu chung
→ Tất cả các chuỗi thuộc ngôn ngữ
εε
R
ε
ε