Есть ли способ представить DFA (конечные автоматы Deterministi c) в список смежности?

Question

Итак, у меня очень большой DFA, и он заполнен PHI, поэтому я хочу преобразовать его в список смежности, чтобы сэкономить много памяти и использовать его, чтобы проверить, принят ли ввод, или вернуть состояние, в котором ввод

И я много искал, но ничего не нашел ...

Я знаю код для графиков веса, но в машине DFA есть несколько весов.

Другое дело, когда мы переходим к таблице переходов DFA, мы используем этот код

state = DFA_TransitionTable[state][weight];

И мне нужна альтернатива для этого.

Answer 1

Вот один из способов представить DFA со списком смежности в Java. Вместо того, чтобы иметь массив для функции перехода, вы представляете его как карту «символов» в «состояния», так что, учитывая состояние и символ, вы получаете следующее состояние с state.transitionFunction.get(symbol).

class DFA {
    Set<State> states;
    State initialState;
    Set<State> acceptStates;
}

class State {
    Map<Symbol, State> transitionFunction;
}

class Symbol {}

Предполагается, что вы хотите иметь собственный класс Symbol - вы, конечно, можете использовать Character или String для традиционного варианта использования, когда DFA применяется к строкам.