Здравствуйте, VjcheslavV, Вы писали:

Pzz>>Однако слово квантификация мне ничего не говорит. Может, введешь в курс дела?

VV>квантификация у регулярных выражений https://ru.wikipedia.org/wiki/%D0%A0%D0%B5%D0%B3%D1%83%D0%BB%D1%8F%D1%80%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%80%D0%B0%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F
VV>одним словом бывает так что можно пойти по одним и тем же символам по разному с разными состояниями

А, понятно. Обрати внимание, у тебя содержательно есть только один "интересный" символ, это бесконечный повтор. Остальные разворачиваются так (e — это epsilon, примитив регулярного выражения, всегда сопоставляющийся с пустой строкой):

X?     -> X | e
X+     -> X X*
X{n}   -> X X X ... X
X{m,n} -> X X X ... X   (X | e) (X | e) ... (X | e)

Т.е., все эти красивые штучки — это синтаксический сахар в общепринятой записи регулярных выражений. Содержательно, у тебя есть только три операции: конкатенация, альтернация и бесконечный повтор.

При преобразовании в детерминированный КА эти красивые штучки не порождают прохода по одним и тем же символам в разных состояниях, а порождают сложный автомат в виде развесистой клюквы, в котором повторяющиеся фрагменты регулярного выражения порождают повторяющиеся фрагменты в графе состояний.

Ну и учти еще, что POSIX regexp, из-за возможности ссылаться на уже насканированное, не является регулярным языком по Хомскому, и обычно реализуется в виде автомата с возвратами и стеком состояний.