1
Văn phạm chính quy
& các tính chất
Nội dung:
•
Văn phạm chính quy (RG: Regular Grammar)
•
Sự tương đương giữa RG và FA
•
Bổ đề bơm cho tập hợp chính quy
•
Tính chất đóng của tập hợp chính quy
Chương 4:
2
Văn phạm chính quy
Văn phạm chính quy: là văn phạm mà tất cả các luật sinh
của nó đều có dạng tuyến tính trái (hoặc tuyến tính phải)
•
Tuyến tính trái: dạng A → Bw hoặc A → w
•
Tuyến tính phải: dạng A → wB hoặc A → w
Văn phạm chính quy, ngôn ngữ chính quy, biểu thức chính
quy và tập hợp chính quy:
•
Văn phạm chính quy sinh ra ngôn ngữ chính quy
•
Ngôn ngữ chính quy có thể được ký hiệu đơn giản
bằng một biểu thức chính quy
•
Tập hợp các chuỗi được ký hiệu bởi một biểu thức
chính quy được gọi là tập hợp chính quy

Start
ε
[0]
[1S]
ε
1
0
•
Đảo ngược automata
0
[0]
ε
Start
ε
[01S]
[ε]
0
1
0
[S] [1S]
5
Sự tương đương giữa RG & FA
Định lý 4.2: Nếu L là một tập hợp chính quy thì L được sinh
ra từ một văn phạm tuyến tính trái hoặc một văn phạm
tuyến tính phải nào đó
Ý nghĩa: một Automata hữu hạn có thể được biểu diễn bởi
một văn phạm chính quy.
Ví dụ: xét DFA cho 0(10)*
A CB
0