Языки с конечным антисловарем: индекс роста и свойства автоматов

Abstract

Рассматриваются факториальные языки с конечным антисловарем и экспоненциальной функцией сложности, а также распознающие их автоматы. Улучшен алгоритм оценки роста таких языков, доказан ряд графовых свойств распознающих автоматов, а также приведена классификация бинарных языков, распознаваемых маленькими автоматами.

We study factorial languages with a finite antidictionary and an exponential complexity function as well as automata recognizing such languages. We improve an algorithm for estimation of the growth rate of such languages and establish certain graph properties of their recognizing automata. Binary languages with small recognizing automata are completely classified.