Сибирский федеральный университет

Тип публикации: статья из журнала

Год издания: 2022

Идентификатор DOI: 10.17223/2226308X/15/20

Ключевые слова: polynomial grammars, noncommutative variables, formal power series, commutative image, jacobian, полиномиальные грамматики, некоммутативные переменные, формальный степенной ряд, коммутативный образ, якобиан

Аннотация: Исследуются формальные грамматики - системы полиномиальных уравнений относительно некоммутативных переменных, которые решаются в виде формальных степенных рядов, выражающих нетерминальные символы алфавита через терминальные; первая компонента решения является формальным языком. Рассмотрено определение грамматики, имеющей бесконечно много решений (порождающей бесконечное множество языков). Такие грамматики могут возникать в ситуации, когда якобиан коммутативного образа грамматики тождественно равен нулю. Показано, что в этом случае описание множества решений грамматики сложнее, чем для аналогичных полиномиальных систем с вещественными или комплексными переменными, поскольку могут реализовываться все возможные ситуации: такая грамматика может иметь бесконечно много решений, любое конечное число решений либо не иметь решений вовсе. We continue the study of formal grammars, by which we mean systems of polynomial equations with respect to noncommutative variables, which are solved in the form of formal power series expressing nonterminal alphabet symbols through terminal alphabet symbols. The first component of the solution is a formal language. The definition of a grammar having infinitely many solutions (generating an infinite number of languages) is considered. Such grammars can arise in a situation, where the Jacobian of the commutative image of the grammar is identically equal to zero. It is shown that in the case of the Jacobian, which is identically equal to zero, it is more difficult to describe the set of grammatical solutions than for similar polynomial systems with real or complex variables, since all possible situations can be realized: such a grammar may have infinitely many solutions, any finite number of solutions, or no solutions at all.

Журнал: Прикладная дискретная математика. Приложение

Выпуск журнала: № 15

Номера страниц: 78-80

ISSN журнала: 2226308X

Место издания: Томск

Издатель: Национальный исследовательский Томский государственный университет

• Егорушкин Олег Игоревич (Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнёва)
• Колбасина Ирина Валерьевна (Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнёва)
• Сафонов Константин Владимирович (Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнёва)

• РИНЦ (eLIBRARY.RU)