DFA и обычные языки

Question

Я думал о следующем, и думаю, что ответ утвердительный.

Правда ли, что каждое подмножество DFA-приемлемого языка, который является регулярным, также DFA-приемлемо?

Answer 1

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

Answer 2

Нет. Контрпример: Алфавит цифр цифр. DFA принимает все натуральные числа. Подмножество: DFA принимает все простые числа.

Редактировать: Алфавит это цифры. Извините, неправильная терминология там.

Натуральные числа можно выразить как обычный язык (и, следовательно, для них можно построить DFA):

0|([1-9][0-9]*)