有限自動機只拒絕有限數量的字符串

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，...}。