0.2 Ôtômat hữu hạn và biểu thức chính quy  (Page 14/16)

1. Nằm trong Rk-1ij (để không bao giờ đi ngang qua một trạng thái nào cao như qk).
2. Bao gồm một chuỗi trong Rk-1ik (chuỗi làm M chuyển đến qk), theo sau bởi không hoặc nhiều chuỗi trong Rk-1kk (chuỗi làm M chuyển từ qk trở về qk mà không ngang qua qk hoặc một trạng thái nào cao hơn) và cuối cùng là một chuỗi trong Rk-1kj (chuỗi làm M chuyển từ qk đến qj ).

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 rkij ký hiệu cho ngôn ngữ Rkij. Ta quy nạp theo k như sau:

. k = 0 : khi đó R0ij là tập hợp hữu hạn các chuỗi có một ký hiệu hoặc . Vậy r0ij có thể viết dưới dạng a1 + a2 + ... + ap (hoặc a1 + a2 + ... + ap+  nếu i = j). Trong đó {a1, a2,..., ap} là tập hợp tất cả các ký hiệu a sao cho (qi, a) = qj. Nếu không có ký hiệu a nào như thế thì  (hoặc  khi i = j) ký hiệu cho r0ij.

. Công thức (1) cho Rkij 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 rk-1lm sao cho L(rk-1lm) = Rk-1lm. Vậy đối với rkij ta có thể chọn biểu thức chính quy :

(rk-1ik) (rk-1kk)* (rk-1kj) + rk-1ij

Cuối cùng ta có nhận xét rằng L(M) = Èqj  F Rn1j vì Rn1j ký hiệu cho tất cả các nhãn của tất cả các đường đi từ q1 tới qj.

Vậy L(M) được ký hiệu bởi biểu thức chính quy r = rn1j1 + rn1j2+ ... + rn1jp, trong đó tập F = {qj1, qj2,..., qjp}

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 ({q1, q2, q3}, {0, 1}, , q1, {q2, q3}). 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 q1 đến một trong hai trạng thái kết thúc q2 và q3 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 = r312 + r313

Theo công thức đã được chứng minh trong Định lý, ta có thể tính được các giá trị rkij 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 :

r122 = r021 (r011 )* r012 + r022 = 0()*0 +  = 00 + 

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

r213 = r112 (r122 )* r123 + r113 = 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 :

r213 = 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 r312 và r313. Ta viết:

r312 = r213 (r233 )* r232 + r212

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

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

và

r313 = r213 (r233 )* r233 + r213

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