@@aaafin да, до этого никак не мог вкурить как из словаря конструкции языка составляются, хотя и писал лексер из начала книги и он работал, но дальше без понимания конечных автоматов никак не шло.
Насчёт наивного алгоритма. Есть последовательность abababbab и слово ababb (длина слова 5). Почему нельзя читаль исходную последовательность по 5 символов и сравнивать прочитанное со словом? Если совпало - запоминаем номер символа, с которого начиналась текущая пятерка. Откуда в наивном алгоритме возвраты и чем плох предложенный вариант? Время его работы это примерно произведение длины строки на длину слова, у автомата сильно меньше?
Благодаря вашим видео я наконец-то понял книгу дракона. Респект и уважуха.
Да ладно! Так таки уж и поняли :)))
@@aaafin да, до этого никак не мог вкурить как из словаря конструкции языка составляются, хотя и писал лексер из начала книги и он работал, но дальше без понимания конечных автоматов никак не шло.
Насчёт наивного алгоритма. Есть последовательность abababbab и слово ababb (длина слова 5). Почему нельзя читаль исходную последовательность по 5 символов и сравнивать прочитанное со словом? Если совпало - запоминаем номер символа, с которого начиналась текущая пятерка. Откуда в наивном алгоритме возвраты и чем плох предложенный вариант? Время его работы это примерно произведение длины строки на длину слова, у автомата сильно меньше?
Так придется читать по пять символов начиная с каждого символа же. Кол-во операций - длина исходной последовательности умножить на 5.
@@aaafin это я понимаю, я так и написал mN, имея в виду, что m=5. А какая асимптотика у поиска при помощи конечного автомата?
@@Vadim_Ozheredov В автоматах скорость линейная. Это всё подробно написано в книжке "Строки, деревья и последовательности в алгоритмах"
Это камера так показывает или у Вас лицо реально такое же белое, как кусочек мела в Ваших руках? )
Освещение такое