如何让DFA代码正确遵循终态规则？解决短字符串误判问题

我编写了一段DFA代码，能够正确判定x=abbaaa、y=baba、z=abaaabaaab这类字符串的接受状态，但输入a、ab、b这类短字符串时，代码会错误输出“ACCEPTED”。现需修正代码，使其严格遵循DFA的终态规则（DFA的终态为q3和q5）。

原代码 #

state = 0
flag = False 
string = input("Introduce the string to determine if is accepted or not by the DFA: ")
separated_string= list(string)
print("The string is:", separated_string)


for i in(separated_string):
    if state==0:
        if i=="a":
            print("From q0 to q1")
            state=1
        elif i=="b":
            print("From q0 to q4")
            state=4
    elif state==1:
         if i=="b":
            print("From q1 to q2")
            state=2
         else:
            print("not accepted")
            flag = True
            break;
    elif state==2:
         if i=="a":
            print("From q2 to q2")
            state=2
         else:
            print("From q2 to q3")
            state=3
    elif state==3:
         if i=="a":
            print("From q3 to q3")
            state=3
         else:
            print("Not accepted")
            flag = True
            break;
    elif state==4:
         if i=="a":
            print("From q4 to q4")
            state=4
         else:
            print("From q4 to q5")
            state = 5
    elif state==5:
         if i=="a":
            print("From q5 to q5")
            state=5
         else:
            print("Not accepted")
            flag = True
            break;

if (flag == True):
   pass
else:
   print("ACCEPTED ")

问题原因 #

原代码仅在遇到非法字符转移时标记flag=True，但未检查字符串处理完毕后当前状态是否为DFA的接受态。例如输入a后，最终状态是q1（非接受态），但代码因未触发flag就输出ACCEPTED，违反了DFA的核心规则：只有当字符串处理完成后处于终态时，才判定为接受。

修复后的代码 #

state = 0
flag = False
# 定义DFA的接受态集合
accept_states = {3, 5}
string = input("输入要判定的字符串：")
separated_string = list(string)
print("字符串拆分后：", separated_string)

for i in separated_string:
    if state == 0:
        if i == "a":
            print("从q0转移到q1")
            state = 1
        elif i == "b":
            print("从q0转移到q4")
            state = 4
    elif state == 1:
        if i == "b":
            print("从q1转移到q2")
            state = 2
        else:
            print("不接受：非法转移")
            flag = True
            break
    elif state == 2:
        if i == "a":
            print("从q2转移到q2")
            state = 2
        else:
            print("从q2转移到q3")
            state = 3
    elif state == 3:
        if i == "a":
            print("从q3转移到q3")
            state = 3
        else:
            print("不接受：非法转移")
            flag = True
            break
    elif state == 4:
        if i == "a":
            print("从q4转移到q4")
            state = 4
        else:
            print("从q4转移到q5")
            state = 5
    elif state == 5:
        if i == "a":
            print("从q5转移到q5")
            state = 5
        else:
            print("不接受：非法转移")
            flag = True
            break

if flag:
    print("NOT ACCEPTED")
else:
    # 检查最终状态是否属于接受态
    print("ACCEPTED" if state in accept_states else "NOT ACCEPTED")

修复说明 #

1. 新增accept_states集合，明确指定DFA的终态为q3和q5；
2. 字符串处理循环结束后，先判断是否存在非法转移（flag为True时直接输出NOT ACCEPTED）；
3. 若无非法转移，进一步检查当前状态是否在接受态集合中，只有满足该条件才输出ACCEPTED，否则输出NOT ACCEPTED。

修正后，a（终态q1）、ab（终态q2）、b（终态q4）这类短字符串会被正确判定为NOT ACCEPTED，符合条件的长字符串仍能正常识别。

内容的提问来源于stack exchange，提问作者JPtheOne