context-free-grammar - 构造CFG

Question

如何为语言x^ay^bz^2(a+b)其中 a>=0, b>=0 构建上下文无关语法。感谢您的帮助...

Answer 1

这样想

x^a y^b z^2(a+b) = x^a y^b z^2a z^2b = x^a y^b (z^2)^b (z^2)^a 

所以

S -> xSzz | S1
S1 -> yS1zz | e

Answer 2

请注意，对于 eachx和 each ，由于 2( a + b ) y，您需要生成两个's。此外，请注意每个字符串可以被视为 's 和 's 的“内部”部分，以及' s和's 的“外部”部分。zyzxz

因为对于每个y你需要两个z'，内部部分可以描述为（使用大写字母表示非终结符号和[]空字符串）：

I --> []
I --> y I z z

现在以相同的方式为外部部分编写语法，但I在基本情况下引用。

Answer 3

基本上有两种情况需要治疗：

• 您可以x在字符串的开头添加一个，在这种情况下，您需要z在末尾添加两个。
• 或者你可以y在中间添加一个，在这种情况下你还需要在z最后添加两个。

尝试将这些描述中的任何一个简化a^n b^n为您知道解决方案的更简单的语法（例如）。

这个提示应该足以推导出生成语法。