跳至內容

鄂登引理

維基百科,自由的百科全書

形式語言理論中,Ogden引理提供了在上下文無關語言泵引理上靈活性的擴展。

Ogden 引理聲稱如果語言 L 是上下文無關的,則存在某個數 p > 0 (這裡的 p 可以是也可以不是抽吸長度),使得對於 L 中任何長度至少 p 字符串 w,和「標記」 p 或更多個 w 中的位置的所有方式,w 可以被寫為

w = uvxyz

帶有字符串 u, v, x, yz,使得 vy 有至少一個標記了的位置,vxy 有最多 p 個標記了的位置,而

L 中,對於所有

Ogden 引理可以在上下文無關語言泵引理不充分的情況下,被用來證明特定語言不是上下文無關的。一個例子是語言

觀察到在所有位置都被標記了的時候,這個引理等價於上下文無關語言的泵引理。

參見

[編輯]

引用

[編輯]