Дата публикации: 2022

Дата публикации в реестре: 2022-10-06T22:43:15Z

Аннотация:

Исследуются формальные грамматики — системы полиномиальных уравнений относительно некоммутативных переменных, которые решаются в виде формальных степенных рядов, выражающих нетерминальные символы алфавита через терминальные; первая компонента решения является формальным языком. Рассмотрено определение грамматики, имеющей бесконечно много решений (порождающей бесконечное множество языков). Такие грамматики могут возникать в ситуации, когда якобиан коммутативного образа грамматики тождественно равен нулю. Показано, что в этом случае описание множества решений грамматики сложнее, чем для аналогичных полиномиальных систем с вещественными или комплексными переменными, поскольку могут реализовываться все возможные ситуации: такая грамматика может иметь бесконечно много решений, любое конечное число решений либо не иметь решений вовсе.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2022. № 15. С. 78-80