有限自动机只拒绝有限数量的字符串

Question

有限自动机是否总是拒绝有限数量的字符串？在我看来，当一个自动机可以以相同的方式接受无限数量的字符串时，它也可以拒绝无限数量的字符串。请举证。

Answer 1

DFA接受或拒绝字符串。它可以：

1. 接受无限多的字符串并拒绝无限多的字符串;或
2. 接受无限多个字符串并拒绝有限多个字符串;或
3. 接受有限的许多字符串并拒绝无限多的字符串。

DFA无法接受有限多个字符串并同时拒绝有限多个字符串，因为在任何字母表中都有无限多的字符串，并且DFA必须接受或拒绝其中的每一个字符串。

案例1的示例：常规语言（00）* = {e，00，0000，...}在字母{0}上的任何DFA。它接受{e，00，000，...}并拒绝{0，000，00000，...}。

案例2的示例：在字母{0}上的常规语言0+ = {0，00，000，...}的任何DFA。它接受{0，00，000，...}并拒绝{e}。

案例3的示例：针对字母{0}的常规语言{e}的任何DFA。它接受{e}并拒绝{0，00,000，...}。