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

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

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

شرح این الگوریتم پیرو گفته‌های Hopcroft و Ullman است.
یک ماشین تعیین‌پذیر حالات متناهی (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 گام به گام از R برای k = -۱، ۰، … , محاسبه می‌شود. از ویژگی‌های جبر کلینی برای ساده‌سازی عبارات باقاعده تا حد امکان استفاده شده‌است.

گام صفر:

گام یک:

گام دو:

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

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

منابع 

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