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

由右线性文法构造等价的FA可以遵循以下步骤：

1. 对于文法中的每个终结符，创建一个状态，并将其作为FA的终止状态。

2. 对于文法中的每个产生式，将其右侧的符号（终结符或非终结符）反向读取，并将其添加到开始状态的转移函数中。如果该符号是终结符，则将其转移到对应的状态。如果该符号是非终结符，则将其转移到该非终结符对应的状态。

3. 如果文法中存在多个产生式的左部相同且右侧不同，则对应的状态应该合并。

4. 如果文法中存在多个产生式的右部相同且左侧不同，则对应的状态应该分裂。

以下是一个 Python 实现的例子：

def right_linear_grammar_to_fa(grammar):
    # 创建终止状态
    states = {}
    for rule in grammar:
        for symbol in rule[1]:
            if symbol not in states and symbol != " ":
                states[symbol] = {"is_final": True}

    # 创建开始状态
    start_state = {"is_final": False, "transitions": {}}
    for rule in grammar:
        if rule[0] not in start_state["transitions"]:
            start_state["transitions"][rule[0]] = []
        start_state["transitions"][rule[0]].append(states[rule[1][-1]])

    # 合并和分裂状态
    for state in states.values():
        if "transitions" not in state:
            state["transitions"] = {}
        for rule in grammar:
            if rule[1][-1] in state:
                if rule[0] not in state["transitions"]:
                    state["transitions"][rule[0]] = []
                state["transitions"][rule[0]].append(states[rule[1][:-1]])
    
    return start_state

这个函数接受一个列表，其中每个元素表示文法中的一个产生式。例如，对于文法 S -> aS | b，可以传入以下列表：

[("S", "aS"), ("S", "b")]

该函数返回一个字典，表示转换后的 FA。该字典包含一个开始状态和多个终止状态。每个状态都有一个 `transitions` 字段，它表示从该状态开始的转移函数。如果该状态是终止状态，则还有一个 `is_final` 字段。