Mô tả pattern là một chuyện — kiểm tra nó bằng máy lại là chuyện khác

Có một điều mình mới thấm gần đây: mô tả một pattern và kiểm tra xem chuỗi nào khớp pattern đó là hai chuyện rất khác nhau.

Mô tả thì dễ. Bạn nói "bao nhiêu chữ a cũng được, rồi tiếp theo bao nhiêu chữ b cũng được" — ai nghe cũng hiểu. Nhưng nếu bạn phải xây một cỗ máy — một cỗ máy rất đơn giản, không giấy nháp, không bộ nhớ ngoài chỗ nó đang đứng — máy đó có kiểm tra được pattern này không?

Hoá ra là được. Cỗ máy đó gọi là ôtômat hữu hạn đơn định (deterministic finite automaton — DFA). Đây là mô hình tính toán đơn giản nhất có thể, nhưng nó nhận diện được rất nhiều loại pattern.

Ở bài trước, mình đã đi qua các khái niệm nền: bảng chữ cái, chuỗi, ngôn ngữ, và ba phép toán (hợp, nối, Kleene star). Bài này tiếp nối ngay từ đó — trước hết hình thức hoá biểu thức chính quy, rồi giới thiệu cỗ máy thật sự kiểm tra pattern.

Biểu thức chính quy được xây đệ quy — từ dưới lên

Định nghĩa hình thức của biểu thức chính quy (regular expression) rất gọn vì nó đệ quy. Bạn bắt đầu từ ba thành phần nguyên tử, rồi kết hợp bằng ba phép toán. Hết. Mọi thứ còn lại đều xây từ đó.

Các quy tắc:

1. Bất kỳ ký tự nào trong bảng chữ cái đều là biểu thức chính quy
2. ε (chuỗi rỗng) là biểu thức chính quy
3. ∅ (tập rỗng) là biểu thức chính quy
4. Nếu R₁ và R₂ là biểu thức chính quy thì R₁ ∪ R₂ cũng vậy
5. Nếu R₁ và R₂ là biểu thức chính quy thì R₁R₂ (nối) cũng vậy
6. Nếu R là biểu thức chính quy thì R* cũng vậy

Đó là toàn bộ định nghĩa. Mọi biểu thức chính quy bạn từng viết đều truy ngược về sáu quy tắc này, áp dụng bao nhiêu lần đó.

Nghĩ như nấu ăn vậy. Bạn bắt đầu với nguyên liệu thô (ký tự đơn, ε, ∅). Rồi kết hợp bằng ba kỹ thuật (hợp, nối, Kleene star) — và tiếp tục kết hợp kết quả bằng chính những kỹ thuật đó, chồng lớp phức tạp lên cho đến khi ra một món tinh tế. Nước mắm pha cũng vậy — đường, chanh, nước mắm, tỏi ớt — nhưng cách bạn pha rồi chỉnh đi chỉnh lại tạo ra hàng trăm biến thể khác nhau.

Ký hiệu tắt hay gặp

Có hai cách viết tắt không nằm trong định nghĩa hình thức nhưng được xây từ đó:

• R⁺ = RR* (một lần trở lên)
• Rᵏ = R nối với chính nó k lần

Đây chỉ là tiện lợi thôi. Không thêm sức mạnh gì — bất cứ gì viết bằng R⁺ hay Rᵏ đều viết lại được bằng sáu quy tắc trên.

Ký hiệu L(R) tách mô tả khỏi ngôn ngữ

Điểm nhỏ nhưng quan trọng. Biểu thức chính quy R là một chuỗi ký hiệu — nó là mô tả. Ngôn ngữ mà nó mô tả được viết là L(R).

Khi bạn viết 0*1, đó là pattern. Khi bạn viết L(0*1), đó là tập hợp các chuỗi khớp pattern đó.

Một số giáo trình không phân biệt rõ, viết kiểu 0*1 = {1, 01, 001, ...}. Về mặt hình thức thì sai vì vế trái là mô tả, vế phải là tập hợp — hai loại đối tượng khác nhau. Nhưng bạn sẽ gặp cách viết này ngoài thực tế.

Thứ tự ưu tiên quan trọng hơn bạn tưởng

Giống như số học có "nhân trước cộng," biểu thức chính quy cũng có thứ tự ưu tiên:

1. Kleene star (cao nhất — áp dụng trước)
2. Nối (concatenation)
3. Hợp (union — thấp nhất — áp dụng cuối)

Nghĩa là ab* KHÔNG phải (ab)*. Nó là a(b*) — chữ a rồi theo sau bởi không hoặc nhiều chữ b.

Giống hệt cách 2 + 3 × 4 bằng 14 (không phải 20) vì phép nhân ưu tiên hơn phép cộng. Dấu ngoặc dùng khi bạn muốn đổi thứ tự mặc định.

Tập rỗng là hố đen của phép nối

Có một điều ban đầu làm mình bối rối. Khi nối bất cứ gì với tập rỗng, kết quả luôn là tập rỗng.

L(R ∘ ∅) = ∅ — bất kể R là gì.

Tại sao? Vì phép nối cần một chuỗi từ mỗi toán hạng. Nếu một bên không có chuỗi nào, bạn không thể nối gì cả. Như kiểu bạn có bánh mì nhưng không có nhân — mà công thức đòi hỏi cả hai.

Nhưng chuỗi rỗng thì khác:

L(R ∘ ε) = L(R) — nối với chuỗi rỗng không thay đổi gì.

∅ huỷ diệt phép nối. ε thì vô hình với phép nối. ∅ vô hình với phép hợp.

Vậy biểu thức chính quy đi được xa cỡ nào?

Đây là câu hỏi mình thấy thú vị nhất. Mình đã xây xong bộ ký hiệu với ba phép toán. Nó mô tả được mọi ngôn ngữ không? Hay có pattern nào quá phức tạp?

Giữ câu hỏi đó trong đầu. Mình sẽ không trả lời đầy đủ cho đến khi tới bổ đề bơm (pumping lemma) ở bài sau. Nhưng gợi ý trước: có những ngôn ngữ mà không biểu thức chính quy nào mô tả được. Và chứng minh điều đó là một trong những lập luận đẹp nhất trong khoa học máy tính.

Giờ thì chuyển từ mô tả pattern sang kiểm tra chúng.

DFA là cỗ máy đọc từng ký tự, không bao giờ quay lại

Tưởng tượng bạn là bảo vệ kiểm tra thẻ ở cổng. Bạn có bộ quy tắc rất cụ thể:

• Bắt đầu ở trạng thái "chờ"
• Khi ai đưa thẻ, bạn kiểm tra từng thông tin một
• Dựa vào thông tin vừa thấy và trạng thái hiện tại, bạn chuyển sang trạng thái mới
• Cuối cùng, bạn hoặc ở trạng thái "cho vào" hoặc "từ chối"
• Bạn không được quay lại kiểm tra thông tin đã xem rồi

Đó là DFA. Một cỗ máy gồm:

• Tập hữu hạn các trạng thái (các trạng thái tinh thần có thể có khi kiểm tra)
• Bảng chữ cái (các ký tự máy có thể đọc)
• Hàm chuyển trạng thái (với mỗi cặp trạng thái + ký tự, có đúng một trạng thái kế tiếp)
• Trạng thái bắt đầu (nơi tính toán khởi đầu)
• Tập trạng thái chấp nhận (kết quả "có")

Định nghĩa hình thức (từ Definition 1.5 của Sipser) viết dưới dạng bộ 5 (5-tuple): (Q, Σ, δ, q₀, F).

Hàm chuyển trạng thái δ là trái tim của máy. Nó nhận một trạng thái và một ký tự, trả về đúng một trạng thái kế tiếp. Không mơ hồ, không lựa chọn — đó là lý do gọi nó đơn định (deterministic).

DFA trông như đồ thị có hướng với bộ từ vựng riêng

Khi vẽ DFA, nó là đồ thị có hướng với:

• Hình tròn là trạng thái
• Mũi tên là chuyển trạng thái (gắn nhãn ký tự)
• Trạng thái bắt đầu có mũi tên đi vào từ hư không
• Trạng thái chấp nhận có hình tròn đôi
• Mỗi trạng thái có đúng một mũi tên đi ra cho mỗi ký tự trong bảng chữ cái

Ví dụ cụ thể: DFA sau nhận diện chuỗi trên a, b mà các chữ a không bao giờ bị theo sau bởi chữ b rồi lại chữ a. Nói cách khác: tất cả a đến trước, rồi tất cả b.

Trạng thái q0, q1, và q2 là trạng thái chấp nhận (vẽ bằng hình tròn đôi trong sơ đồ thật). q3 là "trạng thái bẫy" — vào rồi thì không ra được, và chuỗi bị từ chối.

Tính toán chỉ là đi theo mũi tên

Cho một chuỗi đầu vào, tính toán hoạt động như sau:

1. Bắt đầu ở trạng thái khởi đầu
2. Đọc ký tự đầu tiên
3. Đi theo mũi tên gắn nhãn ký tự đó đến trạng thái kế tiếp
4. Đọc ký tự tiếp theo, đi theo mũi tên tương ứng
5. Lặp lại cho đến hết chuỗi
6. Nếu kết thúc ở trạng thái chấp nhận → chấp nhận. Ngược lại → từ chối.

Thử chạy chuỗi aabb trên DFA ở trên:

Khoan — kết thúc ở q3 (từ chối). Nhưng aabb đáng lẽ phải là "a rồi b" chứ. Mình xem lại DFA... Đúng rồi, q1 chuyển sang q3 khi gặp b, nghĩa là khi đã thấy a rồi gặp b thì vào trạng thái bẫy luôn.

DFA này sai cho ngôn ngữ đó. Dùng DFA đúng từ bài giảng: DFA mà q1 → q4 khi gặp b, và q4 là trạng thái chấp nhận cho giai đoạn "đã thấy b sau a."

Đây là DFA đúng cho "a rồi b" (ít nhất một a, ít nhất một b):

Ở đây q4 là trạng thái chấp nhận duy nhất. q2 là trạng thái "chết" — khi phát hiện vi phạm pattern, bạn kẹt ở đó vĩnh viễn.

Chạy thử aabb:

Trạng thái cuối: q4 (chấp nhận). Chuỗi aabb khớp pattern.

Chạy thử abab:

Trạng thái cuối: q2 (từ chối). Chuỗi abab không khớp vì chữ a xuất hiện sau chữ b.

Mỗi trạng thái trong DFA có một "công việc"

Đây là thứ giúp mình hiểu DFA dễ hơn nhiều. Thay vì nghĩ trạng thái là nhãn trừu tượng, gán cho mỗi trạng thái một vai trò — mô tả ý nghĩa của việc đang ở trạng thái đó với phần đầu vào đã đọc.

Với DFA ở trên:

Giống như nấu phở vậy. Bạn hoặc đang "sơ chế nguyên liệu," "ninh xương," "nêm nếm nước dùng," hoặc "cháy nồi rồi không cứu được." Mỗi giai đoạn quyết định bạn cần làm gì tiếp. DFA cũng vậy — trạng thái hiện tại mã hoá mọi thứ bạn cần biết về phần đã đọc.

Điểm mấu chốt: trạng thái hiện tại là dạng bộ nhớ duy nhất của DFA. Nó không nhớ chính xác chuỗi đã đọc — chỉ nhớ trạng thái nó đang ở. Đó là lý do gọi nó "hữu hạn." Và đó cũng là giới hạn của nó — nhưng chuyện đó để sau.

Ngôn ngữ của DFA là tập tất cả chuỗi nó chấp nhận

Mỗi DFA định nghĩa một ngôn ngữ: tập tất cả chuỗi nó chấp nhận. Viết là L(M) với M là DFA.

Điều này liên hệ trực tiếp với biểu thức chính quy. Ngôn ngữ của DFA ở trên chính là ngôn ngữ mô tả bởi biểu thức chính quy a⁺b⁺ — một hoặc nhiều a theo sau bởi một hoặc nhiều b.

Và câu hỏi lớn từ bài trước: có biểu thức chính quy cho mọi DFA không? Và ngược lại, có DFA cho mọi biểu thức chính quy không?

Câu trả lời cho cả hai là có. Sự tương đương đó là một trong những kết quả nền tảng của lĩnh vực này, và mình sẽ chứng minh hình thức ở bài sau. Nhưng giờ thì biết rằng hai hệ hình thức — một trông như đại số (biểu thức chính quy), một trông như cỗ máy có mũi tên (DFA) — mô tả đúng cùng một lớp ngôn ngữ: ngôn ngữ chính quy (regular languages).

DFA khác nhau có thể nhận diện ngôn ngữ khác nhau — và chứng minh chỉ cần một chuỗi

Làm sao chứng minh hai DFA nhận diện ngôn ngữ khác nhau? Tìm một chuỗi duy nhất mà máy này chấp nhận còn máy kia từ chối.

Vậy thôi. Một phản ví dụ là đủ để thấy L(M₁) ≠ L(M₂).

Nhưng chứng minh hai DFA nhận diện cùng ngôn ngữ thì khó hơn nhiều. Bạn phải chỉ ra rằng mọi chuỗi đều được cả hai máy xử lý giống nhau. Một phản ví dụ phá vỡ bằng nhau; xác nhận bằng nhau đòi hỏi chứng minh toàn diện. Có thuật toán cho việc này (sẽ gặp sau), nhưng sự bất đối xứng đáng chú ý.

Lấy phần bù DFA dễ như đảo trạng thái chấp nhận

Đây là điều hay. Giả sử bạn có DFA nhận diện "chuỗi có ab là chuỗi con." Nếu bạn muốn ngược lại — chuỗi mà ab không bao giờ xuất hiện?

Lấy cùng DFA đó và hoán đổi trạng thái chấp nhận với không chấp nhận. Mọi chuỗi trước đây được chấp nhận giờ bị từ chối, và ngược lại. Ngôn ngữ phần bù được nhận diện bởi DFA phần bù.

Cách này hoạt động vì DFA xử lý mọi chuỗi đến cùng — nó luôn dừng ở một trạng thái nào đó. Nên việc đảo trạng thái nào đếm là "chấp nhận" sẽ đảo ngược hoàn toàn ngôn ngữ.

Nghĩ như buổi thi hát vậy. Ban giám khảo có phiếu chấm. Nếu bạn đảo ngưỡng đậu/rớt — ai trước đó đậu giờ rớt và ngược lại — bạn đã lấy phần bù tiêu chí tuyển chọn mà không thay đổi quá trình thi.

Tính chất này gọi là đóng dưới phép bù (closure under complementation), và đó là một trong những lý do ngôn ngữ chính quy "ngoan" về mặt toán học.

DFA ở khắp nơi trong đời thường — bạn chỉ không để ý thôi

Khái niệm DFA xuất hiện liên tục trong các hệ thống bạn dùng hàng ngày:

• Đèn giao thông chuyển xanh → vàng → đỏ → xanh theo bộ đếm thời gian (tín hiệu đầu vào). Mỗi màu là một trạng thái, chuyển đổi là đơn định.
• Máy bán nước tự động theo dõi bạn bỏ bao nhiêu tiền vào. Mỗi mức tiền là một trạng thái. Bỏ thêm xu thì chuyển sang trạng thái tiếp. "Trạng thái chấp nhận" là khi đủ tiền để ra hàng.
• Bộ điều khiển thang máy phản hồi yêu cầu tầng. Tầng hiện tại là trạng thái, nhấn nút là ký tự đầu vào điều khiển chuyển trạng thái.
• Kiểm tra email — khi bạn gõ địa chỉ email mà website hiện đỏ hoặc xanh, đó thường là DFA kiểm tra pattern từng ký tự.

Điểm chung là tất cả hệ thống này đều có bộ nhớ hữu hạn (số trạng thái cố định), quy tắc đơn định (cùng đầu vào luôn cho cùng chuyển trạng thái), và xử lý đầu vào tuần tự (từng sự kiện một). Đó chính xác là mô hình DFA.

Tiếp theo sẽ đi đâu

Giờ mình có hai cách mô tả ngôn ngữ chính quy: biểu thức chính quy (mô tả đại số) và DFA (máy kiểm tra). Tiếp theo sẽ là ôtômat hữu hạn không đơn định (nondeterministic finite automata — NFA) — máy có thể ở nhiều trạng thái cùng lúc — và chứng minh rằng chúng tương đương DFA dù trông có vẻ mạnh hơn.

Rồi đến bổ đề bơm, cho mình cách chứng minh một số ngôn ngữ không chính quy — thật sự vượt ngoài khả năng của mọi DFA hay biểu thức chính quy. Đó là khi giới hạn thật sự bắt đầu lộ diện.

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

• Biểu thức chính quy được định nghĩa đệ quy — xây từ nguyên tử (ký tự, ε, ∅) bằng ba phép toán (hợp, nối, Kleene star), và kết quả có thể kết hợp tiếp bằng chính những phép toán đó
• Ký hiệu L(R) tách mô tả (biểu thức chính quy) khỏi thứ được mô tả (ngôn ngữ) — lẫn lộn hai cái này giống như nhầm công thức nấu ăn với món ăn
• Thứ tự ưu tiên trong biểu thức chính quy — Kleene star trước, rồi nối, rồi hợp — có thể thay đổi hoàn toàn ngôn ngữ được mô tả
• Nối với tập rỗng huỷ hết mọi thứ (như nhân với 0), nhưng nối với chuỗi rỗng không thay đổi gì (như nhân với 1)
• DFA là bộ 5: trạng thái, bảng chữ cái, hàm chuyển trạng thái, trạng thái bắt đầu, và trạng thái chấp nhận — hàm chuyển trạng thái là thứ làm nó đơn định
• Mỗi trạng thái trong DFA có một "công việc" — gán vai trò cho trạng thái giúp hiểu và xây DFA dễ hơn nhiều
• Trạng thái hiện tại là bộ nhớ duy nhất của DFA — nó không nhớ chính xác đầu vào đã đọc, chỉ nhớ trạng thái đang ở
• DFA khác nhau có thể nhận diện ngôn ngữ khác nhau, và một chuỗi phản ví dụ duy nhất là đủ để chứng minh
• Lấy phần bù DFA chỉ cần đảo trạng thái chấp nhận — máy giữ nguyên, chỉ phán quyết thay đổi
• Biểu thức chính quy và DFA mô tả đúng cùng lớp ngôn ngữ (ngôn ngữ chính quy) — sự tương đương này là kết quả nền tảng sẽ chứng minh sau
• DFA ở khắp nơi trong đời thường: đèn giao thông, máy bán nước, thang máy, kiểm tra email — bất kỳ hệ thống nào có trạng thái hữu hạn và quy tắc đơn định

Điểm gần cuối là điều mình nhớ nhất. Hai hệ hình thức hoàn toàn khác nhau — một trông như đại số, một trông như cỗ máy với mũi tên — mà có đúng cùng sức mạnh biểu diễn. Không phải "gần giống" hay "chồng chéo." Đúng cùng. Kiểu tương đương hoàn hảo giữa hai mô hình tưởng không liên quan này khiến mình cảm giác lĩnh vực đang khám phá thứ gì đó cơ bản, chứ không chỉ phát minh ký hiệu.