O'zaro almashinuvchi lemma - Interchange lemma

Bu maqola juda ko'p narsalarga tayanadi ma'lumotnomalar ga asosiy manbalar. Iltimos, buni qo'shib yaxshilang ikkilamchi yoki uchinchi darajali manbalar. (2019 yil mart) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling)

Nazariyasida rasmiy tillar, almashish lemmasi til bo'lishi uchun zarur shartni bayon qiladi kontekstsiz, xuddi shunga o'xshash kontekstsiz tillar uchun lemma nasoslari.

Unda har bir kontekstsiz til uchun aytilgan ${ displaystyle L}$ bor ${ displaystyle c> 0}$ hamma uchun shunday ${ displaystyle n geq m geq 2}$ har qanday uzunlik to'plami uchun ${ displaystyle n}$ so'zlar ${ displaystyle R subset L}$ bor ${ displaystyle Z = {z_ {1}, ldots, z_ {k} } kichik guruh R}$ bilan ${ displaystyle k geq | R | / (cn ^ {2})}$va parchalanish ${ displaystyle z_ {i} = w_ {i} x_ {i} y_ {i}}$ shunday qilib har biri ${ displaystyle | w_ {i} |}$, ${ displaystyle | x_ {i} |}$, ${ displaystyle | y_ {i} |}$ dan mustaqildir ${ displaystyle i}$, bundan tashqari, ${ displaystyle m / 2 <| x_ {i} | leq m}$va so'zlar ${ displaystyle w_ {i} x_ {j} y_ {i}}$ ichida ${ displaystyle L}$ har bir kishi uchun ${ displaystyle i}$ va ${ displaystyle j}$.

O'zaro almashish lemmasining birinchi qo'llanilishi takrorlanadigan satrlar to'plamini (ya'ni shaklning satrlarini) ko'rsatish edi. ${ displaystyle xyyz}$ bilan ${ displaystyle | y |> 0}$) uchta yoki undan ortiq belgidan iborat alifbo ustida kontekst mavjud emas.

Shuningdek qarang

• Oddiy tillar uchun nasosli lemma

Adabiyotlar

• Uilyam Ogden, Rokford J. Ross va Karl Vinklmann (1982). "Kontekstsiz tillar uchun" almashinuv lemmasi "". Hisoblash bo'yicha SIAM jurnali. 14 (2): 410–415. doi:10.1137/0214031.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)