Докажите, что DFA над двоичным алфавитом с k состояниями может распознавать максимум k^(2k +1) * 2^k языков

Question

Мне дали этот вопрос в тесте, и я не мог этого сделать. Попытавшись немного, я все еще не могу этого сделать. Я думаю, что я что-то упускаю, но не знаю, что. Кто-нибудь может мне помочь?

Answer 1

Так что я думаю, что проблема была немного ошибочной. Позвольте мне вновь заявить:

Рассмотрит множество всех ДКА с к состояний над бинарным языком. Докажите, что число различных языков, распознаваемых DFA в этом множестве, не превышает k^(2k + 1) * 2^k.

Во-первых, при k> 1 количество распознанных разных языков намного меньше.

Но в любом случае, так как число состояний и алфавит фиксированы, любая DFA в этом наборе является defined totally by three things:

1. Переходной функция δ, которая принимает начальное состояние и символ (0 или 1) и дает конечное состояние.

2. Какой из к состояний, мы начинаем в.

3. Какой из к состояний (если таковые имеются) принимающую состояния.

Теперь, очевидно, есть (к) выбор для начального состояния, и поскольку каждое государство может быть либо принимающее государство или нет, есть (2^к) выбор для того, что принимающий состояния.

Это оставляет нам функцию перехода. Для каждого начального состояния с, мы имеем к выбор для б (с, 0) и к выбор для б (с, 1). Поэтому для δ имеем (k^(2 k)) возможности.

Поэтому число различных возможных ДКА является к * (2^к) * (к^(2 к)), что дает Bound просил.

Число языков, конечно, намного меньше, так как каждая машина могла бы переписать все ее состояния без изменения принятого языка, поэтому лучшая оценка была бы (kk (2k + 1) * 2^k)/(k !). Даже это слишком велико, поскольку, например, каждая машина со всеми ее состояниями, установленная для «принятия», принимает тот же язык.