WikiDer > Ardens qoidasi - Vikipediya
 | Bu maqola uchun qo'shimcha iqtiboslar kerak tekshirish. (2010 yil mart) (Ushbu shablon xabarini qanday va qachon olib tashlashni bilib oling) |
Yilda nazariy informatika, Ardenning qoidasi, shuningdek, nomi bilan tanilgan Arden lemmasi, ning ma'lum bir shakli haqidagi matematik bayon til tenglamalari.
Fon
A (rasmiy) til shunchaki torlar to'plamidir. Bunday to'plamlar ba'zilari yordamida aniqlanishi mumkin til tenglamasi, bu esa o'z navbatida tillardagi operatsiyalarga asoslanadi. Til tenglamalari - bu sonli tenglamalarga o'xshash matematik bayonotlar, ammo o'zgaruvchilar raqamlarga emas, balki rasmiy tillarning qiymatlariga ega. Ikki tilda eng keng tarqalgan operatsiyalar orasida A va B ular birlashma o'rnatish A ∪ Bva ularning birlashtirish A⋅B. Va nihoyat, bitta operatsiya sifatida operand, to'plam A* belgisini bildiradi Kleene yulduzi tilning A.
Arden hukmronligi to'g'risidagi bayonot
Arden qoidasida to'plam deyilgan A*⋅B uchun eng kichik til X ichida chiziqli tenglama X = A⋅X ∪ B qayerda X, A, B qatorlar to'plamidir. Bundan tashqari, agar to'plam bo'lsa A bo'sh so'zni o'z ichiga olmaydi, unda bu echim noyobdir.[1][2]
Bunga teng ravishda, to'plam B⋅A* uchun eng kichik til X yilda X = X⋅A ∪ B.
Ilova
Arden qoidasi ba'zi bir cheklangan avtomatlarni odatdagi ifodalarga o'zgartirishga yordam berish uchun ishlatilishi mumkin Klaynning algoritmi.
Shuningdek qarang
Izohlar
- ^ Daintith, Jon (2004). "Ardenning qoidasi". Arxivlandi asl nusxasidan 2010 yil 13 fevralda. Olingan 10 mart 2010.
- ^ Satner, Klaus. "Oddiy tillar algebrasi" (PDF). Arxivlandi asl nusxasi (PDF) 2011-07-08 da. Olingan 15 fevral 2011.
Adabiyotlar
- Arden, D. N. (1960). Kechiktirilgan mantiqiy va cheklangan davlat mashinalari, Hisoblash mashinalari dizayni nazariyasi, 1-35 betlar, Michigan Press universiteti, Ann Arbor, Michigan, AQSh.
- Dekan N. Arden (1961 yil oktyabr). "Kechiktirilgan mantiqiy va cheklangan davlat mashinalari". Proc. 2-Ann. Simp. Kommutatsiya davri nazariyasi va mantiqiy dizayni (SWCT) to'g'risida, Detroyt / MI. (ochiq kirish referati)
- John E. Hopcroft va Jeffrey D. Ullman, Avtomatika nazariyasi, tillar va hisoblash bilan tanishish, Addison-Uesli nashriyoti, Massachusets shtatidagi Reading, 1979 y. ISBN 0-201-02988-X. 2-bob: Cheklangan avtomatlar va doimiy ifodalar, 54-bet.