Mô phỏng ôtômat không đơn định

Cho một ôtômat không đơn định. Muốn biết ôtômat có đoán nhận một xâu cho trước hay không, ta có thể chuyển ôtômat thành ôtômat đơn định, có thể thử bằng cách nào đó, hoặc có thể dùng một thuật toán mô phỏng hoạt động của NFA.

Nguyên lí của thuật toán

Ta minh hoạ nguyên lí qua một ví dụ phù hợp. Cho ôtômat sau:

Đây là một ôtômat hữu hạn không đơn định đoán nhận một ngôn ngữ nào đó. Lúc này ta hoàn toàn không cần quan tâm đó là ngôn ngữ gì. Ta sẽ xem quá trình tính toán của ôtômat này với xâu vào 11001. Ý tưởng như sau: ta xử lí một kí hiệu của xâu và xem nhờ các phép chuyển ứng với cùng một kí hiệu, ta có thể đi đến những trạng thái nào. Ta ghi nhớ tất cả các trạng thái này, ở bước tiếp theo coi như ta đang “ở tất cả các trạng thái này cùng lúc” và xét xem từ các trạng thái đó có thể đi tiếp đến đâu.

Như vậy, ta ghi nhớ tập các trạng thái mà ôtômat có thể đang ở, cùng với phần xâu chưa đọc. Ban đầu ta có cặp ⟨{q₀}, 11001⟩. Ta bắt đầu ở trạng thái q₀ (trạng thái bắt đầu) và đầu vào là xâu 11001. Ôtômat như sau, trạng thái hiện tại được tô màu đỏ và in đậm:

Kí hiệu đầu tiên là 1; từ trạng thái q₀ chỉ có một phép chuyển ứng với kí hiệu 1, nên ta đến trạng thái q₁. Ta ghi nhớ cặp ⟨{q₁}, 1001⟩. Ôtômat như sau:

Ta tiếp tục. Phần xâu chưa đọc là 1001, nên ta lại tìm các phép chuyển ứng với 1. Lần này có hai phép chuyển – quay về trạng thái q₀ và sang trạng thái q₃. Ta đi đến cả hai trạng thái cùng lúc. Như vậy, ta ghi nhớ cặp ⟨{q₀, q₃}, 001⟩.

Vì sao làm như vậy hợp lí? Ta biết rằng từ trạng thái bắt đầu, với xâu 11, có đường đi đến trạng thái q₃ và cũng có đường đi đến trạng thái q₀. Ta chưa biết nhánh nào sẽ có ích, nên cứ ghi nhớ cả hai. Ta tiếp tục. Đầu vào là kí hiệu 0. Bây giờ ta phải xét cả các phép chuyển từ q₀ lẫn các phép chuyển từ q₃. Từ trạng thái q₀ có các phép chuyển đến trạng thái q₁ và q₂, từ trạng thái q₃ có phép chuyển về q₁. Gộp tất cả các trạng thái này, ta được cặp ⟨{q₁, q₂}, 01⟩:

Nhưng bước này chưa xong. Ta thấy từ trạng thái q₂ có phép chuyển epsilon đến trạng thái q₄. Ta biết rằng có thể đi theo phép chuyển epsilon “bất cứ lúc nào” mà không cần đọc kí tự tiếp theo. Nói cách khác, không cần đọc thêm kí hiệu nào của xâu vào, ta vẫn có thể chuyển sang trạng thái q₄. Vì vậy, ta thêm trạng thái q₄ vào các trạng thái mà ôtômat có thể đang ở: ⟨{q₁, q₂, q₄}, 01⟩. Ôtômat được tô màu như sau:

Tiếp theo đầu vào là 0. Ta xét xem từ ba trạng thái hiện tại có thể đi đến đâu. Từ q₁ không đi đâu được, vì không có phép chuyển ứng với 0. Quá trình tính toán ở nhánh này kết thúc. Từ trạng thái q₄ cũng không đi đâu được. Từ trạng thái q₂ ta quay lại trạng thái q₂. Nhưng vì từ trạng thái q₂ lại có phép chuyển epsilon đến trạng thái q₄, nên ta cũng có thể đến trạng thái q₄. Như vậy, từ tập trạng thái {q₁, q₂, q₄}, với kí hiệu 0 ta có thể đến tập trạng thái {q₂, q₄}, ta được cặp ⟨{q₂, q₄}, 1⟩:

Cuối cùng đầu vào là kí hiệu 1. Từ trạng thái q₂ không đi đâu được, quá trình tính toán ở nhánh này kết thúc. Nhưng từ trạng thái q₄ ta đến được các trạng thái q₃ và q₅. Ta được cặp ⟨{q₃, q₅}, ε⟩:

Bây giờ ôtômat đã đọc hết xâu và “đang ở” hai trạng thái: q₃, q₅. Vì ít nhất một trong hai là trạng thái kết thúc, ôtômat đoán nhận xâu 11001.

Thuật toán

Trước hết, ta cần một hàm nhận tham số là một tập trạng thái và tính xem còn có thể đến những trạng thái nào nhờ các phép chuyển epsilon. Đầu vào là ôtômat ⟨Q, Σ, δ, q₀, F⟩ và tập trạng thái States, đầu ra là tập chứa các trạng thái đó cùng mọi trạng thái đến được từ chúng nhờ các phép chuyển epsilon. Phép toán này gọi là bao đóng epsilon của tập States.

$\begin{aligned} Function E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Ta dùng hàm này trong hàm mô phỏng hoạt động của ôtômat không đơn định. Đầu vào là ôtômat, xâu vào w = w₁w₂… w_n và tập các trạng thái mà ôtômat đang ở. Đầu ra là câu trả lời Có hoặc Không, tuỳ theo ôtômat đoán nhận hay không đoán nhận xâu đã cho.

$\begin{aligned} Function C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return YES \\ Else \\ Return NO \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e (⟨ Q, Σ, δ, q_{0}, F ⟩, N e x t S t a t e s) \\ Return C o m p u t e N F A (⟨ Q, Σ, δ, q_{0}, F ⟩, w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Để kiểm tra ôtômat có đoán nhận xâu w hay không, ta gọi hàm như sau: ComputeNFA(⟨Q, Σ, δ, q₀, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q₀, F⟩, {q₀})).

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 hữu hạn không đơn định

Bài tiếp: Chuyển NFA thành DFA »