如何为接受连续0/1的有限状态机编写产生式规则？

一、给定产生式是否可用？ #

可以使用。这套产生式本质是用右线性文法模拟DFA，能够正确接受所有包含连续0或1的字符串：

• 假设起始非终结符为A（代表初始状态，未出现连续相同字符）；
• B、C分别代表刚读入1、刚读入0的状态（均未出现连续相同字符）；
• D是接受状态：当从C读入0（连续两个0）或从B读入1（连续两个1）时，进入D；进入D后可通过D→D0|D1自循环，后续输入任意字符都保持接受状态。

对应示例验证：

• 输入01001：A→C（读0）→B（读1）→C（读0）→D（读0，触发连续0）→D（读1），最终停在接受状态D，符合Accept规则；
• 输入101：A→B（读1）→C（读0）→B（读1），最终停在非接受状态B，符合Reject规则。

二、终结符与状态的区分 #

在形式文法的常规约定中：

• 状态（非终结符）：用大写字母表示（这里的A、B、C、D）；
• 终结符（输入字符）：用数字表示（这里的0、1）。
  若需要绝对明确，可在文法定义前显式声明：

终结符集合 T = {0, 1}，非终结符集合 N = {A, B, C, D}

三、状态的位置选择 #

给定产生式采用的是「目标状态 → 源状态 终结符」的写法（如D→C0表示从状态C读入0后转移到D），这是右线性文法的一种变体。
另一种更标准的右线性文法写法是「源状态 → 终结符 目标状态」（如C→0D），两种写法逻辑等价，只要整套文法保持统一的位置规则即可。

内容的提问来源于stack exchange，提问作者David542