我知道要证明一种语言是非常规的，可以使用抽取引理 . 我想我理解它是如何工作的，但是当谈到表明无上下文语法（或不常规）时，我遇到了很大的问题 .
这是一个CFG的例子，我无法理解如何显示是常规（或非常规）：
i) S → NP VP
ii) NP → DET N
iii) VP → TV NP
iv) N → N N
v) N → A N
vi) NP → Mary |John
vii) DET → a |the |her |his
viii) TV → bought |loves |misses
ix) N → bike |jersey |mountain |sleeve |brake |
x) A → long |hydraulic |knitted |expensive |steep
我最初的猜测是，由于第四条规则，它不常规，但我不知道如何使用抽水引理来显示它 . 如果第四条规则被删除，那么它会不会是正规的？
所以，我的问题是：1 . 上述语法是否有规律？当试图表明这样的CFG是常规的还是非常规的时，有什么方法？ 2.如果移除了递归规则，那么它是否是常规的？
我希望有人能够提供一些有用的工具，当给出如上所述的CFG时，有人想表明它是否有规律 .
2 回答
这里的其他答案指出了我认为你可能会遗漏的细微差别 . 无上下文语法是一组描述语言的规则，但它本身不是一种语言 . 因此，询问无上下文语法是否规则并不是一个有意义的问题 - 就像询问所有自然数的集合是否可被17整除一样 .
另一方面，问题“这个CFG描述的语言是常用语言吗？”是一个有意义的问题，在这种情况下答案是肯定的 . 为了说明这一点，你需要弄清楚所描述的语言实际上是什么样的，然后可以为它构建DFA / NFA，为它编写正则表达式，或者为它编写常规语法 . 在这种特殊情况下，我们可以看到语法等同于以下正则表达式：
其中MJ，DET，A，N和TV是由您提供的无上下文语法中表示的列表给出的选项的缩写（MJ表示“Mary或John” . ）因为您可以为该语言编写正则表达式语法，你有什么
无上下文语法，
这不是常规语法，但是
描述了常规语言 .
想要指出有两点需要注意：
每个正则表达式（RE）也是一个CFG，但反过来却不正确（参见here） . 因此，除非您的提问者知道给定的CFG也是RE（由于问题的构建），否则很可能不是RE .
给定CFG是不可能的，如果它等于RE（不可解除的问题），请参阅here
把这给你的东西放在一起Am_I_Helpful的答案没有理论支持，不应该使用 .