Лемма Огденса - 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 n\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 n\geq 0}$.

Более того, либо каждый из u, v, w занимает выдающееся положение, или каждый из ${\displaystyle w,x,y}$ занимает выдающееся положение.

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

1. Бадер, Кристофер; Моура, Арнальдо (апрель 1982 г.). «Обобщение леммы Огдена». Прикладная математика и вычисления. 29 (2): 404–407. Дои:10.1145/322307.322315. S2CID  33988796.

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

• 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.