这里是语法，
S -> A | B
A -> 0000A | epsilon
B -> 000B | epsilon
我认为上面的正则表达式是
0000(0000)*000(000)* // 因为 0000 和 000 至少会被发现一次。
这个对吗 ？
有人说我，这个语法是模棱两可的。任何人都可以向我解释为什么？
问问题
4218 次
2 回答
2
在以下语法中（实际上是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) 可以有空字符串。
于 2013-02-09T09:14:04.503 回答
1
你的推理不正确。反例：空字符串在语言中，但您的正则表达式与它不匹配。
至于歧义，请考虑一串 12 个零。从该语法中可以得出多少种不同的方法？
于 2013-02-09T01:21:35.303 回答