Может ли DFA быть рассчитан на любой язык?

Question

Ответ нашего инструктора на этот вопрос - ЛОЖЬ.

Однако я думаю, что это должно быть правдой.Возьмите этот DFA, который принимает сигма-звезду.

• Q -> {s_1}
• q_0 -> s_1
• сигма -> {a, b}
• F -> {s_1}
• дельта -> {s_1 [sigma] -> s_1}

Это означает, что этот язык обязательно принимает (сигма-звезда) звезду. Это набор всех языков, включая нерегулярные, такие как {a ^ nb ^ n |n> 1}.Тогда мне кажется, что нерегулярные языки будут приняты, поскольку они являются подмножеством языка, который описывает этот DFA.

Мне кажется, что этот DFA будет принимать любой язык.

Answer 1

Σ * не набор всех языков. Это single язык, который включает все строки.

DFA не могут распознавать любой язык, который требует бесконечного количества состояний. Например, a ^ nb ^ n (язык, содержащий равное количество a и b). Для каждого i набор действительных суффиксов после a ^ i различен, поэтому каждый a ^ i должен приводить к другому состоянию, а число i не ограничено.

См .: https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem

Answer 2

При распознавании языка подразумевается отклонение строк, которые не принадлежат этому языку, а не только принятие строк, которые действительно принадлежат. Тот факт, что вы можете создать автомат, который принимает каждую строку, не означает, что вы можете создать автомат, который принимает специфические строки, которые вам нужно принять, и отклоняет все остальное.

Это остается верным с вашим редактированием; язык, принимаемый автоматом, - это совокупность всех слов, принимаемых автоматом. Произвольные подмножества этого набора не считаются языками, принятыми этим автоматом. («Язык, принимаемый автоматом» и «язык, распознаваемый автоматом», являются синонимами.)