Недетерминированные конечные автоматы

Просто конечные автоматы.
Добавляем недетерминированность.
Подход №1.
Подход №2.
Подход №3.
… и эпсилон-переходы.
… и более формально.
И почему это круто.
Реализация методом «в лоб».
Производительность.
ε-переходы.
Реализация преобразованием в ДКА.
Теория.
Алгоритм.
Код.
Производительность.
Заключение.Недетерминированные конечные автоматы – одна из моделей, используемых в теории вычислений. Вряд ли всё это когда-нибудь пригодится вам «по жизни»… но, чёрт возьми, математика – это интересно! Во всяком случае, для меня. А если уж она хоть как-то с программированием связана, то интересна вдвойне.
Я не претендую на математическую строгость, получилось что-то типа «популярной математики для чайников»… Но надо же с чего-то начинать. А причём здесь орки – поймёте по ходу дела :).