الگوریتم کلینی

در علوم نظری رایانه به خصوص در زبان فُرمال، الگوریتم کلین یک ماشین تعیین‌پذیر حالات متناهی را به یک عبارت باقاعده تبدیل می‌کند.

شرح الگوریتم

بنابه گفته‌های Gross و Yellen, این الگوریتم را می‌توان به کلینی نسبت داد.

شرح این الگوریتم پیرو گفته‌های Hopcroft و Ullman است. یک ماشین تعیین‌پذیر حالات متناهی (M = (Q, Σ, δ, q₀, F با حالت‌های { Q = { q₀,... ,q_n داریم، محاسبه الگوریتم بدین صورت است: مجموعه‌های k
ijR شامل همه رشته‌هایی است که ماشین M از حالت q_i به حالت q_j می‌رود بدون اینکه از حالت‌هایی با شماره بالاتر از k عبور کند. عبور کردن را می‌توان وارد شدن یا خارج شدن تعبیر کرد، پس هر کدام از حالت‌های i و j می‌توانند بزرگتر از k باشد اما حالات میانی نمی‌توانند. هر مجموعه k
ijR با یک عبارت باقاعده نشان داده می‌شود؛ این الگوریتم عبارات را گام به گام برای k = -1, 0, … , n محاسبه می‌کند. از آنجایی که هیچ حالتی با شماره بزرگتر از n وجود ندارد، پس عبارت باقاعده k
0jR مجموعه همه رشته‌هایی است که ماشین M از حالت شروع q₀ به حالت q_j می‌رود. در واقع اگر { F = { q₁,... ,q_f حالات پذیرش باشد، عبارت باقاعده k
0fR | و.. | k
01R نشان‌دهنده زبان پذیرفته‌شده توسط ماشین M است.

عبارت باقاعده اولیه برای k = -۱ به صورت زیر محاسبه می‌شود:

R−1
ij = a₁ | … | a_m, if i≠j, where δ(q_i,a₁) = … = δ(q_i,a_m) = q_j

R−1
ij = a₁ | … | a_m | ε, if i=j, where δ(q_i,a₁) = … = δ(q_i,a_m) = q_j

حال در هر قدم عبارت باقاعده k
ijR از گام‌های قبلی به صورت زیر محاسبه می‌شود:

Rk
ij = Rk-1
ik (Rk-1
kk)^* Rk-1
kj | Rk-1
ij

مثال

ماشین تعیین‌پذیر حالات متناهی داده شده به الگوریتم کلینی

همان‌طور که در تصویر مشاهده می‌شود، یک ماشین تعیین‌پذیر حالات متناهی (M = (Q, Σ, δ, q₀, F با تفاسیر زیر داریم:

• مجموعه حالات { Q = { q₀, q₁, q₂,
• الفبای ورودی { Σ = { a, b,
• تابع انتقال δ که δ(q₀,a)=q₀, δ(q₀,b)=q₁, δ(q₁,a)=q₂, δ(q₁,b)=q₁, δ(q₂,a)=q₁, δ(q₂,b)=q₁,
• حالت شروع q₀,
• مجموعه حالات پذیرش { F = { q₁.

الگوریتم کلینی عبارات باقاعده اولیه را به صورت زیر محاسبه می‌کند:

R−1 00	= a | ε
R−1 01	= b
R−1 02	= ∅
R−1 10	= ∅
R−1 11	= b | ε
R−1 12	= a
R−1 20	= ∅
R−1 21	= a | b
R−1 22	= ε

سپس عبارت باقاعده k
ijR گام به گام از k-1
ijR برای k = -۱، ۰، … , محاسبه می‌شود. از ویژگی‌های جبر کلینی برای ساده‌سازی عبارات باقاعده تا حد امکان استفاده شده‌است.

گام صفر:

R0 00	= R−1 00 (R−1 00)* R−1 00 | R−1 00	= (a | ε)	(a | ε)*	(a | ε)	| a | ε	= a*
R0 01	= R−1 00 (R−1 00)* R−1 01 | R−1 01	= (a | ε)	(a | ε)*	b	| b	= a* b
R0 02	= R−1 00 (R−1 00)* R−1 02 | R−1 02	= (a | ε)	(a | ε)*	∅	| ∅	= ∅
R0 10	= R−1 10 (R−1 00)* R−1 00 | R−1 10	= ∅	(a | ε)*	(a | ε)	| ∅	= ∅
R0 11	= R−1 10 (R−1 00)* R−1 01 | R−1 11	= ∅	(a | ε)*	b	| b | ε	= b | ε
R0 12	= R−1 10 (R−1 00)* R−1 02 | R−1 12	= ∅	(a | ε)*	∅	| a	= a
R0 20	= R−1 20 (R−1 00)* R−1 00 | R−1 20	= ∅	(a | ε)*	(a | ε)	| ∅	= ∅
R0 21	= R−1 20 (R−1 00)* R−1 01 | R−1 21	= ∅	(a | ε)*	b	| a | b	= a | b
R0 22	= R−1 20 (R−1 00)* R−1 02 | R−1 22	= ∅	(a | ε)*	∅	| ε	= ε

گام یک:

R1 00	= R0 01 (R0 11)* R0 10 | R0 00	= a*b	(b | ε)*	∅	| a*	= a*
R1 01	= R0 01 (R0 11)* R0 11 | R0 01	= a*b	(b | ε)*	(b | ε)	| a* b	= a* b* b
R1 02	= R0 01 (R0 11)* R0 12 | R0 02	= a*b	(b | ε)*	a	| ∅	= a* b* ba
R1 10	= R0 11 (R0 11)* R0 10 | R0 10	= (b | ε)	(b | ε)*	∅	| ∅	= ∅
R1 11	= R0 11 (R0 11)* R0 11 | R0 11	= (b | ε)	(b | ε)*	(b | ε)	| b | ε	= b*
R1 12	= R0 11 (R0 11)* R0 12 | R0 12	= (b | ε)	(b | ε)*	a	| a	= b* a
R1 20	= R0 21 (R0 11)* R0 10 | R0 20	= (a | b)	(b | ε)*	∅	| ∅	= ∅
R1 21	= R0 21 (R0 11)* R0 11 | R0 21	= (a | b)	(b | ε)*	(b | ε)	| a | b	= (a | b) b*
R1 22	= R0 21 (R0 11)* R0 12 | R0 22	= (a | b)	(b | ε)*	a	| ε	= (a | b) b* a | ε

گام دو:

R2 00	= R1 02 (R1 22)* R1 20 | R1 00	= a*b*ba	((a|b)b*a | ε)*	∅	| a*	= a*
R2 01	= R1 02 (R1 22)* R1 21 | R1 01	= a*b*ba	((a|b)b*a | ε)*	(a|b)b*	| a* b* b	=
R2 02	= R1 02 (R1 22)* R1 22 | R1 02	= a*b*ba	((a|b)b*a | ε)*	((a|b)b*a | ε)	| a* b* ba	=
R2 10	= R1 12 (R1 22)* R1 20 | R1 10	= b* a	((a|b)b*a | ε)*	∅	| ∅	= ∅
R2 11	= R1 12 (R1 22)* R1 21 | R1 11	= b* a	((a|b)b*a | ε)*	(a|b)b*	| b*	=
R2 12	= R1 12 (R1 22)* R1 22 | R1 12	= b* a	((a|b)b*a | ε)*	((a|b)b*a | ε)	| b* a	=
R2 20	= R1 22 (R1 22)* R1 20 | R1 20	= ((a|b)b*a | ε)	((a|b)b*a | ε)*	∅	| ∅	= ∅
R2 21	= R1 22 (R1 22)* R1 21 | R1 21	= ((a|b)b*a | ε)	((a|b)b*a | ε)*	(a|b)b*	| (a | b) b*	=
R2 22	= R1 22 (R1 22)* R1 22 | R1 22	= ((a|b)b*a | ε)	((a|b)b*a | ε)*	((a|b)b*a | ε)	| (a | b) b* a | ε	=

«گام دوم نیاز به ساده‌سازی دارد»

q₀ حالت شروع و q₁ تنها حالت پایان می‌باشد، لذا عبارت باقاعده 2
01R نشان‌دهنده مجموعه تمام رشته‌های پذیرفته‌شده توسط ماشین M است.