Регулярные языки и конечные автоматы

← →
Ozone © (2004-10-22 05:45) [0]

Есть "стандартная" задача - определение, принадлежит ли некоторая цепочка определенному регулярному языку заданному недетерминированным конечным автоматом.

Для меня сначала показалась эта задача достаточно тривиальной. Думаю, запущу рекурсию и все само получиться. НО, я во-время остановился, т.к. при относительно большой длине зананной цепочкки и не малом кол-ве состояний не хватит никакого стека для реализации данного алгоритма.

Потом думал, что каждую ветку можно пустить в отдельном потоке, НО опять таки - память! + не тривиальная задача их синхронизации.

Вот сижу и думаю, какой алгоритм применить...

Знаю, что есть где-то хорошая книжка, подробно поясняющая как это делать, НО у меня ее нет и денег пока тоже не густо. Может у кого есть какие идеи? Поделитесь, пжлст.

← →
Ozone © (2004-10-22 10:42) [1]

← →
AlexG © (2004-10-22 10:55) [2]

Ты о конечных автоматах и машине Тьюринга что-нибудь знаешь? Используй эту базу...

← →
Holy © (2004-10-22 10:59) [3]

Напиши свой стек. Если такое рассказывали, то думаю про реализацию динам.структур на статических и т.д. должны были упоминать.
Имею ввиду, что любая рекурсия заменяется итерациями, а подобие стека может быть реализовано на файле или боьшом массиве.

Как-то пришлось писать на Бейсике, не понимавшем процедур и соответственно рекурсий, отображение фрактала "Снежинка Коха". Уже был готовый рекурсивный алгоритм на Паскале. Перевели на Басик, поменяв рекурсию на итерации не меняя идеи алгоритма (прямой ход - вычисления, а обратный, в смысле выход, - отображение). В роли стека выступал файл на винте.

← →
Ozone © (2004-10-22 11:30) [4]

AlexG © (22.10.04 10:55) [2]

Конечно знаю. НО не знаю как применить.

← →
Ozone © (2004-10-22 11:36) [5]

Holy © (22.10.04 10:59) [3]

А про свой стек - это интересно!

Есть еще предложения?

← →
AlexG © (2004-10-22 11:42) [6]

// НО не знаю как применить
Да тяжело :) Что именно тебе не понятно?

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

← →
AlexG © (2004-10-22 11:43) [7]

Эта задача решается без собственных стеков

← →
Ozone © (2004-10-22 11:45) [8]

AlexG © (22.10.04 11:42) [6]

Хм... вы меня не поняли. Все это я проделывал с ДКА, а вот про НКА я написал как раз, что первое что пришло в голову - это рекурсия, НО в "стандартном" виде она будет очень кушать стек...

ЗЫ: рррррр.... 2 дня не спал.

← →
Ozone © (2004-10-22 11:47) [9]

AlexG © (22.10.04 11:43) [7]

Это ты говоришь про ДЕТЕРМИНИРОВАННОЙ КОНЕЧНЫЙ АВТОМАТ.

← →
Анонимщик © (2004-10-22 11:47) [10]

Ты бы все-таки купил бы книгу, о которой тебе говорили.
А что касается самой задачи, то можно, например, для твоего недетерминированного конечного автомата построить эквивалентный детерминированный. В той книге все и написано (и не только в ней).

← →
Ozone © (2004-10-22 11:47) [11]

... ЫЙ

← →
Ozone © (2004-10-22 11:50) [12]

Анонимщик © (22.10.04 11:47) [10]

// для твоего недетерминированного конечного автомата построить
// эквивалентный детерминированный

А вот это уже ближе к теме! Я бы даже сказал - очень близко!

// Ты бы все-таки купил бы книгу, о которой тебе говорили.

Денег нет, а задачи горят.

← →
Анонимщик © (2004-10-22 11:52) [13]

Так что, уроки онлайн будем проводить? Поищи в поисковике, наверняка найдешь алгоритм.
Кстати, как у тебя получается так быстро отвечать?

← →
AlexG © (2004-10-22 11:55) [14]

//Анонимщик © (22.10.04 11:47) [10]
Есть языки, котрые не описать с помощью детерминированного

//Ozone
Есть такое... Есть матрица, блин забыл уже все, предпочтений, кажись. И стек там нужен, но собственный.
Вот, посмотри http://softcraft.ru/auto.shtml В свое время здесь я нашел информацию, которая помогла мне

← →
Анонимщик © (2004-10-22 11:58) [15]

AlexG
Ну есть, но тогда и с помощью недетерминированного не опишешь, не так ли?

← →
Ozone © (2004-10-22 12:01) [16]

Анонимщик © (22.10.04 11:52) [13]

Уже нашел.

// Кстати, как у тебя получается так быстро отвечать?

Спасибо нашим администраторам :)

← →
Andryk © (2004-10-22 12:04) [17]

Рекурсия это конечно красиво...
Но любую рекурсию можно представить с помощью вложенных циклов while

← →
AlexG © (2004-10-22 12:09) [18]

//Анонимщик © (22.10.04 11:58) [15]
Нет, не так.

← →
Анонимщик © (2004-10-22 12:25) [19]

Конечные автоматы называются эквивалентными, если оба они допускают одни и те же цепочки. Не так ли?

← →
AlexG © (2004-10-22 12:43) [20]

//Анонимщик © (22.10.04 12:25) [19]
Я был не прав когда утверждал, что нельзя по НКА построить ДКА. Забыл уже...

← →
Анонимщик © (2004-10-22 12:54) [21]

AlexG
А ты такого не говорил.

Ozone
Кстати, посмотри на
http://ukman.narod.ru/
http://rema.44.ru/resurs/study/compiler1/Compiler1.htm

На самом деле в интернете достаточно свободных книг на эту тему, но, должен сказать, не знаю ни одной идеальной.

← →
AlexG © (2004-10-22 13:02) [22]

Еще этот не плохой: http://codenet.ru/ там ечть и про НКА

http://algolang.da.ru/
http://ukman.narod.ru/

Когда я говорил об идеальности, то имел в виду теорию компиляторов вообще, а не конечных автоматов. Она как раз во многих местах хорошо описана.

← →
Boobleek (2004-10-22 14:27) [24]

А если вместо конечного автомата использовать автомат с магазинной памятью?

//Boobleek (22.10.04 14:27) [24]
Это кажись и есть НКА

AlexG
Нет, это контекстно-свободная грамматика.

Boobleek
Я твоего вопроса не понял.

← →
Boobleek (2004-10-22 16:09) [27]

неа 8)

← →
Boobleek (2004-10-22 16:19) [28]

последнее мое сообщение относилось 2 AlexG

2 Анонимщик
Что касается АМП, то пожалуй я загнался. Действительно, для распознавания цепочки регулярного языка не требуется МП.
Требуется приведение недетерминированного автомата к детерминированному, впрочем, об этом уже говорилось выше...

Не понял, мне отвечать или нет? Да и на что?

← →
Boobleek (2004-10-22 16:42) [30]

Ответь ка мне, дружище, цепочки какого языка требуется распознавать? Если не секрет, конечно...

//AlexG © (22.10.04 16:31) [29]
Не секрет конечно, только вопрос задал не я, а Ozone. РЕГУЛЯРНОГО ЯЗЫКА, т.е. такого, который подпадает под определение, чего-то там если не ошибаюсь, S = (G,F,R), где G - граф переходов, F - алвавит, R - правила. Что-то такое. У меня все это было 2 года назад и я к этому не возвращался после, поэтому не могу уверенно сказать...

Регулярные языки и конечные автоматы Найти похожие ветки