유한 한 시간에 두 FSM의 동등성에 대한 일반적인 증거?

Question

항상 유한 한 시간이 걸리는 두 가지 (결정 론적) 유한 상태 기계의 동등성에 대한 일반적인 증거가 있습니까? 즉, 두 개의 FSM이 주어지면 동일한 입력이 주어지면 실제로 FSM을 실행할 필요없이 항상 동일한 출력을 생성한다는 것을 증명할 수 있습니다 (이는 말할 수 없습니까?). 그러한 증거가 존재한다면 시간 복잡성은 얼마입니까?

Answer 1

나는 그것을 모른다. 주제에 대한 Sipser의 교과서를 찾으십시오. 그것이 내가 알고있는 곳입니다.

내 메모리 스크로닝 : 기본적으로 주어진 DFA에 대한 고유 한 최소 DFA가 있으며 항상 종료되는 최소화 알고리즘이 있습니다. A와 B를 모두 최소화하고 동일한 최소 DFA를 가지고 있는지 확인하십시오. 나는 최소화의 복잡성을 알지 못하지만 너무 나쁘지는 않지만 (다항식이라고 생각합니다). 그래프 동형은 계산하기가 매우 어렵지만 특별한 시작 노드가 있기 때문에 다소 쉬울 수 있습니다. 솔직히 말하면 그래프 등가성이 필요하지 않을 수도 있습니다.

그러나 아니요, 실제로 DFA를 실행할 필요는 없으며 구조를 분석하십시오.

Answer 2

O가있는 두 개의 FSM이 있다고 가정합니다.N) 상태. 그런 다음 크기의 FSM을 만들 수 있습니다.N²)는 수용 언어의 대칭 차이 만 인식합니다. (각 FSM에서 하나의 상태에 해당하는 상태가있는 FSM을 만듭니다. 각 단계에서 각 단계에서 쌍의 각 부분을 동시에 업데이트하십시오. 새 FSM의 상태는 쌍 중 하나가 정확히 하나의 수락 상태입니다. 수락 상태.) 이제이 FSM을 최소화하고 그것이 모든 것을 거부하는 사소한 원 스테이트 FSM과 동일한 지 확인하십시오. FSM 최소화 중 상태는 시간이 걸립니다.중 통나무 중), 전체적으로 시간에 모든 것을 할 수 있습니다.N² 통나무 N).

@agor는 Sipser가 이러한 종류의 것들에 대한 좋은 참조라고 올바르게 말합니다. 내 대답의 핵심 요점은 작은 지수로도 다항식 시간에 이것을 할 수 있다는 것입니다.