Kiedy czytasz takie posty jakRegex: NFA i algorytm Thompsona wszystko wygląda dość prosto, dopóki nie uświadomisz sobie w życiu, że potrzebujesz nie tylko bezpośrednich znaków, takich jak „7” czy „b”, ale także:

[A-Z]
[^_]
.

mianowicie klasy postaci (lub zakresy). A zatem moje pytanie - jak zbudować NFA przy użyciu zakresów znaków? Używając meta-znaków takich jak „nie A”, „cokolwiek innego”, a następnie obliczając nakładające się zakresy? Doprowadziłoby to do użycia struktury podobnej do drzewa podczas używania automatu końcowego, a nie tylko tabeli.

Aktualizacja: proszę założyć nietrywialny alfabet wielkości (>> 256).

Pytam o NFA, ale później chciałbym również przekonwertować NFA na DFA.