popoff.donetsk.ua title

форумы popoff.donetsk.ua

Страницы: [1]

Подписаться на уведомления об изменениях в этом топике | << Новый | Старый >> | Ответить

Автор	Сообщение
chtoosha alex Май, 2009 Сообщений: 1	chtoosha url://forum.message:2821 Конечные автоматы и регулярные выражения Вопрос такой: Можно ли как-нить определить распознает ли данный автомат регулярное выражение? Нету ли каких-нить свойств по этому вопросу?
27.05.09 07:02	URL сообщения \| Приват \| Инфо об авторе \| Ответить

popoff Yuri Июл, 2004 Сообщений: 1078	popoff url://forum.message:2823 chtoosha, Нет, каких-то определённых свойств, какими мог бы обладать автомат, таких, что по ним можно было бы сказать, что автомат распознаёт регулярные выражения - не бывает. Нужно анализировать работу автомата и понимать, что он распознаёт - это единственный способ. ________________________________ Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.
27.05.09 18:04	URL сообщения \| Приват \| Инфо об авторе \| Ответить

	Гость	chtoosha url://forum.message:2826 chtoosha а если переффразировыать. скажем так, есть автомат со свойством, что в строках,которые принимаются автоматом, и не принимаются автоматом, никогда не совпадает последний символ. Про автомат сам ничего изначально не известно, известно, что он конечный, а детерминированный или нет --- не извстно. Это просто не школьные и даже не студенчески задачи. Мне вот лично кажется, что автомат недетерминированный не имеет этого свойства. Но увренности нету.
	27.05.09 18:23	URL сообщения \| Ответить

popoff
Yuri

Июл, 2004
Сообщений: 1078

popoff url://forum.message:2831

chtoosha,
Такой автомат может быть как детерменированным, так и недетерменированным. Детерменированность можно определить только зная внутреннее устройство автомата, либо имея достаточно много экспериментальных данных. Вы же привели результат единственного эксперимента:

в строках,которые принимаются автоматом, и не принимаются автоматом, никогда не совпадает последний символ
chtoosha, форумы popoff.donetsk.ua

По этому эксперименту не возможно ответить на Ваш вопрос:

распознает ли данный автомат регулярное выражение
chtoosha, форумы popoff.donetsk.ua

________________________________
Если не будет деревьев — нам нечем будет дышать, если вода загрязнится — нам нечего будет пить.

	Гость	chtoosha url://forum.message:2832 chtoosha а разве детерминированный и недетрминированный автоматы не эквивалентны? Мне казалось, что детерминизм тут вообще не принципиален, так как DFA сводится к NFA? И разве множества регулярных множеств и кнечных автоматов не эквивалентны?
	28.05.09 20:32	URL сообщения \| Ответить

popoff
Yuri

Июл, 2004
Сообщений: 1078

popoff url://forum.message:2833

регулярное выражение
chtoosha, форумы popoff.donetsk.ua

регулярных множеств
chtoosha , форумы popoff.donetsk.ua

Я не знаю, что такое «регулярное множество» и в чём его отличие от «регулярного выражения».

а разве детерминированный и недетрминированный автоматы не эквивалентны?
chtoosha , форумы popoff.donetsk.ua

не слышал раньше о таком, чтобы эквивалентные объекты называли разными словами.

Гость

osipov_oleg at list dot ru url://forum.message:3203

osipov_oleg at list dot ru

Метод исключения состояний существует для этого

Страницы: [1]

Подписаться на уведомления об изменениях в этом топике | << Новый | Старый >> | Ответить

Конечные автоматы и регулярные выражения