我想为以下语言设计一个上下文无关的语法:
L = { w e {(, )}* | w is balanced}
我提出了以下语法:
S -> (S)S | E
而讲座中提出的解决方案是:
S -> (S) | SS | E
我无法弄清楚，我的解决方案可能存在什么问题。
我为各种情况运行了两种语法，例如:
(()()), ()()(), and (())()
并且 CFG 都接受这些字符串。
有人可以帮忙吗，我的 CFG 不涵盖哪些情况。或者它们都是等价的。或者达到最终状态所需的转换次数不同。
最佳答案
两种语法都生成相同的语言，因此都不是错误的。
我更喜欢你的，因为它是明确的，但这不是要求的一部分。许多人似乎发现另一个答案更容易理解，但这也不是要求的一部分，它是一个高度主观的标准。
关于context-free-grammar - 平衡括号的上下文无关语法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42430112/