Kleenes algoritmi - Kleenes algorithm - Wikipedia

Yilda nazariy informatika, xususan rasmiy til nazariyasi, Klaynning algoritmi berilganni o'zgartiradi nondeterministik cheklangan avtomat (NFA) ga a doimiy ifoda. Boshqa konvertatsiya algoritmlari bilan birgalikda u bir nechta tavsiflash formatlarining ekvivalentligini o'rnatadi oddiy tillar. Xuddi shu usulning alternativ prezentatsiyalariga tegishli bo'lgan "yo'q qilish usuli" kiradi Brzozovskiy va Makkluski, ning algoritmi McNaughton va Yamada,^[1] va foydalanish Arden lemmasi.

Algoritm tavsifi

Gross va Yellen (2004) ma'lumotlariga ko'ra,^[2] algoritmni orqaga qaytarish mumkin Kleen (1956).^[3] Holda algoritm taqdimoti aniqlangan cheklangan avtomatlar (DFAs) Hopcroft va Ullman (1979) da berilgan.^[4] Quyida NFA uchun algoritm taqdimoti Gross va Yellen (2004) dan keyin keltirilgan.^[2]

Berilgan nondeterministik cheklangan avtomat M = (Q, Σ, δ, q₀, F) bilan Q = { q₀,...,q_n } uning to'plami davlatlar, algoritm hisoblaydi

to'plamlar R^k
_ij oladigan barcha satrlarning M shtatdan q_men ga q_j dan yuqori raqamlangan har qanday davlatdan o'tmasdan k.

Bu erda "holatdan o'tish" kirish degan ma'noni anglatadi va uni tark etish, shuning uchun ham men va j dan yuqori bo'lishi mumkin k, lekin hech qanday oraliq holat bo'lishi mumkin emas.Har bir to'plam R^k
_ij doimiy ibora bilan ifodalanadi; algoritm ularni bosqichma-bosqich hisoblab chiqadi k = -1, 0, ..., n. Chunki bundan yuqori raqamlangan davlat yo'q n, doimiy ifoda Rⁿ
_0j oladigan barcha satrlar to'plamini ifodalaydi M undan boshlang'ich holati q₀ ga q_j. Agar F = { q₁,...,q_f } - bu to'plam davlatlarni qabul qilish, doimiy ifoda Rⁿ
₀₁ | ... | Rⁿ
_0f tilni ifodalaydi qabul qilindi tomonidan M.

Uchun dastlabki doimiy iboralar k = -1, quyidagicha hisoblanadi men≠j:

R⁻¹
_ij = a₁ | ... | a_m qayerda q_j Δ (q_men,a₁), ..., q_j Δ (q_men,a_m)

va quyidagicha men=j:

R⁻¹
_II = a₁ | ... | a_m | ε qaerda q_men Δ (q_men,a₁), ..., q_men Δ (q_men,a_m)

Boshqa so'zlar bilan aytganda, R⁻¹
_ij dan o'tishni belgilaydigan barcha harflarni eslatib o'tadi men ga j, va biz qaerda bo'lsa, biz ham ε ni kiritamiz men=j.

Shundan so'ng, har bir qadamda iboralar R^k
_ij oldingi tomonidan hisoblab chiqilgan

R^k
_ij = R^k-1
_ik (R^k-1
_kk)^* R^k-1
_kj | R^k-1
_ij

Algoritmning ishlashini tushunishning yana bir usuli - bu "yo'q qilish usuli", bu erda holatlar 0 dan n ketma-ket olib tashlanadi: qachon davlat k olib tashlanadi, doimiy ifoda R^k-1
_ij, holatdan yo'lni belgilaydigan so'zlarni tavsiflaydi men>k bayon qilish j>k, ichiga qayta yozilgan R^k
_ij "yo'q qilingan" holatdan o'tish imkoniyatini hisobga olish uchun k.

Induksiya bo'yicha k, bu uzunligi ko'rsatilishi mumkin^[5] har bir ifodaning R^k
_ij ko'pi bilan 1/3(4^k+1(6s+7) - 4) belgilar, qaerda s in dagi belgilar sonini bildiradi, shuning uchun qabul qilingan tilni ifodalovchi doimiy ifodaning uzunligi M ko'pi bilan 1/3(4ⁿ⁺¹(6s+7)f - f - 3) belgilar, qaerda f yakuniy holatlar sonini bildiradi.Bu eksponent zarba muqarrar, chunki DFA oilalari mavjud bo'lib, ular uchun har qanday ekvivalent doimiy ifoda eksponent o'lchovga ega bo'lishi kerak.^[6]

Amalda algoritmni ishga tushirish natijasida olingan doimiy ifodaning hajmi holatlar protsedura tomonidan ko'rib chiqilish tartibiga, ya'ni ularni 0 dan raqamlash tartibiga qarab juda xilma-xil bo'lishi mumkin. n.

Misol

Kleen algoritmiga berilgan DFA misoli

Rasmda ko'rsatilgan avtomat quyidagicha tavsiflanishi mumkin M = (Q, Σ, δ, q₀, F) bilan

davlatlar to'plami Q = { q₀, q₁, q₂ },
kirish alifbosi Σ = { a, b },
function bilan o'tish funktsiyasi δ (bilan)q₀,a)=q₀δ (q₀,b)=q₁δ (q₁,a)=q₂δ (q₁,b)=q₁δ (q₂,a)=q₁va δ (q₂,b)=q₁,
boshlang'ich holati q₀va
qabul qilingan holatlar to'plami F = { q₁ }.

Kleen algoritmi dastlabki doimiy ifodalarni quyidagicha hisoblab chiqadi

R⁻¹ ₀₀	= a \| ε
R⁻¹ ₀₁	= b
R⁻¹ ₀₂	= ∅
R⁻¹ ₁₀	= ∅
R⁻¹ ₁₁	= b \| ε
R⁻¹ ₁₂	= a
R⁻¹ ₂₀	= ∅
R⁻¹ ₂₁	= a \| b
R⁻¹ ₂₂	= ε

Shundan so'ng, R^k
_ij dan hisoblanadi R^k-1
_ij uchun bosqichma-bosqich k = 0, 1, 2.Kleen algebra doimiyliklarni iloji boricha soddalashtirish uchun tengliklardan foydalaniladi.

0-qadam

R⁰ ₀₀	= R⁻¹ ₀₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₀ \| R⁻¹ ₀₀	= (a \| ε)	(a \| ε)^*	(a \| ε)	\| a \| ε	= a^*
R⁰ ₀₁	= R⁻¹ ₀₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₁ \| R⁻¹ ₀₁	= (a \| ε)	(a \| ε)^*	b	\| b	= a^* b
R⁰ ₀₂	= R⁻¹ ₀₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₂ \| R⁻¹ ₀₂	= (a \| ε)	(a \| ε)^*	∅	\| ∅	= ∅
R⁰ ₁₀	= R⁻¹ ₁₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₀ \| R⁻¹ ₁₀	= ∅	(a \| ε)^*	(a \| ε)	\| ∅	= ∅
R⁰ ₁₁	= R⁻¹ ₁₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₁ \| R⁻¹ ₁₁	= ∅	(a \| ε)^*	b	\| b \| ε	= b \| ε
R⁰ ₁₂	= R⁻¹ ₁₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₂ \| R⁻¹ ₁₂	= ∅	(a \| ε)^*	∅	\| a	= a
R⁰ ₂₀	= R⁻¹ ₂₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₀ \| R⁻¹ ₂₀	= ∅	(a \| ε)^*	(a \| ε)	\| ∅	= ∅
R⁰ ₂₁	= R⁻¹ ₂₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₁ \| R⁻¹ ₂₁	= ∅	(a \| ε)^*	b	\| a \| b	= a \| b
R⁰ ₂₂	= R⁻¹ ₂₀ (R⁻¹ ₀₀)^* R⁻¹ ₀₂ \| R⁻¹ ₂₂	= ∅	(a \| ε)^*	∅	\| ε	= ε

1-qadam

R¹ ₀₀	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₀ \| R⁰ ₀₀	= a^*b	(b \| ε)^*	∅	\| a^*	= a^*
R¹ ₀₁	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₁ \| R⁰ ₀₁	= a^*b	(b \| ε)^*	(b \| ε)	\| a^* b	= a^* b^* b
R¹ ₀₂	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₂ \| R⁰ ₀₂	= a^*b	(b \| ε)^*	a	\| ∅	= a^* b^* ba
R¹ ₁₀	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₀ \| R⁰ ₁₀	= (b \| ε)	(b \| ε)^*	∅	\| ∅	= ∅
R¹ ₁₁	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₁ \| R⁰ ₁₁	= (b \| ε)	(b \| ε)^*	(b \| ε)	\| b \| ε	= b^*
R¹ ₁₂	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₂ \| R⁰ ₁₂	= (b \| ε)	(b \| ε)^*	a	\| a	= b^* a
R¹ ₂₀	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₀ \| R⁰ ₂₀	= (a \| b)	(b \| ε)^*	∅	\| ∅	= ∅
R¹ ₂₁	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₁ \| R⁰ ₂₁	= (a \| b)	(b \| ε)^*	(b \| ε)	\| a \| b	= (a \| b) b^*
R¹ ₂₂	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₂ \| R⁰ ₂₂	= (a \| b)	(b \| ε)^*	a	\| ε	= (a \| b) b^* a \| ε

2-qadam

R² ₀₀	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₀ \| R¹ ₀₀	= a^b^ba	((a\|b)b^a \| ε)^	∅	\| a^*	= a^*
R² ₀₁	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₁ \| R¹ ₀₁	= a^b^ba	((a\|b)b^a \| ε)^	(a\|b)b^*	\| a^* b^* b	= a^* b (a (a \| b) \| b)^*
R² ₀₂	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₂ \| R¹ ₀₂	= a^b^ba	((a\|b)b^a \| ε)^	((a\|b)b^*a \| ε)	\| a^* b^* ba	= a^* b^* b (a (a \| b) b^)^ a
R² ₁₀	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₀ \| R¹ ₁₀	= b^* a	((a\|b)b^a \| ε)^	∅	\| ∅	= ∅
R² ₁₁	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₁ \| R¹ ₁₁	= b^* a	((a\|b)b^a \| ε)^	(a\|b)b^*	\| b^*	= (a (a \| b) \| b)^*
R² ₁₂	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₂ \| R¹ ₁₂	= b^* a	((a\|b)b^a \| ε)^	((a\|b)b^*a \| ε)	\| b^* a	= (a (a \| b) \| b)^* a
R² ₂₀	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₀ \| R¹ ₂₀	= ((a\|b)b^*a \| ε)	((a\|b)b^a \| ε)^	∅	\| ∅	= ∅
R² ₂₁	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₁ \| R¹ ₂₁	= ((a\|b)b^*a \| ε)	((a\|b)b^a \| ε)^	(a\|b)b^*	\| (a \| b) b^*	= (a \| b) (a (a \| b) \| b)^*
R² ₂₂	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₂ \| R¹ ₂₂	= ((a\|b)b^*a \| ε)	((a\|b)b^a \| ε)^	((a\|b)b^*a \| ε)	\| (a \| b) b^* a \| ε	= ((a \| b) b^* a)^*

Beri q₀ boshlang'ich holati va q₁ yagona qabul qilish holati, doimiy ifoda R²
₀₁ avtomat tomonidan qabul qilingan barcha satrlar to'plamini bildiradi.

Shuningdek qarang

Floyd-Uorshall algoritmi - Kleen algoritmi yordamida ma'lum bir narsadan foydalanib amalga oshiriladigan vaznli grafikalar bo'yicha algoritm Kleen algebra
Yulduz balandligi muammosi - ma'lum bir DFA ga mos keladigan barcha doimiy ifodalarning minimal yulduzcha uyalash chuqurligi qancha?
Umumiy yulduz balandligi muammosi - agar komplement operatoriga oddiy iboralarda qo'shimcha ravishda ruxsat berilsa, mumkin yulduzlarning uyalash chuqurligi Kleen algoritmining natijasi belgilangan chegaralar bilan chegaralanadimi?
Tompsonning qurilish algoritmi - doimiy ifodani cheklangan avtomatga aylantiradi

Adabiyotlar

^ McNaughton, R .; Yamada, H. (1960 yil mart). "Avtomatika uchun muntazam ifodalar va holat grafikalari". Elektron kompyuterlarda IRE operatsiyalari. EC-9 (1): 39–47. doi:10.1109 / TEC.1960.5221603. ISSN 0367-9950.
^ ^a ^b Jonathan L. Gross va Jey Yellen, tahrir. (2004). Grafika nazariyasi qo'llanmasi. Diskret matematika va uning qo'llanilishi. CRC Press. ISBN 1-58488-090-2. Bu erda :.2.1-sektsiya, 65-betdagi R13 izohi
^ Kleen, Stiven S (1956). "Hodisalarni asab tarmoqlarida aks ettirish va cheklangan avtomatlashtirish" (PDF). Avtomatika tadqiqotlari, matematika yilnomalari. Tadqiqotlar. Princeton Univ. Matbuot. 34. Bu erda: mazhab.9, s.37-40
^ John E. Hopcroft, Jeffrey D. Ullman (1979). Avtomatika nazariyasi, tillar va hisoblash bilan tanishish. Addison-Uesli. ISBN 0-201-02988-X. Bu erda: 3.2.1-bo'lim 91-96 betlar
^ Aniqrog'i, oddiy ifodali belgilar soni "a_men"," ε "," | ","^*"," · "; Qavslarni hisobga olmaganda.
^ Gruber, German; Xolzer, Markus (2008). Aseto, Luka; Damgard, Ivan; Goldberg, Lesli Ann; Xoldorsson, Magnus M.; Ingolfsdóttir, Anna; Walukievich, Igor (tahr.). "Sonlu avtomatika, Digraf ulanishi va muntazam ifoda hajmi". Avtomatika, tillar va dasturlash. Kompyuter fanidan ma'ruza matnlari. Springer Berlin Heidelberg. 5126: 39–50. doi:10.1007/978-3-540-70583-3_4. ISBN 9783540705833.. Teorema 16.

[1] McNaughton, R .; Yamada, H. (1960 yil mart). "Avtomatika uchun muntazam ifodalar va holat grafikalari". Elektron kompyuterlarda IRE operatsiyalari. EC-9 (1): 39–47. doi:10.1109 / TEC.1960.5221603. ISSN 0367-9950.

[gross2004handbook-2] Jonathan L. Gross va Jey Yellen, tahrir. (2004). Grafika nazariyasi qo'llanmasi. Diskret matematika va uning qo'llanilishi. CRC Press. ISBN 1-58488-090-2. Bu erda :.2.1-sektsiya, 65-betdagi R13 izohi

[3] Kleen, Stiven S (1956). "Hodisalarni asab tarmoqlarida aks ettirish va cheklangan avtomatlashtirish" (PDF). Avtomatika tadqiqotlari, matematika yilnomalari. Tadqiqotlar. Princeton Univ. Matbuot. 34. Bu erda: mazhab.9, s.37-40

[4] John E. Hopcroft, Jeffrey D. Ullman (1979). Avtomatika nazariyasi, tillar va hisoblash bilan tanishish. Addison-Uesli. ISBN 0-201-02988-X. Bu erda: 3.2.1-bo'lim 91-96 betlar

[5] Aniqrog'i, oddiy ifodali belgilar soni "a_men"," ε "," | ","^*"," · "; Qavslarni hisobga olmaganda.

[6] Gruber, German; Xolzer, Markus (2008). Aseto, Luka; Damgard, Ivan; Goldberg, Lesli Ann; Xoldorsson, Magnus M.; Ingolfsdóttir, Anna; Walukievich, Igor (tahr.). "Sonlu avtomatika, Digraf ulanishi va muntazam ifoda hajmi". Avtomatika, tillar va dasturlash. Kompyuter fanidan ma'ruza matnlari. Springer Berlin Heidelberg. 5126: 39–50. doi:10.1007/978-3-540-70583-3_4. ISBN 9783540705833.. Teorema 16.

[1]

[2]

[3]

[4]

[5]

[6]

R¹ ₀₀	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₀ \| R⁰ ₀₀	= a^*b	(b \| ε)^*	∅	\| a^*	= a^*
R¹ ₀₁	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₁ \| R⁰ ₀₁	= a^*b	(b \| ε)^*	(b \| ε)	\| a^* b	= a^* b^* b
R¹ ₀₂	= R⁰ ₀₁ (R⁰ ₁₁)^* R⁰ ₁₂ \| R⁰ ₀₂	= a^*b	(b \| ε)^*	a	\| ∅	= a^* b^* ba
R¹ ₁₀	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₀ \| R⁰ ₁₀	= (b \| ε)	(b \| ε)^*	∅	\| ∅	= ∅
R¹ ₁₁	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₁ \| R⁰ ₁₁	= (b \| ε)	(b \| ε)^*	(b \| ε)	\| b \| ε	= b^*
R¹ ₁₂	= R⁰ ₁₁ (R⁰ ₁₁)^* R⁰ ₁₂ \| R⁰ ₁₂	= (b \| ε)	(b \| ε)^*	a	\| a	= b^* a
R¹ ₂₀	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₀ \| R⁰ ₂₀	= (a \| b)	(b \| ε)^*	∅	\| ∅	= ∅
R¹ ₂₁	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₁ \| R⁰ ₂₁	= (a \| b)	(b \| ε)^*	(b \| ε)	\| a \| b	= (a \| b) b^*
R¹ ₂₂	= R⁰ ₂₁ (R⁰ ₁₁)^* R⁰ ₁₂ \| R⁰ ₂₂	= (a \| b)	(b \| ε)^*	a	\| ε	= (a \| b) b^* a \| ε

R² ₀₀	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₀ \| R¹ ₀₀	= a^b^ba	((a\|b)b^a \| ε)^	∅	\| a^*	= a^*
R² ₀₁	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₁ \| R¹ ₀₁	= a^b^ba	((a\|b)b^a \| ε)^	(a\|b)b^*	\| a^* b^* b	= a^* b (a (a \| b) \| b)^*
R² ₀₂	= R¹ ₀₂ (R¹ ₂₂)^* R¹ ₂₂ \| R¹ ₀₂	= a^b^ba	((a\|b)b^a \| ε)^	((a\|b)b^*a \| ε)	\| a^* b^* ba	= a^* b^* b (a (a \| b) b^)^ a
R² ₁₀	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₀ \| R¹ ₁₀	= b^* a	((a\|b)b^a \| ε)^	∅	\| ∅	= ∅
R² ₁₁	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₁ \| R¹ ₁₁	= b^* a	((a\|b)b^a \| ε)^	(a\|b)b^*	\| b^*	= (a (a \| b) \| b)^*
R² ₁₂	= R¹ ₁₂ (R¹ ₂₂)^* R¹ ₂₂ \| R¹ ₁₂	= b^* a	((a\|b)b^a \| ε)^	((a\|b)b^*a \| ε)	\| b^* a	= (a (a \| b) \| b)^* a
R² ₂₀	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₀ \| R¹ ₂₀	= ((a\|b)b^*a \| ε)	((a\|b)b^a \| ε)^	∅	\| ∅	= ∅
R² ₂₁	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₁ \| R¹ ₂₁	= ((a\|b)b^*a \| ε)	((a\|b)b^a \| ε)^	(a\|b)b^*	\| (a \| b) b^*	= (a \| b) (a (a \| b) \| b)^*
R² ₂₂	= R¹ ₂₂ (R¹ ₂₂)^* R¹ ₂₂ \| R¹ ₂₂	= ((a\|b)b^*a \| ε)	((a\|b)b^a \| ε)^	((a\|b)b^*a \| ε)	\| (a \| b) b^* a \| ε	= ((a \| b) b^* a)^*