由右线性文法构造与之等价的FA的程序实现

以下是一个简单的 Python 程序实现：

from collections import defaultdict

def build_fa(rules, start_symbol):
    fa = defaultdict(dict)
    for rule in rules:
        lhs, rhs = rule.split('->')
        rhs = rhs.strip()
        if len(rhs) == 1:
            fa[lhs][rhs] = lhs
        else:
            for i in range(len(rhs)-1):
                fa[rhs[i]][rhs[i+1]] = rhs[i+1]
            fa[lhs][rhs[0]] = rhs
    return fa, start_symbol


def match(fa, start_symbol, input_string):
    state = start_symbol
    for c in input_string:
        if c not in fa[state]:
            return False
        state = fa[state][c]
    return state == input_string[-1]


if __name__ == '__main__':
    rules = [
        'S -> aSb',
        'S -> ε'
    ]
    fa, start_symbol = build_fa(rules, 'S')

    assert match(fa, start_symbol, '') == True
    assert match(fa, start_symbol, 'ab') == True
    assert match(fa, start_symbol, 'aabb') == True
    assert match(fa, start_symbol, 'aabbb') == False

这个程序使用 defaultdict 构建了一个 FA，其中每个状态都是一个字典，字典中的键是输入符号，值是转移到的下一个状态。`build_fa` 函数接受一个右线性文法的规则列表和起始符号，然后构建出对应的 FA。`match` 函数接受一个 FA、起始符号和输入字符串，然后检查输入字符串是否被 FA 接受。在这个例子中，右线性文法规则为 S -> aSb 和 S -> ε，它们对应的 FA 如下图所示：