خوارزمية كلين

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

في علم الحاسوب النظري ، وتحديدًا في نظرية اللغات الرسمية ، تُحوّل خوارزمية كلين آلة الحالة المحدودة غير الحتمية (NFA) إلى تعبير نمطي . وتُثبت ، إلى جانب خوارزميات تحويل أخرى، تكافؤ العديد من صيغ وصف اللغات النمطية . ومن بين العروض البديلة لهذه الطريقة "طريقة الحذف" المنسوبة إلى برزوزوفسكي وماكلوسكي ، وخوارزمية ماكناوتون ويامادا ، [ 1 ] واستخدام مبرهنة آردن .

وصف الخوارزمية

بحسب غروس ويلين (2004)، [ 2 ] يمكن تتبع أصل الخوارزمية إلى كلين (1956). [ 3 ] وقُدِّم عرضٌ للخوارزمية في حالة الأوتوماتا المحدودة الحتمية (DFAs) في هوبكروفت وأولمان (1979). [ 4 ] ويتبع عرض الخوارزمية للأوتوماتا المحدودة غير الحتمية (NFAs) أدناه ما ورد في غروس ويلين (2004). [ 2 ]

بالنظر إلى آلة حالة محدودة غير حتمية M = ( Q , Σ, δ, q0 , F )، حيث Q = { q0 , ..., qn } ، فإن الخوارزمية تحسب

المجموعات R k ij لجميع السلاسل التي تنقل M من الحالة q i إلى q j دون المرور بأي حالة مرقمة أعلى من k .

هنا، تعني عبارة "المرور بحالة" الدخول إليها والخروج منها، لذا قد يكون كل من i و j أكبر من k ، ولكن لا توجد حالة وسيطة. تُمثَّل كل مجموعة R<sub> k, ij</sub> بتعبير نمطي؛ وتحسب الخوارزمية هذه التعبيرات خطوة بخطوة لـ k = -1، 0، ...، n . بما أنه لا توجد حالة مرقمة أعلى من n ، فإن التعبير النمطي R<sub> n, 0j</sub> يُمثِّل مجموعة جميع السلاسل التي تنقل M من حالتها الابتدائية q<sub> 0</sub> إلى q<sub> j </sub>. إذا كانت F = { q <sub>1</sub> , ..., q<sub> f</sub> } هي ​​مجموعة حالات القبول ، فإن التعبير النمطي R <sub>n, 01</sub> | ... | R <sub>n, 0f </sub> يُمثِّل اللغة التي يقبلها M.

يتم حساب التعبيرات النمطية الأولية، لـ k = -1، على النحو التالي لـ i ≠ j :

R −1 ij = a 1 | ... | a m حيث q j ∈ δ( q i , a 1 ), ..., q j ∈ δ( q i , a m )   

وكما يلي بالنسبة لـ i = j :

R −1 ii = a 1 | ... | a m | ε حيث q i ∈ δ( q i , a 1 ), ..., q i ∈ δ( q i , a m )   

بمعنى آخر، يشير R −1 ij إلى جميع الأحرف التي تحدد الانتقال من i إلى j ، ونحن ندرج أيضًا ε في الحالة التي يكون فيها i = j .

بعد ذلك، في كل خطوة يتم حساب التعبيرات R k ij من التعبيرات السابقة بواسطة

R k ij = R k -1 ik ( R k -1 kk ) * R k -1 kj | ص ك -1 ي

هناك طريقة أخرى لفهم عمل الخوارزمية وهي "طريقة الحذف"، حيث تتم إزالة الحالات من 0 إلى n على التوالي: عند إزالة الحالة k ، تتم إعادة كتابة التعبير العادي R k -1 ij ، الذي يصف الكلمات التي تحدد مسارًا من الحالة i > k إلى الحالة j > k ، إلى R k ij بحيث يأخذ في الاعتبار إمكانية المرور عبر الحالة "المحذوفة" k .

باستخدام الاستقراء على k ، يمكن إثبات أن طول كل تعبير R <sub> k </sub> ij لا يتجاوز 1/3 ( 4k + 1 ( 6s + 7 ) - 4) رمزًا، حيث s يمثل عدد الأحرف في Σ. بالتالي، فإن طول التعبير النمطي الذي يمثل اللغة المقبولة بواسطة M لا يتجاوز 1/3 ( 4n + 1 ( 6s + 7 ) f - f - 3 ) رمزًا، حيث f يمثل عدد الحالات النهائية. هذا التضخم الأسي حتمي، لأنه توجد عائلات من آلات الحالة المحدودة المحددة (DFAs) التي يجب أن يكون أي تعبير نمطي مكافئ لها ذا حجم أسي. [ 6 ]

من الناحية العملية، يمكن أن يكون حجم التعبير النمطي الذي تم الحصول عليه عن طريق تشغيل الخوارزمية مختلفًا جدًا اعتمادًا على الترتيب الذي يتم به النظر في الحالات بواسطة الإجراء، أي الترتيب الذي يتم به ترقيمها من 0 إلى n .

مثال

مثال على آلة الحالة المحدودة المحددة (DFA) المعطاة لخوارزمية كلين

يمكن وصف الآلة الموضحة في الصورة على النحو التالي: M = ( Q , Σ, δ , q0 , F )

  • مجموعة الحالات Q = { q 0 , q 1 , q 2 },
  • الأبجدية المدخلة Σ = { a , b },
  • دالة الانتقال δ مع δ( q0 , a ) = q0 ، δ  ( q0 , b ) = q1 ، δ ( q1 , a ) = q2 ، δ ( q1 , b ) = q1 ، δ ( q2 , a ) = q1 ، و δ ( q2 , b ) = q1 ،   
  • الحالة الابتدائية q 0 ، و
  • مجموعة حالات القبول F = { q 1 }.

تحسب خوارزمية كلين التعبيرات النمطية الأولية على النحو التالي:

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

بعد ذلك، يتم حساب R k ij من R k -1 ij خطوة بخطوة لـ k = 0، 1، 2. يتم استخدام معادلات جبر كلين لتبسيط التعبيرات النمطية قدر الإمكان.

الخطوة 0
R 0 00  = R −1 00 ( R −1 00 ) * R −1 00 | R −1 00  = ( أ | ε)( أ | ε) *( أ | ε)| أ | ε   = أ *
R 0 01= R −1 00 ( R −1 00 ) * R −1 01 | R −1 01= ( أ | ε)( أ | ε) *ب| ب= أ * ب
R 0 02= R −1 00 ( R −1 00 ) * R −1 02 | R −1 02= ( أ | ε)( أ | ε) *∅| ∅= ∅
R 0 10= R −1 10 ( R −1 00 ) * R −1 00 | R −1 10= ∅( أ | ε) *( أ | ε)| ∅= ∅
R 0 11= R −1 10 ( R −1 00 ) * R −1 01 | R −1 11= ∅( أ | ε) *ب| ب | ε= ب | ε
R 0 12= R −1 10 ( R −1 00 ) * R −1 02 | R −1 12= ∅( أ | ε) *∅| أ= أ
R 0 20= R −1 20 ( R −1 00 ) * R −1 00 | R −1 20= ∅( أ | ε) *( أ | ε)| ∅= ∅
R 0 21= R −1 20 ( R −1 00 ) * R −1 01 | R −1 21= ∅( أ | ε) *ب| أ | ب= أ | ب
R 0 22= R −1 20 ( R −1 00 ) * R −1 02 | R −1 22= ∅( أ | ε) *∅| ε= ε
الخطوة 1
1.00 ريال سعودي  = R 0 01 ( R 0 11 ) * R 0 10 | R 0 00  = أ * ب( ب | ε) *∅| أ *    = أ *
R 1 01= R 0 01 ( R 0 11 ) * R 0 11 | R 0 01= أ * ب( ب | ε) *( ب | ε)| أ * ب= أ * ب * ب
R 1 02= R 0 01 ( R 0 11 ) * R 0 12 | R 0 02= أ * ب( ب | ε) *أ| ∅= أ * ب * با
R 1 10= R 0 11 ( R 0 11 ) * R 0 10 | R 0 10= ( b | ε)( ب | ε) *∅| ∅= ∅
R 1 11= R 0 11 ( R 0 11 ) * R 0 11 | R 0 11= ( b | ε)( ب | ε) *( ب | ε)| ب | ε= ب *
R 1 12= R 0 11 ( R 0 11 ) * R 0 12 | R 0 12= ( b | ε)( ب | ε) *أ| أ= ب * أ
R 1 20= R 0 21 ( R 0 11 ) * R 0 10 | R 0 20= ( أ | ب )( ب | ε) *∅| ∅= ∅
R 1 21= R 0 21 ( R 0 11 ) * R 0 11 | R 0 21= ( أ | ب )( ب | ε) *( ب | ε)| أ | ب= ( أ | ب ) ب *
R 1 22= R 0 21 ( R 0 11 ) * R 0 12 | R 0 22= ( أ | ب )( ب | ε) *أ| ε= ( أ | ب ) ب * أ | ε
الخطوة الثانية
200 ريال سعودي  = R 1 02 ( R 1 22 ) * R 1 20 | R 1 00  = أ * ب * با(( أ | ب ) ب * أ | ε) *∅| أ *= أ *
R 2 01= R 1 02 ( R 1 22 ) * R 1 21 | R 1 01= أ * ب * با(( أ | ب ) ب * أ | ε) *( أ | ب ) ب *| أ * ب * ب= أ * ب ( أ ( أ | ب ) | ب ) *
R 2 02= R 1 02 ( R 1 22 ) * R 1 22 | R 1 02= أ * ب * با(( أ | ب ) ب * أ | ε) *(( أ | ب ) ب * أ | ε)| أ * ب * با= أ * ب * ب ( أ ( أ | ب ) ب * ) * أ
R 2 10= R 1 12 ( R 1 22 ) * R 1 20 | R 1 10= ب * أ(( أ | ب ) ب * أ | ε) *∅| ∅= ∅
R 2 11= R 1 12 ( R 1 22 ) * R 1 21 | R 1 11= ب * أ(( أ | ب ) ب * أ | ε) *( أ | ب ) ب *| ب *= ( أ ( أ | ب ) | ب ) *
R 2 12= R 1 12 ( R 1 22 ) * R 1 22 | R 1 12= ب * أ(( أ | ب ) ب * أ | ε) *(( أ | ب ) ب * أ | ε)| ب * أ= ( أ ( أ | ب ) | ب ) * أ
R 2 20= R 1 22 ( R 1 22 ) * R 1 20 | R 1 20= (( أ | ب ) ب * أ | ε)(( أ | ب ) ب * أ | ε) *∅| ∅= ∅
R 2 21= R 1 22 ( R 1 22 ) * R 1 21 | R 1 21= (( أ | ب ) ب * أ | ε)(( أ | ب ) ب * أ | ε) *( أ | ب ) ب *| ( أ | ب ) ب *= ( أ | ب ) ( أ ( أ | ب ) | ب ) *
R 2 22= R 1 22 ( R 1 22 ) * R 1 22 | R 1 22= (( أ | ب ) ب * أ | ε)(( أ | ب ) ب * أ | ε) *(( أ | ب ) ب * أ | ε)| ( أ | ب ) ب * أ | ε   = (( أ | ب ) ب * أ ) *

بما أن q 0 هي حالة البداية و q 1 هي حالة القبول الوحيدة، فإن التعبير النمطي R 2 01 يشير إلى مجموعة جميع السلاسل التي يقبلها الجهاز الآلي.

انظر أيضاً

مراجع

  1. ↑ ماكناوتون، ر.؛ يامادا، هـ. (مارس 1960). "التعابير النمطية ومخططات الحالة للأتمتة". معاملات معهد مهندسي الراديو في الحواسيب الإلكترونية . EC-9 (1): 39-47 . doi : 10.1109/TEC.1960.5221603 . ISSN 0367-9950 . 
  2. 1 2 جوناثان ل. غروس وجاي يلين، محرران (2004). دليل نظرية الرسم البياني . الرياضيات المتقطعة وتطبيقاتها. مطبعة سي آر سي. ISBN 1-58488-090-2.هنا: القسم 2.1، الملاحظة R13 في الصفحة 65
  3. ↑ كلين، ستيفن سي. (1956). "تمثيل الأحداث في الشبكات العصبية والآلات المحدودة" (ملف PDF) . دراسات الآلات، حوليات الدراسات الرياضية . 34. مطبعة جامعة برينستون.هنا: القسم 9، الصفحات 37-40
  4. ↑ جون إي. هوبكروفت، جيفري د. أولمان (1979). مقدمة في نظرية الأوتوماتا واللغات والحوسبة . أديسون-ويسلي. ISBN 0-201-02988-X.هنا: القسم 3.2.1 الصفحات 91-96
  5. ↑ وبشكل أدق، عدد رموز التعبير النمطي، " a i "، "ε"، "|"، " * "، "·"؛ دون احتساب الأقواس.
  6. ^ جروبر ، هيرمان. هولزر، ماركوس (2008). “الأتمتة المحدودة واتصال Digraph وحجم التعبير العادي”. في أسيتو، لوكا؛ دامجارد، إيفان؛ غولدبرغ، ليزلي آن؛ هالدورسون، ماغنوس م.؛ إنجولفسدوتير، آنا؛ والوكيويتز، إيغور (محرران). الأتمتة واللغات والبرمجة . ملاحظات محاضرة في علوم الكمبيوتر. المجلد. 5126. سبرينغر برلين هايدلبرغ. الصفحات من 39 إلى 50. دوى : 10.1007/978-3-540-70583-3_4 . رقم ISBN   9783540705833. S2CID 10975422 . النظرية 16.