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

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

 شرح الگوریتم 
بنابه گفته‌های Gross و Yellen, Here: sect.2.1, remark R13 on p.65 این الگوریتم را می‌توان به کلینی نسبت داد.

شرح این الگوریتم پیرو گفته‌های Hopcroft و Ullman است. Here: Theorem 2.4, p.33-34
یک ماشین تعیین‌پذیر حالات متناهی (M = (Q, Σ, δ, q0, F با حالت‌های { Q = { q0,... ,qn داریم، محاسبه الگوریتم بدین صورت است:
مجموعه‌های R شامل همه رشته‌هایی است که ماشین M از حالت qi به حالت qj می‌رود بدون اینکه از حالت‌هایی با شماره بالاتر از k عبور کند. عبور کردن را می‌توان وارد شدن یا خارج شدن تعبیر کرد، پس هر کدام از حالت‌های i و j می‌توانند بزرگتر از k باشد اما حالات میانی نمی‌توانند. هر مجموعه R با یک عبارت باقاعده نشان داده می‌شود؛ این الگوریتم عبارات را گام به گام برای k = -1, 0, … , n محاسبه می‌کند. از آنجایی که هیچ حالتی با شماره بزرگتر از n وجود ندارد، پس عبارت باقاعده R مجموعه همه رشته‌هایی است که ماشین M از حالت شروع q0 به حالت qj می‌رود. در واقع اگر { F = { q1,... ,qf حالات پذیرش باشد، عبارت باقاعده R | و.. | R نشان‌دهنده زبان پذیرفته‌شده توسط ماشین M است.

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

R = a1 | … | am, if i≠j, where δ(qi,a1) = … = δ(qi,am) = qj
R = a1 | … | am | ε, if i=j, where δ(qi,a1) = … = δ(qi,am) = qj

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

R = R (R)* R | R

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

همان‌طور که در تصویر مشاهده می‌شود، یک ماشین تعیین‌پذیر حالات متناهی (M = (Q, Σ, δ, q0, F با تفاسیر زیر داریم:
 مجموعه حالات { Q = { q0, q1, q2,
 الفبای ورودی { Σ = { a, b,
 تابع انتقال δ که δ(q0,a)=q0, δ(q0,b)=q1, δ(q1,a)=q2, δ(q1,b)=q1, δ(q2,a)=q1, δ(q2,b)=q1,
 حالت شروع q0,
 مجموعه حالات پذیرش { F = { q1.

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

 R = a | ε R  = b R  = ∅ R  = ∅ R  = b | ε R  = a R  = ∅ R  = a | b R  = ε

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

گام صفر:

 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 | ε)* ∅ | ε = ε

گام یک:

 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 = R = R (R)* R | R = a*b*ba ((a|b)b*a | ε)* ((a|b)b*a | ε) | a* b* ba = 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* = R = R (R)* R | R = b* a ((a|b)b*a | ε)* ((a|b)b*a | ε) | 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* = R = R (R)* R | R = ((a|b)b*a | ε) ((a|b)b*a | ε)* ((a|b)b*a | ε) | (a | b) b* a | ε =

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

q0 حالت شروع و q1 تنها حالت پایان می‌باشد، لذا عبارت باقاعده R نشان‌دهنده مجموعه تمام رشته‌های پذیرفته‌شده توسط ماشین M است.

 منابع 

رده:الگوریتم‌ها
رده:عبارت‌های باقاعده
رده:ماشین متناهی
رده:نظریه اتوماتا