Лемма об обмене - Interchange lemma

Эта статья слишком полагается на Рекомендации к основные источники. Пожалуйста, улучшите это, добавив вторичные или третичные источники. (Март 2019 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

В нем говорится, что для каждого контекстно-свободного языка ${ displaystyle L}$ Существует ${ displaystyle c> 0}$ такой, что для всех ${ Displaystyle п geq м geq 2}$ для коллекции любой длины ${ displaystyle n}$ слова ${ Displaystyle R подмножество L}$ Существует ${ Displaystyle Z = {z_ {1}, ldots, z_ {k} } subset R}$ с ${ Displaystyle к geq | R | / (сп ^ {2})}$, и разложения ${ displaystyle z_ {i} = w_ {i} x_ {i} y_ {i}}$ так что каждый из ${ displaystyle | w_ {i} |}$, ${ displaystyle | x_ {i} |}$, ${ displaystyle | y_ {i} |}$ не зависит от ${ displaystyle i}$, более того, ${ Displaystyle m / 2 <| x_ {i} | leq m}$, и слова ${ displaystyle w_ {i} x_ {j} y_ {i}}$ находятся в ${ displaystyle L}$ для каждого ${ displaystyle i}$ и ${ displaystyle j}$.

Первым применением леммы об обмене было показать, что набор повторяющихся строк (т. Е. Строк формы ${ displaystyle xyyz}$ с ${ displaystyle | y |> 0}$) над алфавитом из трех или более символов не является контекстно-зависимым.

Смотрите также

• Лемма о накачке для регулярных языков

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

• Уильям Огден, Рокфорд Дж. Росс и Карл Винклманн (1982). «Лемма об обмене для контекстно-свободных языков». SIAM Журнал по вычислениям. 14 (2): 410–415. Дои:10.1137/0214031.CS1 maint: несколько имен: список авторов (связь)