К вопросу частичного угадывания формальных языков
Авторы: Исмагилов Р.С., Мастихина А.А. | Опубликовано: 04.04.2016 |
Опубликовано в выпуске: #2(65)/2016 | |
DOI: 10.18698/1812-3368-2016-2-3-15 | |
Раздел: Математика и механика | Рубрика: Математическая логика, алгебра и теория чисел | |
Ключевые слова: частичное угадывание, граф, автомат |
Рассмотрены бесконечные цепочки символов некоторого алфавита, порожденные размеченным ориентированным графом. Модифицировано понятие частичного угадывания. Изложены методы частичного угадывания для класса языков, основанные на ином подходе к рассматриваемым задачам. Доказан критерий и приведен конструктивный алгоритм угадывания. Сопоставлены результаты, полученные в настоящей работе, с результатами, полученными ранее. Изложение замкнуто в себе и использует лишь элементарные понятия, связанные с графами и автоматами.
Литература
[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.