Добрый день!

1. Можно ли поиск с помощью регулярных выражений отнести к "прямому поиску"? Под прямым поиском понимают поиск без предварительного индексирования. Однако в Perl строка, насколько мне известно, подвергается хешированию перед обработкой регулярным выражением. 
2. Фридл пишет, что регулярные выражения Perl основаны на действии недетерминированного конечного автомата. При этом считается, что детерминированный конечный автомат работает быстрее, но недетерминированный дает больше возможностей для поиска. Можно ли средствами Perl конвертировать код регулярного выражения в код, совместимый с детерминированными конечными автоматими? (может модуль такой есть)
3. Где можно увидеть схему работы Perl НКА? Т.е. как механизм действует при обработке регулярного выражения. У Фридла всего две страницы про механизм действия. Про исходный код знаю, но, к сожалению, не силен в сях :(
4. Я прочитал на одном английском сайте, что регулярные выражения Perl и подобные намного слабее регулярных выражений в языке SNOBOL. Там использовалась система на контестно-независимой BNF-грамматике. Подобная система была в Алголе. Только я не нашел, в чем именно сноболовские регулярные выражения были сильнее перловских. 

1. откуда известно?
2. ...
3. perldoc re
4. не уверен

1. У перла есть внутренний тип SvPVBM в котором хранятся данные необходимые для поиска в строке (алгоритм Бойера-Мура).
Используется ф-ями типа index, а также движком регулярных выражений.
Внутри структуры типа SvPVBM есть данные о самом редком символе в строке, индекс первого вхождения искомой подстроки и др.

3. В книге фридла есть все, чтобы понимать как работу механизма, для того чтобы составлять регулярные выражения. Наглядно можно посмотреть в проге RegexBuddy. Еще помогает в отладке встроенный код, особенно (?{print "$`\[$&]$'\n"})
4. Тоже стало интересно. Насколько я понимаю это те самые грамматики которые появились в Perl 6, и вроде там специализация синтаксический разбор различных исходных текстов. Т.е. для написания своих языков, или вообще скриптов исполняющих/валидирующих тексты на языках.
Если есть инфа, особенно на русском и разжеванная, прошу сюда .

KSURi, насколько мне известно, Perl использует упрощенный алгоритм Бойера-Мура-Пратта. Он отличается от алгоритма Бойера-Мура тем, что не строит таблицу суффиксов (строит только таблицу стоп-символов). Этот алгоритм используется в предварительных оптимизациях регулярных выражений для поиска одиночных символов в строке. 
Например, есть регулярка /(abcabcabcabcabcabc)d/, алгоритм сначала ищет в строке символ "d" с помощью алгоритма БМП и только потом обрабатывает остальную часть регулярного выражения. Соответственно, если "d" не найден, то нет смысла обрабатывать остальную длинную строку - экономия времени.
-------
arto - "откуда известно?". Насколько мне известно, есть не так уже много видов поиска: с предварительной индексацией(инвертированные индексы), основанный на деревьях, основанных на сигнатурах, прямой поиск. В прямой поиск входят упомянутые алгоритмы Боейра-Мура, а также Карпа-Рабина, Ахо-Корасик и т.д. Туда же часто относят поиск с помощью детерминированных и недетерминированных автоматов (собственно, Ахо как раз и строится на автомате). 
По идее, регулярные выражения Perl работают на недетерминированных автоматах + большое количество разнообразных предварительных оптимизаций. Но при этом используется и индексирование строки (ведь создаются же переменные $_, $' и т.п.).  Выходит, что поиск с помощью рег.выр. какой-то смешанный. И я думаю, можно ли его отнести к прямому поиску?
------
Logo, насчет Снобола - в википедии прочитал. Цитирую:
In recent years its use has faded as newer languages such as Awk and Perl have made string manipulation by means of regular expressions fashionable. SNOBOL4 patterns, however, subsume BNF grammars, which are equivalent to Context-free grammars and more powerful than regular expressions [1] (Gimpel, J. F. 1973. A theory of discrete patterns and their implementation in SNOBOL4. Commun. ACM 16, 2 (Feb. 1973), 91-100.). Мне самому интересно, чем же они отличались от перловских. Насколько мне известно, SNOBOL представлял язык для обработки текста, разработки компиляторов и систем ИИ.

Хм, я не встречал упоминаний по поводу упрощенности алгоритма. Хотя, судя по его описанию, возможно вы правы.
В SvPVBM также есть поле BmUSEFUL, в котором хранится вес полезности данной подстроки при оптимизации. Весьма похоже на то, что вы описали с регуляркой /(abcabcabcabcabcabc)d/, если я все правильно понял.

ЗЫ: возможно стоит попробовать написать в рассылку для разработчиков (http://dev.perl.org/perl5/lists.html)

SvPVBM -- функция, которая нигде не используется.

SvPVBM - тип данных. Структуры такого типа создаются ф-ией fbm_compile(). По крайней мере так говорят в PerlGuts Illustrated v0.9

смотреть надо исходники

perl-5.10.0# grep -Fr SvPVBM .
./ext/B/B.xs:SvPVBM(sv)
perl-5.10.0#