context-free-grammar - 这是一种自由上下文语法语言吗？

Question

这是一种上下文无关的语言吗？

{a^(2k) b^n c^n : k >= 0 ∧ 0 <= n <= m}∪<br> {a^(2k+1) b^n c^m :k >= 0 ∧ n >= m >= 0}

Answer 1

证明语言为上下文无关语言的一种方法是为给定语言编写上下文无关语法：（或绘制 PDA）

下面的语言：

{a ^(2k) b ⁿ c ^m : k >= 0 和 0 <= n <= m} U {a ^(2k+1) b ⁿ c ^m : k >= 0 和 n >= m >= 0}

是上下文无关语言

_{我认为您在写问题时犯了错误，因为我对您的问题发表了评论，我正在为上述语法做}

我们可以为这种语言编写上下文无关语法：

在 Context-Free-Grammar 产生式中，α --> β其中α是单个变量。

S --> S ₁ | ₂ _

S ₁生成这部分 {a ^(2k) b ⁿ c ^m : k >= 0 and 0 <= n <= m} 并且 S ₂ 生成 {a ^(2k+1) b ⁿ c ^m : k >= 0 and n >= 米 >= 0}

S ₁ --> AB

一个 --> 啊 | ^

B --> bBc | ^

B --> Bc

和

S ₂ --> AaC

C --> bCc | ^

C --> bC

在语法S中是 start Variable 和 {S, S ₁ , S ₂ , A, B, C} 都是可变的。
因此，在上述语法中，每个产生式都采用单个变量 的形式α --> β，因此给定的语言是上下文无关语言。α

_{如果您有其他疑问或我误解了您的语言，请告诉我}