Хорошо, когда знаешь несколько языков. Поиск по английскому гуглу не дал результатов.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм перевода недетерминированного автомата в |
| Автор: neutrino 9.8.2009, 10:47 |
| Приветствую! Ищу САБЖ. Проект встал из-за того, что парсер, который я пишу использует недетерминированный автомат. Поскольку мне надо парсить текстовые файлы > 1 гига, необходимо перевести автомат в детерминированный (очень важна скорость). |
| Автор: neutrino 9.8.2009, 11:31 |
| Однако: http://is.ifmo.ru/download/determ.pdf Хорошо, когда знаешь несколько языков. Поиск по английскому гуглу не дал результатов. |
| Автор: skyboy 9.8.2009, 12:55 |
| можно тезисно: хотя бы название у этого алгоритма есть? |
| Автор: neutrino 10.8.2009, 09:03 |
| Я понятия не имею. Сам ищу что-нибудь съедобное... |
| Автор: GoldFinch 10.8.2009, 13:50 |
| Брауэр В. Введение в теорию конечных автоматов. - М.: Радио и связь, 1987 вот в этой книжке есть глава "перевод НРС автоматов в РС" (НРС - недетерминированые РС) (сам эту главу не читал) |
| Автор: Dims 10.8.2009, 14:38 |
| Что-то я не понял задачу. Недетерминированный автомат, насколько я понимаю, это просто-напросто параллельный компьютер, то есть, автомат, который движется сразу несколькими путями. Поскольку все современные компьютеры последовательны, то недетерминированный автомат и невозможно исполнить без преобразования в детерминированный. При "детерминизации" быстродействие не увеличивается, а уменьшается, так как переходы, которые недетерминированный автомат способен выполнить параллельно, детерминированный автомат будет выполнять последовательно. При этом может даже возникнуть "комбинаторный взрыв", то есть, может оказаться практически невозможно выполнить программу автомата на последовательном компьютере. |
| Автор: neutrino 11.8.2009, 12:18 |
| Мдя... Недетерминированный автомат - это автомат с лямбда (епсилон) переходами и возможностью перехода из одного состояния в два разных по тем же самым терминальным символам. Вот и все. Да, по такому автомату надо идти паралельно. И да, по детерминированному автомату обход получается быстрее. Почему? Да потому что не надо идти по нескольким направлениям параллельно. Думаю так понятно. В теории может случиться так, что при детерминировании автомата получиться 2^н состояний. Но это теория. У меня автомат не такой страшный. |
| Автор: skyboy 11.8.2009, 15:04 | ||
мне кажется, что образно говоря, "детерминированный" - это "поиск в глубину", а "недетерминированный" - это "поиск в ширину". и в общем случае, мне кажется, "поиск в ширину" быстрее даст результат, чем N поисков в глубину. я не прав? а недостаток недетерминированного аппарата - не в скорости, как таковой, а в необходимости сохранять промежуточные состояния, где происходит выбор одного из нескольких вариантов обработки. или я что-то путаю? |
| Автор: gcc 11.8.2009, 16:14 |
| системная функция seek? а что нужно сделать поиск? или сам файл откоректировать? во многих языках программирование применяется детерминированный поиск, даже в awk (foo|foobar) |
| Автор: skyboy 13.8.2009, 00:29 |
gcc, эй-эй, ты чего?  про поиск это я спросил для внесения ясности в понимание предмета. у neutrino там парсер упоминается. |
| Автор: Franka 18.9.2009, 21:59 | ||
Вы, по сути, ничего не путаете, но проблема в следующем: недетеринированный автомат может содержать очень большое количество переходов типа <q, aw_1, q_1>, <q,aw_2, q_2>. В итоге с момента каждого такого перехода прохождение автомата "расслаивается" на несколько вариантов. Вот тут память и полетит, потому что необходима уже действительно параллельная обработка. Объективно получается, что детерменированный автомат в худшем случае будет содержать действительно 2^n - 1 состояние. Базовый алгоритм жутко тормозной по этой причине. Просто в тот момент, когда выбираем подмножества, нужны определенные правила того, как их отсеивать. Я сейчас говорю скорее как математик. Более программистский подход представлю завтра, если это интересно и актуально. Только тогда хотелось бы знать, в какой степени алгоритм расписывать. |
| Автор: neutrino 28.9.2009, 11:04 | ||
Franka,
В понятной А лучше сразу на каком-нибудь языке программирования. |
| Автор: AndryG 30.9.2009, 20:33 |
| А можно поинтересоваться, с чем вообще автомат работает? И насколько он у Вас недетерминированный? Может просто его тут переведут в КА да и алгоритм не понадобится А алгоритм приведения НКА в КА хорошо описан в "красном драконе". Не помню алгоритма, но помню что там описан хорошо |
| Автор: neutrino 1.10.2009, 15:44 | ||
автомат - несколько сот состояний.
Не пошлете? |
| Автор: AndryG 1.10.2009, 16:20 |
http://www.infanata.org/computers/prog/1146096903-kompiljatory.-principy-tekhnologii.html Добавлено через 1 минуту и 21 секунду Что же Вы такое разбираете ?! Может стоит разбить на несколько более простых автоматов? Задача проще смотрится по частям. |
