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

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

Sự tương đương giữa ôtômát 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à , 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 :

1) r = r1+ r2.

Cả hai biểu thức chính quy r1, r2 có ít hơn i phép toán, vậy ta có 2 ôtômát hữu hạn NFA M1 (Q1, 1, 1, q1, {f1}) và M2 (Q2, 2, 2, q2, {f2}) sao cho L(M1) = L(r1) và L(M2) = L(r2). 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 Q1 và Q2 là rời nhau. Đặt q0 là trạng thái bắt đầu mới và {f0} là tập trạng thái kết thúc mới, ta xây dựng NFA M (Q1  Q2  {q0, f0}, 1  2, , q0, {f0}), trong đó  được xác định như sau:

. d(q0, e) = {q1, q2}

. d(q, a) = d1(q, a) với q  Q1 - {f1} và a  1  {}

. d(q, a) = d2(q, a) với q  Q2 - {f2} và a  2  {}

. d(f1, e) = d(f2, e) = {f0}

­­Chú ý do giả thiết quy nạp là không có phép chuyển nào ra khỏi f1, f2 trong M1, M2. Vì vậy tất cả các phép chuyển của M1 và M2 đề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ừ q0 tới f0 phải bắt đầu bằng cách đi tới q1 hoặc q2 bằng nhãn . Nếu đường đi qua q1 thì nó theo một đường đi nào đó trong M1 tới f1 rồi sau đó tới f0 bằng nhãn .

Tương tự trong trường hợp đường đi qua q2. Có một đưòng đi từ q0 đến f0 nhãn x khi và chỉ khi có đường đi nhãn x trong M1 từ q1 đến f1 hoặc có đường đi nhãn x trong M2 từ q2 đến f2.

Vậy L(M) = L(M1)  L(M2)

Hình a - Phép hợp

Hình b - Phép nối kết

Hình c - Phép bao đóng

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

2) r = r1 r2

Đặt M1 và M2 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,  , , {q1}, {f2}), trong đó  được xác định như sau:

. (q, a) = 1(q, a) với q  Q1 - {f1} và a  1  {}

. d(f1, e) = {q2}

. (q, a) = 2(q, a) với q  Q2 và a  2  {}

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

Vậy L(M) = {xy  x  L(M1) và y  L(M2)} hay L(M) = L(M1) L(M2).