是吗？如果是这样，为什么这两个常规语法不同呢？

Question

我负责编写基于正则表达式的正则语法。

给出的正则表达式a*b可以写成S -> b | aS

它是不正确的是ba*作为常规语法S -> b | Sa？

有人告诉我正确的答案其实S -> bA，A -> ^| aA但我看不出区别自己。

解释将不胜感激！

Answer 1

IIRC，你的答案和被称为“正确”的答案都是正确的。请参阅this。你所建立的是一个“左正规文法”，而“正确”答案的支持者显然更喜欢“正确的正则文法”。还有其他任意的规则可能或多或少地含蓄一些，比如“不空制作”规则，但它们并不影响正规语言的类别，仅仅是用于特定语言的语法的紧凑性，例如您的示例突出显示了一个产品，其中两种产品与两种产品相比，一种产品有单一条款，另一种产品有两种产品，其中一种是空的。