Какое количество языков принимается DFA размера

19

Вопрос прост и прям: для фиксированного , сколько (разных) языков принято DFA размером n (то есть nnnn состояний)? Я официально заявлю это:

Определите DFA как , где все как обычно и δ : Q × Σ Q (возможно, частичная) функция. Нам нужно установить это, поскольку иногда только полные функции считаются действительными.(Q,Σ,δ,q0,F)δ:Q×ΣQ

Для каждого определите отношение (эквивалентности) n на множестве всех DFA как: A n B, если | A | = | Б | = n и L ( A ) = L ( B ) .n1nAnB|A|=|B|=nL(A)=L(B)

Тогда возникает вопрос: для данного , каков индекс n ? То есть каков размер множества { L ( A ) A  - DFA размера  n } ?nn{L(A)A is a DFA of size n}

Даже когда - полная функция, это не кажется легким подсчетом (по крайней мере, для меня). Граф может быть не связан, и состояния в связанном компоненте, содержащем начальное состояние, могут все приниматься, поэтому, например, существует много графов размера n, принимающих Σ . То же самое с другими тривиальными комбинациями для пустого языка и других языков, чей минимальный DFA имеет меньше чем n состояний.δnΣn

(Наивная) рекурсия тоже не работает. Если мы возьмем DFA размера и добавим новое состояние, то, если мы хотим сохранить детерминизм и сделать новый граф подключенным (чтобы избежать тривиальных случаев), мы должны удалить переход, чтобы соединить новое состояние, но в этом случае мы можем потерять язык оригинала.k

Есть предположения?

Заметка. Я снова обновил вопрос, с формальным заявлением и без предыдущих отвлекающих элементов.

Janoma
источник
Просто чтобы уточнить: Вы имеете в виду «сколько разных языков можно определить, используя состояний?», Где язык определяется с использованием n состояний, если существует DFA с n состояниями, которые его принимают. Кроме того, для регулярных выражений регулярное выражение "a * aaaaaa", безусловно, имеет> 1 конкатенации, но DFA требуется только одно состояние (два, если вам нужен отдельный приемник), нет? nnn
Евгений Торстенсен
Извинения: Для примера регулярного выражения это должно быть "a a a a a *", так как это допускает любое число.
Евгений Торстенсен
Определение кажется очень связанным с понятием «точка-глубина», за исключением того, что понятие обычно применяется к языкам без звездочек (вероятно, по причинам, изложенным @Evgenij Thorstensen). c(r)
mhum
1
Тривиальное наблюдение: состояния могут использоваться для определения как минимум 2 n различных языков. n+12n
Евгений Торстенсен
2
Мы можем получить немного больше, поэтому кажется нормальным. Но число автоматов с n состояниями составляет около n c n 2 n = 2 c n log n + n = 2 Θ ( n log n ) (при условии | Σ | = c ). Можем ли мы получить 2 ω ( n ) ? 2Ω(n)ncn2n=2cnlogn+n=2Θ(nlogn)|Σ|=c2ω(n)
Каве

Ответы:

20

Я думаю, что этот вопрос был изучен ранее. Майк Домарацки написал обзор исследований в этой области: «Перечень формальных языков», Bull. EATCS, vol. 89 (июнь 2006 г.), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf

Герман Грубер
источник
4
В статье точно указан заданный вопрос, начиная со страницы 120 и далее. Это функция , и статья дает довольно узкие границы (близкие к тому, что Каве упоминает выше), хотя я не вдыхал все детали. gk(n)
Евгений Торстенсен
1
В самом деле. То, что мы хотим, - это или, согласно заданному соотношению, f k ( n ) , которое представляет собой число попарно неизоморфных минимальных DFA с n состояниями в алфавите k- букв. Я также не рассматривал это подробно, но кажется, что известны только границы, а не точные величины. gk(n)fk(n)nk
Янома
6
И от того же автора у нас есть статья « О числе отдельных языков, принятых конечными автоматами с n состояниями» , которая даже дает явные вычисления для ( 1 n 10 ), g 2 ( n ) ( 1 n 6 ) и g 3 ( n ) ( 1 n 4 ). g1(n)1n10g2(n)1n6g3(n)1n4
Янома