5
Cho hai không xác định automata hữu hạn M1 và M2, là có một thuật toán hiệu quả để xác định xem các ngôn ngữ được chấp nhận bởi M1 là một superset của ngôn ngữ được chấp nhận bởi M2?Có một thuật toán hiệu quả để quyết định liệu ngôn ngữ được chấp nhận bởi một NFA có phải là một siêu ngôn ngữ của ngôn ngữ khác được chấp nhận không?
Tôi tự hỏi, bạn có biết về sự giảm từ một vấn đề NP hoàn chỉnh khác đối với đẳng cấu NFA không? – hugomg
@missigno: Tôi đã thêm một liên kết vào một bài báo giải thích việc cắt giảm một cách cẩn thận hơn một chút. – Mikola
Mikola, câu trả lời của bạn là chính xác nhưng từ ngữ của bạn là sai: isomorphic có nghĩa là "của hình dạng bằng nhau", hai automatas là isomorphic iff có một bản đồ 1-1 giữa các tiểu bang của họ, như vậy bla bla. Điều không liên quan ở đây, hai automatas có thể chấp nhận cùng một ngôn ngữ mà không bị đẳng cấu. (Nó thêm vào sự nhầm lẫn rằng việc kiểm tra đẳng cấu đồ thị cũng là NP-Hard) Nếu bạn chỉnh sửa câu trả lời của bạn là "liệu hai NFA chấp nhận cùng một ngôn ngữ" thay vì "cho dù hai NFA là isomorphic" tất cả sẽ được sử dụng tốt. –