Когда вы читаете такие сообщения, какRegex: NFA и алгоритм Томпсона все выглядит довольно просто, пока вы не поймете, что в реальной жизни вам нужны не только прямые символы, такие как «7» или «b», но также:

[A-Z]
[^_]
.

а именно классы символов (или диапазоны). И, таким образом, мой вопрос - как построить NFA, используя диапазоны символов? Использование метасимволов типа «не А», «что-нибудь еще», а затем вычисление перекрывающихся диапазонов? Это привело бы к использованию древовидной структуры при использовании конечного автомата, а не только таблицы.

Обновить: Пожалуйста, примите алфавит нетривиального размера (>> 256).

Я спрашиваю о NFA, но позже я хотел бы также преобразовать NFA в DFA.