门|门CS 2010 |问题40

考虑语言 L1={0 ^我 1. ^J |我！=j} 。 L2={0 ^我 1. ^J |i=j}。 L3={0 ^我 1. ^J |i=2j+1}。 L4={0 ^我 1. ^J |我！=2j}。 （A） 只有L2是上下文无关的 （B） 只有L2和L3是上下文无关的 （C） 只有L1和L2是上下文无关的 （D） 所有这些都是上下文无关的 答复: （D） 说明：

所有这些语言都有可以派生它们的有效CFG。因此，它们都是CFL。凭直觉， （A） &（B）是众所周知的CFL，而（C）和（D）的CFG只需在 A&B的CFGs。

这个解决方案是由 维内特·珀斯瓦尼 .

这个问题的小测验