基于推导规则求解正则表达式对应语言的星号规则应用疑问

首先澄清一个表述歧义：你看到的示例L((a|b)*) = ab是简化写法，实际含义为ab是L((a|b)*)集合中的一个合法元素，而非L((a|b)*)这个集合整体等于ab。L((a|b)*)的完整集合是所有由a、b组成的任意长度的字符串（包括空串）。

第一步推导的依据 #

Kleene星号*的推导规则包含两条，你引用的资料里列出了对应≥1次拼接的第二条，还有一条对应0次拼接的规则：

• 规则1（0次拼接）：s* => ε（ε表示空字符串）
• 规则2（≥1次拼接）：s* => s(s*)

你给出的推导过程目标是得到长度为2的字符串ab，需要至少两次匹配(a|b)，所以第一步选择了规则2，将s替换为当前的正则单元(a|b)，自然就得到了：
(a|b)* => (a|b)(a|b)*

完整推导的逻辑补充 #

你看到的推导过程省略了最后一步的规则1使用，完整流程如下：

1. (a|b)* 应用星号规则2 → (a|b)(a|b)*
2. 第一个(a|b)选择分支a → a(a|b)*
3. 剩余的(a|b)*再次应用星号规则2 → a(a|b)(a|b)*
4. 第二个(a|b)选择分支b → ab(a|b)*
5. 剩余的(a|b)*应用星号规则1推导为空串 → ab + ε = ab

这样就完成了ab属于L((a|b)*)的推导。

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