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

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

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

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

См. также

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

Ссылки

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