결정 론적 유한 오토 마톤 (DFA)은 모든 정규 언어 만 수용 할 수있는 상태 머신 모델입니다. DFA는 각 상태가 입력 알파벳의 모든 요소에 대해 약간의 전환을 제공해야하는 방식으로 정의 될 수 있으며 일반적으로 정의 될 수 있습니다. 즉, 전이 함수 는 (총) 함수 여야합니다.
δ:Q×Σ→Q우리가 DDFA (Doublely Deterministic Finite Automaton)라고 부르는 것을 상상해보십시오. DFA와 유사하게 정의되며 두 가지 예외가 있습니다. 첫째, 가능한 모든 입력 심볼마다 하나의 상태에서 다른 상태로 전환하는 대신 두 개의 개별 상태로 연결되어야합니다. 둘째, 문자열을 허용하려면 모든 잠재적 경로가 다음 조건 중 하나를 만족해야합니다.
- DDFA를 통한 모든 잠재적 경로는 수용 상태로 이어집니다 (이를 유형 1 DDFA라고합니다).
- DDFA를 통한 모든 잠재적 경로는 동일한 수락 상태로 이어집니다 (이를 유형 -2 DDFA라고합니다).
이제 내 질문에 :
유형 1 및 유형 2 DDFA는 어떤 언어를 허용합니까? 구체적으로, , L ( D D F A ) = L ( D F A ) 또는 L ( D D F A ) ⊊ L ( D F) A ) ? 경우에서 L ( D D F )
L(DFA)⊊L(DDFA)L(DDFA)=L(DFA)
L(DDFA)⊊L(DFA)
, L ( D D)에 대한 쉬운 설명이 있습니까?
L(DDFA)≠L(DFA)?
L(DDFA)
너무 복잡하지 않은 증거 (또는 적어도 적당히 살해진 스케치)는 높이 평가됩니다.
답변
이것은 Alex의 답변 과 결합되어 완전한 그림을 제공합니다.
는 수정 된 최종 상태 조건으로 일반적인 전원 구성을 조정하여 증명할 수 있습니다. 전원 세트 구성에서 상태는 원래 오토 마톤의 상태 세트입니다. 일반적으로 파워 셋 구성을 수행 한 후 세트의 상태 중 하나가 원래 오토 마톤에서 최종이면 상태가 최종입니다.
L(DDFA)⊆L(DFA)-
타입 -1 DDFA에서, 생성 된 오토 마톤의 최종 상태는 모든 요소가 원래 오토 마톤에서 최종인 세트입니다.
-
유형 2 DDFA에서 최종 상태는 원래 오토 마톤의 최종 상태의 단일 세트입니다.
두 경우 모두 결과 오토마타는 DFA입니다.
이제 type-2DDFA 는 시작 상태가 허용되는지 여부에 따라 및 ∅ 언어 만 표현할 수 있습니다 . 한 상태에서 두 개의 전이가 별개의 상태로 이동해야하지만, 동일한 상태에서 끝나는 경우에만 승인이 가능하기 때문입니다.
{ϵ}∅
답변
분석을 시작하기 위해 유형 1에 대해 이라고 말할 수 있습니다 .
L(DFA)⊆L(DDFA)DFA를 복제하고 복제 된 상태에 에지를 추가하면됩니다. 상태 경우 로 전환이 의 2 에 X를 , 당신은에서 전환 할 의 1 까지 의 ‘ 2 에 X 뿐만 아니라. 또한, s의 ‘ 1 로 천이 보유 S 2 및 S ‘ (2) 에서 X가 . 물론,이 방법은 우리는 거의 항상 상태에있을 것입니다 의 난 과 이야 ‘ 나는 동시에 (또는 아마도에만 이야 난을
s1s2
x
s1
s2′
x
s1′
s2
s2′
x
si
si′
si
) 따라서 동일한 언어를 인식 할 것입니다.
업데이트 : 언어 { a } 를 인식하는 type-2 DDFA가 없으므로 type-2에 대해 있습니다 . 당신은이 DDFA을하려고하면, 당신은 시작 상태가 S , 다음은 상태에 두 나가는 가장자리가 있어야 의 1 과 s의 2 온 을 하지만, 이러한 상태는 구별되어야하고, 따라서 두 받아들이는 경로의 끝 다른 수락 상태에 있습니다.
L(DFA)≠L(DDFA){a}
s
s1
s2
a
Dave Clarke의 답변과 함께 완벽한 분석을 제공합니다.