biểu thức chính quy (RE : Regular Expressions)

Định nghĩa

Cho Σ là một bộ chữ cái. Biểu thức chính quy trên Σ và các tập hợp mà chúng mô tả được định nghĩa một cách đệ quy như sau:

1) ∅ size 12{ emptyset } {} là biểu thức chính quy ký hiệu cho tập rỗng

2) ε là biểu thức chính quy ký hiệu cho tập {ε}

3) ∀a ∈ Σ, a là biểu thức chính quy ký hiệu cho tập {a}

4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs) và( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R size 12{ union } {}S, RS, R^* tương ứng.

Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lưu ý rằng thứ tự ưu tiên của các phép toán xếp theo thứ tự giảm dần là: phép bao đóng, phép nối kết, phép hợp.

Chẳng hạn : Biểu thức ((0(1^*)) + 1) có thể viết là 01^*+ 1.

Phép toán bao đóng dương cũng có thể được sử dụng khi viết biểu thức chính quy. Ta có thể viết rút gọn rr^* hay r^*rthành r⁺.

Nếu cần thiết phân biệt thì ta sẽ dùng ký hiệu r cho biểu thức chính quy r và L(r) cho ngôn ngữ được ký hiệu bởi biểu thức chính quy r; ngược lại một cách tổng quát, ta có thể dùng r cho cả hai.

Thí dụ 3.11 : Một số biểu thức chính quy ký hiệu cho các ngôn ngữ :

. 00 là biểu thức chính quy biểu diễn tập {00}.

. (0+1)* ký hiệu cho tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng

= {e, 0, 1, 00, 01, 10, 11, 010, 011, 0010 ... }

. (0+1)^*00(0+1)* ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp.

= {00, 000, 100, 0000, 0001, 1000, 1001, 011001, ... }

. (1+10)^* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số 0 liên tiếp = {e, 1, 10, 11, 1010, 111, 101010, ... }

. (0+ε)(1+10)^* ký hiệu cho tất cả các chuỗi không có hai số 0 liên tiếp.

= {e, 0, 01, 010, 1, 10, 01010, 0111, ... }

. (0+1)^*011 ký hiệu cho tất cả các chuỗi 0, 1 tận cùng bởi 011.

= {011, 0011, 1011, 00011, 11011, ... }

. 0^*1^*2^* ký hiệu cho tất cả các chuỗi có một số bất kỳ các số 0, theo sau là một số bất kỳ số 1 và sau nữa là một số bất kỳ số 2.

= {e, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... }

. 00*11*22* ký hiệu cho tất cả các chuỗi trong tập 0^*1^*2^* với ít nhất một trong mỗi ký hiệu. 00^*11^*22^* có thể được viết gọn thành 0⁺1⁺2⁺

Thí dụ 3.12 : Biểu thức chính quy ký hiệu cho tập hợp các chuỗi tên biến đúng trong ngôn ngữ lập trình Pascal :

Một chuỗi tên biến (identifiers) được gọi là hợp lệ trong một chương trình Pascal nếu như nó bắt đầu bằng ít nhất một chữ cái và theo sau đó là các chữ cái, số, ký hiệu underline hoặc một vài ký hiệu cho phép khác trên bàn phím máy tính.

Biểu thức chính quy có dạng như sau :

r = (A + …+ Z + a + … + z) (A + …+ Z + a + … + z + 0 + … + 9 + _ + … )^*

Thí dụ 3.13 : Biểu thức chính quy ký hiệu cho tập hợp các số nguyên trong ngôn ngữ lập trình Pascal :

Một chuỗi số nguyên trong một chương trình Pascal có thể bắt đầu bằng dấu âm (-) hoặc dấu dương (+) hay không chứa ký hiệu dấu, và theo sau đó là một chuỗi các ký hiệu số với ít nhất là một số.

Biểu thức chính quy có dạng như sau :

r = ( ‘+’ + ‘-‘ + ε) ( 0 + … + 9 (0 + … +9 )^*

Nhận xét : Thông thường, việc tìm một biểu thức chính quy ký hiệu cho một ngôn ngữ khó hơn việc xác định ngôn ngữ được ký hiệu bởi một biểu thức chính quy vì không có giải thuật cho loại bài toán này.

Một số tính chất đại số của biểu thức chính quy

Dễ dàng chứng minh rằng, nếu cho r, s, t là các biểu thức chính quy thì ta có các đẳng thức sau :

Trong đó, ta có r = s có nghĩa là L(r) = L(s).