Статьи

Более тонкая характеризация буквенно-ограниченных языков, задаваемых GF(2)-грамматиками

В. Макаров, М. Мовсин

Cанкт-Петербургский государственный университет, факультет математики и компьютерных наук, 199178, Санкт-Петербург, Россия

Аннотация: Относительно недавно Бакинова и др. ввели семейство GF(2)-грамматик. Семейство GF(2)-грамматик примечательно тем, что у него много алгебраических свойств, которыми не обладает семейство обыкновенных бесконтекстных грамматик. В статье “Bounded languages described by GF(2)-grammars” Макаров доказал необходимое условие, которым должны обладать все задаваемые GF(2)-грамматиками подмножества $a_1^* a_2^* \ldots a_k^*$. Усиливая его методы, мы доказываем более точные верхние и нижние оценки на подмножества $a_1^* a_2^* \ldots a_k^*$, задаваемые GF(2)-грамматиками. Данные верхние и нижние оценки выражаются в терминах семейств подотрезков $\{1, 2, \ldots, n\}$, любые два из которых либо не пересекаются, либо вложены.

Ключевые слова: формальные грамматики, буквенно-ограниченные языки, конечные поля, кольца.

Поступила в редакцию: 26.11.2025