Cách tốt nhất để xây dựng Biểu đồ từ theo chu kỳ được chỉ định (DAWG)

Question

Tôi hiện đang xem xét DAWG và tôi không thể tìm thấy một cách tốt để xây dựng một automaton tuần hoàn.

Vì vậy, về cơ bản, những gì tôi muốn làm là thế này:

Nó cơ bản là một cây, nơi mà số lượng của các quốc gia đang giảm. Tôi sẽ sử dụng nó với các con số nhưng khái niệm là chính xác như nhau.

Tôi tự hỏi điều gì sẽ là cách nhanh nhất để làm điều đó, kế hoạch thực tế của tôi là xây dựng biểu đồ như hình bên trái, và sau đó nhìn vào các trạng thái ở mức thấp và khi chúng tương tự như vậy.

Mặc dù, tôi không chắc đây là cách tốt nhất để làm điều đó, không ai có ý tưởng về cách xây dựng nó.

Trân trọng.

Answer 1

DAWG là loại tự động hữu hạn tối thiểu của tiểu bang cho tập hợp cụ thể nếu chuỗi chúng lưu trữ. Bạn có thể xây dựng chúng bằng cách xử lý trie bạn có như một automaton hữu hạn không tối thiểu và chạy một thuật toán giảm thiểu DFA tiêu chuẩn trên nó. Đây có lẽ là cách dễ nhất để xây dựng DAWG, và cũng có thể là nhanh nhất.

Hy vọng điều này sẽ hữu ích!