Tối thiểu hoá ôtômat

Tối thiểu hoá ôtômat là tìm một ôtômat tương đương có số trạng thái nhỏ nhất có thể. Ngay cả ôtômat không có trạng thái thừa nào vẫn có thể rút gọn thêm.

Ví dụ

Xét ôtômat sau:

Ôtômat này chỉ đoán nhận các xâu 01 và 11. Rõ ràng có một ôtômat đơn giản hơn với ba trạng thái đoán nhận cùng ngôn ngữ đó. Có thể gộp hai trạng thái q₁ và q₂ thành một trạng thái mới {q₁, q₂}: các phép chuyển trước đây đi vào q₁ hoặc q₂ sẽ đi vào trạng thái mới, các phép chuyển xuất phát từ q₁ và q₂ cũng vậy. Ta được ôtômat sau:

Rõ ràng ôtômat này đoán nhận cùng ngôn ngữ với ôtômat trước, đồng thời có ít trạng thái hơn.

Trạng thái tương đương

Cho ôtômat A = ⟨Q, Σ, δ, q₀, F⟩. Ngôn ngữ của trạng thái q ∈ Q, kí hiệu L(q), được định nghĩa là

$L (q) = L (⟨ Q, Σ, δ, q, F ⟩)$

Tức là ta đổi trạng thái bắt đầu của ôtômat A từ q₀ thành q và tìm ngôn ngữ mà ôtômat này đoán nhận. Nói cách khác, ngôn ngữ L(q) gồm mọi xâu w sao cho trong ôtômat A, xuất phát từ trạng thái q và đọc xâu w, ta đến một trạng thái kết thúc của ôtômat. Với ôtômat ở trên, L(q₁) = {1}.

Ta nói hai trạng thái khác nhau q₁ và q₂ là tương đương nếu

$L (q_{1}) = L (q_{2})$

Điều này có nghĩa là gì? Nếu hai trạng thái q₁, q₂ tương đương, thì khi lấy chúng làm trạng thái bắt đầu của ôtômat, chúng sẽ cho cùng một ngôn ngữ. Nói cách khác: nếu ôtômat ở cấu hình ⟨q₁, w⟩ hoặc ⟨q₂, w⟩, thì trong cả hai trường hợp nó phải cùng đoán nhận hoặc cùng từ chối.

Quay lại ôtômat ở trên: hai trạng thái q₁ và q₂ tương đương, vì khi ở trạng thái q₁, ta chỉ có thể đoán nhận xâu vào nếu phần xâu chưa đọc bằng 1. Ở trạng thái q₂ cũng vậy.

Như vậy, khi tối thiểu hoá ôtômat, ta cần tìm các trạng thái tương đương và loại bỏ chúng bằng cách gộp chúng thành một trạng thái mới, như đã làm ở ví dụ trên.

Cách tìm các trạng thái tương đương

Những trạng thái nào chắc chắn không tương đương? Một trạng thái kết thúc và một trạng thái không kết thúc chắc chắn không tương đương, vì ngôn ngữ của trạng thái kết thúc khác ngôn ngữ của trạng thái không kết thúc – trạng thái kết thúc chắc chắn đoán nhận xâu ε, còn trạng thái không kết thúc thì không. Ta xem ngay cách làm qua một ví dụ. Cho ôtômat sau:

Ta bắt đầu bằng việc tạo hai tập trạng thái

$\begin{array}{rcl} S_{1} & = & F = {q_{3}, q_{6}}, \\ S_{2} & = & Q ∖ F = {q_{0}, q_{1}, q_{2}, q_{4}, q_{5}} . \end{array}$

Bây giờ ta lập bảng các phép chuyển và giữ thông tin về các nhóm S₁ và S₂:

$\begin{array}{ccccc} nhóm & trạng thái & 0 & 1 \\ S_{1} & q_{3} & q_{5} & q_{4} \\ q_{6} & — & — \\ S_{2} & q_{0} & q_{1} & q_{2} \\ q_{1} & — & q_{3} \\ q_{2} & — & q_{3} \\ q_{4} & q_{6} & — \\ q_{5} & q_{6} & — \end{array}$

Bây giờ ta sửa bảng: thay vì ghi trực tiếp trạng thái mà ta đi đến ứng với mỗi kí hiệu, ta chỉ ghi nhóm mà ta đi đến. Chẳng hạn, từ trạng thái q₃ với kí hiệu 0 ta đến trạng thái q₅, thuộc nhóm S₂. Vì vậy, thay cho q₅ ta ghi S₂ vào bảng:

$\begin{array}{ccccc} nhóm & trạng thái & 0 & 1 \\ S_{1} & q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ S_{2} & q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Bây giờ ta chia nhỏ tiếp cả hai nhóm. Ta luôn xếp vào cùng một nhóm những trạng thái mà với mọi kí hiệu đều đi đến cùng một nhóm. Chẳng hạn, hai trạng thái q₃ và q₆ sẽ không cùng nhóm, vì cả với 0 lẫn với 1 chúng đều không đi đến cùng một nhóm. Ngược lại, hai trạng thái q₁ và q₂ sẽ cùng nhóm, vì cả hai đều không có phép chuyển ứng với 0 và cả hai đều đi đến nhóm S₁ ứng với 1. Ta được các nhóm mới:

$\begin{array}{ccccc} nhóm & trạng thái & 0 & 1 \\ q_{3} & S_{2} & S_{2} \\ q_{6} & — & — \\ q_{0} & S_{2} & S_{2} \\ q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ q_{4} & S_{1} & — \\ q_{5} & S_{1} & — \end{array}$

Trong mỗi nhóm, các phép chuyển đều giống nhau. Ta đặt tên các nhóm mới và lại xác định xem các trạng thái đi đến nhóm mới nào:

$\begin{array}{ccccc} nhóm & trạng thái & 0 & 1 \\ S_{1} & q_{3} & S_{5} & S_{5} \\ S_{2} & q_{6} & — & — \\ S_{3} & q_{0} & S_{4} & S_{4} \\ S_{4} & q_{1} & — & S_{1} \\ q_{2} & — & S_{1} \\ S_{5} & q_{4} & S_{2} & — \\ q_{5} & S_{2} & — \end{array}$

Lúc này ta chia nhỏ các nhóm thêm một lần nữa. Nhưng ta thấy không thể chia thêm được, vì sẽ được đúng các nhóm như cũ – hai trạng thái q₁ và q₂ tuy có cùng phép chuyển giữa các nhóm, nhưng đã ở cùng một nhóm và nhóm S₄ không có trạng thái nào khác. Thuật toán tìm trạng thái tương đương kết thúc. Từ mỗi nhóm, ta chỉ cần chọn một trạng thái, xoá các trạng thái còn lại, và mọi phép chuyển trước đây đi vào các trạng thái đã xoá sẽ đi vào trạng thái được chọn.

Chẳng hạn, ta có thể chọn ôtômat mới có các trạng thái q₃, q₆, q₀, q₁, q₄ và loại bỏ các trạng thái q₂ và q₅. Mọi phép chuyển trước đây đi vào q₂ bây giờ đi vào q₁, và mọi phép chuyển trước đây đi vào q₅ bây giờ đi vào q₄:

Các bước tối thiểu hoá ôtômat

Loại bỏ các trạng thái không đến được,
loại bỏ các trạng thái thừa,
loại bỏ các trạng thái tương đương.

Tài liệu tham khảo

Mục lục: Trạng thái không đến được, Trạng thái thừa, Tối thiểu hoá ôtômat

« Bài trước: Trạng thái thừa

Bài tiếp: Tính đóng của ngôn ngữ chính quy »