Лемма Огдена — результат, расширяющий утверждение леммы о разрастании для контекстно-свободных языков: если язык контекстно-свободен, то существует некоторое число (где может быть, а может и не быть длиной накачки), такое что для любой строки длины не меньше из и для любой «разметки» или более позиций в , может быть представлено в виде:
где , , , , и — строки, такие что: содержит по меньшей мере одну помеченную позицию, либо и и содержат помеченную позицию, либо её содержат и и , содержит не более отмеченных позиций, и принадлежит для любого .
Утверждение может использоваться для доказательства того, что данный язык не является контекстно-свободным в случаях, когда леммы о разрастании для контекстно-свободных языков недостаточно. Примером может быть язык . Также может применяться для доказательства существенной неоднозначности некоторых языков.
Если все позиции отмечены, утверждение эквивалентно лемме о разрастании для контекстно-свободных языков.
Литература
Категория:Теория формальных языков Огдена