Вы все еще не ответили на вопрос о том, что понимаете под дка и нка...
Цитата:
Сообщение от ProxyGreen
Тесты вам ни чего не показывают.
|
Показывают. Показывают замечательное различие между двумя эквивалентными грамматиками, записанными по-разному. Что на автоматах не должно быть. А на переборах с возвратом исходной грамматики - запросто (там действительно для выбора и для [] могут использоваться различные механизмы).
Цитата:
|
Ни нка ни дка ни где не используются, их судя по всему вообще не существует.
|
Используются. В тех задачах, для которых подходят. А в тех, которых не походят, не используются.
Цитата:
|
Что используется тогда? Как называется механизм, который используется в регулярных выражениях?
|
Вообще, он может никак не называться. Иногда там совершенно банальный перебор с возвратом с присущими ему тормозами на совершенно ровном месте. В некоторых случаях - с оптимизацями под какие-то особые сценарии (гибридные механизмы). Чисто теоретически, на некоторых видах выражений (для хороших выражений) он может строить дка и ходить по нему. А может не строить. Кстати, этот самый "перебор с возвратом" гораздо лучше описывает идею разбора регулярных выражений. Он же описывает и разницу в записях [abc] и (a|b|c) (в одном случае отктаты есть, в другом - нет). Откуда там хоть какие-то автоматы - хз.
Да вроде не врет. Только вот он не говорит, что НКА используется в автоматах. Там фраза "при использовании логики НКА" и далее - описание перебора с возвратом. А на том же НКА можно гонять "поиск в ширину", например. Про это автор почему-то не говорит. Но в целом если термин "использование логики НКА" в статье введен в определенном смысле - дальше в статье/работе его можно использовать. Общеупотребительным он от этого все равно не станет и без конкретизации особого значения иметь не будет. Так что терминология очень спорная.
Обратите внимание, в 5-м абзаце пункта 6.1 автор пишет, что нка и дка преобразуются друг в друга. Я это вам уже говорил. Так что точнее механику называть "перебором с возвратом", а не нка.