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

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

δ : Q \times Σ \to Q

$\delta : Q \times \Sigma \rightarrow Q$

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

DDFA를 통한 모든 잠재적 경로는 수용 상태로 이어집니다 (이를 유형 1 DDFA라고합니다).
DDFA를 통한 모든 잠재적 경로는 동일한 수락 상태로 이어집니다 (이를 유형 -2 DDFA라고합니다).

이제 내 질문에 :

유형 1 및 유형 2 DDFA는 어떤 언어를 허용합니까? 구체적으로, , 또는 ? 경우에서 $L (D F A) ⊊ L (D D F A)$
$L (D F A) ⊊ L (D D F A)$
$L(DFA) \subsetneq L(DDFA)$ $L (D D F A) = L (D F A)$
$L (D D F A) = L (D F A)$
$L(DDFA) = L(DFA)$ $L (D D F A) ⊊ L (D F A)$
$L (D D F A) ⊊ L (D F A)$
$L(DDFA) \subsetneq L(DFA)$ , 대한 쉬운 설명이 $L (D D F A) \neq L (D F A)$
$L (D D F A) \neq L (D F A)$
$L(DDFA) \neq L(DFA)$ ? $L (D D F A)$
$L (D D F A)$
$L(DDFA)$

너무 복잡하지 않은 증거 (또는 적어도 적당히 살해진 스케치)는 높이 평가됩니다.

답변

이것은 Alex의 답변 과 결합되어 완전한 그림을 제공합니다.

는 수정 된 최종 상태 조건으로 일반적인 전원 구성을 조정하여 증명할 수 있습니다. 전원 세트 구성에서 상태는 원래 오토 마톤의 상태 세트입니다. 일반적으로 파워 셋 구성을 수행 한 후 세트의 상태 중 하나가 원래 오토 마톤에서 최종이면 상태가 최종입니다. $L (D D F A) \subseteq L (D F A)$

L (D D F A) \subseteq L (D F A)

$L(DDFA)\subseteq L(DFA)$

타입 -1 DDFA에서, 생성 된 오토 마톤의 최종 상태는 모든 요소가 원래 오토 마톤에서 최종인 세트입니다.
유형 2 DDFA에서 최종 상태는 원래 오토 마톤의 최종 상태의 단일 세트입니다.

두 경우 모두 결과 오토마타는 DFA입니다.

이제 type-2DDFA 는 시작 상태가 허용되는지 여부에 따라 및 언어 만 표현할 수 있습니다 . 한 상태에서 두 개의 전이가 별개의 상태로 이동해야하지만, 동일한 상태에서 끝나는 경우에만 승인이 가능하기 때문입니다. ${ϵ}$

{ϵ}

$\{\epsilon\}$ $\emptyset$

\emptyset

$\emptyset$

답변

분석을 시작하기 위해 유형 1에 대해 이라고 말할 수 있습니다 . $L (D F A) \subseteq L (D D F A)$

L (D F A) \subseteq L (D D F A)

$L(DFA) \subseteq L(DDFA)$

DFA를 복제하고 복제 된 상태에 에지를 추가하면됩니다. 상태 경우 로 전환이 에 , 당신은에서 전환 할 까지 에 뿐만 아니라. 또한, 로 천이 보유 및 에서 . 물론,이 방법은 우리는 거의 항상 상태에있을 것입니다 과 동시에 (또는 아마도에만 $s_{1}$

s_{1}

$s_1$ $s_{2}$

s_{2}

$s_2$ $x$

x

$x$ $s_{1}$

s_{1}

$s_1$ $s_{2}^{'}$

s_{2}^{'}

$s_2'$ $x$

x

$x$ $s_{1}^{'}$

s_{1}^{'}

$s_1'$ $s_{2}$

s_{2}

$s_2$ $s_{2}^{'}$

s_{2}^{'}

$s_2'$ $x$

x

$x$ $s_{i}$

s_{i}

$s_i$ $s_{i}^{'}$

s_{i}^{'}

$s_i'$ $s_{i}$

s_{i}

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

업데이트 : 언어 를 인식하는 type-2 DDFA가 없으므로 type-2에 대해 있습니다 . 당신은이 DDFA을하려고하면, 당신은 시작 상태가 , 다음은 상태에 두 나가는 가장자리가 있어야 과 온 하지만, 이러한 상태는 구별되어야하고, 따라서 두 받아들이는 경로의 끝 다른 수락 상태에 있습니다. $L (D F A) \neq L (D D F A)$

L (D F A) \neq L (D D F A)

$L(DFA) \neq L(DDFA)$ ${a}$

{a}

$\{ a \}$ $s$

s

$s$ $s_{1}$

s_{1}

$s_1$ $s_{2}$

s_{2}

$s_2$ $a$

a

$a$

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

How IT

언제든지 물어보세요.

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

답변

답변

답변