P S*_*ved 27
首先,您应该尝试构建一个无上下文的语法,形成主语言.如果所有产品的左侧都包含一个非终端符号,则语法是无上下文的.根据定义,如果存在,那么语言是无上下文的.
等效构造将是下推自动机.它与DFA相同,但可以使用堆栈.它可能比语法更容易构建.
但是,如果您未能构建语法或自动机,则并不意味着语言不是无上下文的; 也许,它只是你谁也不能建立足够的棘手语法(例如,我曾经花了大约7小时搭建一个棘手的语言语法).
如果您开始怀疑该语言是否是无上下文的,那么您应该使用所谓的"为无上下文语言提供引理".它描述的属性所有上下文无关语言,如果你的语言违反了它,那么它绝对不是上下文无关的(见使用说明在维基百科).
这个引理是奥格登引理的必然结果.所以奥格登的是更强大的,如果你无法应用泵引理,你可以尝试奥格登(它的使用方法相同).