Ngôn ngữ chính quy vẫn chính quy — dù bạn làm gì với chúng

Mình luôn thấy thú vị khi nhận ra rằng: trong lĩnh vực này, cách chứng minh tốt nhất thường chỉ là bắt tay vào xây dựng cái máy.

Muốn chứng minh một lớp ngôn ngữ có tính chất đẹp? Đừng nói trừu tượng — xây cái máy làm đúng việc đó, rồi chỉ ra nó hoạt động. Bài này nói về chuyện đó.

Ở bài trước, mình đã giới thiệu DFA — loại máy đơn giản nhất kiểm tra xem chuỗi có khớp pattern hay không. Bài này mình sẽ làm hai việc: tập xây DFA từ đầu, rồi chứng minh lớp ngôn ngữ mà DFA nhận diện được đóng với phép bù, phép hợp, và phép giao.

"Đóng" nghĩa là nếu bạn bắt đầu với ngôn ngữ chính quy rồi áp dụng các phép toán này, kết quả luôn là ngôn ngữ chính quy. Không thoát ra được. Giống như nấu ăn trong bếp với nguyên liệu sẵn — bạn không bao giờ phải lo chuyện nấu ra thứ gì đó không ăn nổi khi đã có sẵn những nguyên liệu và công thức chuẩn trong tay.

Xây DFA bắt đầu bằng việc giao nhiệm vụ cho mỗi trạng thái

Kỹ thuật hữu ích nhất khi xây DFA là nghĩ mỗi trạng thái có một vai trò — mô tả ý nghĩa của việc đang ở trạng thái đó, dựa trên những gì đã đọc được từ đầu vào.

Hãy xây DFA nhận diện ngôn ngữ "tất cả chuỗi có ít nhất hai chữ a" trên bảng chữ cái a, b.

Vai trò mỗi trạng thái khá rõ ràng:

Để ý rằng chuyển trạng thái khi gặp b luôn quay lại chính trạng thái đó. Lý do đơn giản: b không ảnh hưởng đến số lượng a — nó không thay đổi những gì ta "biết" về đầu vào. Còn q2 là một "hố đen" theo nghĩa tích cực: đã thấy hai chữ a rồi thì mãi mãi vẫn đã thấy ít nhất hai chữ a, bất kể tiếp theo là gì.

Hình dung như đi xem nhà vậy. Bạn có checklist cần kiểm tra. q0 là "chưa tìm thấy điều kiện nào." q1 là "tìm được một, đang tìm cái thứ hai." q2 là "đủ cả hai điều kiện — căn nhà đạt." Một khi đã tick cả hai ô, không có gì trong chuyến đi xem nhà có thể bỏ tick được nữa.

Đảo câu hỏi — có DFA mới miễn phí

Bây giờ, còn "tất cả chuỗi có nhiều nhất hai chữ a" thì sao? Vai trò thay đổi một chút:

q3 là trạng thái bẫy (trap state) — vào rồi thì kẹt luôn, không ra được. Nó giống kiểu nấu cháy món ăn vậy. Đã thấy quá nhiều chữ a, và không có đầu vào nào tiếp theo có thể cứu được.

Điểm quan trọng: q3 bẫy vĩnh viễn các đầu vào vi phạm. Mỗi ký tự trong DFA phải đi đâu đó (hàm chuyển là toàn phần), nên bạn cần một trạng thái để hấp thụ những đầu vào đã vi phạm pattern. Trạng thái bẫy chính là giải pháp.

Tìm chuỗi con đòi hỏi nhớ tiến trình

Ví dụ thú vị hơn: xây DFA nhận diện chuỗi chứa baba như chuỗi con. Cái này khó hơn vì bạn cần theo dõi đã khớp được bao nhiêu ký tự của từ mục tiêu.

Vai trò:

Phần khó nằm ở các chuyển trạng thái khi tiến trình bị "mất một phần." Từ q2 (đã thấy "ba"), nếu gặp thêm a, bạn có "baa" — pattern bị phá, quay về q0. Nhưng từ q3 (đã thấy "bab"), nếu gặp thêm b, bạn có "babb" — kết thúc bằng b, tức vẫn có khởi đầu tiềm năng cho baba mới. Vì vậy q3 đi đến q1 khi gặp b, không phải q0.

Giống tập đàn piano vậy. Bạn đang cố chơi đúng chuỗi bốn nốt. Nếu bấm sai nốt giữa chừng, bạn không phải lúc nào cũng bắt đầu lại từ đầu — đôi khi nốt sai đó lại chính là nốt đầu tiên của lần thử mới. "Trạng thái" (bạn đang ở đâu trong chuỗi) cần tính đến những chỗ chồng chéo kiểu này.

Muốn thấy ý tưởng "phục hồi từ chỗ chồng chéo" này đẩy đến cực hạn — khớp nhiều pattern cùng lúc bằng một automaton duy nhất — thì Aho–Corasick là thuật toán kinh điển. Cùng mẹo, chỉ là tổng quát hoá lên:

Ngôn ngữ chính quy được định nghĩa bởi khả năng nhận diện của DFA

Giờ đến định nghĩa quan trọng. Ngôn ngữ chính quy (regular language) là bất kỳ ngôn ngữ nào có thể được nhận diện bởi một DFA nào đó.

Mỗi DFA mình xây ở trên đều chứng minh ngôn ngữ tương ứng là chính quy. Ngôn ngữ "ít nhất hai chữ a" là chính quy vì mình đã xây được DFA cho nó. Ngôn ngữ "chứa baba" là chính quy vì mình đã xây được DFA cho nó.

Sau này mình sẽ chỉ ra biểu thức chính quy mô tả chính xác cùng lớp ngôn ngữ. Nhưng trước mắt, mình cứ tạm định nghĩa: "ngôn ngữ chính quy là ngôn ngữ được DFA nhận diện".

Tính đóng nghĩa là không thoát ra được

Một lớp ngôn ngữ đóng (closed) với một phép toán nếu áp dụng phép toán đó lên ngôn ngữ trong lớp luôn cho ra ngôn ngữ khác cũng thuộc lớp.

Đây là tính chất rất mạnh. Nó có nghĩa là ngôn ngữ chính quy khép kín với các phép toán này. Bạn kết hợp chúng, phủ định chúng, lấy giao chúng — vẫn ở trong cùng một lớp.

Nghĩ như thể loại nhạc vậy. Lấy hai bài jazz trộn lại, vẫn ra jazz. Lấy bài jazz phát ngược lại — vẫn jazz (ít nhất là có thể cãi vậy). Thể loại "đóng" với các phép toán này. Ngôn ngữ chính quy cũng thế — đóng với phép bù, hợp, giao, nối, và Kleene star.

Phép bù: chỉ cần đảo trạng thái chấp nhận

Đây là chứng minh tính đóng đơn giản nhất, và nó đẹp vì cách xây dựng cực kỳ gọn.

Định lý: Nếu A là ngôn ngữ chính quy thì phần bù Ā cũng chính quy.

Ý tưởng chứng minh: Lấy DFA của A. Đổi tất cả trạng thái chấp nhận thành từ chối và ngược lại. Xong.

Hình thức: cho DFA M = (Q, Σ, δ, q₀, F), xây M' = (Q, Σ, δ, q₀, Q − F). Mọi thứ giữ nguyên trừ tập trạng thái chấp nhận.

Tại sao nó đúng: Mỗi chuỗi hoặc kết thúc ở trạng thái chấp nhận (và được M chấp nhận) hoặc không (và bị M từ chối). Đảo trạng thái nào là "chấp nhận" sẽ đảo hoàn hảo kết quả. Nếu M chấp nhận chuỗi, M' từ chối, và ngược lại. Nên L(M') = phần bù của L(M).

Để chứng minh chặt chẽ, ta dùng phép chứng minh tập con hai chiều (bidirectional subset argument): chỉ ra L(M') ⊆ Ā và Ā ⊆ L(M'). Nhưng trực giác thì rõ ràng: cùng máy, ngược kết quả.

Nhớ DFA tìm chuỗi con "baba" lúc nãy không? Phần bù của nó — "chuỗi mà baba KHÔNG xuất hiện" — dùng đúng các trạng thái và chuyển tiếp y chang. Bạn chỉ đổi q0, q1, q2, q3 thành trạng thái chấp nhận và q4 thành trạng thái từ chối. Cái máy kiểm tra sự có mặt của pattern, chỉ chỉnh một chút, cũng là cái máy kiểm tra sự vắng mặt của nó.

Phép hợp: chạy hai máy song song

Cái này phức tạp hơn. Mình cần chứng minh rằng nếu A₁ và A₂ là ngôn ngữ chính quy thì A₁ ∪ A₂ cũng chính quy.

Ý tưởng: Xây DFA mới mô phỏng cả hai DFA gốc cùng lúc. Ở mỗi bước, nó theo dõi vị trí cả hai máy nếu chúng xử lý cùng đầu vào một cách độc lập.

Phép xây dựng tích Descartes (Cartesian product)

Cho:

• M₁ = (Q₁, Σ, δ₁, q₁, F₁) nhận diện A₁
• M₂ = (Q₂, Σ, δ₂, q₂, F₂) nhận diện A₂

Xây M = (Q, Σ, δ, q₀, F) với:

Hàm chuyển chạy cả hai máy độc lập. Nếu bạn đang ở trạng thái (r, s) và đọc ký tự a, thành phần thứ nhất đi theo M₁ từ r khi gặp a, thành phần thứ hai đi theo M₂ từ s khi gặp a.

Điều kiện chấp nhận biểu diễn phép "hoặc" — nếu một trong hai thành phần kết thúc ở trạng thái chấp nhận của máy tương ứng, máy kết hợp chấp nhận.

Ví dụ cụ thể

Giả sử M₁ nhận diện "chuỗi bắt đầu bằng a" và M₂ nhận diện "chuỗi b" (chỉ đúng một ký tự b, không gì khác).

M₁ có trạng thái q0, q1, q2 (q1 là chấp nhận — đã thấy a đầu tiên; q2 là bẫy — bắt đầu bằng b). M₂ có trạng thái p0, p1, p2 (p1 là chấp nhận — đọc đúng "b"; p2 là bẫy).

Máy tích có trạng thái kiểu (q0,p0), (q1,p2), v.v. Nhưng không phải tất cả cặp đều đến được từ trạng thái bắt đầu. Bạn chỉ cần vẽ những cặp thật sự đến được.

Trạng thái chấp nhận: (q1,p2) vì q1 ∈ F₁, và (q2,p1) vì p1 ∈ F₂. Máy chấp nhận "chuỗi bắt đầu bằng a" HOẶC "chuỗi b" — chính xác là A₁ ∪ A₂.

Lưu ý tích Descartes có thể có 3 × 3 = 9 trạng thái, nhưng chỉ 4 cái đến được. Các trạng thái còn lại tồn tại trên lý thuyết nhưng không cần vẽ.

Hình dung như hai giám khảo ẩm thực chấm cùng một món ăn đồng thời vậy. Mỗi giám khảo có tiêu chí riêng (DFA riêng). Món ăn "đạt" nếu một trong hai giám khảo cho qua. Tích Descartes theo dõi đánh giá của cả hai giám khảo ở mỗi bước, và kết quả cuối cùng là "đạt nếu ít nhất một giám khảo đồng ý."

Phép giao có miễn phí từ phép bù và phép hợp

Mẹo hay đây. Mình đã chứng minh tính đóng với phép bù và phép hợp. Định luật De Morgan cho phép chúng ta có luôn phép giao mà không cần tốn công chứng minh lại:

A₁ ∩ A₂ = phần bù của (phần bù(A₁) ∪ phần bù(A₂))

Vì ngôn ngữ chính quy đóng với phép bù và phép hợp, mình xâu chuỗi các phép toán:

1. Lấy bù A₁ → chính quy (đóng với phép bù)
2. Lấy bù A₂ → chính quy (đóng với phép bù)
3. Hợp chúng lại → chính quy (đóng với phép hợp)
4. Lấy bù kết quả → chính quy (đóng với phép bù)

Mỗi bước giữ nguyên tính chính quy, nên kết quả cuối cùng chính quy. Phép giao đóng.

Bạn cũng có thể chứng minh trực tiếp bằng cách sửa phép xây dựng tích Descartes — đổi điều kiện chấp nhận từ "một trong hai chấp nhận" thành "cả hai chấp nhận": F = {(r,s) : r ∈ F₁ AND s ∈ F₂}. Vậy là có phép giao thay vì phép hợp, cùng ý tưởng mô phỏng song song.

Cấu trúc chứng minh luôn giống nhau

Mọi chứng minh tính đóng đều theo pattern này:

Bước 3 là phần sáng tạo — xây dựng máy. Bước 4 là phần chặt chẽ — chứng minh đúng đắn. Với phép bù, cách xây dựng rất đơn giản (đảo trạng thái chấp nhận) và chứng minh là đối số hai chiều đơn giản. Với phép hợp, cách xây dựng là tích Descartes và chứng minh theo dõi cách mô phỏng song song bảo toàn điều kiện chấp nhận.

Cách tiếp cận "chứng minh bằng cách xây" này là đặc trưng của lý thuyết tính toán (computability theory). Bạn không chỉ chỉ ra thứ gì đó tồn tại — bạn chỉ ra cách xây nó. Và điều đó rất thỏa mãn.

Còn thiếu gì

Mình đã chứng minh tính đóng với phép bù, hợp, và giao. Nhưng còn phép nối (concatenation) và Kleene star thì sao?

Hai cái này khó hơn. Mẹo tích Descartes không áp dụng được cho phép nối vì bạn cần biết cắt ở đâu trên chuỗi đầu vào giữa hai máy. DFA đọc từ trái sang phải và không quay lại được — nên nó không thể thử các điểm cắt khác nhau.

Để xử lý phép nối và Kleene star, mình cần công cụ mới: tính không đơn định (nondeterminism). Đó là chủ đề bài tiếp theo.

Vài điều mình rút ra

• Chiến lược hiệu quả nhất để xây DFA là giao cho mỗi trạng thái một vai trò — mô tả bằng ngôn ngữ thường trạng thái đó "biết" gì về đầu vào
• Trạng thái bẫy hấp thụ các đầu vào đã vi phạm pattern vĩnh viễn — chúng cần thiết vì mỗi trạng thái phải có chuyển tiếp cho mọi ký tự
• Tìm chuỗi con trong DFA đòi hỏi theo dõi tiến trình từng phần và xử lý cẩn thận các pattern chồng chéo
• Ngôn ngữ chính quy được định nghĩa là ngôn ngữ mà DFA nào đó nhận diện được — đây là điểm xuất phát hình thức
• Tính đóng với phép toán nghĩa là không thoát khỏi lớp khi áp dụng phép toán đó — ngôn ngữ chính quy khép kín đáng kinh ngạc
• Lấy bù DFA rất đơn giản: cùng máy, đảo trạng thái chấp nhận — chứng minh bằng lập luận tập con hai chiều gọn gàng
• Phép xây dựng tích Descartes chứng minh tính đóng với phép hợp bằng cách chạy hai DFA song song và chấp nhận nếu một trong hai chấp nhận
• Phép giao có miễn phí từ định luật De Morgan (hoặc trực tiếp, bằng cách đổi điều kiện chấp nhận của tích Descartes từ "hoặc" thành "và")
• Mọi chứng minh tính đóng đều theo cùng cấu trúc: giả sử chính quy → DFA tồn tại → xây DFA mới → chứng minh đúng đắn
• Phép nối và Kleene star không xử lý được bằng tích Descartes — chúng cần tính không đơn định, sẽ nói ở bài sau

Điểm cuối cùng là cái mình mong chờ nhất. Mình đã làm việc hoàn toàn trong thế giới đơn định — mỗi trạng thái có đúng một chuyển tiếp cho mỗi ký tự, không mơ hồ, không lựa chọn. Tính không đơn định phá vỡ ràng buộc đó, và hoá ra nó là chìa khóa mở khoá các tính chất đóng còn lại mà không làm chứng minh phức tạp quá mức.