Теорема Савича показывает, что для всех достаточно больших функций , и доказательство того, что это тесно, является открытой проблемой на протяжении десятилетий ,
Предположим, мы подходим к проблеме с другого конца. Для простоты предположим булев алфавит. Объем пространства, используемого ТМ для выбора вычислимого языка, часто тесно связан с логарифмом числа состояний, используемых автоматом, моделирующим ТМ, для каждого регулярного фрагмента языка. Это мотивирует следующий вопрос.
Пусть - количество синтаксически различных DFA с состояниями, а - количество различных NFA с состояниями. Нетрудно показать, что близко к .
Кроме того, пусть будет числом различных регулярных языков, которые могут быть распознаны DFA с состояниями, и пусть будет числом, распознанным NFA.
Известно ли, что близко к ?
Мне не ясно, как и , или и , связаны друг с другом или насколько тесно. Если все это относится к общеизвестному вопросу в теории автоматов, то будет полезен намек или указатель. Этот же вопрос актуален и для двусторонних автоматов по той же причине, и я особенно заинтересован в этой версии.
источник
Ответы:
В моей статье с Домарацки и Кисманом «О количестве различных языков, принимаемых конечными автоматами с n состояниями», опубликованной в J. Automata, Languages and Combinatorics 7 (2002), мы доказали, что если есть число отдельные языки, принятые NFA с n состояниями в алфавите k- буквы, и g k ( n ) аналогично числу различных языков, принятых DFA, тогда для фиксированных k ≥ 2Gk(n) n k gk(n) k≥2
(i) асимптотически с точностью до порядка меньшего порядка k n log nloggk(n) knlogn
(ii) , с точностью до членов меньшего порядка, асимптотически между ( k - 1 ) n 2 и k n 2 .logGk(n) (k−1)n2 kn2
источник