Аннотация:В работе Ж. Раджабова решается следующая задача. Рассматривается класс регулярных языков с линейной функцией роста в двухэлементном алфавите {a,b}. Сложностью такого языка называем Глубиной этого представления называем число s. На такие языки действует функция f побуквенного алфавитного кодирования. Сложностью функции кодирования называем максимальную длину ее элементарных кодов f(a),f(b). Задача состоит в том, чтобы оценить сверху и снизу самое большое значение длины образа минимальной склейки, то есть пары различных слов языка с совпадающим образом. При этом рассматриваются только такие языки нашего вида и такие функции кодирования, которые имеют сложность не выше k и у которых есть хоть одна склейка.
Известно, что в двухэлементном алфавите есть общий вид f(a)=(alpha)^m, f(b)=(alpha)^n схем кодирования, имеющих хоть одну склейку. Поэтому при поиске минимальной длины образа склейки достаточно ограничиться рассмотрением схем вида f(a)=0^n,f(b)=0^m.
Жахонгир смог найти соответствующую нижнюю оценку для класса языков глубины 2 и соответствующую верхнюю оценку для класса языков произвольной глубины. Для класса языков глубины 2 оценки совпали по порядку (отличие в 2 раза). Нижняя оценка получена конструктивно, верхняя – изящным рассуждением о псевдосклейках (лемма 1).