NFA中的缩写,python

0 投票
1 回答
531 浏览
提问于 2025-04-17 16:07

我正在尝试创建一个方法,让缩写可以从一个点跳到另一个点。

我已经创建了一个非确定性有限自动机(NFA),并且有了当前的边界:

EDGES = [
(0, 'h', 1),
(1,'a',2),
(2,'z', 3),
(3,'a',4),
(4, 'r', 5),
(5, 'd', 6)
)]

这是我想要实现的例子: nrec("h-rd", nfa, 1) 应该返回 accept

nrec 是处理字符串的一个方法,用来检查这个字符串是否被 NFA 接受或拒绝。

def nrec(tape, nfa, trace=0):
"""Recognize in linear time similarly to transform NFA to DFA """
char = "-"
index = 0
states = [nfa.start]
while True:
    if trace > 0: print " Tape:", tape[index:], "   States:", states
    if index == len(tape): # End of input reached
        successtates = [s for s in states
                          if s in nfa.finals]
        # If this is nonempty return True, otherwise False.
        return len(successtates)> 0
    elif len(states) == 0:
        # Not reached end of string, but no states.
        return False
    elif char is tape[index]:

    # the add on method to take in abreviations by sign: -
    else:
        # Calculate the new states.
        states = set([e[2] for e in nfa.edges
                           if e[0] in states and
                              tape[index] == e[1] 
                      ])
        # Move one step in the string
        index += 1 

我需要添加一个方法,考虑到缩写的情况。我不太确定如何从一个状态跳到另一个状态。 这是 NFA 类中的内容:

def __init__(self,start=None, finals=None, edges=None):
    """Read in an automaton from python shell"""
    self.start = start
    self.edges = edges
    self.finals = finals
    self.abrs = {}

我考虑过使用缩写,但每次尝试定义自己的缩写时,总是会出现错误,比如:

nfa = NFA(
start = 0,
finals = [6],
abrs = {0:4, 2:5},
edges=[
(0,'h', 1),
(1,'a', 2),
(2,'z', 3),
(3,'a', 4),
(4,'r', 5),
(5,'d', 6)
])

我收到错误信息 "TypeError: init() got an unexpected keyword argument 'abrs'" 我为什么会收到这个错误呢?

对于这个修改,我想我可以这样做:

 elif char is tape[index]:
 #get the next char in tape tape[index+1] so
 #for loop this.char with abrs states and then continue from that point.

这样做聪明吗?或者有没有更好的解决方案?

1 个回答

0

这个错误是因为 __init__ 方法没有接受 abrs 这个关键字参数,按照现在的定义是这样的。

def __init__(self,start=None, finals=None, edges=None):

你需要把 abrs=None(或者其他值)加上,这样它才能成为一个关键字参数,或者直接把 abrs 放进去,这样它就变成了一个必须提供的参数。

撰写回答