上下文无关语言 编辑
上下文无关语言是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于下推自动机所接受的语言的集合。
1
相关
在形式语言理论中，Ogden引理提供了在上下文无关语言的泵引理上灵活性的扩展。
在理论计算机科学中，帕里克定理指出，对于上下文无关语言，如果只关心其中每个上下文无关文法出现的次数，而不考虑它们的顺序，那么存在正则语言与其对应。这个定理可用于确定具有给定数量终止符号的字符串是否能为上下文无关语法接受。1961年罗希特·帕里克第一次证明了它，论文于1966年再次发表。
在形式语言理论中，Ogden引理提供了在上下文无关语言的泵引理上灵活性的扩展。