Распознавание окончаний в словах: построение и анализ автоматов

возникла проблема с тем, что программа не считывает верные окончания при применении НКА. Нужно было реализовать процедуру/метод работы детерминированного конечного автомата по входной цепочке символов алфавита НКА. (Решить задачу об окончаниях -ое, -ая, -ие). При вводе слово:красная (false), хотя должно быть (true). Не знаете в чем может быть проблема? Программный код:

class DeterministicFiniteAutomaton:
    def __init__(self, alphabet):
        # Инициализируем ДКА с заданным алфавитом
        self.alphabet = alphabet
        self.states = set()  # Множество состояний
        self.init_state = None  # Начальное состояние
        self.end_states = set()  # Множество конечных состояний
        self.transitions = {}  # Словарь для хранения переходов

    def add_state(self, state):
        # Добавляем состояние в множество состояний
        self.states.add(state)

    def set_init_state(self, state):
        # Устанавливаем начальное состояние
        self.init_state = state

    def add_end_state(self, state):
        # Добавляем состояние в множество конечных состояний
        self.end_states.add(state)

    def add_transition(self, from_state, to_state, symbol):
        # Добавляем переход в словарь переходов
        if (from_state, symbol) in self.transitions:
            return False
        self.transitions[(from_state, symbol)] = to_state
        return True

    def run(self, input_str):
        # Запускаем ДКА на входной строке
        current_state = self.init_state

        for char in input_str:
            # Проверяем, существует ли переход для текущего символа и состояния
            if (current_state, char) not in self.transitions:
                return False
            # Переходим в следующее состояние
            current_state = self.transitions[(current_state, char)]

        # Возвращаем True, если текущее состояние является конечным
        return current_state in self.end_states


# Создаем ДКА для задачи об окончаниях -ое, -ая, -ие
dfa = DeterministicFiniteAutomaton(['а', 'б', 'в', 'г', 'д', 'е', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'р', 'т', 'у', 'ы'])
dfa.add_state('q0')
dfa.add_state('q1')
dfa.add_state('q2')
dfa.add_state('q3')

dfa.set_init_state('q0')
dfa.add_end_state('q1')
dfa.add_end_state('q2')
dfa.add_end_state('q3')

# Добавляем переходы
dfa.add_transition('q0', 'q1', 'о')
dfa.add_transition('q1', 'q2', 'е')
dfa.add_transition('q2', 'q3', 'й')
dfa.add_transition('q0', 'q2', 'а')
dfa.add_transition('q2', 'q3', 'я')
dfa.add_transition('q0', 'q2', 'и')
dfa.add_transition('q2', 'q3', 'е')

# Пример использования
input_str = input("Введите строку: ")
result = dfa.run(input_str)
print(f'Строка "{input_str}" соответствует окончаниям -ое, -ая, -ие: {result}')