Trạng thái không đến được

Ôtômat hữu hạn có thể có những trạng thái mà ta không thể đi đến. Các trạng thái như vậy gọi là trạng thái không đến được. 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 không đến được

Cho ôtômat sau:

Ta thấy dù làm gì đi nữa, ta cũng không bao giờ đến được trạng thái q₃, vì không có phép chuyển nào đi vào trạng thái đó. Ta nói trạng thái q₃ là không đến được. Câu hỏi: trạng thái q₃ có đến được không nếu có một phép chuyển từ một trạng thái khác đi vào nó? Nếu vẽ một cạnh từ một trong các trạng thái q₀, q₁, q₂, q₅ thì trạng thái này sẽ đến được. Nếu ta thêm một nút nữa và vẽ phép chuyển từ nút đó…

…thì tất nhiên cả hai trạng thái q₃ và q₄ đều không đến được.

Định nghĩa trạng thái không đến được

Trước hết ta định nghĩa trạng thái đến được. Cho ôtômat hữu hạn A = ⟨Q, Σ, δ, q₀, F⟩. Ta nói trạng thái q ∈ Q là đến được nếu tồn tại xâu w ∈ Σ^∗ sao cho

$$⟨q_0,w⟩{\mapsto }^{\ast }⟨q,\epsilon ⟩.$$

Trạng thái q ∈ Q là không đến được nếu nó không phải là trạng thái đến được.

Cách loại bỏ trạng thái không đến được

Nếu ôtômat đã có trạng thái không đến được, nên loại bỏ chúng. Ta xây dựng ôtômat tương đương A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ không có trạng thái không đến được.

Ta xây dựng dần tập các trạng thái đến được. Bắt đầu với tập S₀ = {q₀}, vì trạng thái bắt đầu chắc chắn đến được. Tập tiếp theo được xây dựng như sau:

$$S_i=\{r|\delta (q,a)=r\text{ với một cặp }q\in S_{i-1},a\in \mathrm{\Sigma }\}\cup S_{i-1}$$

Nói bằng lời, tập S₀ luôn cho trước; để xây dựng tập S₁, ta lấy mọi trạng thái của tập S₀ và tìm xem các phép chuyển ứng với mọi kí hiệu thuộc Σ dẫn đến đâu. Lấy hợp các trạng thái này với tập ban đầu S₀. Làm tương tự, ta tìm được tập S₂ và các tập tiếp theo. Rõ ràng S_{i − 1} ⊆ S_i.

Khi đó tập các trạng thái đến được là:

$$\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Lấy hợp của vô hạn tập S_i thoạt nhìn có vẻ lạ, nhưng ôtômat chỉ có hữu hạn trạng thái. Điều đó có nghĩa là đến một lúc nào đó, các tập S_j, S_{j + 1} và mọi tập sau đó sẽ bằng nhau, nên dù lấy hợp của vô hạn tập, ta vẫn có thể được một tập trạng thái hữu hạn.

Quay lại ôtômat

và thử tìm tập các trạng thái đến được. Trước hết ta đặt

$$S_0=\left\{q_0\right\}$$

Bây giờ ta tính tập S₁. Cần tìm mọi phép chuyển từ trạng thái q₀ và thêm các trạng thái đích của chúng vào tập S₀. Vì q₀ → ^a q₁ và q₀ → ^bq₂, nên tập S₁ có thêm các trạng thái q₁ và q₂:

$$S_1=\{q_0,q_1,q_2\}$$

Tiếp theo ta xây dựng tập S₂. Ta xét xem từ các trạng thái q₀, q₁, q₂ có thể đến những đâu. Trạng thái mới duy nhất là q₅, đến được từ trạng thái q₁:

$$S_2=\{q_0,q_1,q_2,q_5\}$$

Tiếp theo ta xây dựng tập S₃. Từ các trạng thái q₀, q₁, q₂, q₅ có đến được trạng thái mới nào không? Không, nên tập S₃ có cùng các phần tử với S₂:

$$S_3=\{q_0,q_1,q_2,q_5\}$$

Vì S₂ = S₃ nên S₃ = S₄ = S₅ = … Lấy hợp của mọi S_i, ta được tập S₂, vì không tập nào sau đó có thêm phần tử mới.

Vậy tập các trạng thái đến được của ôtômat là {q₀, q₁, q₂, q₅}. Tập các trạng thái không đến được ta tìm bằng phép hiệu hai tập hợp:

$$Q\setminus \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$$

Tập các trạng thái không đến được của ôtômat này là {q₃, q₄}. Ta loại bỏ khỏi ôtômat A mọi trạng thái không đến được và mọi phép chuyển có liên quan đến trạng thái không đến được. Tức là ôtômat A′ = ⟨Q′, Σ, δ′, q₀, F′⟩ không có trạng thái không đến được, tương đương với ôtômat A = ⟨Q, Σ, δ, q₀, F⟩, được định nghĩa như sau:

• $Q^{\prime }=\bigcup _{i=1}^{\mathrm{\infty }}{S}_i$
• ∀q ∈ Q′, a ∈ Σ:  δ′(q, a) = δ(q, a)
• $F^{\prime }=F\cap Q^{\prime }=F\cap \bigcup _{i=1}^{\mathrm{\infty }}{S}_i$

Tài liệu tham khảo

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