Previous Page  12 / 13 Next Page
Information
Show Menu
Previous Page 12 / 13 Next Page
Page Background

Рис. 3. Автомат, представляющий с помощью семейства множеств состояний

{{

d

}{

d, e

}}

язык

настоящей работе. Далее в работе [3] доказано, что объединение язы-

ков вида

L

(

q

0

, Q, Q

0

)

являтся частично угадываемым в широком смы-

сле, когда каждый язык частично угадываем в широком смысле. Верно

и обратное.

Для указанного объединения языков в работе [3] был использован

термин “язык, представимый с помощью семейства множеств состо-

яний” и объяснялась их роль в проблеме угадывания. Автомат, пред-

ставляющий с помощью семейства множеств состояний

{{

d

}{

d, e

}}

язык, который состоит из всех слов, где после некоторого момента не

встречается две единицы подряд, приведен на рис. 3.

Общерегулярные языки были исследованы в работах [2, 3], в ко-

торых показано, что вопрос об их угадывании сводится к частичному

угадыванию языков вида

L

(

q

0

, Q, Q

0

)

. Угадывание выполнялось с по-

мощью конечных автоматов.

В настоящей статье изложение, приведенное в упомянутых рабо-

тах, модифицировали, в частности, указали простые алгоритмы уга-

дывания.

Завершая сопоставление работы [3] с настоящей, отметим су-

щественный инструмент, использованный в работе [3]. Язык вида

L

(

q

0

, Q, Q

0

)

— частично угадываемый тогда и только тогда, когда най-

дется слово, не содержащееся ни в одном слове этого языка. Этот

критерий наличия “запрещенного” слова представляет самостоятель-

ный интерес, но в данной работе не используется.

ЛИТЕРАТУРА

1.

Вереникин А.Г.

,

Гасанов Э.Э.

Об автоматной детерминизации множеств сверх-

слов // Дискретная математика. 2006. Т. 18. № 2. C. 84–97.

2.

Мастихина А.А.

О частичном угадывании сверхслов // Интеллектуальные си-

стемы 2007. Т. 11. Вып. 1–4. С. 609–619.

3.

Мастихина А.А.

Критерий частичного предвосхищения общерегулярных сверх-

событий // Дискретная математика. 2011. T. 23. № 4. C. 103–114.

4.

Трахтенброт Б.А.

,

Бардзин Я.М.

Конечные автоматы (поведение и синтез). М.:

Наука, 1970.

5.

Мастихина А.А.

Частичное угадывание сверхсобытий, порожденных простыми

LL

(1)

-грамматиками // Интеллектуальные системы. 2011. T. 15. C. 507–532.

14

ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. “Естественные науки”. 2016. № 2