context-free-grammar - CFG 到正则表达式

Question

这里是语法，

S -> A | B

A -> 0000A | epsilon

B -> 000B | epsilon

我认为上面的正则表达式是

0000(0000)*000(000)* // 因为 0000 和 000 至少会被发现一次。

这个对吗 ？

有人说我，这个语法是模棱两可的。任何人都可以向我解释为什么？

Answer 1

在以下语法中（实际上是Right liner grammar）

S -> A | B

A -> 0000A | epsilon

B -> 000B | epsilon 

S您可以通过A或从起始变量生成字符串，B因此语法 L(G) 的语言是 Union ( +)，两种语言可以从A和生成B。

生产：

A -> 0000A | epsilon    

生成 (0000)*.

和

生产：

B -> 000B | epsilon     

生成 (000)*

所以 L(G) 的正则表达式是： (000)* + (0000)*

注意L(G) 可以有空字符串。

Answer 2

你的推理不正确。反例：空字符串在语言中，但您的正则表达式与它不匹配。

至于歧义，请考虑一串 12 个零。从该语法中可以得出多少种不同的方法？