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

Theo giả thiết quy nạp thì ’(q0, w) =  *(q0, w). Đặt  *(q0, w) = P, ta cần chỉ ra rằng (P, a) =  *(q0, wa).

Ta có ’(P, a) = ÈqP ’(q, a) = ÈqP  *(q, a).

Hơn nữa vì P =  *(q0, w) nên ÈqP  *(q, a) =  *(q0, wa) ( theo quy tắc 2 trong định nghĩa  *).

Vậy ’(q0, wa) =  *(q0, wa)

Để đầy đủ chứng minh ta còn phải chỉ ra rằng ’(q0, x) chứa một trạng thái trong F’ nếu và chỉ nếu  *(q0, x) chứa một trạng thái trong F.

Nếu x = e thì điều đó hiển nhiên đúng (theo định nghĩa của F’)

Nếu x  e thì ta đặt x = wa với a  .

Nếu  *(q0, x) chứa một trạng thái trong F thì chắc chắn ’(q0, x) chứa cùng trạng thái trong F’. Ngược lại, nếu ’(q0, x) chứa một trạng thái trong F’ khác hơn q0 thì (q0, x) phải chứa một trạng thái trong F (vì tập F và F’ chỉ chênh lệch nhau trạng thái q0). Nếu ’(q0, x) có chứa trạng thái q0 và q0 cũng là một trạng thái thuộc tập trạng thái kết thúc F thì vì  *(q0, x) = e-CLOSURE(( *(q0, w),a)), nên trạng thái chung trong e-CLOSURE(q0) và trong F phải ở trong  *(q0, x).

Thí dụ 3.9 : Chuyển NFA với e-dịch chuyển ở hình 3.4 sang dạng NFA không có chứa e-dịch chuyển.

Ta xây dựng NFA tương đương M’(Q, , ’, q0, F’) chấp nhận L(M) với các thành phần : . Q = {q0, q1, q2}

. å = {0, 1, 2}

. Trạng thái bắt đầu : q0

. F' = {q0, q2} do e-CLOSURE(q0) = {q0, q1, q2} có chứa q2  F

. Hàm chuyển ’ của M’ được xác định theo công thức :

d’(q, a) = d*(q, a) = e-CLOSURE(d(d*(q0, e), a)

Kết quả được chỉ ra trong bảng hàm chuyển sau :

Sơ đồ chuyển trạng thái:

Hình 3.5 - NFA tương đương cho thí dụ 3.9

Giải thuật xây dựng dfa từ nfa

Qua khảo sát các dạng mở rộng từ mô hình ôtômát hữu hạn ban đầu, ta thấy DFA thực chất là một trường hợp đặc biệt của NFA, nhưng :

- Nó không có sự truyền rỗng (truyền trên nhãn e)

- Với mỗi trạng thái q và ký hiệu nhập a, chỉ có duy nhất một đường truyền đến một trạng thái khác.

Giả sử mỗi trạng thái của DFA là một tập trạng thái của NFA, DFA dùng trạng thái của mình để lưu giữ tất cả các trạng thái của NFA đạt được sau khi NFA đọc một ký tự nhập. Như vậy sau khi đọc các ký tự nhập a1, a2, ... , an, DFA ở trạng thái là tập con của các trạng thái thuộc NFA, đạt được khi NFA đi từ trạng thái bắt đầu theo một con đường nào đó có tên a1a2 ... an. Số trạng thái của DFA lúc đó phải bằng số phần tử trong tập lũy thừa của số trạng thái NFA. Song, trên thực tế trường hợp xấu nhất này ít khi xảy ra. Các trạng thái thực sự được dùng trong sơ đồ chuyển cho một DFA sẽ được xác định theo các phép chuyển trạng thái trên nhãn là mọi ký hiệu từ trạng thái bắt đẩu của DFA, và sau đó lần lượt được bổ sung thêm vào tập trạng thái nếu như nó chưa có trong đó.

Giải thuật chi tiết được trình bày như sau :

Input: Một ôtômát hữu hạn không đơn định NFA.

Output: Một ôtômát hữu hạn đơn định DFA nhận dạng cùng ngôn ngữ như NFA.

Phương pháp: Xây dựng bảng hàm chuyển cho DFA mô phỏng đồng thời tất cả các chuyển dịch của NFA trên chuỗi nhập cho trước.

Ta dùng các tác vụ sau để lưu giữ các tập trạng thái của NFA :