Лемма Огдена

В теории формальных языков, лемма Огдена предоставляет расширение гибкости леммы о разрастании для контекстно-свободных языков.

Лемма Огдена утверждает, что если язык L контекстно-свободен, то существует некоторое число p > 0 (где p может быть, а может и не быть длиной накачки), такое что для любой строки w длины не меньше p из L и для любой «разметки» p или более позиций в w, w может быть представлено в виде

w = uvxyz

где u, v, x, y, и z — строки, такие что

1. x содержит по меньше мере одну помеченную позицию,
2. либо и u и v содержат помеченную позицию, либо её содержат и y и z,
3. vxy содержит не более p отмеченных позиций, и
4. uvⁱxyⁱz принадлежит L для любого i ≥ 0.

Лемма Огдена может использоваться для доказательства того, что данный язык не является контекстно-свободным, в случаях, когда леммы о разрастании для контекстно-свободных языков недостаточно. Примером может быть язык {aⁱb^jc^kd^l : i = 0 или j = k = l}. Она также полезна для доказательства существенной неоднозначности некоторых языков.

Заметим, что если все позиции отмечены, данная лемма эквивалентна лемме о накачке для контекстно-свободных языков.

См. также

• Лемма о разрастании для контекстно-свободных языков
• Лемма о разрастании

Эта страница в последний раз была отредактирована 23 ноября 2023 в 18:38.