是嗎？如果是這樣，爲什麼這兩個常規語法不同呢？

Question

我負責編寫基於正則表達式的正則語法。

給出的正則表達式a*b可以寫成S -> b | aS

它是不正確的是ba*作爲常規語法S -> b | Sa？

有人告訴我正確的答案其實S -> bA，A -> ^| aA但我看不出區別自己。

解釋將不勝感激！

Answer 1

IIRC，你的答案和被稱爲「正確」的答案都是正確的。請參閱this。你所建立的是一個「左正規文法」，而「正確」答案的支持者顯然更喜歡「正確的正則文法」。還有其他任意的規則可能或多或少地含蓄一些，比如「不空製作」規則，但它們並不影響正規語言的類別，僅僅是用於特定語言的語法的緊湊性，例如您的示例突出顯示了一個產品，其中兩種產品與兩種產品相比，一種產品有單一條款，另一種產品有兩種產品，其中一種是空的。