大门| 2007大门|问题46

下面给出的两个语法在字母表{x，y，z}上生成一种语言 以下哪个选项描述了这些语言中字符串满足的属性？ （A） G1：在任何x之前都不会出现y G2：每个x后面至少有一个y （B） G1：在任何x之前都不会出现y G2：没有x出现在任何y之前 （C） G1：任何x之后都不会出现y G2：每个x后面至少有一个y （D） G1：任何x之后都不会出现y G2：每个y后面至少有一个x 答复: （A） 说明： 对于上述问题，我们可以看到，对于所有选项，字符串满足的属性可以定义为x和y字母之间的某种关系。 语法1 ，同时包含x和y的字符串只能通过以下语法生成形式生成。

S–>xS–>xyB或

S–>zS–>zxS–>zxyB

（如果开始生产是S–>x | z | yB，则不能同时给出字符串中的x和y） 因此，在任何带有x和y的字符串中，在x被描述为语言字符串满足的属性之前，都不能出现y。 语法2也是如此 ，可以使用以下方法生成同时包含x和y的字符串

仅语法的产生形式。

S–>yS–>yxB–>yxy或S–>yS–>yxB–>yxyB

S–>xB–>xy或S–>xB–>xyB

因此，在任何带有x和y的字符串中，每个x后面至少有一个y可以被描述为语言字符串所满足的属性。

这个解决方案是由 安田荣彦 . 这个问题的小测验