Biểu thức chính quy

A Regular Expression có thể được định nghĩa đệ quy như sau:

• ε là một Biểu thức chính quy cho biết ngôn ngữ có chứa một chuỗi rỗng. (L (ε) = {ε})

• φ là một Biểu thức chính quy biểu thị một ngôn ngữ trống. (L (φ) = { })

• x là một Biểu thức chính quy trong đó L = {x}

• Nếu X là một Biểu thức chính quy biểu thị ngôn ngữ L(X) và Y là một Biểu thức chính quy biểu thị ngôn ngữ L(Y), sau đó

  • X + Y là một Biểu thức chính quy tương ứng với ngôn ngữ L(X) ∪ L(Y) Ở đâu L(X+Y) = L(X) ∪ L(Y).

  • X . Y là một Biểu thức chính quy tương ứng với ngôn ngữ L(X) . L(Y) Ở đâu L(X.Y) = L(X) . L(Y)

  • R* là một Biểu thức chính quy tương ứng với ngôn ngữ L(R*)Ở đâu L(R*) = (L(R))*

• Nếu chúng tôi áp dụng bất kỳ quy tắc nào trong số các quy tắc từ 1 đến 5 nhiều lần, chúng là Biểu thức chính quy.

Một số ví dụ về RE

Biểu thức chính quy	Bộ thông thường
(0 + 10 *)	L = {0, 1, 10, 100, 1000, 10000,…}
(0 * 10 *)	L = {1, 01, 10, 010, 0010,…}
(0 + ε) (1 + ε)	L = {ε, 0, 1, 01}
(a + b) *	Tập hợp các chuỗi a và b có độ dài bất kỳ bao gồm cả chuỗi rỗng. Vậy L = {ε, a, b, aa, ab, bb, ba, aaa …….}
(a + b) * abb	Tập hợp các chuỗi a's và b's kết thúc bằng chuỗi abb. Vậy L = {abb, aabb, babb, aaabb, ababb, ………… ..}
(11) *	Tập hợp bao gồm số chẵn của 1 bao gồm chuỗi rỗng, Vì vậy, L = {ε, 11, 1111, 111111, ……….}
(aa) * (bb) * b	Tập hợp các chuỗi gồm số chẵn của a theo sau là số lẻ của b, do đó L = {b, aab, aabbb, aabbbbb, aaaab, aaaabbb, ………… ..}
(aa + ab + ba + bb) *	Chuỗi a và b có độ dài chẵn có thể thu được bằng cách ghép bất kỳ tổ hợp nào của các chuỗi aa, ab, ba và bb kể cả null, do đó L = {aa, ab, ba, bb, aaab, aaba, ………… .. }