|

К вопросу частичного угадывания формальных языков

Авторы: Исмагилов Р.С., Мастихина А.А. Опубликовано: 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.