Bằng chứng chung về sự tương đương của hai FSM trong thời gian hữu hạn?

Question

Có một bằng chứng chung tồn tại cho sự tương đương của hai máy tính hữu hạn (xác định) hữu hạn luôn luôn mất thời gian hữu hạn? Tức là, với hai FSM, bạn có thể chứng minh rằng với cùng một đầu vào, chúng sẽ luôn tạo ra cùng một kết quả đầu ra mà không cần thực thi FSM (có thể không kết thúc?). Nếu bằng chứng đó tồn tại, độ phức tạp của thời gian là gì?

Answer 1

Có bằng chứng, mặc dù tôi không biết. Hãy tìm sách giáo khoa của Sipser về chủ đề, đó là nơi tôi biết về nó.

Scrounging bộ nhớ của tôi: về cơ bản, có một DFA tối thiểu duy nhất cho một DFA nhất định, và có một thuật toán giảm thiểu luôn luôn chấm dứt. Giảm thiểu cả A và B và xem liệu chúng có cùng DFA tối thiểu hay không. Tôi không biết sự phức tạp của việc giảm thiểu, mặc dù nó không quá tệ (tôi nghĩ rằng đa thức của nó). Graph isomorphism là khá khó tính toán, nhưng vì có một nút khởi đầu đặc biệt, nó hy vọng có thể dễ dàng hơn một chút. Bạn thậm chí có thể không đòi hỏi đồ thị đẳng cấu, phải trung thực.

Nhưng không, bạn không bao giờ cần thực sự chạy DFA, chỉ cần phân tích cấu trúc của chúng.

Answer 2

Giả sử bạn có hai FSM với trạng thái O (n). Sau đó, bạn có thể tạo FSM có kích thước O (n) chỉ nhận ra sự khác biệt đối xứng của ngôn ngữ chấp nhận của chúng. (Tạo một FSM có các trạng thái tương ứng với một cặp trạng thái, một từ mỗi FSM. Sau đó, trên mỗi bước, cập nhật từng phần của cặp cùng một lúc. Một trạng thái trong FSM mới là một trạng thái chấp nhận iff chính xác một trong các cặp là một trạng thái chấp nhận.) Bây giờ giảm thiểu FSM này và xem nó có giống FSM một trạng thái tầm thường loại bỏ mọi thứ không. Giảm thiểu một FSM với m tiểu bang đòi hỏi thời gian O (m log m), vì vậy tổng thể bạn có thể làm tất cả mọi thứ trong thời gian O (n log n).

@Agor nêu chính xác rằng Sipser là một tham chiếu tốt cho những thứ này. Điểm mấu chốt của câu trả lời của tôi là bạn có thể làm điều này trong thời gian đa thức, ngay cả với một số mũ nhỏ.