Giảm thiểu NFA mà không cần xác định

Question

Người ta biết rõ cách người ta nhận được từ NFA cho một ngôn ngữ thông thường đến DFA tối thiểu. Tuy nhiên, DFA có thể có số lượng tiểu bang lớn hơn theo cấp số nhân.

Điều tôi cần là cách để giảm NFA, cho lại NFA nhưng với số lượng nhỏ hơn tiểu bang. T.i. Tôi không cần kết quả là xác định, nhưng tôi muốn nó càng nhỏ càng tốt trong khi vẫn giữ được ngôn ngữ được công nhận (có lẽ không hoàn toàn tối ưu, nhưng nhỏ hơn, càng tốt).

Thuật toán tốt nhất cho vấn đề này là gì? Hoặc có lẽ không phải là "tốt nhất" nhưng ít nhất "dễ nhất để thực hiện với hiệu quả phi kiêu căng"? Hay vấn đề có một cái tên nổi tiếng để tôi có thể tự tìm được nguồn thông tin tốt?

Answer 1

Tôi tin rằng vấn đề này cũng chỉ được biết đến là giảm thiểu NFA. Đó là NP-hard nói chung, tôi tin.

Một cách tiếp cận hiệu quả có thể là Giảm thiểu bực bội [Paige, Tarjan 1987] và các dẫn xuất tiếp theo.

This presentation có một số lưu ý về khả năng di chuyển của vấn đề cũng như tham chiếu đến một số phương pháp tiếp cận với giá trị tương đối của chúng được viết.

Answer 2

Có một thực hiện các thuật toán Kameda-Weiner cho NFA giảm thiểu ở đây: https://github.com/coder0xff/parlex/blob/master/IDE/Nfa.cs