Лемма о перестановке

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

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

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