Об одной гипотезе теории формальных языков. Часть I
Автор: Мельников Б.Ф.
Статья в выпуске: 3 т.12, 2023 года.
Бесплатный доступ
Основной предмет статьи - рассмотрение задач, возникающих при исследовании необходимых условий равенства бесконечных итераций конечных языков. В предыдущих публикациях автором рассматривались примеры применения соответствующего этому равенству специального бинарного отношения эквивалентности на множестве конечных языков, причем рассматривались как примеры, описывающие необходимые условия его выполнения, так и примеры его использования. К одному из таких необходимых условий применены два варианта сведeния рассматриваемой задачи: к конечным автоматам и к бесконечным итерационным деревьям. Также в статье приведены несколько вариантов важной гипотезы, формулируемой для множества конечных языков; ее исследование дает и иные варианты сведeния рассматриваемой задачи к специальным задачам для недетерминированных конечных автоматов. При этом в случае выполнения сформулированной гипотезы некоторые из таких задач решаются за полиномиальное время, а некоторые не решаются; при продолжении работ по данной тематике последний факт может дать возможность переформулировки проблемы P = NP в виде специальной задачи теории формальных языков.
Формальные языки, итерации языков, бинарные отношения, морфизмы, инверсные морфизмы, алгоритмы, полиномиальные алгоритмы
Короткий адрес: https://sciup.org/147241763
IDR: 147241763 | DOI: 10.14529/cmse230305
Список литературы Об одной гипотезе теории формальных языков. Часть I
- Melnikov B.F., Korabelshchikova S.Yu., Dolgov V.N. On the task of extracting the root from the language // International Journal of Open Information Technologies. 2019. Vol. 7, no. 3. P. 1–6.
- Melnikov B.F., Melnikova A.A. Some more on !-finite automata and !-regular languages. Part I: The main definitions and properties // International Journal of Open Information Technologies. 2020. Vol. 8, no. 8. P. 1–7.
- Мельников Б.Ф., Мельникова А.А. Бесконечные деревья в алгоритме проверки условия эквивалентности итераций конечных языков. Часть I // International Journal of Open Information Technologies. 2021. Vol. 9, no. 4. P. 1–11.
- Мельников Б.Ф., Мельникова А.А. Бесконечные деревья в алгоритме проверки условия эквивалентности итераций конечных языков. Часть II // International Journal of Open Information Technologies. 2021. Vol. 9, no. 5. P. 1–11.
- Мельников Б.Ф. Варианты конечных автоматов, соответствующих бесконечным итерационным деревьям морфизмов. Часть I // International Journal of Open Information Technologies. 2021. Vol. 9, no. 7. P. 5–13.
- Мельников Б.Ф. Варианты конечных автоматов, соответствующих бесконечным итерационным деревьям морфизмов. Часть II // International Journal of Open Information Technologies. 2021. Vol. 9, no. 10. P. 1–8.
- Мельников Б.Ф., Мельникова А.А. Полиномиальный алгоритм построения конечного автомата для проверки равенства бесконечных итераций двух конечных языков // International Journal of Open Information Technologies. 2021. Vol. 9, no. 11. P. 1–10.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть I. Извлечение корня из языка // International Journal of Open Information Technologies. 2022. Vol. 10, no. 4. P. 1–9.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть II. Построение инверсного морфизма // International Journal of Open Information Technologies. 2022. Vol. 10, no. 5. P. 1–8.
- Мельников Б.Ф. Полурешетки подмножеств потенциальных корней в задачах теории формальных языков. Часть III. Условие существования решетки // International Journal of Open Information Technologies. 2022. Vol. 10, no. 7. P. 1–9.
- Мельников Б.Ф. Лепестковые конечные автоматы: основные определения, примеры и их связь с полными автоматами. Часть I // International Journal of Open Information Technologies. 2022. Vol. 10, no. 9. P. 1–11.
- Мельников Б.Ф. Лепестковые конечные автоматы: основные определения, примеры и их связь с полными автоматами. Часть II // International Journal of Open Information Technologies. 2022. Vol. 10, no. 10. P. 1–10.
- Мельников Б.Ф. Регулярные языки и недетерминированные конечные автоматы (монография). М.: Изд-во Российского государственного социального университета, 2018. 179 с.
- Melnikov B.F. The equality condition for infinite catenations of two sets of finite words // International Journal of of Foundations of Computer Science. 1993. Vol. 4, no. 3. P. 267–273.
- Мельников Б.Ф. Описание специальных подмоноидов глобального надмоноида свободного моноида // Известия высших учебных заведений. Математика. 2004. № 3. С. 46–56.
- Алексеева А.Г., Мельников Б.Ф. Итерации конечных и бесконечных языков и недетерминированные конечные автоматы // Вектор науки Тольяттинского государственного университета. 2011. № 3 (17). С. 30–33.
- Hopcroft R., Motwani R., Ullman J. Introduction to Automata Theory, Languages, and Computation. Massachusetts: Addison-Wesley Publishing Company Reading, 2006. 530 p.
- Hromkoviˇc J. Theoretical Computer Science. Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography. Berlin: Springer, 2003. 323 p.
- Melnikov B.F. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol. 104, no. 3. P. 267–283.
- Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Том 1. М.: Мир, 1978. 617 с.
- Melnikov B.F. The complete finite automaton // International Journal of Open Information Technologies. 2017. Vol. 5, no. 10. P. 9–17.
- Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2003. 384 с.
