DFA 可以设计为接受任何语言吗？
Can a DFA be designed to accept any language?
我们的老师对这个问题的回答是错误的。
不过，我觉得应该是真的。就拿这个接受sigma star的DFA来说吧。
- Q -> {s_1}
- q_0 -> s_1
- 西格玛 -> {a, b}
- F -> {s_1}
- delta -> {s_1[sigma] -> s_1}
这意味着这种语言必然接受 (sigma star) star，这是所有语言的集合，包括 non-regular 像 {a^nb^n | n > 1}。在我看来，non-regular 语言会被接受，因为它们是此 DFA 描述的语言的子集。
在我看来，这个 DFA 可以接受任何语言。
识别一种语言意味着拒绝 不属于该语言的字符串，而不仅仅是接受属于该语言的字符串。您可以构建一个接受每个字符串的自动机这一事实并不意味着您可以构建一个接受您需要接受的 特定 字符串并拒绝其他所有字符串的自动机。
您的编辑仍然如此；自动机接受的语言是自动机接受的所有单词的集合。该集合的任意子集不算作该自动机接受的语言。 （"The language accepted by an automaton" 和 "the language recognized by an automaton" 是同义词。）
Σ* 不是所有语言的集合。这是包含所有字符串的单一语言。
DFA 无法识别任何需要无限数量状态的语言。例如，a^nb^n（包含相同数量的 a 和 b 的语言）。对于每个 i，a^i 之后的一组有效后缀是不同的，因此每个 a^i 必须导致不同的状态，并且数字 i 是无界的。
参见：https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem
我们的老师对这个问题的回答是错误的。
不过，我觉得应该是真的。就拿这个接受sigma star的DFA来说吧。
- Q -> {s_1}
- q_0 -> s_1
- 西格玛 -> {a, b}
- F -> {s_1}
- delta -> {s_1[sigma] -> s_1}
这意味着这种语言必然接受 (sigma star) star，这是所有语言的集合，包括 non-regular 像 {a^nb^n | n > 1}。在我看来，non-regular 语言会被接受，因为它们是此 DFA 描述的语言的子集。
在我看来，这个 DFA 可以接受任何语言。
识别一种语言意味着拒绝 不属于该语言的字符串，而不仅仅是接受属于该语言的字符串。您可以构建一个接受每个字符串的自动机这一事实并不意味着您可以构建一个接受您需要接受的 特定 字符串并拒绝其他所有字符串的自动机。
您的编辑仍然如此；自动机接受的语言是自动机接受的所有单词的集合。该集合的任意子集不算作该自动机接受的语言。 （"The language accepted by an automaton" 和 "the language recognized by an automaton" 是同义词。）
Σ* 不是所有语言的集合。这是包含所有字符串的单一语言。
DFA 无法识别任何需要无限数量状态的语言。例如，a^nb^n（包含相同数量的 a 和 b 的语言）。对于每个 i，a^i 之后的一组有效后缀是不同的，因此每个 a^i 必须导致不同的状态，并且数字 i 是无界的。
参见：https://en.wikipedia.org/wiki/Myhill%E2%80%93Nerode_theorem