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

Nhận xét :

Một cách tổng quát, ta thấy tập Q của DFA thể hiện các trạng thái lưu trữ của ôtômát trong quá trình đoán nhận ngôn ngữ, và như vậy khả năng lưu trữ của ôtômát là hữu hạn. Mặt khác, hàm chuyển d là hàm toàn phần và đơn trị, cho nên các bước chuyển của ôtômát luôn luôn được xác định một cách duy nhất. Chính vì hai đặc điểm này mà DFA mô tả như trên được gọi là ôtômát hữu hạn đơn định.

Ôtômát hữu hạn không đơn định - nfa (nondeterministic finite automata)

Xét một dạng sửa đổi mô hình DFA để chấp nhận không, một hoặc nhiều hơn một phép chuyển từ một trạng thái trên cùng một ký hiệu nhập. Mô hình mới này gọi là ôtômát hữu hạn không đơn định (NFA).

Một chuỗi ký hiệu nhập a1 a2 ... an được chấp nhận bởi một NFA nếu có tồn tại một chuỗi các phép chuyển, tương ứng với chuỗi nhập, từ trạng thái bắt đầu đến trạng thái kết thúc. Chẳng hạn, chuỗi 01001 được chấp nhận bởi ôtômát trong hình dưới đây vì có chuỗi phép chuyển qua các trạng thái q0, q0, q0, q3, q4, q4 có nhãn tương ứng là 0, 1, 0, 0, 1. NFA này chấp nhận tất cả các chuỗi có hai số 0 liên tiếp hoặc hai số 1 liên tiếp.

Thí dụ 3.3 :

Hình 3.3 ­- Sơ đồ chuyển của một NFA

Chú ý rằng có thể xem ôtômát hữu hạn đơn định - DFA (hay gọi tắt là FA) là một trường hợp đặc biệt của NFA, trong đó mỗi trạng thái chỉ có duy nhất một phép chuyển trên mỗi ký hiệu nhập. Vì thế trong DFA, với một chuỗi nhập w và trạng thái q, chỉ có đúng một đường đi nhãn w bắt đầu từ q. Để xác định chuỗi w có được chấp nhận bởi DFA hay không chỉ cần kiểm tra đường đi này. Nhưng đối với NFA, có thể có nhiều đường đi có nhãn là w, và do đó tất cả phải được kiểm tra để thấy có hay không có đường đi tới trạng thái kết thúc.

Tương tự như DFA, NFA cũng hoạt động với một bộ điều khiển hữu hạn đọc trên băng nhập. Tuy nhiên, tại mỗi thời điểm, bộ điều khiển có thể chứa một số bất kỳ trạng thái. Khi có sự lựa chọn trạng thái kế tiếp, chẳng hạn như từ trạng thái q0 trên ký hiệu nhập 0 ở hình 3.3, ta phải tưởng tượng như có các bản sao của ôtômát đang thực hiện đồng thời. Mỗi trạng thái kế tiếp mà ôtômát có thể chuyển đến sẽ tương ứng với một bản sao của ôtômát mà tại đó bộ điều khiển đang chứa trạng thái đó.

Chẳng hạn, với chuỗi 01001, ta có :

Định nghĩa

Một cách hình thức ta định nghĩa ôtômát hữu hạn không đơn định NFA là một bộ 5 thành phần (Q, , , q0, F) trong đó Q, , q0 và F có ý nghĩa như trong DFA, nhưng  là hàm chuyển ánh xạ từ Q    2Q.

Khái niệm (q, a) là tập hợp tất cả các trạng thái p sao cho có phép chuyển trên nhãn a từ trạng thái q tới p.

Hàm chuyển trạng thái mở rộng

Để thuận tiện trong việc mô tả hoạt động ôtômát trên chuỗi, ta mở rộng hàm chuyển  ánh xạ từ Q  *  2Q như sau :

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

1. (q, wa) = { p  có một trạng thái r trong (q, w) mà p thuộc (r, a)}

= ((q, w), a)

1. d(P, w) = Èq  P d(q, w) , P  Q.

Ngôn ngữ được chấp nhận bởi NFA

Ngôn ngữ L(M), với M là ôtômát hữu hạn không đơn định NFA (Q, , , q0, F) là tập hợp :

L(M) = {w  (q0, w) có chứa một trạng thái trong F }

Thí dụ 3.4 : Xét sơ đồ chuyển của hình 3.3. Theo khái niệm hình thức, ta có :