[maxkar]

Успешно использует нка и имеет уважение.

Дайте, пожалуйста, ваше определение нка. И расскажите, как именно разбор регулярных выражений ими пользуется. Особенно с учетом того, что нка должны быть одинаковы для грамматик.

Чёрт возьми да. Да это про особенности. Они то нам и важны. Каждый день мы сталкиваемся именно с особенностями, самой конкретной, самой материальной реализации, а не со схемкой в википедии.

Да. Но почему вы считаете, что при разборе реуглярных выражений используются нка или дка?

Как вы это определили интересно знать?

Ну... backreferences не могут обрабатываться конечными автоматами. Никогда. Доказательство элементартное. Регэксп (.*)b\1. Будем кормить конечному автомату строки вида a....ab, где количество a варьируется. И будем смотреть, в каком состоянии находится автомат после прохождения этой строки. Так как количество состояний автомата конечно, на какие-то две строки мы получим одно и то же состояние (если состояний N, рассмотрим N+1 строку). Пусть это m и n букв a. Тогда рассмотрим строки "m штук a, b, m штук a" и "m штук a, b, n штук a". Так как после символа b автомат находится в одном и том же состоянии, дальнейший "разбор" будет одинаков и автомат придет в одно и то же конечное состояние. Но в одном случае результате неверный (одно из них подходит под regexp, второе - нет - ответы разные, а автомат дает один ответ).

Это было доказательство для дка. нка нужно предварительно перевести в дка. Вроде бы по сссылке (которую я давал в wiki) было написано, как это делается. В крайнем случае там должна была быть ссылка на литературу.

Вывод - если что-то успешно обрабатывает регулярные выражения и корректно работает с backreferences, оно не является конечным автоматом. Ну а использовать нка при разборе регулярного выражения смысла нет. Как минимум, некоторые вещи в автомате не представимы. А все остальное, что остается от нка, нормально представляется "позициями" в регулярном выражении + состоянием разбора. И, кстати, это как раз и может давать разницу в производительности для двух эквивалентных грамматик . А использование нка его давать не должно.

Шутку понял. Смешно.

Это не шутка. Это суровая правда жизни. При проектировании систем приходится учитывать области, в которых используемые библиотеки не дают требуемых гарантий. В этом случае наблюдаемое поведение может быть "случайным". И я сам на code review в некоторых случая настоятельно рекомендовал в документации писать, что "наблюдаемое поведение не является гарантируемым и может измениться в следующих версиях" (там это касалось отсортированности массива-результата).