الگوریتم کلینی
در علوم نظری رایانه به خصوص در زبان فُرمال، الگوریتم کلین یک ماشین تعیینپذیر حالات متناهی را به یک عبارت باقاعده تبدیل میکند.
شرح الگوریتم ویرایش
بنابه گفتههای Gross و Yellen,[۱] این الگوریتم را میتوان به کلینی[۲] نسبت داد.
شرح این الگوریتم پیرو گفتههای Hopcroft و Ullman است.[۳]
یک ماشین تعیینپذیر حالات متناهی (M = (Q, Σ, δ, q0, F با حالتهای { Q = { q0,... ,qn داریم، محاسبه الگوریتم بدین صورت است:
مجموعههای k
ijR شامل همه رشتههایی است که ماشین M از حالت qi به حالت qj میرود بدون اینکه از حالتهایی با شماره بالاتر از k عبور کند. عبور کردن را میتوان وارد شدن یا خارج شدن تعبیر کرد، پس هر کدام از حالتهای i و j میتوانند بزرگتر از k باشد اما حالات میانی نمیتوانند. هر مجموعه k
ijR با یک عبارت باقاعده نشان داده میشود؛ این الگوریتم عبارات را گام به گام برای k = -1, 0, … , n محاسبه میکند. از آنجایی که هیچ حالتی با شماره بزرگتر از n وجود ندارد، پس عبارت باقاعده k
0jR مجموعه همه رشتههایی است که ماشین M از حالت شروع q0 به حالت qj میرود. در واقع اگر { F = { q1,... ,qf حالات پذیرش باشد، عبارت باقاعده k
0fR | و.. | k
01R نشاندهنده زبان پذیرفتهشده توسط ماشین M است.
عبارت باقاعده اولیه برای k = -۱ به صورت زیر محاسبه میشود:
- R−1
ij = a1 | … | am, if i≠j, where δ(qi,a1) = … = δ(qi,am) = qj - R−1
ij = a1 | … | am | ε, if i=j, where δ(qi,a1) = … = δ(qi,am) = qj
حال در هر قدم عبارت باقاعده k
ijR از گامهای قبلی به صورت زیر محاسبه میشود:
- Rk
ij = Rk-1
ik (Rk-1
kk)* Rk-1
kj | Rk-1
ij
مثال ویرایش
همانطور که در تصویر مشاهده میشود، یک ماشین تعیینپذیر حالات متناهی (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−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 | ε | = |
«گام دوم نیاز به سادهسازی دارد»
q0 حالت شروع و q1 تنها حالت پایان میباشد، لذا عبارت باقاعده 2
01R نشاندهنده مجموعه تمام رشتههای پذیرفتهشده توسط ماشین M است.
منابع ویرایش
- ↑ Jonathan L. Gross and Jay Yellen, ed. (2004). Handbook of Graph Theory. Discrete Mathematics and it Applications. CRC Press. ISBN 1-58488-090-2. Here: sect.2.1, remark R13 on p.65
- ↑ Kleene, Stephen C. (1956). "Representation of Events in Nerve Nets and Finite Automate" (PDF). Automata Studies, Annals of Math. Studies. Princeton Univ. Press. 34.
- ↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X. Here: Theorem 2.4, p.33-34