Лемма Огденса - Википедия - Ogdens lemma

В теории формальные языки, Лемма Огдена (названный в честь Уильям Ф. Огден ) является обобщением лемма о прокачке для контекстно-свободных языков.

Заявление

Лемма Огдена утверждает, что если язык L не зависит от контекста, то существует некоторое число ${ displaystyle p geq 1}$ (куда п может быть или не быть длиной накачки), так что для любой струны s длины не менее п в L и всяческие способы "маркировки" п или более позиций в s, s можно записать как

${ displaystyle s = uvwxy}$

со струнами у, в, ш, х, и у, так что

1. vx имеет хотя бы одну отмеченную позицию,
2. vwx имеет самое большее п отмеченные позиции, и
3. ${ displaystyle uv ^ {n} wx ^ {n} y in L}$ для всех ${ Displaystyle п geq 0}$.

В частном случае, когда каждая позиция отмечена, лемма Огдена эквивалентна лемме о прокачке для контекстно-свободных языков. Лемму Огдена можно использовать, чтобы показать, что некоторые языки не являются контекстно-свободными в случаях, когда леммы о накачке недостаточно. Примером является язык ${ displaystyle {a ^ {i} b ^ {j} c ^ {k} d ^ {l}: i = 0 { text {or}} j = k = l }}$Лемму Огдена можно также использовать для доказательства присущая двусмысленность некоторых языков.^{[нужна цитата ]}

Обобщенное состояние

Бадер и Моура обобщили лемму^[1] чтобы можно было отметить некоторые позиции, которые нет быть включенным в vx. Их зависимость параметров позже была улучшена Дёмёси и Кудлеком. Если обозначить количество таких не входит позиции по е, то число d из выдающийся позиции, некоторые из которых мы хотим включить в vx должен удовлетворить ${ displaystyle d geq p (e + 1)}$, куда п - некоторая константа, которая зависит только от языка. Утверждение становится, что каждый s можно записать как

${ displaystyle s = uvwxy}$

со струнами у, в, ш, х, и у, так что

1. vx имеет хотя бы одну выдающуюся позицию и не имеет исключенных позиций,
2. vwx имеет самое большее ${ displaystyle p ^ {(e + 1)}}$ выдающиеся должности и
3. ${ displaystyle uv ^ {n} wx ^ {n} y in L}$ для всех ${ Displaystyle п geq 0}$.

Более того, либо каждый из u, v, w занимает выдающееся положение, или каждый из ${ Displaystyle ш, х, у}$ занимает выдающееся положение.

Рекомендации

дальнейшее чтение

• Dömösi, P .; Кудлек, М. (1999). «Сильные итерационные леммы для регулярных, линейных, контекстно-свободных и линейно индексированных языков». FCT'99, LNCS. Конспект лекций по информатике. 1684: 226–233. Дои:10.1007/3-540-48321-7_18. ISBN  978-3-540-66412-3.
• Огден, В. (1968). «Полезный результат для доказательства врожденной двусмысленности». Математическая теория систем. 2 (3): 191–194. Дои:10.1007 / BF01694004. S2CID  13197551.
• Хопкрофт; Мотвани; Ульман (1979). Теория автоматов, языки и вычисления. Эддисон-Уэсли. ISBN  81-7808-347-7.