| Цитата |
| Если это считается за ход, то тогда символ "b" должен быть на третьем ходу а не на втором. |
В смысле? Для куска шаблона "a+b" мы строим такие переходы: один по букве "a", потом сколько угодно переходов по "a" в себя же, потому что они ничего не меняют, но потом выйти из текущего состояния мы можем только по букве "b".
2) Хоть убей, не вижу ни одного перехода из состояния 3
Он соответствует окончанию шаблона "a+bc", какие из него могут переходы? Если в строке встречаются другие шаблончики, то они по другим ветвям автомата обнаружатся.3) Если мы пришли в состояние 3, то мы обнаружили шаблон "a+bc". Если после этого идёт буква "d", то получится, что строка содержит "abcd", т.е. мы обнаружим шаблон "bcd+", в состоянии 4.
4) Например, над состоянием 1 эти значки обозначают, что из состояний с 1 по 10 есть переходы в 1 по букве "a". Вот это как раз "откаты", например, если строка S="abcabc", то после обработки "abc" мы будем в состоянии 3, потом по букве "a" откатимся к состоянию 1, а после обработки "bc" придём в состояние 3 и зафиксируем второе вхождение шаблона.
5) 6) НКА требует порядка стольки операций: число_состояний * длина_строки. Изначально в множестве достижимых состояний содержится только состояния 0, после буквы "a" это будет {0,1}, и т.д. Так как вообще говоря, на каждом шаге достижимыми состояния могут быть вообще все, то для каждой буквы строки будет выполняться (число_состояний) операций. Т.е. с точки зрения числа операций, НКА может работать медленнее. Но зато число состояний и переходов в НКА гарантированно есть порядка длин шаблонов.
ДКА, напротив, может содержать много состояний и переходов (например, на рисунке видно очень много переходов по "двойным стрелочкам"). Хотя, насколько я знаю, есть сложные алгоритмы, которые позволяют "удержать" число состояний и переходов в линейных границах. Зато обработку строк ДКА делает очень эффективно - ровно за O(длины_строки). Мы просто начинаем со стартового состояния и "скармливаем" по одной букве, переходя из одного состояния в другое (в отличие от НКА, где мы должны были держать целое множество достижимых состояний).
Точные количества переходов на конкретном примере можно посчитать, но, думаю, КДА всё равно окажется намного быстрей.