鄂登引理

维基百科,自由的百科全书
跳转至: 导航搜索

形式语言理论中,Ogden 引理提供了在上下文无关语言泵引理上灵活性的扩展。

Ogden 引理声称如果语言 L 是上下文无关的,则存在某个数 p > 0 (这里的 p 可以是也可以不是抽吸长度),使得对于 L 中任何长度至少 p 字符串 w,和“标记” p 或更多个 w 中的位置的所有方式,w 可以被写为

w = uvxyz

带有字符串 u, v, x, yz,使得 vy 有至少一个标记了的位置,vxy 有最多 p 个标记了的位置,而

uvixyizL 中,对于所有 i ≥ 0。

Ogden 引理可以在上下文无关语言泵引理不充分的情况下,被用来证明特定语言不是上下文无关的。一个例子是语言 {aibjckdl : i = 0 或 j = k = l}。

观察到在所有位置都被标记了的时候,这个引理等价于上下文无关语言的泵引理。

参见[编辑]

引用[编辑]

  • Ogden, W. A helpful result for proving inherent ambiguity. Mathematical Systems Theory. 1968, 2: 191–194. 
  • Hopcroft, Motwani and Ullman. Automata Theory, Languages, and Computation. Adison Wesley. 1979.