Sự tương đương giữa otomat hữu hạn và biểu thưc chính quy

Như trên đã nói, các ngôn ngữ được chấp nhận bởi ôtômát hữu hạn cũng là các ngôn ngữ được mô tả bởi biểu thức chính quy. Chính vì sự tương đương này, mà người ta gọi ngôn ngữ chấp nhận bởi ôtômát hữu hạn là các tập chính quy. Trong phần này, thông qua hai định lý, ta sẽ chỉ ra bằng quy nạp theo kích thước của (số phép toán trong) biểu thức chính quy rằng có tồn tại một NFA với e-dịch chuyển chấp nhận cùng ngôn ngữ; đồng thời với mỗi DFA cũng có một biểu thức chính quy xác định chính ngôn ngữ của nó.

ĐỊNH LÝ 3.3: Nếu r là biểu thức chính quy thì tồn tại một NFA với e-dịch chuyển chấp nhận L(r).

Chứng minh

Ta sẽ chứng minh quy nạp theo số phép toán của biểu thức chính quy r rằng có tồn tại một NFA M với e-dịch chuyển có một trạng thái kết thúc và không có các phép chuyển khỏi trạng thái này chấp nhận biểu thức chính quy r: L(M) = L(r).

r không có phép toán:

Vậy r phải là ∅ size 12{ emptyset } {}, e hoặc a (với a ∈ Σ).

Các NFA dưới đây thoả mãn điều kiện:

Hình 3.7 - Các NFAe cho các kết hợp đơn

r có chứa các phép toán:

Giả sử định lý đúng với r có ít hơn i phép toán, i ≥ 1.

Xét r có i phép toán. Có 3 trường hợp :

r = r1+ r2.

Cả hai biểu thức chính quy r 1 , r 2 có ít hơn i phép toán, vậy ta có 2 ôtômát hữu hạn NFA M 1 (Q 1 , Σ 1 , δ 1 , q 1 , {f 1 }) và M 2 (Q 2 , Σ 2 , δ 2 , q 2 , {f 2 }) sao cho L(M 1 ) = L(r 1 ) và L(M 2 ) = L(r 2 ). Vì các trạng thái có thể thay đổi tên nên ta giả sử hai tập trạng thái Q 1 và Q 2 là rời nhau. Đặt q 0 là trạng thái bắt đầu mới và {f 0 } là tập trạng thái kết thúc mới, ta xây dựng NFA M (Q 1  Q 2  {q 0 , f 0 }, Σ 1  Σ 2 , δ , q 0 , {f 0 }), trong đó δ được xác định như sau:

. d (q 0 , e ) = {q 1 , q 2 }

. d (q, a) = d 1 (q, a) với q ∈ Q 1 - {f 1 } và a ∈ Σ 1 size 12{ union } {} { ε }

. d (q, a) = d 2 (q, a) với q ∈ Q 2 - {f 2 } và a ∈ Σ 2 size 12{ union } {} { ε }

. d (f 1 , e ) = d (f 2 , e ) = {f 0 }

­­ Chú ý do giả thiết quy nạp là không có phép chuyển nào ra khỏi f 1 , f 2 trong M 1 , M 2 . Vì vậy tất cả các phép chuyển của M 1 và M 2 đều có trong M. Cách xây dựng M chỉ ra trong hình a. Bất kỳ đường đi nào trong sơ đồ chuyển của M từ q 0 tới f 0 phải bắt đầu bằng cách đi tới q 1 hoặc q 2 bằng nhãn ε . Nếu đường đi qua q 1 thì nó theo một đường đi nào đó trong M 1 tới f 1 rồi sau đó tới f 0 bằng nhãn ε .

Tương tự trong trường hợp đường đi qua q 2 . Có một đưòng đi từ q 0 đến f 0 nhãn x khi và chỉ khi có đường đi nhãn x trong M 1 từ q 1 đến f 1 hoặc có đường đi nhãn x trong M 2 từ q 2 đến f 2 .

Vậy L(M) = L(M 1 ) size 12{ union } {} L(M 2 )

Hình 3.8 - Các NFAe cho kết hợp phức

r = r 1 r 2

Đặt M 1 và M 2 là các ôtômát NFA như trong trường hợp trên và ta xây dựng ôtômát M (Q, Σ , δ , {q 1 }, {f 2 }), trong đó δ được xác định như sau:

. δ (q, a) = δ 1 (q, a) với q ∈ Q 1 - {f 1 } và a ∈ Σ 1 size 12{ union } {} { ε }

. d (f 1 , e ) = {q 2 }

. δ (q, a) = δ 2 (q, a) với q ∈ Q 2 và a ∈ Σ 2 size 12{ union } {} { ε }

Cách xây dựng M chỉ ra trong hình b. Mỗi đường đi trong M từ q 1 tới f 2 là đường đi có nhãn x từ q 1 tới f 1 sau đó là một cung từ f 1 tới q 2 nhãn ε và tiếp đến là đường đi từ q 2 tới f 2 .

Vậy L(M) = {xy | x ∈ L(M 1 ) và y ∈ L(M 2 )} hay L(M) = L(M 1 ) L(M 2 ).

r = r *

Đặt M 1 (Q 1 , Σ 1 , δ 1 , q 1 , {f 1 }) và L(M 1 ) = r 1 .

Xây dựng M (Q 1 size 12{ union } {} {q 0 , f 0 } Σ 1 , δ , q 0 , {f 0 }), trong đó δ được cho:

. d (q 0 , e ) = d (f 1 , e ) = {q 1 , f 0 }

. d (q, a) = d 1 (q, a) với q ∈ Q 1 - {f 1 } và a ∈ Σ 1 size 12{ union } {} { ε }

Cách xây dựng M được chỉ ra trong hình c. Mỗi đường đi từ q 0 tới f 0 gồm: hoặc đường đi từ q 0 tới f 0 bằng nhãn ε ; hoặc đường đi từ q 0 tới q 1 bằng nhãn ε và sau đó là đường đi từ q 1 tới f 1 trên chuỗi thuộc L(M), rồi đến f 0 bằng nhãn ε . Như vậy có đường đi từ q 0 tới f 0 nhãn là x nếu và chỉ nếu ta có thể viết x = x 1 x 2 ... x j với j ≥ 0 (trường hợp j = 0 khi x = ε ) ∀ x i ∈ L(M 1 ). Vậy L(M) = L(M 1 ) * .

Thí dụ 3.14 : Xây dựng NFAε chấp nhận lớp ngôn ngữ được ký hiệu bởi biểu thức chính quy r = 01^* + 1.

Ta thấy L(r) = { 1, 0, 01, 011, 0111, 01111, 011111, … } là tập ngôn ngữ chứa các bit đơn 0, 1 và các chuỗi bit nhị phân bắt đầu bằng bit 0, theo sau là một chuỗi bit 1 với độ dài tuỳ ý.

Theo quy luật thứ tự ưu tiên, biểu thức 01^* + 1 thực chất là (0(1^*)) + 1, vì vậy nó có dạng r1 + r2 với r1 = 01^* và r2 = 1.

Ta sẽ lần lượt xây dựng các NFA cho các biểu thức chính quy con, sau đó dựa vào các quy tắc kết hợp để xây dựng NFA cho toàn bộ biểu thức chính quy đã cho.

. NFA cho r₂ = 1 dễ dàng để xây dựng :

Định nghĩa

Cho Σ là một bộ chữ cái. Biểu thức chính quy trên Σ và các tập hợp mà chúng mô tả được định nghĩa một cách đệ quy như sau:

1) ∅ size 12{ emptyset } {} là biểu thức chính quy ký hiệu cho tập rỗng

2) ε là biểu thức chính quy ký hiệu cho tập {ε}

3) ∀a ∈ Σ, a là biểu thức chính quy ký hiệu cho tập {a}

4) Nếu r và s là các biểu thức chính quy ký hiệu cho các tập hợp R và S thì (r + s), (rs) và( r*) là các biểu thức chính quy ký hiệu cho các tập hợp R size 12{ union } {}S, RS, R^* tương ứng.

Trong khi viết biểu thức chính quy ta có thể bỏ bớt các dấu ngoặc đơn với lưu ý rằng thứ tự ưu tiên của các phép toán xếp theo thứ tự giảm dần là: phép bao đóng, phép nối kết, phép hợp.

Chẳng hạn : Biểu thức ((0(1^*)) + 1) có thể viết là 01^*+ 1.

Phép toán bao đóng dương cũng có thể được sử dụng khi viết biểu thức chính quy. Ta có thể viết rút gọn rr^* hay r^*rthành r⁺.

Nếu cần thiết phân biệt thì ta sẽ dùng ký hiệu r cho biểu thức chính quy r và L(r) cho ngôn ngữ được ký hiệu bởi biểu thức chính quy r; ngược lại một cách tổng quát, ta có thể dùng r cho cả hai.

Thí dụ 3.11 : Một số biểu thức chính quy ký hiệu cho các ngôn ngữ :

. 00 là biểu thức chính quy biểu diễn tập {00}.

. (0+1)* ký hiệu cho tập hợp tất cả các chuỗi số 0 và số 1, kể cả chuỗi rỗng

= {e, 0, 1, 00, 01, 10, 11, 010, 011, 0010 ... }

. (0+1)^*00(0+1)* ký hiệu cho tập hợp tất cả các chuỗi 0,1 có ít nhất hai số 0 liên tiếp.

= {00, 000, 100, 0000, 0001, 1000, 1001, 011001, ... }

. (1+10)^* ký hiệu cho tất cả các chuỗi 0, 1 bắt đầu bằng số 1 và không có hai số 0 liên tiếp = {e, 1, 10, 11, 1010, 111, 101010, ... }

. (0+ε)(1+10)^* ký hiệu cho tất cả các chuỗi không có hai số 0 liên tiếp.

= {e, 0, 01, 010, 1, 10, 01010, 0111, ... }

. (0+1)^*011 ký hiệu cho tất cả các chuỗi 0, 1 tận cùng bởi 011.

= {011, 0011, 1011, 00011, 11011, ... }

. 0^*1^*2^* ký hiệu cho tất cả các chuỗi có một số bất kỳ các số 0, theo sau là một số bất kỳ số 1 và sau nữa là một số bất kỳ số 2.

= {e, 0, 1, 2, 01, 02, 12, 012, 0012, 0112, ... }

. 00*11*22* ký hiệu cho tất cả các chuỗi trong tập 0^*1^*2^* với ít nhất một trong mỗi ký hiệu. 00^*11^*22^* có thể được viết gọn thành 0⁺1⁺2⁺

Thí dụ 3.12 : Biểu thức chính quy ký hiệu cho tập hợp các chuỗi tên biến đúng trong ngôn ngữ lập trình Pascal :

Một chuỗi tên biến (identifiers) được gọi là hợp lệ trong một chương trình Pascal nếu như nó bắt đầu bằng ít nhất một chữ cái và theo sau đó là các chữ cái, số, ký hiệu underline hoặc một vài ký hiệu cho phép khác trên bàn phím máy tính.

Biểu thức chính quy có dạng như sau :

r = (A + …+ Z + a + … + z) (A + …+ Z + a + … + z + 0 + … + 9 + _ + … )^*

Thí dụ 3.13 : Biểu thức chính quy ký hiệu cho tập hợp các số nguyên trong ngôn ngữ lập trình Pascal :

Một chuỗi số nguyên trong một chương trình Pascal có thể bắt đầu bằng dấu âm (-) hoặc dấu dương (+) hay không chứa ký hiệu dấu, và theo sau đó là một chuỗi các ký hiệu số với ít nhất là một số.

Biểu thức chính quy có dạng như sau :

r = ( ‘+’ + ‘-‘ + ε) ( 0 + … + 9 (0 + … +9 )^*

Nhận xét : Thông thường, việc tìm một biểu thức chính quy ký hiệu cho một ngôn ngữ khó hơn việc xác định ngôn ngữ được ký hiệu bởi một biểu thức chính quy vì không có giải thuật cho loại bài toán này.

Một số tính chất đại số của biểu thức chính quy

Dễ dàng chứng minh rằng, nếu cho r, s, t là các biểu thức chính quy thì ta có các đẳng thức sau :

Trong đó, ta có r = s có nghĩa là L(r) = L(s).

Hình 3.9 - NFAe cho ví dụ 3.13

Phần chứng minh của Định lý 3.3 trên cũng chính là cơ sở của giải thuật chuyển đổi một biểu thức chính quy thành ôtômát hữu hạn. Một điểm cần lưu ý là thứ tự ưu tiên của các phép toán được sử dụng trong biểu thức chính quy, điều này rất quan trọng cho quá trình tách biểu thức chính quy thành các biểu thức con trong những trường hợp viết biểu thức chính quy ở dạng tắt (không có dấu ngoặc).

Bây giờ, ta cần chứng tỏ rằng mọi tập hợp được chấp nhận bởi một ôtômát hữu hạn thì cũng được ký hiệu bởi một số biểu thức chính quy.

ĐỊNH LÝ 3.4 : Nếu L được chấp nhận bởi một DFA, thì L được ký hiệu bởi một biểu thức chính quy.

Chứng minh

Đặt L là tập hợp được chấp nhận bởi DFA M ({q₁, q₂,..., q_n}, Σ, δ, q₁, F).

Đặt R^k_ij là tập hợp tất cả các chuỗi x sao cho δ(q_i, x) = q_j và nếu δ(q_i, y) = q_l, với y là tiền tố bất kỳ của x, khác x hoặc ε, thì l ≤ k. Tức là R^k_ij là tập hợp tất cả các chuỗi làm cho ôtômát đi từ trạng thái qi tới qj không đi ngang qua trạng thái nào (được đánh số) lớn hơn k. (Chú ý, khái niệm "đi ngang qua một trạng thái" có nghĩa là có phép chuyển vào và ra khỏi trạng thái đó, nên i hoặc j đều có thể lớn hơn k). Vì chỉ có n trạng thái nên Rⁿ_ij sẽ là tập hợp tất cả các chuỗi làm ôtômát đi từ qi tới qj.

Ta định nghĩa R^k_ij một cách đệ quy như sau:

Một cách hình thức, R^k_ij định nghĩa như trên là các chuỗi nhập hay nguyên nhân đưa M từ q_i tới q_j không đi ngang qua trạng thái cao hơn q_k, nghĩa là xảy ra hoặc một trong hai trường hợp sau :

1. Nằm trong R^k-1_ij (để không bao giờ đi ngang qua một trạng thái nào cao như q_k).
2. Bao gồm một chuỗi trong R^k-1_ik (chuỗi làm M chuyển đến q_k), theo sau bởi không hoặc nhiều chuỗi trong R^k-1_kk (chuỗi làm M chuyển từ q_k trở về q_k mà không ngang qua q_k hoặc một trạng thái nào cao hơn) và cuối cùng là một chuỗi trong R^k-1_kj (chuỗi làm M chuyển từ q_k đến q_j ).

Ta sẽ chỉ ra rằng với mỗi i, j và k tồn tại biểu thức chính quy r k ij ký hiệu cho ngôn ngữ R k ij . Ta quy nạp theo k như sau:

. k = 0 : khi đó R 0 ij là tập hợp hữu hạn các chuỗi có một ký hiệu hoặc ε . Vậy r 0 ij có thể viết dưới dạng a 1 + a 2 + ... + a p (hoặc a 1 + a 2 + ... + a p + ε nếu i = j). Trong đó {a 1 , a 2 ,..., a p } là tập hợp tất cả các ký hiệu a sao cho δ (q i , a) = q j . Nếu không có ký hiệu a nào như thế thì ∅ size 12{ emptyset } {} (hoặc ε khi i = j) ký hiệu cho r 0 ij .

. Công thức (1) cho R k ij chỉ liên quan đến các phép toán trên biểu thức chính quy: hợp, nối kết, và bao đóng. Hơn nữa theo giả thiết quy nạp, với mỗi l, k và m tồn tại biểu thức chính quy r k-1 lm sao cho L( r k-1 lm ) = R k-1 lm . Vậy đối với r k ij ta có thể chọn biểu thức chính quy :

Cuối cùng ta có nhận xét rằng L(M) = È_{qj ∈ F} Rⁿ_1j vì Rⁿ_1j ký hiệu cho tất cả các nhãn của tất cả các đường đi từ q₁ tới q_j.

Vậy L(M) được ký hiệu bởi biểu thức chính quy r = rⁿ_1j1 + rⁿ_1j2+ ... + rⁿ_1jp, trong đó tập F = {q_j1, q_j2,..., q_jp}

Thí dụ 3.15 : Viết biểu thức chính quy ký hiệu cho ngôn ngữ được chấp nhận bởi DFA sau :

Hình 3.10 – DFA cho ví dụ 3.13

Gọi DFA được chỉ ra trong hình 3.10 là M ({q₁, q₂, q₃}, {0, 1}, δ, q₁, {q₂, q₃}). Ta thấy, tập hợp tất cả các chuỗi được chấp nhận bởi DFA trên là các chuỗi làm cho ôtômát chuyển từ trạng thái bắt đầu q₁ đến một trong hai trạng thái kết thúc q₂ và q₃ và không chuyển qua số tối đa là 3 (k = 3) trạng thái của ôtômát. Vậy ta cần viết biểu thức chính quy ký hiệu cho tập hợp này như sau :

r = r³₁₂ + r³₁₃

Theo công thức đã được chứng minh trong Định lý, ta có thể tính được các giá trị r^k_ij với i, j là chỉ số các trạng thái từ 1 đến 3 và với k = 0, 1 và 2, như chỉ ra trong bảng sau:

Bằng cách dùng các công thức tương đương như (r + s) t = rt + st và (ε + r)^* = r^* để đơn giản các biểu thức, chẳng hạn khi tính biểu thức :

r¹₂₂ = r⁰₂₁ (r⁰₁₁ )^* r⁰₁₂ + r⁰₂₂ = 0(ε)*0 + ε= 00 + ε

Tương tự, khi đơn giản biểu thức

r²₁₃ = r¹₁₂ (r¹₂₂ )^* r¹₂₃ + r¹₁₃ = 0(00 + ε)*(1 + 01) + 1

ta nhận thấy (00 + ε)* tương đương với (00)^* và (1 + 01) thì tương đương với (ε + 0)1 nên ta rút gọn :

r²₁₃ = 0(00)*(ε + 0)1 + 1

Mặt khác, chú ý rằng (00)*(ε + 0) thì tương đương với 0*, vì thế 0(00)*(ε + 0)1 + 1 cũng bằng 00*1 + 1 hay cuối cùng là 0*1.

Để hoàn thành việc xây dựng biểu thức chính quy cho M, ta cần tính r³₁₂ và r³₁₃. Ta viết:

r³₁₂ = r²₁₃ (r²₃₃ )^* r²₃₂ + r²₁₂

= 0*1(ε + (0 + 1)0*1)*(0 ­+ 1)(00)* + 0(00)*

= 0*1((0 + 1)0*1)*(0 ­+ 1)(00)* + 0(00)*

và

r³₁₃ = r²₁₃ (r²₃₃ )^* r²₃₃ + r²₁₃

= 0*1(ε + (0 + 1)0*1)*(ε + (0 ­+ 1))0*1) + 0*1

= 0*1((0 + 1)0*1)*

Vậy biểu thức chính quy có dạng :

r = r³₁₂ + r³₁₃ = 0*1((0 + 1)0*1)*(ε + (0 ­+ 1)(00)*) + 0(00)*