如何构造L={x∈{0,1}∗|x为可被4整除的二进制编码}的正则文法

我们先明确核心判定规则：二进制数的权值从右到左为2^0、21、2^2...，因此除数字0外，所有无多余前导零、可被4整除的二进制串的最后两位必然是00。

以下给出符合要求的右线性正则文法（起始符为S，默认不包含多余前导零，若需要包含数字0可额外添加产生式 S → 0）：

• 起始产生式（首个字符为1，避免前导零）：S → 1A
• 非终结符A（代表当前串对应的数值模4余1）：
  • A → 0B （末尾加0后模4余2，进入状态B）
  • A → 1C （末尾加1后模4余3，进入状态C）
• 非终结符B（代表当前串对应的数值模4余2）：
  • B → 0 （末尾加0后模4余0，串结束，符合要求）
  • B → 0D （末尾加0后模4余0，继续追加后续字符）
  • B → 1A （末尾加1后模4余1，进入状态A）
• 非终结符C（代表当前串对应的数值模4余3）：
  • C → 0B （末尾加0后模4余2，进入状态B）
  • C → 1C （末尾加1后模4余3，进入状态C）
• 非终结符D（代表当前串对应的数值模4余0，已满足整除要求）：
  • D → 0 （末尾加0后模4仍为0，串结束）
  • D → 0D （末尾加0后模4仍为0，继续追加字符）
  • D → 1A （末尾加1后模4余1，进入状态A）

验证示例 #

你给出的示例均可由该文法生成，举几个简单的推导过程：

• 100：S → 1A → 10B → 100
• 1100：S → 1A → 11C → 110B → 1100
• 10100：S → 1A → 10B → 101A → 1010B → 10100

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