建设CFG

Question

如何为语言x^a ^b^ z^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

请注意，对于每个x和每个y，由于2(a + b)的缘故，您需要生成两个z。此外，请注意，每个字符串都可以被看作是y和z的“内部”部分，以及x和z的“外部”部分。

由于每个y都需要两个z，所以内部部分可以用(使用大写表示非终端符号和空字符串的[] )来描述：

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

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

Answer 3

从本质上讲，有两种情况你需要治疗：

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

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

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