NFA 최소화 결정없이

Question

일반 언어의 경우 NFA에서 최소 DFA로받는 방법은 잘 알려져 있습니다. 그러나 DFA는 기하 급수적으로 많은 상태를 가질 수 있습니다.

내가 필요로하는 것은 NFA를 줄이기 위해 NFA를 다시주는 방법이지만 작은 숫자로 개의 상태를 제공합니다. T.i. 그 결과가 결정 론적 일 필요는 없지만 인식 된 언어를 보존하면서 가능한 한 작게하고 싶습니다 (아마도 절대적으로 최적은 아니지만 작을수록 좋을 것입니다).

이 문제에 가장 적합한 알고리즘은 무엇입니까? 아니면 "최고"가 아니라 적어도 "비 심적 효율성으로 구현하기 가장 쉬운"것일까? 또는 문제의 이름이 잘 알려져있어 좋은 정보 출처를 직접 찾을 수 있습니까?

Answer 1

이 문제는 NFA 최소화라고도합니다. 일반적으로 NP는 힘들지만 믿습니다.

하나의 유익한 접근법은 Bisimulation Minimization [Paige, Tarjan 1987] 및 그 후의 파생물 일 수 있습니다.

This presentation에는 문제의 취급 용이성에 대한 참고 사항과 상대적인 장점이있는 일부 접근법에 대한 참고 사항이 있습니다. 여기 NFA 최소화를위한 카메-위너 알고리즘의 구현있다

Answer 2

: https://github.com/coder0xff/parlex/blob/master/IDE/Nfa.cs