Shen的书“算法和编程。问题和解决方案”。问题本身是由M. Sipser传达的。作者要求读者定义一个上下文无关文法,该文法生成以下语言: {X2Y | X ∈ {0, 1}*, Y ∈ {0, 1}*, X ≠ Y}。首先,我不能理解这样的语言怎么可能是上下文无关的(从我的新手的角度来看):X和Y可以是任何序列,但它们不能同时是一个序列。对我来说,这似乎是一个上下文</e
我对生成乔姆斯基所描述的上下文敏感语言的元素很感兴趣,正如Chomsky Classification of Grammars中“类型1语法”部分所描述的那样。(基本上,类似于标准的上下文无关语法,但允许在产生式规则的左侧使用多个符号,包括终端)。 我知道Prolog中的定从句语法,但我没有看到它们与乔姆斯基的上下文敏感语言之间