Giáo trình Kiến trúc máy tính và
Hệ điều hành 65
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
Biểu thức chính quy
Ngôn ngữ chính quy
Văn phạm chính qui
Giáo trình Kiến trúc máy tính và
Hệ điều hành 66
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Biểu Thức chính quy
1.1. Định nghĩa:
Cho bộ chữ , biểu thức chính quy
(BTCQ) trên được định nghĩa đệ qui như sau:
là BTCQ
là BTCQ
a, a là BTCQ
-Với r, s là BTCQ thì (r+s), rs, r*, s* là BTCQ
Có thể viết (r+s) hay (r s)
Giáo trình Kiến trúc máy tính và
Hệ điều hành 67
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Biểu Thức chính quy
1.1. Định nghĩa:
Ví dụ: Cho ={0,1} ta có:
, , 0, 1 là BTCQ
-(0+1), 01, 0*, 1*, (0+1)01, (0+1)0*, (01)*,
((0+1)01)* là BTCQ
Giáo trình Kiến trúc máy tính và
Hệ điều hành 68
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Biểu Thức chính quy
1.1. Định nghĩa:
Ví dụ:
-(a+b+c) là BTCQ chỉ định 3 xâu a, b, c trên bộ
chữ {a, b, c}
-(a+b)* là BTCQ chỉ định mọi xâu trên {a, b}
-aa*bb* hay a+b+ là BTCQ chỉ định các xâu bắt
đầu bằng một số ký hiệu a, tiếp theo là một số
ký hiệu b trong đó ký hiệu a và b xuất hiện ít
nhất 1 lần
Giáo trình Kiến trúc máy tính và
Hệ điều hành 69
CHƯƠNG 3. BIỂU THỨC & VĂN PHẠM CHÍNH QUY
TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐÀ NẴNG
1. Biểu Thức chính quy
1.1. Định nghĩa:
Ví dụ:
-(b+)(a+ab)* là BTCQ chỉ định các xâu trên {a,
b} không chứa bb
-(0+1)*1 là BTCQ chỉ định các xâu là số nhị
phân lẻ