видел в драконьей книге как недетерминированный КА превращают в детерминированный
а что делать если есть квантификация?
если недетерминированный интерпретировать то всё понятно — или самое короткое или самое длинное вхождение
а как быть с этим преобразованием? или он с квантификацией не дружит?
Здравствуйте, VjcheslavV, Вы писали:
VV>видел в драконьей книге как недетерминированный КА превращают в детерминированный 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, из-за возможности ссылаться на уже насканированное, не является регулярным языком по Хомскому, и обычно реализуется в виде автомата с возвратами и стеком состояний.
VV>видел в драконьей книге как недетерминированный КА превращают в детерминированный VV>а что делать если есть квантификация? VV>если недетерминированный интерпретировать то всё понятно — или самое короткое или самое длинное вхождение VV>а как быть с этим преобразованием? или он с квантификацией не дружит?
Любая конечная или бесконечная итерация выражается через либо конечное объединение, либо через звезду Клини.
Их можно преобразовать в ε-НКА (3.2.3. Преобразование регулярного выражения в автомат в «Введение в теорию автоматов, языков и вычислений»)
Любой ε-НКА же, как утверждается в той же книге (2.5.5. Устранение ε-переходов), преобразуется в ДКА.
Здравствуйте, σ, Вы писали:
σ>Любая конечная или бесконечная итерация выражается через либо конечное объединение, либо через звезду Клини. σ>Их можно преобразовать в ε-НКА (3.2.3. Преобразование регулярного выражения в автомат в «Введение в теорию автоматов, языков и вычислений») σ>Любой ε-НКА же, как утверждается в той же книге (2.5.5. Устранение ε-переходов), преобразуется в ДКА.
глянул как-то не на наглядном примере объяснено ...
там повторяются только цифры а после них идёт точка или конец (то есть квантификация не где, ни на что не повлияет)
как я понял чтобы построить детерминированный автомат всегда строят эквивалентный не детерминированный?
вот был бы пример с квантификацией ...
Здравствуйте, Pzz, Вы писали:
Pzz>Причем, что характерно, если не полениться сделать минимализацию, то всегда одним и тем же образом, с точностью то поворотов в графе.
Здравствуйте, VjcheslavV, Вы писали:
Pzz>>Причем, что характерно, если не полениться сделать минимализацию, то всегда одним и тем же образом, с точностью то поворотов в графе.
VV>а причём тут оптимизация?
Не оптимизация, а минимализация машины состояний. Один и тот же регулярный язык может быть представлен разными конечными автоматами. Но при этом минимальный автомат однозначно определяется языком.
Здравствуйте, VjcheslavV, Вы писали:
VV>весь интернет прогуглил но про квантификацию ничего не нашёл... VV>как её всё таки делают в регулярных выражениях? ума не приложу...
В чём проблема-то? Что именно тебе не понятно? Pzz вроде всё доступно изложил.
Здравствуйте, Pzz, Вы писали:
Pzz>Ну и учти еще, что POSIX regexp, из-за возможности ссылаться на уже насканированное, не является регулярным языком по Хомскому, и обычно реализуется в виде автомата с возвратами и стеком состояний.
Насколько я помню, с регвырами несложно построить выражение, которое при реализации через КА построит КА то ли экспоненциального то ли около того размера. В общем большой КА получится. Получается, что НКА в худшем случае долго работает, а КА в худшем случае требует очень много памяти. Ну и НКА более богатый и на практике с вырожденными случаями сталкиваться приходится редко. Поэтому НКА и используют для реализации, хотя есть и реализации на КА, если действительно важна O(N) производительность.
VV>весь интернет прогуглил но про квантификацию ничего не нашёл... VV>как её всё таки делают в регулярных выражениях? ума не приложу... https://swtch.com/~rsc/regexp/
vsb>В чём проблема-то? Что именно тебе не понятно? Pzz вроде всё доступно изложил.
действительно я ничего не понял ...
я понял что якобы это не по теме — там вроде не было как задаются жадная или ленивая квантификация...
Pzz>X? -> X | e
Pzz>X+ -> X X*
Pzz>X{n} -> X X X ... X
Pzz>X{m,n} -> X X X ... X (X | e) (X | e) ... (X | e)
Pzz>
Pzz>Т.е., все эти красивые штучки — это синтаксический сахар в общепринятой записи регулярных выражений. Содержательно, у тебя есть только три операции: конкатенация, альтернация и бесконечный повтор.
Здравствуйте, VjcheslavV, Вы писали:
vsb>>В чём проблема-то? Что именно тебе не понятно? Pzz вроде всё доступно изложил. VV>действительно я ничего не понял ... VV>я понял что якобы это не по теме — там вроде не было как задаются жадная или ленивая квантификация...
Ну сразу бы и написал, что тебе нужна эта жадность или ленивость. В классических алгоритмах такого понятия нет. Там или есть совпадение, или нет. Для этого нужны более продвинутые алгоритмы, можешь попробовать почитать труд "NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions".
Здравствуйте, vsb, Вы писали:
vsb>Ну сразу бы и написал, что тебе нужна эта жадность или ленивость. В классических алгоритмах такого понятия нет. Там или есть совпадение, или нет. Для этого нужны более продвинутые алгоритмы, можешь попробовать почитать труд "NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions".
продвинутые алгоритмы???
я офигиваю ... а на русском чтонибудь есть?
а эти алгоритмы с детерминированным KA или только с недетерминированным?
Здравствуйте, VjcheslavV, Вы писали:
vsb>>Ну сразу бы и написал, что тебе нужна эта жадность или ленивость. В классических алгоритмах такого понятия нет. Там или есть совпадение, или нет. Для этого нужны более продвинутые алгоритмы, можешь попробовать почитать труд "NFAs with Tagged Transitions, their Conversion to Deterministic Automata and Application to Regular Expressions".
VV>продвинутые алгоритмы??? VV>я офигиваю ... а на русском чтонибудь есть?
Сомневаюсь, на русском вообще мало что есть кроме совсем уж классических трудов, а уж малоизвестные исследования — тем более, кому надо их переводить.
VV>а эти алгоритмы с детерминированным KA или только с недетерминированным?
Deterministic Automata это и есть детерминированный автомат. Так что да — с детерминированным.
