Ôtômat đầy đủ
Theo định nghĩa cơ bản của ôtômat hữu hạn, không nhất thiết từ mọi trạng thái đều có phép chuyển ứng với mọi kí hiệu. Ôtômat đầy đủ là ôtômat có phép chuyển từ mọi trạng thái ứng với mọi kí hiệu của bảng chữ cái vào.
Cách xây dựng ôtômat đầy đủ
Cho ôtômat A = ⟨Q, Σ, δ, q0, F⟩ sau:
Ở đây không có phép chuyển từ trạng thái q0 ứng với chữ “b”. Nếu gặp tình huống này, ta nói ôtômat không đoán nhận xâu vào đó. Tuy nhiên, về mặt hình thức, hàm chuyển trạng thái δ không xác định tại một số giá trị là điều không thuận tiện; ở đây, chẳng hạn, δ(q0, b) không xác định.
Có thể khắc phục điều này dễ dàng bằng cách xây dựng một ôtômat tương đương có thêm một trạng thái – các phép chuyển “còn thiếu” sẽ đi vào trạng thái này, trạng thái này không phải trạng thái kết thúc và mọi đầu vào tiếp theo đều quay vòng tại đó. Ôtômat như vậy gọi là ôtômat đầy đủ. Ôtômat tương đương sau khi sửa có thể trông như sau:
Ta đã thêm trạng thái qfail. Từ mỗi trạng thái khác, ta vẽ phép chuyển đến trạng thái này đúng ở những chỗ trước đó chưa có phép chuyển. Trạng thái này không phải trạng thái kết thúc và quay vòng với mọi đầu vào tiếp theo. Như vậy, ở chỗ mà ôtômat trước gặp một phép chuyển còn thiếu, ôtômat mới không thiếu phép chuyển nào mà đi vào trạng thái qfail.
Do đó, không mất tính tổng quát, ta luôn có thể giả sử ôtômat có phép chuyển với mọi tổ hợp trạng thái và kí hiệu của bảng chữ cái.
Định nghĩa
Với ôtômat đầy đủ A = ⟨Q, Σ, δ, q0, F⟩ ta có
Tài liệu tham khảo
Mục lục: Ôtômat hữu hạn, Ôtômat đầy đủ, Ôtômat hữu hạn không đơn định, Mô phỏng ôtômat không đơn định, Chuyển NFA thành DFA