ДКА. Принадлежность последовательности автомату

У Вас в автомате ошибка, как минимум одна, но скорее всего 4 (либо Вы используете специфическую нотацию для ДКА). Т.е. у Вас не ДКА. В частности, он НЕ детерминированный. Цитата:

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором нет дуг с меткой ε (предложение, не содержащее ни одного символа), и из любого состояния по любому символу возможен переход не более, чем в одно состояние.

В вершине 3 у вас есть 2 ребра с одинаковыми символами для перехода. Далее, я буду считать, что петля для символа 3 имеет символ d, а не b.

Также у Вас не выбраны единственные: начальная и конечная вершины. Я выберу их сам: 0 и 5 соответсвенно.

Для вершины 4, если считать её не конечной нет перехода.. Но мы на это забъём.

В начальную вершину не может быть ребёр. Не обращаем внимания.

Всё очень несложно. Задача формулируется так. Дан граф G = G(V, E), где V -- множество вершин с двумя выделенными вершинами: начальная и конечная (минимальный id, максимальный id). E -- множество пар (vi, vj), где vi, vj -- вершины. Требуется построить алгоритм, который по упорядоченному списку вершин даст ответ: существует ли такой путь в графе или нет.

Пример. Пусть есть тот граф, который Вы предложили. Начальное состояние: 0, конечное состояние: 1. Зададим путь: [a,a,a,a,a,a,b,d,b]. Тогда: 0-1-2-0-1-2-0-3-3-5

Другой пример: [a,a,a,a,a,a,b,c,c]. Здесь получается, что мы оказываемся не в финальной вершине.

Модификация алгоритма обхода в глубину решает Вашу задачу. Граф будем хранить как матрицу смежности, представленную словарём вершин и их соседей.

def iterate_over_neighbours(elem, ngbs):
    next_vertex = None
    for label, vertex in ngbs.items():
        if elem != label:
            continue
        next_vertex = vertex
        break
    if next_vertex is None:
        return -1
    return next_vertex


def dfs(g, seq, s, f):
    cv = s  # current vertex
    step = 0
    for step in range(len(seq)):
        if cv == f:
            break
        next_vertex = iterate_over_neighbours(seq[step], g[cv])
        if next_vertex == -1:
            return False
        cv = next_vertex
    if cv == f and len(seq)-1 == step:
        return True
    return False


g = {
   0: {'a': 1, 'b': 3},
   1: {'a': 2},
   2: {'a': 0},
   3: {'d': 3, 'c': 4, 'b': 5},
   4: {},
   5: {},
}
final = 5
start = 0
seq = ['a','a','a','a','a','a','b','d','b']
print(dfs(g, seq, start, final))

Вариант решения задачи распознавания цепочки для автомата, представленного таблично:

# -*- coding: utf-8 -*-
from __future__ import unicode_literals

"""
* Входные данные для проверки
"""

# Автомат в табличном виде
f = """
   a  b  c
0  1  3  E  0
1  2  E  E  0
2  0  E  E  0
3  E  5  4  0
4  E  E  E  1
5  E  E  E  1
E  E  E  E  0
"""

# Проверяемая цепочка
chain = 'aaabc'
# chain = input() # раскомментировать, если цепочку нужно вводить с клавиатуры


"""
* Работа алгоритма
"""

f = [line for line in f.split('\n') if line.strip()]

alphabet = [
    letter.strip()
    for letter in f[0].split()
    if letter.strip()
]

if len(alphabet) != len(set(alphabet)):
    raise Exception("В алфавите недопустимы повторяющиеся символы")

alphabet = {
    alphabet[i] : i
    for i in range(len(alphabet))
}

constructor = {
    f[i].split()[0] : (f[i].split()[1:-1], f[i].split()[-1])
    for i in range(1, len(f))
}

status = list(constructor.keys())[0]
for c in chain:
    status = constructor[status][0][alphabet[c]]
    print(f'Символ: {c}; Статус: {status}')
print(f'Результат: цепочка {"принимается" if int(constructor[status][1]) else "отвергается"}')

Как уже было сказано в другом ответе, представленный вами граф не является корректным автоматом, потому в примере приведены следующие изменения:

• Убрана цепочка 3 -b-> 3
• Состояния 4 и 5 выделены как принимающие
• Добавлено E-состояние для переходов, которых нет на графе
• Состояние 0 выделено как начальное (по умолчанию начальным состоянием считается первая строка табличного автомата)