Chuyển ôtômat thành biểu thức chính quy

Ta sẽ xem cách chuyển một ôtômat hữu hạn bất kì thành biểu thức chính quy.

Mô tả thuật toán

Đầu vào là một NFA A. Trước hết ta chuyển nó thành GNFA. Ở giai đoạn thứ hai, mỗi bước ta loại bỏ một trạng thái, sửa lại hàm chuyển trạng thái cho đúng, rồi lặp lại cho đến khi chỉ còn hai trạng thái – trạng thái bắt đầu và trạng thái kết thúc. Giữa chúng có một cạnh, nhãn của cạnh là một biểu thức chính quy, và đó chính là kết quả của toàn bộ thuật toán. Như vậy, cốt lõi của cả quá trình là loại bỏ một trạng thái rồi sửa ôtômat sao cho được một ôtômat tương đương.

Loại bỏ một trạng thái

Cách loại bỏ một trạng thái có thể minh hoạ bằng một ví dụ đơn giản. Giả sử một phần của ôtômat như sau:

trong đó R_i là các biểu thức chính quy nào đó. Ôtômat sẽ như thế nào nếu loại bỏ trạng thái q_r? Có thể hình dung ta đang ở trạng thái q_i và hỏi: trên đoạn này, ta có thể sinh ra những xâu nào? Nếu đi thẳng từ trạng thái q_i đến trạng thái q_j, đó là mọi xâu khớp với biểu thức chính quy R₄.

Còn nếu đi đến trạng thái q_r, ta có thể sinh ra các xâu dạng R₁. Nhưng ở trạng thái q_r, ta có thể quay vòng theo biểu thức chính quy R₂, nên thực ra ta có thể sinh ra các xâu dạng $R_1\circ (R_2^{\ast })$. Vì từ trạng thái q_r còn có thể đi đến trạng thái q_j, ta thêm biểu thức chính quy R₃. Tóm lại, theo đường này ta có thể nhận được các xâu dạng $R_1\circ (R_2^{\ast })\circ R_3$.

Bây giờ ta biết rằng phần này của ôtômat có thể sinh ra các xâu dạng R₄ hoặc dạng $R_1\circ (R_2^{\ast })\circ R_3$. Tất nhiên có thể viết điều này dưới dạng biểu thức chính quy $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Bây giờ có thể dễ dàng loại bỏ trạng thái q_r, chỉ giữ lại hai trạng thái q_i và q_j, và thay cho R₄ ta ghi biểu thức chính quy vừa tìm được:

Ta làm như vậy với mọi cạnh từ mỗi trạng thái q_i đến một trạng thái q_j nào đó, kể cả các khuyên, tức là kể cả trường hợp q_i = q_j.

Sau khi loại bỏ một trạng thái, ta được một ôtômat tương đương – ôtômat đoán nhận cùng một ngôn ngữ.

Toàn bộ thuật toán

Đầu vào là NFA A = ⟨Q, Σ, δ, q₀, F⟩.

1. Chuyển NFA A thành GNFA Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Từ đây kí hiệu k là số trạng thái của Z.
2. Nếu k = 2, thuật toán kết thúc và biểu thức chính quy cần tìm nằm trên cạnh giữa trạng thái bắt đầu và trạng thái kết thúc.
3. Nếu k>2, chọn một trạng thái bất kì q_r khác trạng thái bắt đầu và trạng thái kết thúc, tức là q_r ≠ q₀′ và q_r ≠ q_f′. Tiếp theo, tạo GNFA mới Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩ thoả mãn: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ và với mọi q_i ∈ Q′′ ∖ {q_f′} và mọi q_j ∈ Q′′ ∖ {q₀′}, đặt $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ trong đó R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Sau đó quay lại bước 2.

Ví dụ

Cho ôtômat hữu hạn đầu vào sau:

Trước hết ta chuyển nó thành GNFA (không vẽ các phép chuyển ∅ thừa):

Bây giờ ta áp dụng phần thứ hai của thuật toán và loại bỏ một nút. Bắt đầu với nút q₂. Ta loại bỏ nút q₂ và thêm phép chuyển từ trạng thái q₁ đến trạng thái q_f. Phép chuyển này được ghi là b(a|b)^∗, vì từ nút q₁ ta đến trạng thái q₂ với các xâu dạng b, sau đó có thể quay vòng với a|b, ta được (a|b)^∗, và cuối cùng chuyển sang q_f nhờ phép chuyển epsilon. Ở đây b(a|b)^∗ϵ = b(a|b)^∗. Ta được ôtômat:

Chỉ còn một trạng thái cần loại bỏ là q₁. Ta thêm cạnh từ trạng thái q_s đến trạng thái q_f. Ghi nhãn cạnh này thế nào? Ta đến trạng thái q₁ nhờ phép chuyển epsilon, có thể bỏ qua ngay phần này. Sau đó ta có thể quay vòng với a, nên được biểu thức chính quy a^∗. Cuối cùng, qua cạnh còn lại ta đến q_f, nên ghép biểu thức này với b(a|b)^∗. Như vậy, nhãn của cạnh là biểu thức chính quy a^∗ b(a|b)^∗.

Ôtômat chỉ còn hai trạng thái, nên thuật toán kết thúc. Trên cạnh là biểu thức chính quy cần tìm.

Tài liệu tham khảo

• Ví dụ và mô tả thuật toán lấy từ M. Sipser: Introduction to the Theory of Computation