显示语言是上下文无关的

我被要求证明ABA^R形式的歌曲集是上下文无关的（其中A^R是A颠倒的）。我不知道如何显示一种语言无上下文。显示语言是上下文无关的

我们还没有专门研究如何显示一种语言是上下文无关的，所以它不能太复杂。我能想到的唯一的事情就是为语言创建一个上下文无关的语法，但我不知道这足以证明它没有上下文，或者我如何为一组歌曲创建语法。

2014-09-26 Þór Óðinsson

这里有一个答案︰http://stackoverflow.com/questions/3510109/how-can-i-determine-if-a-language-is-context-free- or-not另外请注意，创建上下文无关语法对于显示语言无上下文是很好的。 – 2014-09-26 04:21:47

您不能使用抽象引理来显示语言无上下文。它只能用来表明它不是。有满足抽象引理的非上下文无关语言。 – 2014-09-26 04:23:13

A和B是一组字符串还是什么？ – 2014-09-26 04:24:38

假设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'

来源

2014-09-26 04:35:01

在从你的S中获得一个句子（“歌曲”）时，S_A'不会被限制为派生一个与S_A派生出来的相反的短语，我认为原始问题需要什么。 – 2014-09-26 17:21:08

@MichaelDyck S_A从A派生字符串，S_A'从A^R派生字符串。这两个字符串可能不是彼此相反，这是故意的。这是OP要求的。如果这些应该是彼此相反的（我认为你是这样想的），那么问题应该被问为L = {xyx^R | x \ in A和y \ in B} – 2014-09-26 19:48:55

显示语言是上下文无关的

回答

相关问题