0.2 Ôtômat hữu hạn và biểu thức chính quy  (Page 11/16)

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

Câu hỏi :

?

Như trên ta nói, biểu thức chính quy dùng ký hiệu cho một lớp ngôn ngữ. Bạn

hãy thử liệt kê một vài chuỗi và hình dung lớp ngôn ngữ được ký hiệu bởi biểu

thức chính quy r = 01*+ 1 trên ?

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*r thà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 :

1.r + s = s + r2. r + r = r

3.r + (s+t) = (r+s) + t4. r (st) = (rs) t

5. r (s+t) = rs + rt6. (r+s) t = rt + st

7. r =  r = r8. r = r = 

9. r +  = r10.* = 

11. ( + r)* = r*12.r + r* = r*

13. ( r* )* = r*14. ( r* s* )* = (r+s)*