Ôtômat hữu hạn không đơn định tổng quát

Ôtômat hữu hạn không đơn định tổng quát, viết tắt GNFA, là ôtômat không đơn định mà trên các phép chuyển không chỉ có kí hiệu của bảng chữ cái mà có thể có cả biểu thức chính quy.

Định nghĩa

Ta sẽ cần GNFA trong thuật toán chuyển ôtômat hữu hạn thành biểu thức chính quy. Như vậy, GNFA là một NFA có các phép chuyển được cho bằng biểu thức chính quy. Ví dụ về một GNFA như vậy:

Chẳng hạn, ta thấy từ trạng thái q₂ có phép chuyển đến trạng thái q_f, được ghi bằng biểu thức chính quy a^∗ b. Các yêu cầu khác đối với GNFA:

• Trạng thái bắt đầu q₀ phải có phép chuyển đến mọi trạng thái khác. Trên hình, ta thấy từ trạng thái q₀ có phép chuyển đến mọi trạng thái khác.
• GNFA chỉ có một trạng thái kết thúc, và mọi trạng thái khác đều có phép chuyển đến trạng thái này. Như thấy trên hình, mọi trạng thái đều có mũi tên đi đến q_f.
• Trạng thái bắt đầu không được trùng với trạng thái kết thúc. Vì vậy, GNFA có ít nhất hai trạng thái.
• Mọi trạng thái khác, ngoài trạng thái bắt đầu và trạng thái kết thúc, phải có phép chuyển đến mọi trạng thái khác, ngoài trạng thái bắt đầu và trạng thái kết thúc. Kể cả các khuyên (phép chuyển từ trạng thái q_i đến chính trạng thái q_i).

Chuyển NFA thông thường thành GNFA

Chuyển một NFA bất kì thành GNFA rất đơn giản.

1. Tạo một trạng thái bắt đầu mới q_s và một phép chuyển epsilon từ đó đến trạng thái bắt đầu cũ.
2. Tạo một trạng thái kết thúc mới q_f và từ mọi trạng thái kết thúc cũ vẽ phép chuyển epsilon đến trạng thái q_f. Các trạng thái kết thúc cũ trở thành trạng thái thông thường.
3. Nếu ở đâu đó có nhiều phép chuyển giữa hai trạng thái (chẳng hạn từ trạng thái q₁ đến trạng thái q₂ được cả với kí hiệu 0 lẫn kí hiệu 1), ta gộp chúng thành một biểu thức chính quy, nối mọi kí hiệu ban đầu bằng phép hợp (tức là ghi trên mũi tên biểu thức chính quy 0|1).
4. Nếu ôtômat thiếu một phép chuyển mà theo định nghĩa phải có, ta tạo phép chuyển đó và ghi trên nó biểu thức chính quy ∅. Làm vậy không thay đổi ngôn ngữ mà ôtômat đoán nhận, vì phép chuyển như vậy không bao giờ được thực hiện.

Có thể dùng ôtômat này để chuyển ôtômat thành biểu thức chính quy.