输入符号为 {0,1,2} 且倒数第二个符号为 1 的最小 DFA 中的状态数是多少？

Question

四个选项：-

A. 8

B. 9

C. 6

D. None

谁能用图表解释一下答案..

Answer 1

B.9

每当问题说从右侧开始的第 n 个符号是固定的并且输入语言有 m 个符号时，最小 dfa 的答案是 m^n 。所以 3^2 = 9

Answer 2

接受的答案是错误的。考虑以下语言的最小 DFA：

q    e    q'
q0   0    q0
q0   1    q1
q0   2    q0
q1   0    q2
q1   1    q3
q1   2    q2
q2   0    q0
q2   1    q1
q2   2    q0
q3   0    q2
q3   1    q3
q3   2    q2

另一个答案出错的原因是因为在这种语言中符号 0 和 2 之间没有真正的区别。符号也可以是“1”和"not 1"。当您正确地意识到这一点时，最小状态数确实如其他答案所指出的那样：2^2 = 4 个状态。如果更容易理解的话，这是一个粗略的图表。

  /------0,2--------\
 |         /---1--\ |
 v        v        \|
q0 --1-> q1 -0,2-> q2
         |          ^
         1          |
         v          |
         q3---0,2--/
        / ^
        /

输入符号为 {0,1,2} 且倒数第二个符号为 1 的最小 DFA 中的状态数是多少？

What is the number of states in the minimal DFA with input symbols {0,1,2} where 2nd last symbol is 1?

expression

regular-language

computation-theory

dfa