Đang cố gắng tìm một thuật toán có 2 cụm từ thông dụng và cho biết chúng tương đương với

Question

Tôi đang cố gắng tìm hiểu thuật toán sẽ được đưa ra hai ngôn ngữ L1 và L2 để xác định xem chúng có tương đương hay không (L1 = L2) .

Đó là đáng ngạc nhiên khó khăn để đến với một như tôi đã tìm thấy, mặc dù tôi khá chắc chắn nó cần phải được chuyển đổi sang một DFA đầu tiên và sau đó giảm mỗi người trong số họ một DFA tối thiểu ..

Ngoài ra, Tôi biết rằng nếu L1 - L2 và L2 - L1 trống, thì L1 = L2.

Bất kỳ ai giỏi về lý thuyết ở đây?

Answer 1

Bạn có thể tìm thấy mô tả về thuật toán hiệu quả hợp lý để kiểm tra r.e. bình đẳng ở đây:

http://arxiv.org/PS_cache/arxiv/pdf/0907/0907.5058v1.pdf

Dig qua tài liệu tham khảo của bài viết để tìm các giải pháp khác mà bạn có thể kém hiệu quả, nhưng dễ dàng để thực hiện.

Answer 2

Đây là câu trả lời đơn giản về khái niệm (giả sử L1 và L2 là thông thường).

1) Tìm DFA D1 và D2 ​​tương ứng với L1 và L2.

2) Xây dựng D'1 và D'2 từ D1 và D2 ​​bằng cách hoán đổi trạng thái chấp nhận/không chấp nhận (lưu ý rằng D'1 chấp nhận chính xác ~ L1 và D'2 chấp nhận ~ L2 trong đó ~ có nghĩa là "bổ sung")

3) Sử dụng việc xây dựng sản phẩm tiêu chuẩn ba lần để tạo ra một DFA chấp nhận chính xác (L1 giao nhau ~ L2) công đoàn (L2 giao nhau ~ L1)

4) Kiểm tra xem nếu DFA từ phần 3 chấp nhận bất kỳ chuỗi nào bằng cách kiểm tra từng trạng thái chấp nhận để có thể truy cập từ trạng thái bắt đầu.

5) Nếu DFA từ phần 3 chấp nhận bất kỳ chuỗi nào, sau đó L1 <> L2. Nếu không, L1 = L2

Có một số lượng lớn các chẩn đoán bạn có thể sử dụng để tăng tốc độ này, nhưng về khái niệm, đây có lẽ là thuật toán đơn giản nhất. Một tài liệu tham khảo tốt cho việc xây dựng sản phẩm trong phần 3 là "Automata và Computability" của Dexter Kozen.