Biểu thức chính quy

Biểu thức chính quy là một xâu văn bản cho phép mô tả một tập hợp xâu nào đó. Cũng có thể xem biểu thức chính quy là một cách đơn giản để mô tả một ôtômat hữu hạn.

Biểu thức chính quy là gì

Trong số học, ta dùng các kí hiệu như · và + để lập biểu thức, chẳng hạn (2 + 3) · 4. Tính giá trị biểu thức này, ta được một số. Biểu thức chính quy là một dãy gồm các kí tự và một vài kí hiệu đặc biệt, chẳng hạn a(x ∪ y), có giá trị là một ngôn ngữ (hình thức). Giá trị của biểu thức (2 + 3) · 4 là số 20, còn giá trị của biểu thức chính quy a(x ∪ y) là tập hợp gồm hai xâu “ax”, “ay”.

Ta tính giá trị của biểu thức chính quy a(x ∪ y) ở trên như thế nào? Thực ra mỗi chữ cái là cách viết tắt của tập hợp một phần tử chứa chữ cái đó, còn phép nhân ẩn là phép ghép xâu. Có thể viết lại biểu thức chính quy “đầy đủ” như sau:

$$\left\{a\right\}\circ (\left\{x\right\}\cup \left\{y\right\})$$

Tiếp theo ta tính như sau: hợp {x} ∪ {y} cho ngôn ngữ {x,y}. Ghép hai ngôn ngữ {a} và {x,y}, ta được ngôn ngữ {ax, ay}.

Biểu thức chính quy được dùng rất nhiều trong lập trình, và hầu hết các ngôn ngữ lập trình đều cài đặt biểu thức chính quy theo cách nào đó. Chẳng hạn, biểu thức chính quy dùng để kiểm tra văn bản do người dùng nhập có thoả mãn những tiêu chí nhất định hay không (có phải là email hợp lệ, ngày tháng hợp lệ, …), hay để thay thế văn bản (chẳng hạn thay mọi URL trong văn bản bằng các liên kết bấm được, …).

Các cài đặt biểu thức chính quy trong thực tế thường mạnh hơn biểu thức chính quy mô tả ở đây, và dùng cú pháp hơi khác, nhưng chủ yếu là phức tạp hơn.

Định nghĩa biểu thức chính quy

Ta định nghĩa biểu thức chính quy trên một bảng chữ cái Σ nào đó. Khi đó biểu thức chính quy là:

1. a, trong đó a ∈ Σ. Tức là bản thân một kí tự của bảng chữ cái là biểu thức chính quy.
2. ϵ: xâu rỗng, trong lập trình còn được viết là cặp dấu nháy rỗng “”.
3. ∅: biểu thức chính quy phải mô tả được cả ngôn ngữ rỗng, vì vậy ngôn ngữ rỗng là biểu thức chính quy.
4. (R₁ ∪ R₂), trong đó R₁, R₂ là biểu thức chính quy.
5. (R₁ ∘ R₂), trong đó R₁, R₂ là biểu thức chính quy.
6. (R^∗), trong đó R là biểu thức chính quy.

Thay cho kí hiệu ∪ ở mục 4, ta cũng có thể dùng dấu gạch đứng: |. Thay cho kí hiệu ∘, ta không cần dùng gì cả. Giống như thường không viết dấu nhân (dấu chấm giữa ·), ta cũng thường không viết kí hiệu phép ghép ∘. Như vậy, hai biểu thức chính quy sau là như nhau: a ∘ (b ∪ c) và a(b|c).

Các toán tử có nghĩa gì?

• ∪ hoặc | là phép hợp các ngôn ngữ.
• ∘ là phép ghép các ngôn ngữ.
• ^∗ là bao đóng của ngôn ngữ.

Ví dụ:

• a biểu diễn ngôn ngữ đơn giản {a}.
• a|b biểu diễn ngôn ngữ gồm hai xâu {a, b}.
• a ∘ b biểu diễn ngôn ngữ {ab}.
• a(b|c)d biểu diễn ngôn ngữ {abd, acd}.
• a(b^∗) biểu diễn ngôn ngữ gồm mọi xâu bắt đầu bằng chữ “a”, theo sau là chữ “b” lặp lại số lần tuỳ ý (kể cả 0 lần).
• (ab)^∗ biểu diễn ngôn ngữ gồm mọi xâu {ϵ, ab, abab, ababab, …}.
• 0^∗10^∗ biểu diễn ngôn ngữ gồm mọi xâu nhị phân chứa đúng một chữ số 1. (Lưu ý rằng viết chính xác hơn thì biểu thức này là (0^∗)1(0^∗), nhưng khi cách viết vẫn dễ đọc mà không cần ngoặc, ta có thể bỏ ngoặc.)
• Σ^∗1Σ^∗ biểu diễn ngôn ngữ gồm mọi xâu chứa ít nhất một chữ số 1.
• (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)^∗ biểu diễn ngôn ngữ gồm mọi số tự nhiên khác 0.

Tiếp theo ta sẽ chứng minh sự tương đương giữa biểu thức chính quy và ôtômat hữu hạn: với mỗi biểu thức chính quy biểu diễn ngôn ngữ R, tồn tại ôtômat hữu hạn A sao cho L(A) = R, và ngược lại.

Tài liệu tham khảo

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools