Naqsh tili (rasmiy tillar) - Pattern language (formal languages)

Yilda nazariy informatika, a naqsh tili a rasmiy til bu barcha aniq misollar to'plami sifatida aniqlanishi mumkin mag'lubiyat konstantalar va o'zgaruvchilar. Naqshiy tillar tomonidan kiritilgan Dana Angluin kontekstida mashinada o'rganish.^[1]

Ta'rif

Ning cheklangan to'plami berilgan doimiy belgilar va hisoblanadigan to'plam X ning o'zgaruvchan symbols, a dan ajratilgan belgilar naqsh cheklangan bo'sh emas mag'lubiyat Σ∪ dan belgilarX.The uzunlik naqshning p, | bilan belgilanadip|, faqat uning belgilarining soni. To'liq o'z ichiga olgan barcha naqshlar to'plami n aniq o'zgaruvchilar (ularning har biri bir necha marta sodir bo'lishi mumkin) bilan belgilanadi P_n, barcha naqshlarning to'plami P_*.A almashtirish xaritalashdir f: P_* → P_* shu kabi^{[eslatma 1]}

f a homomorfizm munosabat bilan torli birikma (⋅), rasmiy ravishda: ∀p,q∈P_*. f(p⋅q) = f(p)⋅f(q);
f o'chirilmaydi, rasmiy ravishda: ∀p∈P_*. f(p) ≠ ε, bu erda ε ni bildiradi bo'sh satr; va
f barqarorlarni hurmat qiladi, rasmiy ravishda: ∀s∈Σ. f(s) = s.

Agar p = f(q) ba'zi naqshlar uchun p, q ∈ P_* va ba'zi bir almashtirish f, keyin p deb aytilgan kamroq umumiy q, yozilgan p≤q; u holda, albatta |p| ≥ |q| naqsh uchun p, uning til rasmiy ravishda faqat doimiylardan tuzilgan kamroq umumiy naqshlarning to'plami sifatida aniqlanadi: L(p) = { s ∈ Σ⁺ : s ≤ p }, qaerda Σ⁺ $ Delta $ dan barcha sonli bo'sh bo'lmagan satrlar to'plamini bildiradi.

Masalan, Σ = {0, 1} sobit va o'zgaruvchilardan foydalanish X = { x, y, z, ...}, naqsh 0x10xx1 ∈P₁ va xxy ∈P₂ mos ravishda 7 va 3 uzunliklarga ega, avvalgi naqsh namunasi 00 ga tengz100z0z1 va 01z101z1z1, bu xaritani almashtirish bilan olinadi x 0 gaz va 1 gaznavbati bilan va bir-birining o'zi uchun ramz. Ikkalasi ham 00z100z0z1 va 01z101z1z1-ning misollari xxy. Aslini olib qaraganda, L(0x10xx1) ning pastki qismidir L(xxy). Naqsh tili x0 va x1 - juft va toqni bildiruvchi barcha bit qatorlarining to'plami ikkilik raqam navbati bilan. Tili xx bit qatorini o'zi bilan birlashtirish orqali olinadigan barcha satrlar to'plami, masalan. 00, 11, 0101, 1010, 11101110 ∈ L(xx).

Xususiyatlari

NP-ning namunaviy tilga a'zoligi, tomonidan kamaytirish dan To'liq emas 1-in-3-SAT muammosi: Berilgan a CNF ning m bilan bandlar n o'zgaruvchilar, 3 uzunlikdagi naqshn+4m+1 bilan 2n o'zgaruvchilar va uzunlik qatori 4n + 5m+1 ko'rsatilgandek tuzilishi mumkin (m= 3 va n= 4 misolda). Naqshdagi katta harflar o'zgaruvchisi CNFdagi inkor qilingan o'zgaruvchilarga mos keladi. Satr naqshga mos keladi, agar faqat bitta topshiriq bo'lsa, har bir bandda bitta bittadan harf 1 bo'lsa ("to'g'ri"CNFda). Chap qismda, masalan." 0wW0 "faqat bitta bo'lsa," 01110 "bilan mos keladi w,V "1" bilan mos keladi (mos keladigan "yolg'on") va boshqasi" 11 "bilan (" mos keladigan "to'g'ri"), ya'ni w ning inkoriga mos keladi V. O'ng qismda, masalan. "0xYZ0 ", agar aynan bittasi bo'lsa," 011110 "bilan mos keladi x,Y,Z "11" bilan, boshqalari esa "1" bilan mos keladi, ya'ni aynan bittasi "to'g'ri".

Yo'qligini hal qilish muammosi s ∈ L(p) ixtiyoriy mag'lubiyat uchun s ∈ Σ⁺ va naqsh p bu To'liq emas (rasmga qarang) va shuning uchun qaror qabul qilish muammosi p ≤ q o'zboshimchalik naqshlari uchun p, q.^[2]

Naqshli tillarning sinfi yopiq emas ostida ...

birlashma: masalan. ph = {0,1} uchun yuqorida, L(01)∪L(10) naqsh tili emas;
to‘ldiruvchi: Σ⁺ \ L(0) naqsh tili emas;
kesishma: L(x0y)∩L(x1y) naqsh tili emas;
Kleene plus: L(0)⁺ naqsh tili emas;
homomorfizm: f(L(x)) = L(0)⁺ faraz qilsak, naqsh tili emas f(0) = 0 = f(1);
teskari gomomorfizm: f⁻¹(111) = {01, 10, 000}, taxmin qilsak, naqsh tili emas f(0) = 1 va f(1) = 11.

Naqsh tillarining sinfi yopiq ostida ...

birlashma: L(p)⋅L(q) = L(p⋅q);
bekor qilish: L(p)^rev = L(p^rev).^[3]

Agar p, q ∈ P₁ aniq bir o'zgaruvchini o'z ichiga olgan naqshlar, keyin p ≤ q agar va faqat agar L(p) ⊆ L(qXuddi shu tenglik teng uzunlikdagi naqshlar uchun ham amal qiladi.^[4]Turli uzunlikdagi naqshlar uchun yuqorida misol p = 0x10xx1 va q = xxy buni ko'rsatadi L(p) ⊆ L(q) nazarda tutmasdan ushlab turishi mumkin p ≤ q.Shunga qaramay, har qanday ikkita naqsh p va q, o'zboshimchalik uzunliklarida, agar ular o'zgaruvchan o'zgaruvchan nomlanishiga teng bo'lsa, xuddi shu tilni yarating.^[5]Har bir naqsh p a umumiy umumlashtirish uning yaratilgan tilidagi barcha satrlarni L(p), (⋅) ning modulli assotsiatsiyasi.

Xomskiy ierarxiyasida joylashish

Qayta qilingan Xomskiy ierarxiyasi, naqsh tillari sinfi singletonning tegishli superklassi va subklassidir^[2-eslatma] va indekslangan tillar navbati bilan, lekin orasidagi til darslari bilan taqqoslanmaydi; ikkinchisidan kelib chiqib, naqsh tili klassi jadvalda aniq ko'rsatilmagan quyida.

Naqshiy tillar sinfi bilan sinfini taqqoslash mumkin emas cheklangan tillar, sinf bilan oddiy tillar va sinf bilan kontekstsiz tillar:

naqsh tili L(xx) kontekstsiz emas (shuning uchun ham emas) muntazam na cheklangan ) tufayli nasosli lemma;
cheklangan (shuning uchun ham odatiy va kontekstsiz) til {01, 10} naqsh tili emas.

Har bir singleton tili ahamiyatsiz naqsh tili bo'lib, o'zgaruvchisiz naqsh bilan hosil qilingan.

Har bir naqsh tili tomonidan ishlab chiqarilishi mumkin indekslangan grammatika: Masalan, Σ = {dan foydalanish a, b, v } va X = { x, y }, naqsh a x b y v x a y b noaniq belgilar bilan grammatika asosida hosil bo'ladi N = { S_x, S_y, S } ∪ X, terminal belgilari T = Σ, indeks belgilari F = { a_x, b_x, v_x, a_y, b_y, v_y }, boshlanish belgisi S_xva quyidagi ishlab chiqarish qoidalari:

S_x[σ]	→ S_x[a_x σ]	\| S_x[b_x σ]	\| S_x[v_x σ]	\| S_y[σ]
S_y[σ]	→ S_y[a_y σ]	\| S_y[b_y σ]	\| S_y[v_y σ]	\| S[σ]
S[σ]	→ a x[σ] b y[σ] v x[σ] a y[σ] b

x[a_x σ]	→ a	x[σ]	y[a_x σ]	→	y[σ]
x[b_x σ]	→ b	x[σ]	y[b_x σ]	→	y[σ]
x[v_x σ]	→ v	x[σ]	y[v_x σ]	→	y[σ]
x[a_y σ]	→	x[σ]	y[a_y σ]	→ a	y[σ]
x[b_y σ]	→	x[σ]	y[b_y σ]	→ b	y[σ]
x[v_y σ]	→	x[σ]	y[v_y σ]	→ v	y[σ]
x[]	→ ε		y[]	→ ε

Hosil bo'lishga misol:

S_x[] ⇒ S_x[b_x] ⇒ S_x[a_x b_x] ⇒ S_y[a_x b_x] ⇒ S_y[v_y a_x b_x] ⇒ S[v_y a_x b_x] ⇒ a x[v_y a_x b_x] b y[v_y a_x b_x] v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ a x[a_x b_x] b y[v_y a_x b_x] v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ a a x[b_x] b y[v_y a_x b_x] v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ a ab x[] b y[v_y a_x b_x] v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ a ab b y[v_y a_x b_x] v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ ... ⇒ a ab b v y[] v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ a ab b v v x[v_y a_x b_x] a y[v_y a_x b_x] b ⇒ ... ⇒ a ab b v v ab x[] a y[v_y a_x b_x] b ⇒ a ab b v v ab a y[v_y a_x b_x] b ⇒ ... ⇒ a ab b v v ab a v y[] b ⇒ a ab b v v ab a v b

Xuddi shu tarzda, indeks grammatikasini har qanday naqsh asosida tuzish mumkin.

O'rganish naqshlari

Namuna to'plami berilgan S torlar, naqsh p deyiladi tavsiflovchi ning S agar S ⊆ L(p), lekin emas S ⊆ L(q) ⊂ L(p) har qanday boshqa naqsh uchun q.

Har qanday namuna to'plami berilgan S, uchun tavsiflovchi naqsh S tomonidan hisoblash mumkin

eng qisqa satrdan uzun bo'lmagan barcha naqshlarni (o'zgaruvchan nomini o'zgartirishga qadar) sanab chiqish S,
ulardan yuqori to'plamni hosil qiladigan naqshlarni tanlash S,
ulardan maksimal uzunlikdagi naqshlarni tanlash va
ulardan ≤ ga nisbatan minimal bo'lgan naqshni tanlash.^[6]

Ushbu algoritm asosida naqsh tillari klassi bo'lishi mumkin limitda belgilangan ijobiy misollardan.^[7]

Izohlar

^ Angluinning almashtirish tushunchasi odatdagi tushunchadan farq qiladi mag'lubiyatni almashtirish.
^ ya'ni bitta qatordan iborat tillar; ular mos keladi to'g'ri chiziqli grammatikalar

Adabiyotlar

^ Dana Angluin (1980). "Bir qator torlarga xos naqshlarni topish". Kompyuter va tizim fanlari jurnali. 21: 46–62. doi:10.1016/0022-0000(80)90041-0.
^ Teorema 3.6, p.50; Xulosa 3.7, s.52
^ Teorema 3.10, s.53
^ Lemma 3.9, s.52; Xulosa 3.4, p.50
^ Teorema 3.5, p.50
^ 4.1-teorema, 53-bet
^ Dana Angluin (1980). "Ijobiy ma'lumotlardan rasmiy tillarning induktiv xulosasi" (PDF). Axborot va boshqarish. 45 (2): 117–135. doi:10.1016 / s0019-9958 (80) 90285-5.; bu erda: 1-misol, 125-bet

[2] Angluinning almashtirish tushunchasi odatdagi tushunchadan farq qiladi mag'lubiyatni almashtirish.

[7] ya'ni bitta qatordan iborat tillar; ular mos keladi to'g'ri chiziqli grammatikalar

[1] Dana Angluin (1980). "Bir qator torlarga xos naqshlarni topish". Kompyuter va tizim fanlari jurnali. 21: 46–62. doi:10.1016/0022-0000(80)90041-0.

[3] Teorema 3.6, p.50; Xulosa 3.7, s.52

[4] Teorema 3.10, s.53

[5] Lemma 3.9, s.52; Xulosa 3.4, p.50

[6] Teorema 3.5, p.50

[8] 4.1-teorema, 53-bet

[9] Dana Angluin (1980). "Ijobiy ma'lumotlardan rasmiy tillarning induktiv xulosasi" (PDF). Axborot va boshqarish. 45 (2): 117–135. doi:10.1016 / s0019-9958 (80) 90285-5.; bu erda: 1-misol, 125-bet

[1]

[eslatma 1]

[2]

[3]

[4]

[5]

[2-eslatma]

[6]

[7]