我被要求表明ABA ^ R形式的歌曲集是无上下文的（其中A ^ R是A反转） . 我不知道如何显示语言是无上下文的 .
我们还没有具体研究如何证明语言是无上下文的，所以它不能太复杂 . 我唯一能想到的是为语言制作一个无上下文的语法，但我真的不知道这是否足以表明它是无上下文的，或者我是如何为一组歌曲制作语法的 .
假设A和B是一组字符串并且它们是无上下文的，那么语言A和B就有上下文无关语法，比如说G_A和G_B . 您可以非常轻松地从G_A获取语言A ^ R的上下文无关语法 . 只需反转语法规则的右侧，即可获得A ^ R的语法 .
如果G_A的起始变量是S_A，G_B是S_B而G_A ^ R是S_A'那么最终语法将是这些语法的组合（三个语法的每个变量应该唯一地命名）与新的起始变量和新的规则陈述
S -> S_A S_B S_A'
1 回答
假设A和B是一组字符串并且它们是无上下文的，那么语言A和B就有上下文无关语法，比如说G_A和G_B . 您可以非常轻松地从G_A获取语言A ^ R的上下文无关语法 . 只需反转语法规则的右侧，即可获得A ^ R的语法 .
如果G_A的起始变量是S_A，G_B是S_B而G_A ^ R是S_A'那么最终语法将是这些语法的组合（三个语法的每个变量应该唯一地命名）与新的起始变量和新的规则陈述