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