Question

编译原理题目

Answer 1

这个问题可以用数学归纳法证明。

下面先给出一个定义 嵌套深度： S恰经过n步推理后，语句中不含S，则说S的嵌套深度为n。

显然，S的嵌套深度至少为1.

下面对嵌套深度用归纳法。

嵌套深度为1时，语句为y，满足x*yx*的形式。

设嵌套深度为k时，语句满足形式x*yx*。

嵌套深度为k+1时，语句为x*Sx*，其中S->xSx->xyx。所以x*Sx*任然是x*Sx*的形式。

所以语言为x*Sx*。嵌套深度为n时，语句为

至于您的第二个问题，也可以用数学归纳法。第一个问题不解。

追问

自己想通了，，3q