确定性有限自动机的实现

Question

我需要构建一个状态机，并编写一个控制程序来识别一组0和1字符串，在这些字符串中，每出现一次都有三个零。下面是我的代码，它不能正常工作。我将非常感谢你的建议

Z = ["0", "1"]
Q = ["A", "B"]
S = "A"
F = "B"

def delta(s, z):
    i = Q.index(s)
    j = Z.index(z)
    matrix = [["A", "B"], ["B", "A"]]
    return matrix[i][j]

chain = "1000110110101"
transitions = ""

for char in range(len(chain)):
    if char == 0:
        transitions += S
        s = delta(S, chain[char])
    else:
        s = delta(s, chain[char])
    transitions += s

if transitions != "":
    print("The sequence of transitions of a finite automaton:", transitions)
    if transitions[-1] == F:
        print("Chain ", chain, "is allowed automaton, because the latter is the allowable state ", F)
    else:
        print("Chain ", chain, " is rejected by the automaton, so its final state is an inadmissible state", S)
else:
    print("The chain is empty.")

Answer 1

您可能还没有被介绍到类，但我肯定会推荐使用他们的DFAs。

class binaryNode:
    def __init__(self):
        self.zero = self
        self.one = self
        self.isAccept = True
    def process(self,char):
        if char == "0":
            return self.zero
        if char == "1":
            return self.one

#Define Nodes
start = binaryNode()
one = binaryNode()
firstZero = binaryNode()
secondZero = binaryNode()
thirdZero = binaryNode()
trailingZero = binaryNode()
reject = binaryNode()

#Define Edges
start.one = one
one.one = reject
one.zero = firstZero
firstZero.zero = secondZero
firstZero.one = reject
secondZero.zero = thirdZero
secondZero.one = reject
thirdZero.one = one
thirdZero.zero = trailingZero
trailingZero.one = reject

#Set Accept (or in this case reject) state
reject.isAccept = False

def process(chain,node):
    for char in chain:
        node = node.process(char)
    return node.isAccept

tests = ["0000",
         "01000100",
         "0100010001000100",
         "0100001",
         "100101",
         "10001",
         "10000"]

for chain in tests:
    print(chain)
    print(process(chain,start))
    print()

我解释了你的“识别一组0和1的字符串，其中一次发生之间有三个零”，重点是在so 100000000次传递和100次之间，因为没有第二个1来满足“中间”方面，但也许我误解了。