12 / 13
Рис. 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