Math
Скінченні автомати
Перетворіть регулярні вирази на автомати та прочитайте вхідну послідовність.
Що спробувати
Редагуйте регулярний вираз над a та b, використовуючи |, *, дужки й конкатенацію. NFA Томпсона перетворюється на досяжні підмножини DFA. Читайте слово по одній літері; подвійні кола приймають. Ліміт: 16 станів DFA.
Рівняння модуля
Рівняння
Побудова Томпсона: символ, конкатенація, об'єднання, зірка Кліні
початок DFA = ε-closure(NFA-початок)
δ(S,c) = ε-closure({q : p ∈ S і p —c→ q})
Підмножина приймає тоді й лише тоді, коли містить приймальний стан NFA
