مرجع
آخر الزيارات

تجربة بناء طومسون

929 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: تجربة بناء طومسون. تتناول المقالة 10 أقسام، منها «يحول تعبير نجمة كلين إلى s*»، «التعريف» و«يحول رمز a من الحرف الهجائي الداخل».
المحتويات
  1. يحول تعبير نجمة كلين إلى s*
  2. التعريف
  3. يحول رمز a من الحرف الهجائي الداخل
  4. الخوارزمية
  5. الأمثلة
  6. تطبيق الخوارزمية
  7. القواعد
  8. (0|(1(01*(00)*0)*1)*)*
  9. المثال الصغير
  10. العلاقة بالخوارزميات الأخرى

تجربة بناء طومسون

يحول تعبير نجمة كلين إلى s*

من جانب آخر، يوصل انتقال ε الحالة الأولية والنهائية للأتومات المحدودة غير الحتمية مع الأتومات المحدودة غير الحتمية الفرعية في s)N) ما بينهم.

كذلك، يسمح انتقال ε آخر من الحالة النهائية الداخلية للحالة الأولية الداخلية لـs)N) تكرار التعبير s طبقا لمشغل النجمة.

التعريف

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

المحتوى

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

يحول رمز a من الحرف الهجائي الداخل

وعلى صعيد آخر، تصبح حالاتهم النهائية حالات متوسطة من كل الأتومات المحدودة غير الحتمية وتظهر عن طريق انتقالين ε اثنين إلي الحالة النهائية للأتومات المحدودة غير الحتمية .يحول التعبير المسلسل st إلى الحالة الأولية لـ هي الحالة الأولية لكل الأتومات المحدودة غير الحتمية . الحالة النهائية لـ s)N) تصبح الحالة الأولية لـ t)N). الحالة النهائية لـ t)N)هي الحالة النهائية لكل الأتومات المحدودة غير الحتمية.

علاوةً على ذلك، يحول التعبير المتحد إلى s – t تذهب حالة q عن طريق ε إما إلي الحالة الأولية لـ s)N) أو t)N)

الخوارزمية

وفي هذا السياق، تعمل هذه الخوارزمية بشكل تكراري عن طريق تقسيم التعبير إلي تعبيراته الفرعية الجوهرية والتي من خلالها ستبني الأتومات المحدودة غير الحتمية باستخدام مجموعة من القواعد أكثر دقة ، من التعبير المنتظم E الأوتوماتون الناتج A مع الوظيفة الانتقالية ẟ تطبق الخصائص الآتية:

من جهة ثانية، لأن الأتومات المحدودة غير الحتمية لحالات m وعلي الأكثر انتقالات e من أي حالة يمكن أن تطابق سلسة الطول n في وقت (O (emn ,أتومات طومسون المحدودة غير الحتمية يمكن أن تفعل نمط يتطابق في وقت خطي بفرض ثبوت حجم حرف الهجاء.

عدد الانتقالات المغادرة لأي حالة هي على الأكثر اثنان

وفي السياق ذاته، A لها حالة نهائية واحدة بالضبط qf والتي لا يمكن الوصول إليها من أي حالة, وهذا لأي رسالة a

كذلك، لتكن c عدد تسلسل التعبير المنتظم E ولتكن s عدد الرموز بعيدا عن الأقواس هذا , *, a و ε . فيما بعد عدد حالات A هي 2s -c (خطي في حجم E )

(ẟ (q,a لا تحتوي على q0 .

(Ø =ẟ (qf,a.

وعلى صعيد آخر، A لها حالة أولية واحدة بالضبط q0 والتي لا يمكن الوصول أليها من أي حالة أخرى. هذا لأي حالة q وأي حرف a

الأمثلة

وفي السياق ذاته، مثالان معطيان الآن واحد غير رسمي صغير مع النتيجة وآخر أكبر مع تطبيق الخوارزمية خطوة بخطوة.

تطبيق الخوارزمية

وفي هذا الصدد، { ε, "0", "00", "11", "000", "011", "110", "0000", "0011", "0110", "1001", "1100", "1111", "00000", ... }.

  • خطوات الخوارزمية كالآتي :
  • q : بداية تحويل تعبير نجمة كلين
  • (0|(1(01*(00)*0)*1)*)*
  • b: بداية تحويل التعبير المتحد
  • 0|(1(01*(00)*0)*1)*
  • a : حول الرمز
  • 0
  • p : ابدأ تحويل تعبير نجمة كلين
  • (1(01*(00)*0)*1)*
  • d : ابدأ تحويل التعبير المتسلسل
  • 1(01*(00)*0)*1
  • c: حول الرمز
  • 1
  • n: ابدأ تحويل تعبير نجمة كلين
  • (01*(00)*0)*
  • f: ابدأ تحويل التعبير المتسلسل
  • 01*(00)*0
  • e : حول الرمز
  • 0
  • h : ابدأ تحويل تعبير نجمة كلين
  • 1*
  • g : حول الرمز
  • 1
  • h : أنهي تحويل تعبير نجمة كلين
  • 1*
  • I : ابدأ تحويل تعبير نجمة كلين
  • (00)*
  • j : ابدأ تحويل التعبير المتسلسل
  • 00
  • i : حول الرمز
  • 0
  • k : حول الرمز
  • 0
  • j : أنهي تحويل التعبير المتسلسل
  • 00
  • l : أنهي تحويل تعبير نجمة كلين
  • (00)*
  • m : حول الرمز
  • 0
  • f : أنهي تحويل التعبير المتسلسل
  • 01*(00)*0
  • n : أنهي تحويل تعبير نجمة كلين
  • (01*(00)*0)*
  • o : حول الرمز
  • 1
  • d : أنهي تحويل التعبير المتسلسل
  • 1(01*(00)*0)*1
  • p : أنهي تحويل تعبير نجمة كلين
  • (1(01*(00)*0)*1)*
  • b : أنهي تحويل التعبير المتحد
  • 0|(1(01*(00)*0)*1)*
  • q : أنهي تحويل التعبير المتحد

علاوةً على ذلك، يظهر الجزء الأيمن العلوي البناء المنطقي ( شجرة السياق ) للتعبير مع توضيح التسلسل ( بفرض وجود وضوح متباين )

كذلك، أغفل وضوح ε كملصق انتقالي - الانتقالات غير الملصقة هي في الحقيقة انتقالات ε . حالة الإدخال والإخراج حسب التعبير الجذري q هي حالة لبداية وقبول الأتومات علي الترتيب.

وفي هذا الصدد، كمثال تظهر الصورة نتيجة خوارزمية بناء طومسون علي التعبير المنتظم (0|(1(01*(00)*0)*1)*)*

التي تشير إلي مجموعة أرقام ثنائية التي هي مضاعفات 3 .

من جهة ثانية، التعبيرات الفرعية تسمي a-q لأغراض مرجعية. يظهر الجزء الأيسر الأتوماتون المحدود الغير حتمي الناتج من خوارزمية طومسون مع حالة إدخال وإخراج لكل تعبير فرعي ملون بالأرجواني والسماوي علي الترتيب.

القواعد

وفي هذا السياق، تصور القواعد الآتية حسب ماهو وآخرين فيما تتبع s)N) وt)N) هما الأتومات المحدودة غير الحتمية للتعبيرات الفرعية sو t علي التوالي

يحول التعبير الفارغ إلى ε

(0|(1(01*(00)*0)*1)*)*

يوضح في الأسفل ما يعادل الحد الأدنى للأتومات الحتمية

المثال الصغير

إضافةً إلى ذلك، تظهر الصورة في الأسف نتيجة بناء طومسون علي (ε – a*b) . البيضاوي البمبي يناظر a

إضافةً إلى ذلك، ويناظر البيضاوي البترولي a* ويناظر البيضاوي الأخضر b ويناظر البيضاوي البرتقالي a*b ويناظر البيضاوي الأزرق ε

العلاقة بالخوارزميات الأخرى

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

ومن ناحية أخرى، خوارزمية طومسون واحدة من الخوارزميات العديدة لبناء الأتومات المحدودة غير الحتمية من تعبيرات منتظمة.

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.