Пусть есть автомат (ДКА) R, такой, что он распознаёт слова из множества M. Требуется оценить число состояний автомата (ДКА), который реализует регулярное выражение вида: (. звезда клини)R(. звезда клини), где . - любой символ алфавита.

задан 5 Май '17 22:25

изменен 5 Май '17 22:28

Используемые обозначения какие-то непонятные. Почему используется точка? Если $%A$% -- алфавит, то множество всех слов естественно обозначить в виде $%A^{\ast}$%. Ведь этот оператор применяется к множеству слов, а не к точке.

Непонятно также, почему в регулярном выражении посередине фигурирует $%R$%, то есть автомат. Если это язык, распознаваемый автоматом, то должно быть, наверное, $%M$%.

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

(5 Май '17 23:08) falcao

Давайте так, есть автомат, с который распознает слова из мн-ва M, алфавита A. Все слова в M не являются префиксом другого. Теперь нужно оценить число состояний автомата, такого что (в нотации PCRE была моя запись, звезду редактор съел) автомат выполняет поиск слов из M, в словах которые могут содержать слова из M, либо в начале, либо после, либо в конце.

(5 Май '17 23:19) doublench

Правильно ли я понял, что есть регулярный язык M (с какими-то дополнительными условиями типа префиксности), и далее рассматривается язык, состоящий из слов, содержащих какие-то подслова из M? Если так, то через что требуется оценить число состояний нового автомата? Достаточно ли будет здесь грубой оценки типа 2^k, где k -- число состояний автомата R?

(6 Май '17 3:40) falcao

Скорее всего слова которые мы подаём на вход могут и не обладать префиксностью. (А если обладают, то это упростит выкладки?) А вот слова из M, точно не могут быть префиксом другого. Ну и нужно как-то оценить число состояний автомата - поиск таких подстрок в строках того же алфавита. (Алгоритм Ахо-Корасик вроде подходит, и число состояний - сумма длин слов, но у меня и в исходном автомате столько же + 1) В целом я не знаю куда двигаться.

(6 Май '17 8:58) doublench

Если изначально дано конечное множество слов, обладающее свойством префиксности, и нужен автомат, который в произвольных словах отслеживает наличие таких подслов, то алгоритм Ахо - Корасик вроде как действительно подходит. Но чем он тогда не устраивает -- тем более, если состояний там сравнительно немного?

(6 Май '17 13:21) falcao

А другого подхода нет ? Просто алгоритм Ахо - Карасик вообще говоря для произвольных слов, а может свойство префиксности как-то улучшит ситуацию ? Не приходит ничего более в голову...

(6 Май '17 13:30) doublench

@doublench: для самого общего случая, скорее всего, что-то новое искать трудно. Но если в Вашем случае есть какие-то особенности множества слов M, то не исключено, что на этом можно будет как-то "сыграть". Можно ли указать какой-то "типовой" пример слов, с которыми Вы имеете дело, чтобы понять, нельзя ли для такого множества придумать что-то своё специфическое?

(6 Май '17 13:35) falcao

Автомат распознающий слова из M: http://imgur.com/a/gjCJK Оранжевый круг - финальное(поглощающее состояние), самый нижний круг - финальное(принимающее). A = {0, 1} M = {01, 1111} Скажем мы хотим переделать автомат выше для случая поиска этих подслов в любых слова A*

(6 Май '17 13:41) doublench

У Вас на картинке автомат принимает пустое слово по оранжевой стрелке. Наверное, так быть не должно.

Для случая подслов 01 и 1111 автомат устроен очень просто. Он отслеживает наличие нуля (и тогда за ним все нули, если 01 не встречается), а при наличии 1 он по состояниям запоминает, сколько таких единиц было. Может быть, какой-то более сложный пример можно рассмотреть -- чтобы понять, в чём именно "интрига", и можно ли не привлекать общих методов, для которых состояний получится много?

(6 Май '17 14:22) falcao

Пустых слов вообще говоря для моей работы быть не может. Соль тут везде одна, бегая по автомату http://imgur.com/a/gjCJK в какой-то момент, если далее идет символ не соответствующий слову из M мы должны вернуться в начальное, вот только в начальном состоянии нам нужно вернуться на один символ назад. Пример для A = {0, 1} M = {01, 1111}. Для слова 101. Начали по ветке для 1111 на 2ом шаге видим что вместо 1 имеем 0, нужно возвратиться в начальное с тем же символом 0, но в начальное попадаем со следующим символом 1. То есть вроде как должны пройтись по 1ой ветке (01) а пройти не можем.

(6 Май '17 14:57) doublench

То, что пустых слов быть не должно, это понятно. Но я обратил внимание на то, что на картинке пустое слово принимается.

Мне непонятно, зачем надо само множество M задавать автоматом. Ведь это конечный язык, и эти слова просто предъявляются, а потом уже по ним строится автомат для случая подслов. Совершенно не обязательно второй автомат получать как результат переработки первого.

В данном примере после 0 могут идти только нули. Если попалась 1, то сразу идём на выход. Для множества {01,1111} всё строится бесхитростно.

(6 Май '17 15:19) falcao

Это тоже звучит вполне логично, но как поставили вопрос, так его и решаем )

(6 Май '17 18:51) doublench
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×61

задан
5 Май '17 22:25

показан
491 раз

обновлен
6 Май '17 18:51

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

по почте:

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

по RSS:

Ответы

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

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