두 DFA의 결합을 어떻게 구성합니까?

Question

주어진 두 DFA의 합집합을 생성하는 알고리즘에 대한 간단한 설명이 있습니까? 예를 들어, 우리는 두 DFA의 이상 {0,1}이 말을 어디

{w|w has an odd number of characters} 
    w has states A and B 

delta | 0 | 1 
---------------- 
    A | B | B 
---------------- 
    B | A | A 


{x|x has an even number of 1s} 
    x has states a and b 

delta | 0 | 1 
---------------- 
    a | a | b 
---------------- 
    b | b | a 

내가 가지고있는 노동 조합 보여주는 결과 전환 테이블 : 내 강의 노트에 그림으로 솔루션을

delta | 0 | 1 
---------------- 
    Aa | Ba | Bb 
---------------- 
    Ab | Bb | Ba 
---------------- 
    Ba | Aa | Ab 
---------------- 
    Bb | Ab | Aa 

을, 다른 사람들이 어떻게 설명하는지보고 싶습니다. 이것으로부터, 우리는 근본적으로 두 개의 원래 테이블에 상태 값을 "곱하여"더 큰 전이 테이블을 생성한다는 것을 알 수 있습니다. 따라서 DFA는 결과 테이블에서 가져올 수 있습니다. 이 말이 맞는 것인가요?이 방법이 모든 DFA 사례에서 효과가 있습니까, 아니면 제가 누락 된 것이 있습니까?

Answer 1

두 가지 DFA를 동시에 실행해야하거나 일반적으로 DFA의 두 DFA 상태를 유지 관리해야한다는 것을 이해해야합니다.

그런 이유로 원래 DFA의 새 상태를 원래 상태의 직접적인 곱셈으로 만들어야합니다. 이렇게하면 원본 DFA의 모든 상태 조합에 대한 상태가됩니다.

새 DFA의 전환 규칙을 직접 계산할 수 있습니다. 예를 들어 상태가 Ab이고 입력이 0 인 경우 첫 번째 DFA는 상태 B로 이동하고 두 번째 것은 상태 b로 이동하므로이 DFA의 다음 입력은 Bb가됩니다.

이 방법은 두 개 이상의 DFA가 결합되어야 할 때마다 작동합니다. 결과로 생성되는 DFA는 최적이 아니지만 나중에 원하는 알고리즘으로 최소화 할 수 있습니다.