theory - DFA 和常规语言

Question

我一直在思考以下问题，我认为答案是肯定的。

DFA 可接受的常规语言的每个子集是否也是 DFA 可接受的，这是真的吗？

Answer 1

不。反例：字母是数字。DFA 接受所有自然数。子集：DFA 接受所有素数。

编辑：字母是数字。对不起，那里的术语有误。

自然数可以表示为常规语言（因此可以为它们构造 DFA）：

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

Answer 2

所有有限自动机——确定性和非确定性——都可以表示为常规语言，反之亦然。如果语言的子集是正则的，那么是的，它可以表示为 DFA。