context-free-language - 这是上下文无关的还是上下文敏感的语言？

Question

我正在学习形式语言和自动机理论，我有一个关于书中没有回答的问题的问题。问题是：

这种语言是上下文无关的、常规的还是上下文相关的？

L={a^ib^jc^k|i<=j 或 j<=i , j=k}

Answer 1

它是无上下文的。可以使用以下 CFG 指定：

S -> AX
A -> aA
A -> epsilon
X -> bXc
X -> epsilon

A 状态可以根据需要接受任意数量a的 s。X 生成b和c等量。因此，此 CFG 指定语言 L。

Answer 2

它是上下文相关的。

不规则：我们必须记住有限状态机不能的 b 或 c 的出现次数。

不是上下文无关的，就像我们应用抽引引理一样，在将 b 推入类似a^{2}b^{2} b^{n-4}b^{2}c^{n}.

所以它是上下文相关的。