Комбинаторная сложность рациональных языков

Комбинаторной сложностью языка $L$ называется функция, сопоставляющая числу $n$ число различных слов длины $n$ в языке $L$. Точному вычислению и оценкам комбинаторной сложности различных языков посвящены десятки работ. В статье приводится классификация по сложности произвольных рациональных языков и доказывается, что все эти классы остаются нетривиальными при переходе к подклассу рациональных языков – языкам с конечными антисловарями. Для таких языков известен алгоритм оценки сложности. Этот алгоритм экспоненциален по памяти, но находит практическое применение. Обсуждаются приближения произвольных факторных языков языками с конечными антисловарями, доказывается теорема о приближениях языка Туэ–Морса и формулируется общая гипотеза о сложности таких приближений.