Chuyển NFA thành DFA

Ta sẽ xem cách chuyển một ôtômat không đơn định thành ôtômat đơn định, qua đó chứng minh rằng khả năng tính toán của ôtômat không đơn định và ôtômat đơn định là như nhau.

Ý tưởng cơ bản

Cho ôtômat không đơn định ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ không có phép chuyển epsilon. Ta xây dựng ôtômat đơn định ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ sao cho

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Hàm chuyển trạng thái δ_D được định nghĩa như sau:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Điều này có nghĩa là gì? Ôtômat không đơn định có thể đồng thời ở nhiều trạng thái, nên chẳng hạn có thể xảy ra tình huống ôtômat không đơn định của ta ở các trạng thái {q₀, q₁}. Đọc kí hiệu tiếp theo, chẳng hạn 1, ta có thể đến tập trạng thái {q₀, q₂, q₃}. Ở bản đơn định của cùng ôtômat đó, điều này thể hiện như sau: ta tạo hai trạng thái, đặt tên chúng là {q₀, q₁} và {q₀, q₂, q₃}, rồi thêm phép chuyển giữa chúng ứng với kí hiệu 1. Về hình thức, ta đi từ một trạng thái sang một trạng thái khác, nhưng nhờ cách đặt tên, ta biết rằng khi đó ôtômat không đơn định ở hai trạng thái, rồi ở ba trạng thái.

Ví dụ

Cho ôtômat không đơn định sau:

Để xây dựng ôtômat đơn định, trước hết cần xây dựng hàm chuyển trạng thái mới. Để làm việc này, ta dùng một bảng ghi lại mọi phép chuyển. Ban đầu bảng như sau:

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}\end{array}$$

Khi thuật toán kết thúc, cột bên trái sẽ chứa mọi trạng thái của ôtômat đơn định. Bảng đã điền đầy đủ sẽ xác định hàm chuyển trạng thái. Bây giờ ta điền vào bảng các trạng thái đến được khi đang ở các trạng thái {q₀} và đầu vào là kí hiệu 0 hoặc 1.

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Từ trạng thái q₀, ứng với kí hiệu 0 chỉ có phép chuyển đến trạng thái q₁, còn ứng với kí hiệu 1 có phép chuyển đến các trạng thái q₁ và q₂. Bây giờ ta thêm vào bảng hai trạng thái mới: {q₁} và {q₁, q₂}. Vì sao? Mỗi khi điền vào bảng một tập trạng thái chưa có ở cột bên trái, ta thêm tập trạng thái đó vào cột bên trái.

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

rồi lại điền tiếp. Với trạng thái {q₁, q₂}, không được quên kiểm tra cả hai trạng thái, tức là lấy hợp của các trạng thái đến được từ q₁ và các trạng thái đến được từ q₂.

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Ta được một số trạng thái mới, cần thêm vào bảng:

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…và lại điền các phép chuyển:

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Các trạng thái {q₀, q₁, q₃}, {q₁} và {q₁,q₂} đã có trong bảng, nên ta chỉ thêm trạng thái {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{trạng thái}/\text{kí hiệu}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Không có trạng thái mới nào được thêm vào, vậy bảng đã điền xong. Bây giờ chỉ còn vẽ đồ thị chuyển trạng thái. Các trạng thái của ôtômat đơn định nằm ở cột thứ nhất, các phép chuyển ứng với kí hiệu 0 và 1 nằm ở các cột tiếp theo. Mỗi trạng thái chứa một trạng thái kết thúc nào đó của ôtômat ban đầu cũng là trạng thái kết thúc của ôtômat này. Nghĩa là mọi trạng thái chứa q₃ đều là trạng thái kết thúc. Ôtômat như sau:

Ta có thể kiểm tra rằng ôtômat này hoạt động đúng. Thử đoán nhận xâu 11001. Ở ôtômat đơn định, ta đi theo đường

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

và ôtômat đoán nhận xâu, vì trạng thái cuối cùng {q₀, q₁, q₂, q₃} là trạng thái kết thúc. Ở ôtômat không đơn định, khi mô phỏng ta cũng đi qua đúng các trạng thái đó: bắt đầu ở trạng thái q₀, với kí hiệu 1 ta đến các trạng thái {q₁, q₂}. Kí hiệu 1 tiếp theo đưa ta đến các trạng thái {q₀,q₃}, và cứ thế với các trạng thái tiếp theo. Cuối cùng ta ở tất cả các trạng thái {q₀, q₁, q₂, q₃} và ôtômat đoán nhận xâu.

Tài liệu tham khảo

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools