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

همان‌طور که در تصویر مشاهده می‌شود، یک ماشین تعیین‌پذیر حالات متناهی (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.
الگوریتم کلینی عبارات باقاعده اولیه را به صورت زیر محاسبه می‌کند:
| 0 | 1 |
| --- | --- |
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 = -۱، ۰، … , محاسبه می‌شود. از ویژگی‌های جبر کلینی برای ساده‌سازی عبارات باقاعده تا حد امکان استفاده شده‌است.
گام صفر:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 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 | ε)* | ∅ | | ε | = ε |
گام یک:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 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 | ε |
گام دو:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| --- | --- | --- | --- | --- | --- | --- |
| 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 | ε | = |
«گام دوم نیاز به ساده‌سازی دارد»
q0 حالت شروع و q1 تنها حالت پایان می‌باشد، لذا عبارت باقاعده 2
01R نشان‌دهنده مجموعه تمام رشته‌های پذیرفته‌شده توسط ماشین M است.
ماشین تعیین‌پذیر حالات متناهی داده شده به الگوریتم کلینی