Kontekstsiz tillar uchun lemma nasoslari - Pumping lemma for context-free languages

Yilda Kompyuter fanlari, xususan rasmiy til nazariyasi, nasosli lemma kontekstsiz tillar uchun, deb ham tanilgan Bar-Xill^{[tushuntirish kerak ]} lemma, a lemma bu hammaga umumiy mulkni beradi kontekstsiz tillar va umumlashtiradi oddiy tillar uchun nasosli lemma.

Nasosli lemma a qurish uchun ishlatilishi mumkin ziddiyat bilan isbot ma'lum bir til emas kontekstsiz. Aksincha, nasosli lemma tilni kafolatlash uchun etarli emas bu kontekstsiz; kabi boshqa zarur shart-sharoitlar mavjud Ogden lemmasi yoki O'zaro almashinuvchi lemma.

Rasmiy bayonot

Isbotlangan fikr: Agar ${ displaystyle s}$ etarlicha uzun, uning hosil qilish daraxti w.r.t. a Xomskiy normal shakli grammatika bir nechtasini o'z ichiga olishi kerak nonterminal ${ displaystyle N}$ ba'zilarida ikki marta daraxt yo'li (yuqori rasm). Takrorlash ${ displaystyle n}$ hosila qismi marta ${ displaystyle N}$ ⇒...⇒ ${ displaystyle vNx}$ uchun lotin hosil qiladi ${ displaystyle uv ^ {n} wx ^ {n} y}$ (pastki chap va o'ng rasm uchun ${ displaystyle n = 0}$ va ${ displaystyle 2}$navbati bilan).

Agar til bo'lsa ${ displaystyle L}$ kontekstsiz, keyin bir nechta butun son mavjud ${ displaystyle p geq 1}$ ("nasos uzunligi" deb nomlangan^[1]) har qanday mag'lubiyat ${ displaystyle s}$ yilda ${ displaystyle L}$ bu bor uzunlik ning ${ displaystyle p}$ yoki undan ko'p belgilar (ya'ni bilan ${ displaystyle | s | geq p}$) deb yozish mumkin

${ displaystyle s = uvwxy}$

bilan pastki chiziqlar ${ displaystyle u, v, w, x}$ va ${ displaystyle y}$, shu kabi

1. ${ displaystyle | vx | geq 1}$,

2. ${ displaystyle | vwx | leq p}$va

3. ${ displaystyle uv ^ {n} wx ^ {n} y in L}$ Barcha uchun ${ displaystyle n geq 0}$.

Quyida nasos lemmasining rasmiy ifodasi keltirilgan.

${ displaystyle { begin {array} {l} ( forall L subseteq Sigma ^ {*}) quad ({ mbox {context free}} (L) Rightarrow quad (( mavjud $ p geq 1) (( forall s in L) ((| s | geq p) Rightarrow quad (( u, v, w, x, y in Sigma ^ {* mavjud) }) (s = uvwxy land | vx | geq 1 land | vwx | leq p land ( forall n geq 0) (uv ^ {n} wx ^ {n} y in L))) )))) end {qator {}}}$

Norasmiy bayonot va tushuntirish

Kontekstsiz tillar uchun nasosli lemma (ushbu maqolaning qolgan qismida shunchaki "nasosli lemma" deb nomlanadi) barcha kontekstsiz tillarga ega bo'lish xususiyatini tavsiflaydi.

Xususiyat - bu tilda hech bo'lmaganda uzunlikdagi barcha satrlarning xususiyati ${ displaystyle p}$, qayerda ${ displaystyle p}$ doimiy - deb ataladi nasos uzunligi- bu kontekstsiz tillar o'rtasida farq qiladi.

Demoq ${ displaystyle s}$ hech bo'lmaganda uzunlikdagi ip ${ displaystyle p}$ bu tilda.

Nasosli lemma buni ta'kidlaydi ${ displaystyle s}$ beshta qatorga bo'linishi mumkin, ${ displaystyle s = uvwxy}$, qayerda ${ displaystyle vx}$ bo'sh emas va uzunligi ${ displaystyle vwx}$ ko'pi bilan ${ displaystyle p}$, shunday qilib takrorlash ${ displaystyle v}$ va ${ displaystyle x}$ bir xil sonda (${ displaystyle n}$) ichida ${ displaystyle s}$ hanuzgacha tilda saqlanib kelayotgan qatorni hosil qiladi. Ko'pincha nol marta takrorlash foydalidir, bu esa olib tashlanadi ${ displaystyle v}$ va ${ displaystyle x}$ ipdan. Qo'shimcha nusxalarini ushbu "nasos" jarayoni ${ displaystyle v}$ va ${ displaystyle x}$ nasos lemmasiga uning nomini beradigan narsa.

Cheklangan tillar (ular odatiy va shu sababli kontekstsiz) ega bo'lish orqali nasos lemmasiga ahamiyatsiz bo'ysunadi ${ displaystyle p}$ mag'lubiyatning maksimal uzunligiga teng ${ displaystyle L}$ ortiqcha bitta. Bunday uzunlikdagi iplar bo'lmaganligi sababli nasos lemmasi buzilmaydi.

Lemmadan foydalanish

Nasosli lemma ko'pincha ma'lum bir tilni isbotlash uchun ishlatiladi L o'zboshimchalik bilan uzun satrlarni ko'rsatib, kontekstsizdir s ichida L tashqarida iplar hosil qilmasdan "pompalanishi" mumkin emas L.

Masalan, til ${ displaystyle L = {a ^ {n} b ^ {n} c ^ {n} | n> 0 }}$ a-dagi nasosli lemma yordamida kontekstsiz ekanligini ko'rsatish mumkin ziddiyat bilan isbot. Birinchidan, buni taxmin qiling L kontekstdan xoli. Nasosli lemma bo'yicha butun son mavjud p bu tilning pompalanadigan uzunligi L. Ipni ko'rib chiqing ${ displaystyle s = a ^ {p} b ^ {p} c ^ {p}}$ yilda L. Nasosli lemma bizga buni aytadi s shaklida yozilishi mumkin ${ displaystyle s = uvwxy}$, qayerda u, v, w, xva y pastki chiziqlar, shunday qilib ${ displaystyle | vx | geq 1}$, ${ displaystyle | vwx | leq p}$va ${ displaystyle uv ^ {i} wx ^ {i} y in L}$ har bir butun son uchun ${ displaystyle i geq 0}$. Tanlash bo'yicha s va haqiqat ${ displaystyle | vwx | leq p}$, substring ekanligini osongina ko'rish mumkin vwx ikkitadan ko'p bo'lmagan belgilarni o'z ichiga olishi mumkin. Ya'ni, biz uchun beshta imkoniyatdan biri mavjud vwx:

1. ${ displaystyle vwx = a ^ {j}}$ kimdir uchun ${ displaystyle j leq p}$.
2. ${ displaystyle vwx = a ^ {j} b ^ {k}}$ kimdir uchun j va k bilan ${ displaystyle j + k leq p}$
3. ${ displaystyle vwx = b ^ {j}}$ kimdir uchun ${ displaystyle j leq p}$.
4. ${ displaystyle vwx = b ^ {j} c ^ {k}}$ kimdir uchun j va k bilan ${ displaystyle j + k leq p}$.
5. ${ displaystyle vwx = c ^ {j}}$ kimdir uchun ${ displaystyle j leq p}$.

Har bir holat uchun bu osonlikcha tasdiqlanadi ${ displaystyle uv ^ {i} wx ^ {i} y}$ har bir harf uchun teng raqamlarni o'z ichiga olmaydi ${ displaystyle i neq 1}$. Shunday qilib, ${ displaystyle uv ^ {2} wx ^ {2} y}$ shaklga ega emas ${ displaystyle a ^ {i} b ^ {i} c ^ {i}}$. Bu ta'rifiga zid keladi L. Shuning uchun bizning dastlabki taxminimiz L if kontekst bepul bo'lishi kerak.

Nasosli lemma ko'pincha ma'lum bir tilning kontekstsiz emasligini isbotlash uchun foydali vosita bo'lsa-da, kontekstsiz tillarning to'liq tavsifini bermaydi. Agar til nasos beruvchi lemma bergan shartni qondirmasa, biz uning kontekstsiz emasligini aniqladik.

Boshqa tomondan, kontekstsiz bo'lmagan, ammo shunga qaramay nasosli lemma bergan shartni qondiradigan tillar mavjud.

${ displaystyle L = {b ^ {j} c ^ {k} d ^ {l} | j, k, l in mathbb {N} } cup {a ^ {i} b ^ {j } c ^ {j} d ^ {j} | i, j in mathbb {N}, i geq 1 }}$

uchun s=b^jv^kd^l masalan. j≥1 ni tanlang vwx faqat iborat bo'lish bNing, uchun s=a^menb^jv^jd^j tanlang vwx faqat iborat bo'lish aNing; ikkala holatda ham barcha nasosli simlar hanuzgacha mavjud L.^[2]

Buni isbotlash uchun 1960 yilda Scheinberg tomonidan nasos lemmasining kashfiyotchisi ishlatilgan ${ displaystyle L = {a ^ {n} b ^ {n} a ^ {n} | n> 0 }}$ kontekstsiz emas.^[3]

Adabiyotlar

• Bar-Xill, Y.; Micha Perles; Eli Shamir (1961). "Oddiy ibora-tuzilish grammatikalarining rasmiy xususiyatlari to'g'risida". Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung. 14 (2): 143–172. - Qayta nashr etilgan: Y. Bar-Xill (1964). Til va ma'lumotlar: ularning nazariyasi va qo'llanilishi bo'yicha tanlangan insholar. Mantiqan Adisson-Uesli seriyasi. Addison-Uesli. 116-150 betlar. ISBN  0201003732. OCLC  783543642.
• Maykl Sipser (1997). Hisoblash nazariyasiga kirish. PWS nashriyoti. ISBN  0-534-94728-X. 1.4 bo'lim: Noto'g'ri tillar, 77-83 betlar. 2.3-bo'lim: Kontekstsiz tillar, 115–119 betlar.