オグデンの補題

オグデンの補題（英: Ogden's lemma）とは、形式言語の理論において、文脈自由言語の反復補題の柔軟性を拡張したものである。
具体的には次の通りである。言語 "L" が文脈自由であるとき、ある正の数 "p" が存在し（"p" は反復長とは限らない）、"L" における "p" 以上の長さの任意の文字列 "w" について、"w" 上の "p" 個以上の位置（文字）をマークする全ての組合せを考える。"w" は次のように表される。
ここで、"u", "v", "x", "y", "z" という文字列について、"vy" が少なくとも1つのマークされた位置を含み（すなわち "|vy|" > 0）、"vxy" には最大でも "p" 個のマークされた位置があるとする。すると
オグデンの補題は、文脈自由言語の反復補題では示せない場合でも、特定の言語が文脈自由でないことを示すことができる。例えば、言語 {"aibjckdl" : "i" = 0 or "j" = "k" = "l"} がそのような言語である。
全位置（文字）がマークされるとき、この補題は文脈自由言語の反復補題と等価になる。