UGC-NET | UGC-NET CS 2017年1月-3日|问题23

考虑到以下两种语言： L1={a ^N B ^N |n≥ 0，n≠ 100} L2={w∈ {a，b，c}*|n _A. （w） =n _B （w） =n _C （w） } 以下哪个选项是正确的？ （A） 都是我 _1. 我呢 _2. 不是上下文无关的语言 （B） 都是我 _1. 我呢 _2. 是上下文无关的语言。 （C） L _1. 是上下文无关语言吗 _2. 不是上下文无关的语言。 （D） L _1. 不是上下文无关的语言，L _2. 是上下文无关的语言。 答复: （C） 说明： 语言L1={a ^N B ^N |n≥ 0，n≠ 100}是 上下文无关 因为我们把所有的a^n放入堆栈中，然后为每个a^n元素弹出所有的b^n元素，因为我们可以只使用一个堆栈来比较所有的a和b。

但是语言L2={w∈ {a，b，c}*|n _A. （w） =n _B （w） =n _C （w） }不是上下文无关的语言，因为我们不能同时比较所有的a、b和c，因为只有一个堆栈。为此，我们需要不止一个堆栈，然后这种语言L2成为上下文敏感的语言。

选项（C）是正确的。 这个问题的小测验