유한 상태 오토마타에 의해 받아 들여지는 언어를위한 좋은 해시 함수를 찾는 것

Question

나는 프로젝트에서 자바로 작업하고있다. (그러나 언어에 의존하지 않는다고 생각한다.) 작은 (4 상태 최대) 비 결정적 유한 상태 오토마타 이진 알파벳에 나는 이전의 것들과 동등한 것을 위해 생성 된 automaton을 빨리 체크해야한다. 따라서 너무 많은 automatas를 사용하지 않으려면 몇 가지 좋은 해시 함수를 사용해야합니다.

첫 번째 생각은 전환시 DFS를 수행하고 길이가 최대가 될 때까지 허용 된 단어를 모두 찾았습니다. 5 그리고 나서 받아 들여진 단어 집합을 64 비트 길이 (길이가 최대 5 인 이진 단어의 양)로 매핑합니다. 그러나 그것은 4 개주의 NFA에서 너무 많은 충돌을 일으키는 것으로 보인다. 길이를 늘리면 해시 코드의 계산이 실제 사용에 비해 너무 느려집니다.

또 다른 접근법은 일련의 단어를 가지고 있고 그것들 중 어떤 것이 오토 마톤을 받아들이지 만 올바른 단어를 찾는 지 테스트하는 것이 사소한 것이 아닙니다.

속도가 크게 저하되지 않으면 서 너무 많은 충돌을 피하기 위해 해시 기능을 개선하는 방법에 대해 알고 계십니까? 단사 어떤 NFA의 기능 (더 정확하게 또는, 그것에 의해 받아 들여 언어) 정수로 - -의가 보자

가

Answer 1

내가 더 생각

(감사 @justhalf가와 @templatetypedef) 내가 생각이 사전에

감사합니다 NFA A. 완전한 델타 함수로 동일한 언어를 받아들이는 최소한의 DFA A_min을 구성합시다. Myhill-Nerode 정리의 결과로이 자동 연산은 동형을 제외하고 모호하지 않아야합니다. 초기 상태에서 BFS를 수행하여 알파벳의 고정 된 문자 순서 (예 : 처음 0, 2 번째 1)에 따라 가장자리 (전환)를 우선합니다. 방문 순서에 따라 주 번호를 다시 매 깁니다. 이제 우리는 표준 최소 DFA를 가지며 상태의 발생 행렬을 정수로 매핑하고 최종 상태의 열거를 추가 할 수 있습니다 (또는 충돌을 피하기 위해 더 나은 튜플을 생성). 이 정수는 두 개의 NFA의 동등성을 결정하는 데 사용될 수 있습니다. 생각하니, 괜찮습니까? 다른 생각이 있습니까?