Обещанная реализация КА и попытка создать таблицу переходов не детерминированному автомату⁠⁠

Предыдущая статья: Конечные автоматы, что там внутри? в vk.com

Как-то никто не голосует, поэтому решил выпустить раньше, язык реализации выбрал на своё усмотрение, посмотреть можно здесь. Пример основан на автомате из прошлой статьи.

Давайте попробуем создать таблицу переходов для этого автомата:

Как-то не особо получается верно? Нам не совсем-то понятно когда переходить в состояние K, мы как-будто застряли в неопределенности. Когда приняли символ a оставаться в состоянии B или переходить уже к другому? Данные типы автоматов называются не детерминированные конечные автоматы или просто НКА, они обладают особой приметой, то что на один и тот же принятый символ в одном состоянии есть более одного варианта перехода. И всё таки мы можем написать для него функцию перехода, добавив какие нибудь условия, например проверять не последний ли это символ. Что же получается я слукавил в прошлый раз? И да и нет, жертва для более наглядного, постепенного объяснения. Да - потому-что функцию перехода можно реализовать разными способами. Нет - потому-что это частный случай реализации детерминированных конечных автоматов или просто ДКА, когда каждый его переход однозначен. ДКА - гораздо эффективнее НКА и у меня хорошие новости:
Теорема Клини. Для каждого НКА можно построить ДКА, допускающий тот же язык.

В следующей статье мы рассмотрим алгоритм преобразования НКА в ДКА, не забывайте подписываться. Все здоровья и удачи.