유한 오토마타의 수정 된 버전에서 허용되는 언어 대신 두 개의 개별

결정 론적 유한 오토 마톤 (DFA)은 모든 정규 언어 만 수용 할 수있는 상태 머신 모델입니다. DFA는 각 상태가 입력 알파벳의 모든 요소에 대해 약간의 전환을 제공해야하는 방식으로 정의 될 수 있으며 일반적으로 정의 될 수 있습니다. 즉, 전이 함수 는 (총) 함수 여야합니다.

δ:Q×Σ→Q

우리가 DDFA (Doublely Deterministic Finite Automaton)라고 부르는 것을 상상해보십시오. DFA와 유사하게 정의되며 두 가지 예외가 있습니다. 첫째, 가능한 모든 입력 심볼마다 하나의 상태에서 다른 상태로 전환하는 대신 두 개의 개별 상태로 연결되어야합니다. 둘째, 문자열을 허용하려면 모든 잠재적 경로가 다음 조건 중 하나를 만족해야합니다.

  1. DDFA를 통한 모든 잠재적 경로는 수용 상태로 이어집니다 (이를 유형 1 DDFA라고합니다).
  2. 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를 복제하고 복제 된 상태에 에지를 추가하면됩니다. 상태 경우 로 전환이 2X를 , 당신은에서 전환 할 1 까지 2X 뿐만 아니라. 또한, s의 1 로 천이 보유 S 2S (2) 에서 X가 . 물론,이 방법은 우리는 거의 항상 상태에있을 것입니다 이야 나는 동시에 (또는 아마도에만 이야 난을

s1

s2

x

s1

s2′

x

s1′

s2

s2′

x

si

si′

si

) 따라서 동일한 언어를 인식 할 것입니다.

업데이트 : 언어 { a } 를 인식하는 type-2 DDFA가 없으므로 type-2에 대해 있습니다 . 당신은이 DDFA을하려고하면, 당신은 시작 상태가 S , 다음은 상태에 두 나가는 가장자리가 있어야 1s의 2 하지만, 이러한 상태는 구별되어야하고, 따라서 두 받아들이는 경로의 끝 다른 수락 상태에 있습니다.

L(DFA)≠L(DDFA)

{a}

s

s1

s2

a

Dave Clarke의 답변과 함께 완벽한 분석을 제공합니다.