Ardens hukmronligi - Ardens rule - Wikipedia

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

  1. ^ Daintith, Jon (2004). "Ardenning qoidasi". Arxivlandi asl nusxasidan 2010 yil 13 fevralda. Olingan 10 mart 2010.
  2. ^ 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.