Вот смотрите: 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:21

6) для какого механизма нужно больше оперативной памяти?

Полагаю, вам лучше задать этот вопрос в разделе "Алгоритмы"

Ясно, спасибо. Там тоже не отвечают :(