正规文法转有穷自动机程序设计 代码

以下是正规文法转有穷自动机的 Python 代码实现：

class FiniteAutomaton:
    def __init__(self, states, alphabet, transitions, start_state, accept_states):
        self.states = states
        self.alphabet = alphabet
        self.transitions = transitions
        self.start_state = start_state
        self.accept_states = accept_states

    def is_accepted(self, string):
        current_state = self.start_state
        for char in string:
            if char not in self.alphabet:
                return False
            current_state = self.transitions[current_state][char]
        return current_state in self.accept_states

def regular_grammar_to_finite_automaton(grammar):
    nonterminals = set(grammar.keys())
    alphabet = set()
    for production in grammar.values():
        for symbol in production:
            if symbol not in nonterminals:
                alphabet.add(symbol)
    start_state = next(iter(nonterminals))
    accept_states = set([state for state in nonterminals if '' in grammar[state]])
    transitions = {}
    for state in nonterminals:
        transitions[state] = {}
        for symbol in alphabet:
            if symbol in grammar[state]:
                transitions[state][symbol] = grammar[state][symbol]
            else:
                transitions[state][symbol] = None
    return FiniteAutomaton(nonterminals, alphabet, transitions, start_state, accept_states)

上述代码中，`FiniteAutomaton` 类表示有穷自动机，包含了状态集合、字母表、转移函数、起始状态和接受状态。`is_accepted` 方法用于判断一个字符串是否被有穷自动机接受。

`regular_grammar_to_finite_automaton` 函数接受一个正规文法作为参数，将其转换为有穷自动机，并返回一个 `FiniteAutomaton` 对象。在转换过程中，首先获取非终结符和终结符的集合，然后找到起始状态和接受状态。接着，构建转移函数，对于每个状态和字母，若在文法中存在该状态和该字母对应的产生式，则将其添加到转移函数中，否则添加 None。最后，将所有信息传入 `FiniteAutomaton` 构造函数中，构建有穷自动机对象并返回。