Một số tính chất của tập hợp chính quy

Bổ đề bơm cho tập hợp chính quy

Một trong những nguyên lý hiệu quả là "Bổ đề bơm", đây là một công cụ mạnh giúp chứng minh các ngôn ngữ không là chính quy. Đồng thời, nó cũng thực sự hữu ích trong việc phát triển các giải thuật liên quan đến các ôtômát, chẳng hạn như một ngôn ngữ được chấp nhận bởi một FA cho trước là hữu hạn hay vô hạn ?

BỔ ĐỀ 4.1: (BỔ ĐỀ BƠM)

Nếu L là tập hợp chính quy thì có tồn tại hằng số n sao cho nếu z là một từ bất kỳ thuộc L và | z | ≤ n, ta có thể viết z = uvw với | uv | ≤ n, | v | ≥ 1 và ∀i ≥ 0, ta có uvⁱw ∈ L.

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, Σ, δ, q₀, 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 = a₁a₂ ... a_m, m ≥ n, và với mỗi i = 1, 2, ..., m , ta đặt δ(q₀, a₁a₂...a_i) = q_i. 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 q_j = q_k. Đường đi nhãn a₁a₂ ... a_m 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 a_j+1...a_k 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 q_m là một trạng thái trong F, nghĩa là chuỗi a₁a₂...a_m thuộc L(M), thì chuỗi a₁a₂...a_j a_k+1a_k+2...a_m cũng thuộc L(M) vì có một đường dẫn từ q₀ đến q_m ngang qua q_j nhưng không qua vòng lặp nhãn a_j+1... a_k. Một cách hình thức, ta có :

d(q₀, a₁a₂...a_j a_k+1a_k+2...a_m) = d (d(q₀, a₁a₂...a_j), a_k+1a_k+2...a_m)

= d (q_j, a_k+1a_k+2...a_m)

= d (q_k, a_k+1a_k+2...a_m)

= q_m

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 a₁...a_j (a_j+1...a_k)ⁱ a_k+1...a_m ∈ 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 = a₁...a_j, v = a_j+1...a_k và w = a_k+1...a_m.

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à ở đó uvⁱw ∉ 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) ∃ ( ∀ z)[ z thuộc L và | z | ≥ n ta có

( ∃ u, v, w)(z = uvw, |uv | ≤ n, | v | ≥ 1 và ( ∀ i)(uv i w thuộc L))]

Thí dụ 4.5 : Chứng minh tập hợp L = { 0ⁱ² | 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 =0ⁿ². Theo bổ đề bơm, từ z có thể viết là z = uvw với 1 ≤ | v | ≤ n và uvⁱw ∈ L, ∀i ≥ 0. Trường hợp cụ thể, xét i = 2 : ta phải có uv²w ∈ L.

Mặt khác : n² < | uv²w | ≤ n² + n < (n+1)².

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

Điều này dẫn đến sự mâu thuẫn, vậy giả thiết ban đầu là sai. Suy ra L không là tập chính quy.

Tính chất đóng của tập hợp chính quy

Có nhiều phép toán trên ngôn ngữ chuyên sử dụng cho tập hợp chính quy, mà cho phép khi áp dụng chúng vào tập hợp chính quy thì vẫn giữ được các tính chất của tập chính quy. Nếu một lớp ngôn ngữ nào đó "đóng" với một phép toán cụ thể, ta gọi đó là tính chất đóng của lớp ngôn ngữ này.

ĐỊNH LÝ 4.3 : Tập hợp chính quy đóng với các phép toán: hợp, nối kết và bao đóng Kleen.

Chứng minh

Hiển nhiên từ định nghĩa của biểu thức chính quy.

ĐỊNH LÝ 4.4 : Tập hợp chính quy đóng với phép lấy phần bù. Tức là, nếu L là tập chính quy và L ⊆ Σ * thì Σ * - L là tập chính quy.

Chứng minh

Gọi L là L(M) cho DFA M (Q, Σ 1 , δ , q 0 , F) và L ⊆ Σ * .

Trước hết, ta giả sử Σ 1 = Σ vì nếu có ký hiệu thuộc Σ 1 mà không thuộc Σ thì ta có thể bỏ các phép chuyển trong M liên quan tới các ký hiệu đó. Do L ⊆ Σ * nên việc xóa như vậy không ảnh hưởng tới M. Nếu có ký hiệu thuộc Σ nhưng không thuộc Σ 1 thì các ký hiệu này không xuất hiện trong L. Ta thiết kế thêm một trạng thái "chết" d trong M sao cho δ (d, a) = d, ∀ a ∈Σ và δ (q, a) = d, ∀ q ∈ Q và a ∈ Σ - Σ 1 .

Bây giờ, để chấp nhận Σ * - L, ta hoàn thiện các trạng thái kết thúc của M. Nghĩa là, đặt M’ = (Q, Σ , δ , q 0 , Q - F). Ta có M’ chấp nhận từ w nếu δ (q 0 ,w) ∈ Q - F, suy ra w Î Σ * - L.

ĐỊNH LÝ 4.5: Tập hợp chính quy đóng với phép giao

Chứng minh

Do ta có công thức biến đổi :

Nên theo các định lý trên, suy ra được tập

là tập chính quy.