Ôtômat hữu hạn không đơn định

Ôtômat hữu hạn giới thiệu ở các bài trước (viết tắt FA hoặc DFA) luôn là đơn định: tại mỗi thời điểm, ta luôn biết rõ ôtômat sẽ làm gì. Bây giờ ta xét khái niệm tổng quát hơn là ôtômat hữu hạn không đơn định (viết tắt NFA), trong đó có thể có nhiều phép chuyển xuất phát từ cùng một trạng thái và ứng với cùng một kí hiệu.

Ví dụ

Xét đồ thị chuyển trạng thái sau:

Điểm gì đặc biệt ở đây? Từ nút q₀ có hai cạnh ứng với kí hiệu 0. Vì vậy, khi thử đoán nhận xâu 001, có vẻ như ôtômat sẽ không biết nên ở lại trạng thái q₀ hay đi theo phép chuyển sang q₁. Ôtômat như vậy là không đơn định.

Đơn định ở đây có nghĩa là trong mọi tình huống, ta đều biết rõ ôtômat sẽ làm gì, không có chỗ cho sự mơ hồ. Ở ôtômat đơn định, với mỗi trạng thái và mỗi kí hiệu chỉ có một phép chuyển. Không đơn định nghĩa là có sự không rõ ràng – từ một trạng thái, ứng với cùng một kí hiệu, có thể có chẳng hạn ba phép chuyển.

Vậy ôtômat chọn thế nào? Ôtômat không đơn định luôn chọn (đôi khi ta còn nói là “đoán”) phép chuyển dẫn đến việc đoán nhận xâu, nếu có thể.

Khi đưa xâu 001 vào ôtômat, ôtômat có các khả năng xử lí xâu như sau:

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

cùng các khả năng không đọc hết xâu. Ở khả năng thứ nhất, ôtômat luôn ở trạng thái q₀, điều này chắc chắn được phép, vì các quy tắc chuyển cho phép như vậy. Ở nhánh thứ hai, ôtômat mạnh dạn đi sang các trạng thái khác và cuối cùng đến trạng thái q₂, là trạng thái kết thúc. Ở nhánh này ôtômat đoán nhận xâu. Ôtômat không đơn định luôn tự động chọn nhánh đoán nhận được xâu, nếu nhánh như vậy tồn tại.

Làm thế nào ôtômat tự động chọn được nhánh “thuận lợi”? Có thể hình dung rằng ôtômat không đơn định đi qua tất cả các nhánh có thể, và nếu tìm được một nhánh đoán nhận xâu thì nó đoán nhận xâu đó. Làm sao để đi qua mọi nhánh? Đơn giản là khi ôtômat ở một trạng thái có n cạnh ứng với kí hiệu hiện tại, ôtômat tự nhân bản thành n bản sao, mỗi bản sao đi theo một đường khác nhau. Như vậy, lần lượt mọi khả năng đều được xét.

Biểu diễn quá trình tính toán bằng cây

Ta sửa ôtômat ở trên một chút:

Tính không đơn định vẫn ở trạng thái đầu tiên. Ôtômat trước đoán nhận mọi xâu kết thúc bằng 01. Ôtômat đã sửa này đoán nhận mọi xâu chứa xâu con 01. Chẳng hạn, nó đoán nhận xâu 101 hay 0101. Có thể dễ dàng minh hoạ mọi nhánh tính toán bằng một cây; chẳng hạn với xâu 01010, cây có thể như sau:

Ban đầu ta ở trạng thái bắt đầu q₀. Đầu vào là xâu 01010, kí tự đầu tiên chưa đọc là 0. Từ trạng thái q₀ có hai phép chuyển ứng với kí hiệu 0, đến các trạng thái q₀ và q₁. Vì vậy, nút này của cây có hai nút con: q₀ và q₁. Tiếp theo ta đọc kí hiệu 1. Ở đây không có sự mơ hồ nào, ta chuyển sang các trạng thái q₀ và q₂. Tiếp theo ta đọc kí tự 0; ở nhánh bên trái lại có sự mơ hồ, ta tách quá trình tính toán thành hai nhánh nữa. Ở một nhánh ta lại ở q₀, ở nhánh kia ta đi đến q₁. Và cứ thế tiếp tục.

Lưu ý rằng có tất cả hai nhánh kết thúc ở trạng thái q₂, là trạng thái kết thúc. Có hai nhánh tính toán mà theo đó ôtômat có thể đoán nhận xâu đã cho. Vậy ôtômat này đoán nhận xâu 01010. Ta có thể thử vẽ cây tương tự cho xâu 1000.

Quá trình tính toán hoặc ở lại trạng thái q₀, hoặc chuyển sang trạng thái q₁, nhưng từ đó không đi tiếp được, vì đầu vào chỉ còn toàn chữ số 0 mà trạng thái q₁ chỉ có phép chuyển ứng với kí hiệu 1. Không có nhánh tính toán nào kết thúc ở trạng thái kết thúc, nên ôtômat không đoán nhận xâu 1000.

Phép chuyển epsilon

Trong ôtômat không đơn định, ta còn có thể dùng phép chuyển epsilon. Đó là những phép chuyển có thể thực hiện bất kể kí hiệu đầu vào là gì, và không cần đọc kí hiệu nào của xâu. Làm thế nào để xây dựng một ôtômat không đơn định đoán nhận xâu rỗng, mọi xâu chỉ gồm chữ số 1 và các xâu dạng (10)ⁿ, tức là 10, 1010, …?

Ta đã chia ôtômat thành hai “ôtômat con”. Ôtômat con phía trên nhận biết các xâu chỉ gồm chữ số 1, ôtômat con phía dưới nhận biết các xâu dạng (10)ⁿ. Thử đoán nhận xâu 111. Ban đầu ôtômat ở trạng thái q₀ và đầu vào là xâu 111. Vì có các phép chuyển epsilon, ôtômat có thể chọn chuyển sang trạng thái q₁ hoặc q₂, tuỳ theo lựa chọn nào có lợi. Ta thấy chuyển sang trạng thái q₁ là có lợi. Ôtômat chuyển sang đó, trong khi đầu vào vẫn là xâu 111! Chỉ từ lúc này ôtômat mới bắt đầu đọc các kí hiệu của xâu và chuyển từ trạng thái q₁ lại về q₁, cho đến khi đọc hết xâu và đoán nhận nó.

Nếu thử đoán nhận xâu 1010, ban đầu ôtômat chuyển sang trạng thái q₂, chỉ từ đó mới bắt đầu xử lí các kí hiệu, và ôtômat cũng đoán nhận xâu này.

Với xâu 1100, dù ôtômat làm gì đi nữa cũng không có cách nào đoán nhận xâu này.

Phép chuyển epsilon và tính không đơn định giúp công việc dễ dàng hơn nhiều. Chẳng hạn, chứng minh hợp của hai ngôn ngữ chính quy là ngôn ngữ chính quy viết với phép chuyển epsilon đơn giản hơn nhiều so với trường hợp ôtômat hữu hạn đơn định. Trong chứng minh đó ta có ví dụ về các ôtômat sau

và

rồi xây dựng một ôtômat hữu hạn đơn định đoán nhận hợp của hai ngôn ngữ. Với phép chuyển epsilon, ta có thể xây dựng ôtômat đó như sau:

Đơn giản là thêm một trạng thái bắt đầu mới, từ đó có hai phép chuyển epsilon đến các trạng thái bắt đầu của hai ôtômat ban đầu, thế là xong. Ôtômat tự chọn một cách không đơn định xem sẽ thử đoán nhận xâu bằng “ôtômat con” thứ nhất hay thứ hai.

Định nghĩa ôtômat không đơn định

Ta đã thấy ôtômat hữu hạn đơn định và không đơn định khác nhau ở đâu, chỉ còn hình thức hoá điều đó. Ôtômat hữu hạn đơn định được định nghĩa là bộ năm ⟨Q, Σ, δ, q₀, F⟩, trong đó Q là tập các trạng thái, Σ là bảng chữ cái, δ là hàm chuyển trạng thái, q₀ là trạng thái bắt đầu và F là tập các trạng thái kết thúc. Trong định nghĩa ôtômat không đơn định, chỉ có định nghĩa hàm chuyển trạng thái thay đổi.

Ở bản đơn định, khi gọi δ(q, w) hàm chỉ có thể trả về một trạng thái, còn ở bản không đơn định hàm có thể trả về nhiều trạng thái – nếu với một kí hiệu có nhiều phép chuyển. Vì cần định nghĩa cả phép chuyển epsilon, ta kí hiệu tập Σ ∪ {ε} là Σ_ε, tức là Σ_ε = Σ ∪ {ε}. Khi đó hàm δ được định nghĩa là

$δ : Q \times Σ_{ε} \to 2^{Q}$

Ở đây 2^Q là tập luỹ thừa, tức là tập hợp tất cả các tập con của Q. Quá trình tính toán được hình thức hoá gần giống như ở ôtômat hữu hạn đơn định. Cấu hình của ôtômat vẫn là cặp ⟨q, w⟩ ∈ Q × Σ^∗. Bước tính toán ↦ là quan hệ trên tập các cấu hình sao cho

$⟨ q_{i}, w_{0} w_{1} \dots w_{n} ⟩ \mapsto ⟨ q_{j}, w_{1} \dots w_{n} ⟩,$

khi và chỉ khi q_j ∈ δ(q_i, w₀). Khác biệt lớn nhất nằm ở câu này. Ở ôtômat đơn định, điều kiện này được viết là q_j = δ(q_i, w₀), vì hàm δ luôn trả về đúng một trạng thái. Hàm chuyển trạng thái ở bản không đơn định trả về một tập trạng thái, vì vậy ở đây dùng kí hiệu ∈. Bao đóng phản xạ và bắc cầu của quan hệ này vẫn kí hiệu là ↦ ^∗. Ta nói ôtômat đoán nhận xâu w khi và chỉ khi tồn tại q_f ∈ F sao cho

$⟨ q_{0}, w ⟩ \mapsto^{*} ⟨ q_{f}, ε ⟩ .$

Tài liệu tham khảo

Mục lục: Ôtômat hữu hạn, Ôtômat đầy đủ, Ôtômat hữu hạn không đơn định, Mô phỏng ôtômat không đơn định, Chuyển NFA thành DFA

« Bài trước: Ôtômat đầy đủ

Bài tiếp: Mô phỏng ôtômat không đơn định »