0.5 Văn phạm chính quy và các tính chất  (Page 4/5)

Hơn nữa n không lớn hơn số trạng thái của FA nhỏ nhất chấp nhận L.

Chứng minh

Nếu một ngôn ngữ L là ngôn ngữ chính quy thì nó sẽ được chấp nhận bởi một DFA M (Q, , , q0, F) với n trạng thái.

Xét chuỗi nhập z có m ký hiệu được cho như trong bổ đề, vậy z = a1a2 ... am, m  n, và với mỗi i = 1, 2, ..., m , ta đặt (q0, a1a2...ai) = qi. Do m  n nên cần phải có ít nhất n+1 trạng thái trên đường đi của ôtômát chấp nhận chuỗi z. Trong n+1 trạng thái này phải có hai trạng thái trùng nhau vì ôtômát M chỉ có n trạng thái phân biệt, tức là có hai số nguyên j và k sao cho 0  j<k  n thỏa mãn qj = qk. Đường đi nhãn a1a2 ... am trong sơ đồ chuyển của M có dạng như sau:

Hình 4.4 - Đường đi trong sơ đồ chuyển của DFA M

Vì j<k nên chuỗi aj+1...ak có độ dài ít nhất bằng 1 và vì k  n nên độ dài đó không thể lớn hơn n.

Nếu qm là một trạng thái trong F, nghĩa là chuỗi a1a2...am thuộc L(M), thì chuỗi a1a2...aj ak+1ak+2...am cũng thuộc L(M) vì có một đường dẫn từ q0 đến qm ngang qua qj nhưng không qua vòng lặp nhãn aj+1... ak. Một cách hình thức, ta có :

d(q0, a1a2...aj ak+1ak+2...am) = d (d(q0, a1a2...aj), ak+1ak+2...am)

= d (qj, ak+1ak+2...am)

= d (qk, ak+1ak+2...am)

= qm

Vòng lặp trong hình trên có thể được lặp lại nhiều lần - thực tế, số lần muốn lặp là tùy ý, do đó chuỗi a1...aj (aj+1...ak)i ak+1...am  L(M), i  0. Điều ta muốn chứng tỏ ở đây là với một chuỗi có độ dài bất kỳ được chấp nhận bởi một FA, ta có thể tìm được một chuỗi con gần với chuỗi ban đầu mà có thể "bơm" - lặp một số lần tùy ý - sao cho chuỗi mới thu được cũng được chấp nhận bởi FA.

Đặt u = a1...aj, v = aj+1...ak và w = ak+1...am.

Ta có điều phải chứng minh.

Ứng dụng của bổ đề bơm

Bổ đề bơm rất có hiệu quả trong việc chứng tỏ một tập hợp không là tập hợp chính quy. Phương pháp chung để ứng dụng nó dùng phương pháp chứng minh “phản chứng” theo dạng sau :

1. Chọn ngôn ngữ mà bạn cần chứng tỏ đó không là ngôn ngữ chính quy.
2. Chọn hằng số n, hằng số được đề cập đến trong bổ đề bơm.
3. Chọn chuỗi z thuộc L. Chuỗi z phải phụ thuộc nghiêm ngặt vào hằng số n đã chọn ở bước 2.
4. Giả thiết phân chuỗi z thành các chuỗi con u, v, w theo ràng buộc | uv |  n và | v |  1
5. Mâu thuẫn sẽ phát sinh theo bổ đề bơm bằng cách chỉ ra với u, v và w xác định theo giả thiết, có tồn tại một số i mà ở đó uviw  L. Từ đó có thể kết luận rằng L không là ngôn ngữ chính quy. Chọn lựa giá trị cho i có thể phụ thuộc vào n, u, v và w.

Ta có thể phát biểu một cách hình thức nội dung của bổ đề bơm như sau :

(L)(n)(z)[ z thuộc L và | z |  n ta có

(u, v, w)(z = uvw, | uv |  n, | v |  1 và (i)(uviw thuộc L))]

Thí dụ 4.5 : Chứng minh tập hợp L = { 0i2  i là số nguyên, i  1} (L chứa tất cả các chuỗi số 0 có độ dài là một số chính phương) là tập không chính quy.

Chứng minh

Giả sử L là tập chính quy và tồn tại một số n như trong bổ đề bơm.

Xét từ z =0n2. Theo bổ đề bơm, từ z có thể viết là z = uvw với 1  | v |  n và uviw  L, i  0. Trường hợp cụ thể, xét i = 2 : ta phải có uv2w  L.

Mặt khác : n2<| uv2w |  n2 + n<(n+1)2.

Do n2 và (n+1)2 là 2 số chính phương liên tiếp nên | uv2w | không thể bằng một số chính phương, vậy uv2w  L.