계산 이론 - DFA

Question

내가 3의 'Z'배수의 번호 (예 : "xzyyxzzyy")

아무도 방법을 알고 있는가에 단어를 받아들이는 알파벳 {X, Y, Z}의 DFA를 설계 할 ? 또는 그것을 받아들이는 언어는 무엇입니까?

Answer 1

표시된 z의 수를 추적하려면 세 가지 상태가 필요합니다 (모듈로 3). 상태는 입력 z에서 서로 순환하고, # z (w) = 0 (mod 3)에 대한 것만이 유일한 수락 상태가됩니다.

임의의 x와 y를 허용하려면 각 상태가이 입력에서 반복 될 수 있습니다.

상태에 대해 q0, q1 및 q2를 사용하면 q0을 초기 상태로 만들고 상태 만 수락 할 수 있습니다. 그런 다음 세 개의 전이 f (qi, z) = wh를 가지며 여기에서 j = i + 1 (mod 3), 세 개의 전이 f (q, x) = q 및 세 개의 전이 f 9 전환.