✖

Trạng thái thừa

Ôtômat hữu hạn có thể có những trạng thái mà từ đó không thể đi đến trạng thái kết thúc, vì vậy chúng vô ích. Các trạng thái như vậy gọi là trạng thái thừa. Thường ta muốn loại bỏ chúng, vì chúng chỉ làm ôtômat rườm rà thêm.

Ví dụ về trạng thái thừa

Cho ôtômat hữu hạn sau:

Ta thấy một khi đã đến trạng thái q4 hoặc q5, ta không bao giờ đến được một trong các trạng thái kết thúc q1 hoặc q2 nữa. Vì vậy, các trạng thái này là thừa và có thể loại bỏ chúng; ta sẽ được một ôtômat mới tương đương, tức là đoán nhận cùng một ngôn ngữ. Sau khi xoá các trạng thái thừa, ôtômat như sau:

Ôtômat này đoán nhận cùng một ngôn ngữ. Tuy nhiên, có những lúc nên giữ một số trạng thái thừa – chẳng hạn khi xây dựng ôtômat đầy đủ.

Định nghĩa trạng thái thừa

Cho ôtômat hữu hạn A = ⟨Q, Σ, δ, q0, F⟩. Ta nói trạng thái q ∈ Q là thừa nếu không tồn tại xâu w ∈ Σ∗ và trạng thái qf ∈ F nào sao cho

⟨q,w⟩↦∗⟨qf,ε⟩.

Cách loại bỏ trạng thái thừa

Giả sử đầu vào là ôtômat A = ⟨Q, Σ, δ, q0, F⟩ đã không còn trạng thái không đến được. Ta lần lượt tìm các trạng thái dẫn đến trạng thái kết thúc, rồi các trạng thái dẫn đến những trạng thái vừa tìm được, và cứ thế tiếp tục. Như vậy ta được tập tất cả các trạng thái không thừa. Ban đầu đặt S0 = F. Ta xây dựng các tập tiếp theo Si với i ∈ ℕ* theo quy tắc sau:

Si={q∈Q|∃a∈Σ:δ(q,a)∈Si−1}∪Si−1

Tập tất cả các trạng thái không thừa có thể viết như sau:

⋃i=1∞Si.

Còn tập các trạng thái thừa là

Q∖⋃i=1∞Si.

Nói cách khác: nếu Si = Si + 1 thì tập Q ∖ Si chứa các trạng thái thừa. Ta minh hoạ cách làm trên ôtômat sau:

Trước hết đặt S0 = {q1, q2}. Tiếp theo ta xây dựng tập S1 bằng cách thêm vào S0 mọi trạng thái dẫn đến một trong các trạng thái thuộc S0. Như vậy ta thêm các trạng thái q0 và q3, vì từ q0 có phép chuyển đến q1 và từ q3 có phép chuyển đến q2. Ta được S1 = {q0, q1, q2, q3}. Vì S0 ≠ S1 nên ta tiếp tục.

Ta xây dựng tập S2. Cần tìm mọi trạng thái chưa thuộc S1 mà từ đó có thể đến S1. Chỉ có một trạng thái như vậy là q6, từ đó có thể đến trạng thái q3. Ta được S2 = {q0, q1, q2, q3, q6}. Vì S1 ≠ S2 nên ta tiếp tục.

Ta xây dựng tập S3. Có trạng thái mới nào mà từ đó đến được một trong các trạng thái thuộc S2 không? Không có: từ các trạng thái q4 và q5 không đến được trạng thái nào thuộc S2, còn các trạng thái khác đã thuộc S2. Do đó S3 = {q0, q1, q2, q3, q6}. Vì S2 = S3 nên thuật toán kết thúc, và S2 là tập các trạng thái không thừa. Tập {q4, q5} là tập các trạng thái thừa.

Về mặt hình thức, ta xây dựng ôtômat tương đương mới không có trạng thái thừa như sau. Cho ôtômat A = ⟨Q, Σ, δ, q0, F⟩, ta xây dựng ôtômat A′ = ⟨Q′, Σ, δ′, q0, F⟩ tương đương với nó và không có trạng thái thừa.

  • Q′=⋃i=1∞Si
  • ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a) nếu δ(q, a) ∈ Q′, trái lại δ′(q, a) không xác định

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