Хотелось бы узнать, каким регулярным выражениям длины $%n$% соответствуют автоматы с числом состояний, экспоненциально зависящим от $%n$%. Думал отталкиваться от определения регулярного языка и рассматривать, за какое количество состояний в худшем случае можно реализовать операции: звезда Клини ,$% \cup,\cdot$%. В одной найденной статье доказано, что если регулярныe языки $%L_1, L_2$% распознаются автоматами с количеством состояний $%n, m$%, то операция $%\cup$% приводит к линейному возрастанию количества состояний, а вот операции звезда Клини и $%\cdot$%, как раз в худшем случае вызывают экспоненциальный рост количества состояний. Проблема в том, что данные оценки связаны с автоматами и из этих наблюдений не получается указать структуры регулярных языков $%L_1,L_2$%. И поэтому встает вопрос, на что лучше обратить внимание? На структуры регулярных языков или стоит исследовать регулярные выражения.

задан 10 Май '17 17:54

изменен 10 Май '17 17:59

Вообще говоря, оба способа разумны, но здесь сам ответ, похоже, в другую сторону. Дело в том, что те теоремы, о которых Вы говорите -- это оценки сверху. Иногда они могут быть весьма далёкими от точных, если предпочитать краткие доказательства. Тогда можно временно использовать недетерминистские автоматы, а от них переходить к обычным, и тогда оценка числа состояний растёт экспоненциально.

В обсуждении здесь утверждается, если я правильно понял, что там линейной оценки всегда хватает.

(10 Май '17 19:03) falcao

В обсуждении линейная оценка даётся не для размерности автомата, а для времени распознавания выражения. У меня такой вопрос, если я найду структуру двух языков, конкатенация которых дает автомат с экспоненциальнымамой количеством состояний. Можно ли тогда утверждать, что если регулярный язык можно представить в виде конкатенации этих двух языков, то он "плохой"? И не будет способа представить его в каком-нибудь другом виде, который даст "хороший" автомат с небольшим колиствои состояний?

(10 Май '17 20:09) PaCman

@PaCman: я просматривал обсуждение бегло, и не уловил до конца смысл. Видимо, там действительно шла речь о чём-то другом.

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

Имеет смысл поискать что-то уже готовое в статьях.

(11 Май '17 0:01) falcao
10|600 символов нужно символов осталось
1

Сейчас я осуществил поиск по несколько более подходящим словам, и нашёл вот такую ссылку. Там ближе к концу есть конкретные упоминания языков, про которые доказано, что минимальные DFA для них имеют экспоненциальное число состояний. Что-то там приводится без доказательства, но есть список литературы. Скорее всего, эти примеры строятся нетривиально, поскольку это содержание отдельных статей, причём относительно недавних.

ссылка

отвечен 11 Май '17 0:13

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×29

задан
10 Май '17 17:54

показан
502 раза

обновлен
11 Май '17 0:13

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru