Вот смотрите: 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) какой механизм быстрее отработал регулярное выражение?
6) в каком случае использовалось больше оперативной памяти?

Спасибо

1) Из состояния 1 есть переход в себя по букве "a". Конечно, это считается за ход - например, он применится на строке "aa". Недетерминированность же автомата проявляется не в этом, а в том, что из 0 есть переход в себя же по любой букве - этот переход "перекрывается" с другими переходами.

В смысле? Для куска шаблона "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(длины_строки). Мы просто начинаем со стартового состояния и "скармливаем" по одной букве, переходя из одного состояния в другое (в отличие от НКА, где мы должны были держать целое множество достижимых состояний).

Точные количества переходов на конкретном примере можно посчитать, но, думаю, КДА всё равно окажется намного быстрей.

maxdiver, спасибо за такой развернутый ответ! 

Хочу уточнить по тем же пунткам:

1) "Конечно, это считается за ход - например, он применится на строке "aa".
Вот если строка "ab", а шаблон "a+". На символе "a" будет первый ход, а на символе "+" будет замыкание на себя (ведь в строке нет еще одного "a"). Автомат при замыкании на себя тоже тратит время, т.е. "ход"? Если много раз замыкать на себя, то быстродейсвтие снизится или нет?

2) Я немного не разобрался  в рисунке. Там используется три разных шаблона 1) a+bc 2) bcd+ 3) cde 
или один шаблон "a+bcbcd+cde"? Если это один шаблон, то получается, что в состоянии 3 автомат не находит символ "b" и возращается в состояние 0? 

4) если честно, я был уверен, что ДКА в отличие от НКА не позволяет делать откаты назад 

Пожалуйста, хотя я знаю о регулярных выражениях только "по наслышке" 
Я получил некоторое представление по книге Смита "Методы и алгоритмы вычисления на строках", но на 100% я не уверен.

1) Для строки "ab" и шаблона "a+" автомат получится такой: из состояния 0 переход по "a" в состояние 1, а из состояния 1 переход в себя же по букве "a". Скармливая строку "ab", мы после обработки первого символа перейдём в состояние 1 и зафиксируем вхождение паттерна (множество достижимых вершин будет содержать 0 и 1), а при обработке второго символа - заметим, что из состояния 1 нет перехода по букве "b", поэтому ничего не произойдёт (множество достижимых вершин будет вновь содержать только стартовое состояние 0). В общем, эти переходы на себя - они в общем-то ничем не отличаются от остальных переходов.

2) Там три шаблона. Построен один автомат для трёх шаблонов сразу, чтобы искать все три шаблона в строке.

4) Строго говоря, никаких "откатов" и не существует вообще  Просто мне показалось логичным в случае детерминированного автомата говорить о них, т.к. в ДКА есть переходы, обеспечивающие переход от обнаружения одного шаблона к совсем другому (в примере - от обнаружения шаблона "a+bc" к обнаружению шаблона "bcd+" в строке "abcd"; мы сначала обнаружили подстроку "abc", а потом при переходе по букве "d" "забыли" про букву "a" и обнаружили подстроку "bcd"). Получается, ДКА содержит такие переходы, а НКА не содержит (за что и приходится расплачиваться: при скармливании строки ДКА мы должны хранить одно-единственное текущее состояние, а в НКА нам приходится хранить сразу кучу состояний, которые могут быть текущими).

"Там три шаблона. Построен один автомат для трёх шаблонов сразу, чтобы искать все три шаблона в строке."
большое спасибо, теперь становится понятно. Просто в регулярных выражениях Perl (там НКА) вот такой шаблон /a+bcbcd+cde/  НЕ найдет ни одного совпадения в строке abcd. И было непонятно, как же так два совпадения находятся?! А вот если эти шаблоны разделить на три регулярные выражения, то как раз два шаблона отыщутся.