Приветствую!

Ищу САБЖ. Проект встал из-за того, что парсер, который я пишу использует недетерминированный автомат. Поскольку мне надо парсить текстовые файлы > 1 гига, необходимо перевести автомат в детерминированный (очень важна скорость).

Однако: http://is.ifmo.ru/download/determ.pdf

Хорошо, когда знаешь несколько языков. Поиск по английскому гуглу не дал результатов.  

можно тезисно: хотя бы название у этого алгоритма есть?

Я понятия не имею. Сам ищу что-нибудь съедобное...

Брауэр В. Введение в теорию конечных автоматов. - М.: Радио и связь, 1987

вот в этой книжке есть глава "перевод НРС автоматов в РС" 
(НРС - недетерминированые РС)

(сам эту главу не читал)

Что-то я не понял задачу. 

Недетерминированный автомат, насколько я понимаю, это просто-напросто параллельный компьютер, то есть, автомат, который движется сразу несколькими путями. Поскольку все современные компьютеры последовательны, то недетерминированный автомат и невозможно исполнить без преобразования в детерминированный.

При "детерминизации" быстродействие не увеличивается, а уменьшается, так как переходы, которые недетерминированный автомат способен выполнить параллельно, детерминированный автомат будет выполнять последовательно. При этом может даже возникнуть "комбинаторный взрыв", то есть, может оказаться практически невозможно выполнить программу автомата на последовательном компьютере.

Мдя...

Недетерминированный автомат - это автомат с лямбда (епсилон) переходами и возможностью перехода из одного состояния в два разных по тем же самым терминальным символам. Вот и все. Да, по такому автомату надо идти паралельно. И да, по детерминированному автомату обход получается быстрее. Почему? Да потому что не надо идти по нескольким направлениям параллельно. Думаю так понятно.

В теории может случиться так, что при детерминировании автомата получиться 2^н состояний. Но это теория. У меня автомат не такой страшный.

мне кажется, что образно говоря, "детерминированный" - это "поиск в глубину", а "недетерминированный" - это "поиск в ширину". и в общем случае, мне кажется, "поиск в ширину" быстрее даст результат, чем N поисков в глубину. я не прав?
а недостаток недетерминированного аппарата - не в скорости, как таковой, а в необходимости сохранять промежуточные состояния, где происходит выбор одного из нескольких вариантов обработки. или я что-то путаю?

системная функция seek? 

а что нужно сделать поиск? или сам файл откоректировать?

во многих языках программирование применяется детерминированный поиск, даже в awk (foo|foobar)

Это сообщение отредактировал(а) gcc - 11.8.2009, 16:46

gcc, эй-эй, ты чего?  про поиск это я спросил для внесения ясности в понимание предмета. у neutrino там парсер упоминается.

Вы, по сути, ничего не путаете, но проблема в следующем: недетеринированный автомат может содержать очень большое количество переходов типа <q, aw_1, q_1>, <q,aw_2, q_2>. В итоге с момента каждого такого перехода прохождение автомата "расслаивается" на несколько вариантов. Вот тут память и полетит, потому что необходима уже действительно параллельная обработка.
Объективно получается, что детерменированный автомат в худшем случае будет содержать действительно 2^n - 1 состояние. Базовый алгоритм жутко тормозной по этой причине. Просто в тот момент, когда выбираем подмножества, нужны определенные правила того, как их отсеивать.
Я сейчас говорю скорее как математик. Более программистский подход представлю завтра, если это интересно и актуально. Только тогда хотелось бы знать, в какой степени алгоритм расписывать.

Franka, 

В понятной 
 А лучше сразу на каком-нибудь языке программирования.

А можно поинтересоваться, с чем вообще автомат работает? 
И насколько он у Вас недетерминированный?

Может просто его тут переведут в КА да и алгоритм не понадобится

А алгоритм приведения НКА в КА хорошо описан в "красном драконе". Не помню алгоритма, но помню что там описан хорошо 

автомат - несколько сот состояний.



Не пошлете?

http://www.infanata.org/computers/prog/114...ekhnologii.html


Добавлено через 1 минуту и 21 секунду
Что же Вы такое разбираете ?! Может стоит разбить на несколько более простых автоматов? Задача проще смотрится по частям.