| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Perl: Общие вопросы > Кто разбирается в механизмах НКА и ДКА |
| Автор: Suppir 5.5.2009, 12:39 |
| Вот смотрите: http://img19.imageshack.us/img19/7200/nfadfa.gif Мне интересно как это работает. . строка = "abcd", регулярное выражение: (1) a+bc (2) bcd+ (3) cde . Первая схема отображает Perl НКА. Вторая схема отображает ДКА. . Вопросы: 1) на первой схеме (NFA), в состоянии 1, при действия квантификатора стрелка замыкается сама на себя - считается ли это за "ход" НКА? Если это считается за ход, то тогда символ "b" должен быть на третьем ходу а не на втором. 2) в состоянии 3, на букве "с" НКА переходит обратно в состояние 0 - т.е. происходит возврат (backtrack)? . 3) на второй схеме (DFA), возврат невозможен. Каким образом после совпадения в состоянии 3 (символ "с") происходит совпадение сразу в состоянии 6 с символом "d"? 4) что обозначают две вертикальные стрелки над состоянием 1 и 8 ? 5) какой механизм быстрее отработал регулярное выражение? Спасибо |
| Автор: Suppir 5.5.2009, 13:37 |
| 6) для какого механизма нужно больше оперативной памяти? |
| Автор: KSURi 5.5.2009, 14:16 |
| Полагаю, вам лучше задать этот вопрос в разделе "Алгоритмы" |
| Автор: Suppir 6.5.2009, 14:46 |
| Ясно, спасибо. Там тоже не отвечают :( |