由左线性文法构造与之等价的FA的代码实现

左线性文法可以通过构造等价的有穷自动机来实现。具体实现步骤如下：

1. 将左线性文法转换为右线性文法。
2. 构造一个空的有穷自动机，包含一个起始状态和一个接受状态。
3. 对于每个右线性文法的产生式，将其转换为状态转移函数，将右侧部分作为输入，左侧部分作为输出，将其添加到自动机中。
4. 如果产生式右侧为空，则将其左侧作为自动机的接受状态。

下面是一个示例代码实现，假设左线性文法为：

S -> aS | b

转换为右线性文法：

S -> Sa | b

代码实现：

class Automaton:
    def __init__(self):
        self.states = {'start': {}, 'accept': {}}
        self.current_state = 'start'

    def add_transition(self, state, input_symbol, output_symbol):
        if state not in self.states:
            self.states[state] = {}
        self.states[state][input_symbol] = output_symbol

    def add_accept_state(self, state):
        self.states['accept'][state] = None

    def is_accept_state(self, state):
        return state in self.states['accept']

    def transition(self, input_symbol):
        if input_symbol in self.states[self.current_state]:
            self.current_state = self.states[self.current_state][input_symbol]
            return True
        else:
            return False

    def reset(self):
        self.current_state = 'start'

def left_linear_grammar_to_fa(grammar):
    # 转换为右线性文法
    right_grammar = {}
    for left, right in grammar.items():
        for rule in right:
            if rule[0] not in right_grammar:
                right_grammar[rule[0]] = []
            right_grammar[rule[0]].append(left)

    # 构造自动机
    automaton = Automaton()
    for input_symbol in right_grammar:
        for output_symbol in right_grammar[input_symbol]:
            automaton.add_transition('start', input_symbol, output_symbol)
    for left in grammar.keys():
        automaton.add_accept_state(left)

    return automaton

使用示例：

grammar = {'S': ['aS', 'b']}
automaton = left_linear_grammar_to_fa(grammar)

# 测试输入字符串
inputs = ['aaab', 'ab', 'b', 'aaaab']
for input_str in inputs:
    automaton.reset()
    for c in input_str:
        automaton.transition(c)
    if automaton.is_accept_state(automaton.current_state):
        print(input_str, 'accepted')
    else:
        print(input_str, 'rejected')

输出结果：

aaab accepted
ab accepted
b accepted
aaaab rejected