نظرية التشغيل الذاتي
المحتويات
قبل الخوض في التفاصيل، نظرية التشغيل الذاتي أو نظرية الآلات ذاتيـة التشغـيل والحركة أو نظـرية الآلات المجـرّدة هي نظرية تـهتم بتعريف ودراسـة خواص الآلات الحاسوبية المجرّدة. تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل الكثير من العمليات الحـاسوبيّة الأسـاسية فـي وقتـنا الحالي ، وتستعمل بكثـرة كـأداة تنفيذ ظواهر البرهان الرياضي الحاسوبي، لذلك تعتبر من أهمّ ركائزعلوم الحاسوب النظرية والتطبيقة. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
التعريف الرياضي
وعلى صعيد آخر، هي دالّة للنقل (أو التحول) معرفة بـ ، يكون مدخلها ثنائية من حالة ورمز دخل ، ومخرجها مجموعة حالات تنتمي إلى المجموعة ، أي .
وعلى صعيد آخر، رياضياً التعريف هو نفس تعريف الآلة المحددة مع اختلاف وحيد في الدالة. الدالة للآلة المحددة تنتج حالة واحدة فقط عند كل ثنائية حالة ورمز، أما دالة الآلة غير المحددة فتنتج مجموعة من الحالات. يمكن استبدال العنصر الثالث في قائمة التعريف السابقة بالتعريف:
وعلى صعيد آخر، يرمز إلى ناتج كل المجموعات التي يمكن تكوينها من عناصر المجموعة .
آلة ذاتية التشغيل
في هذا الإطار، تعتبر الآلة ذاتية التشغيل نموذجاً رياضياً للآلات المجرّدة؛ وهي آلات لها حالات مختلفة، تبدأ في حالة معيّنة ثم تنتقل من حالة إلى أخرى تبعاً لعوامل خارجيّة، تُمثَّل كسلسلة من الرموز الأساسية المتداخلة. يُقرأ الداخل رمزاً فرمزاً حتى تتوقف الآلة عند الانتهاء، أو عند حصول خطأ.
(ح1، 0) {ح2}
- حالة البدأ هي ح0.
- مجموعة الحالات النهائية هي مجموعة وحيدة العنصر وهي: {ح2}.
- 3- آلات ذاتية التشغيل غير محددة بنقلات معدومة الرمز
- بالإنجليزية Nondeterministic finite automata with ε transitions أو ε-NFA.
ومن جهة أخرى، هذه الآلات مشابهة للآلات غير المحددة مع إمكانية تنقلها من حالة إلى أخرى من دون إدخال أي رمز. يرمز للتنقل المعدوم بـ ε. وهذا يعني أن الآلة يمكن أن تكون في مجموعة الحالات التي يمكن التنقل إليها من الحالة الحالية باستعمال هذا الرمز.
(قوي، اضغط) قوي
مجموعة الحالات النهائية هي مجموعة وحيدة العنصر وهي: {قوي}.
حالة البدء هي منطفئ.
التعريف الرياضي للآلات الذاتية التشغيل
- تعرّف الآلة الذاتية التشغيل المحدّدة رياضيات بأنها خماسية بحيث أن:
- هي مجموعة محدودة من الحالات.
- هي مجموعة محدودة من رموز الدخْل.
كذلك، هي حالة البدأ التي يبدأ منها التشغيل، وهي تنتمي إلى المجموعة .
ومن ناحية أخرى، أولا سنقوم بتعريف الآلة الذاتية التشغيل المحدّدة، وهي الآلة التي تكون دائما في حالة واحدة بعد قراءة أي رمز دخْل معيّن، وذلك لأنه عند كل حالة لا يوجد سوى نقلة واحدة لكل رمز دخْل. هناك كذلك الآلات غير المحدّدة، سيتم التفصيل في الفرق بين الإثنين في الأقسام التالية.
وعلى صعيد آخر، هي دالة للنقل (أو التحول) معرفة بـ ، يكون مدخلها ثنائية من حالة ورمز دخل ، ومخرجها حالة ، أي .
هي مجموعة من الحالات النهائية، وهي مجموعة محتواة في .
استعمالات النظرية
تطوير برامج للتّحقق من صحة وسلامة الدّارات الرقمية.
ومن ناحية أخرى، برامج للتحقّق من صحّة موارد البرامج الأخرى، فيما يعرف بالتحقق من هيكلة دفع النموذج (Model Checking).
وفي هذا الصدد، تستعمل نظرية الآلات الذاتية التشغيل في علوم الحاسوب في حلول كثيرة منها:
في هذا الإطار، الانتاج (التركيبي) لأغلب مصرّفات لغات البرمجة؛ أي المكوّن الذي يهتمّ بتحليل وقطع النصّ الدّاخل (مصدر البرنامج) إلى وحدات منطقية؛ كأسماء المتغيرات، والأعداد والتنقيط.المتغيرات، والأعداد والتنقيط.
وفي هذا السياق، برامج لتحليل صفحات كثيرة من الإنترنت، والبحث عن كلمات معينة أو رسم جداول المدفوعات أوهياكل النماذج الصناعية.
كذلك، برامج محاكي التنسيق بين المتشابهات والوحدات الرياضية لنظريات الالآت ذاتية التشغيل.
اضغط-اضغط-اضغط-أطفئ-اضغط-اضغط-اضغط
وفي هذا السياق، لأنها تنتهي كلها عند الحالة النهائية. لكنها لا تقبل السلاسل التالية:
اضغط-اضغط-اضغط-أطفئ
اضغط-أطفئ-اضغط-اضغط
لأنها تنتهي عند حالات غير نهائية.
مثال الآلة غير المحددة السابق
- مجموعة الحالات هي { ح0، ح1، ح2}.
- مجموع رموز الدخل هي {0، 1}.
- الدالة :
- (ح0، 0) {ح0}
- (ح0، 1) {ح0, ح1}
مثال المصباح المتقدم
- في مثال المصباح المتقدّم السابق لدينا:
- مجموعة الحالات هي {منطفئ، ضعيف، متوسط، قوي}.
- مجموع رموز الدخل هي {أطفئ، اضغط}.
- (منطفئ، أطفئ) منطفئ
- (منطفئ، اضغط) ضعيف
- (ضعيف، أطفئ) منطفئ
- (ضعيف، اضغط) متوسط
- (متوسط، أطفئ) منطفئ
- (متوسط، اضغط) قوي
- (قوي، أطفئ) منطفئ
وفي السياق ذاته، تم تمثيل الدالة في الشكل السابق بالأسهم التي تنتقل من حالة إلى أخرى، ويمكن تعداد هذه الدالّة:
أنواع الآلات الذاتية التشغيل
كل الأمثلة السابقة هي آلات محدّدة.
وفي السياق ذاته، كما ذكرنا سابقا فإن الآلات الذاتية التشغيل الحتمية (بالإنجليزية Determinisic Finite State Automaton أو باختصار DFA) تكون دائما في حالة واحدة فقط مهما كانت سلسلة الدخل التي قامت بتصريفها، وذلك لأنه لا توجد سوى نقلة واحدة لكل رمز دخل عند كل حالة.
إضافةً إلى ذلك، تكون الآلة غير المحدّدة في حالة نهائية (أي حالة قبول) إذا كانت أي من الحالات المحتملة الحالية حالة قبول.
مثال آلة غير محدّدة «لا حتمية»
وفي هذا السياق، الآلات غير المحدّدة (بالإنجليزية Nondeterminisic Finite State Automaton أو باختصار NFA) هي آلات يمكن أن تكون في حالات محتملة عدّة عند كل لحظة، حيث يمكن لها أن تشتغل في جهات عدّة عند كلّ رمز دخل. يتم تحديد الاتجاه المناسب خطوة بعد خطوة عند كل رمز كلما رفض اتجاه ما هذا الرمز.
1- آلات ذاتية التشغيل (حتمية)
2- آلات ذاتية التشغيل (غير محددة)
هناك ثلاث أنواع للآلات الذاتية التشغيل:
إضافةً إلى ذلك، الشكل التالي يوضح آلة غير محدّدة. لاحظ أن هذه الآلة تقبل كل السلاسل المتكونة من الأرقام 0 و1 والمنتهية بالسلسلة 1-0 (تُقرأ السلسلة من اليمين إلى اليسار). لاحظ انه في الحالة ح0، عند إدخال الرمز 1 هناك حالتان محتملتان هما ح0 نفسها وح1.
مثال آلة بسيطة ذاتية التشغيل
وعلى صعيد آخر، تبدأ الآلة في حالة «منطفئ» ولذلك هناك السهم «ابدأ» الذي يشير لهذه الحالة. تسمّى الدوائر المرسومة حالات، جمع «حالة»، كلّ حالة تصف وضع المصباح في وقت ما. تمثل الأسهم الظاهرة ما يسمّى بالدّخل، وهذا بدوره يمثّل التأثيرات الخارجية على الآلة، فلدينا هنا رمز دخْل واحد يسمى «اضغط»، يقوم بنقل الآلة بين حالتي الانطفاء والاشتغال.
وفي هذا السياق، لنفرض مثلا أننا نريد تمثيل مصباح كهربائي بسيط يمكن إطفاؤه وتشغيله بالضغط على زر إلكتروني. يمكن تمثيل حالتي المصباح المنطفئة والمشتغلة بالحالتين «منطفئ» و«مشتغل» على التّرتيب. يبقى المصباح في إحدى الحالتين حتى يقوم أحدهم بالضغط على الزر ليتحوّل المصباح إلى الحالة الأخرى.
أطفئ-اضغط-اضغط-اضغط-اضغط
في هذا الإطار، إذا أردنا جعل هدفنا هو تشغيل المصباح إلى أقصى قوة يمكن تمثيله بالشّكل التّالي:
اضغط-اضغط-اضغط
وفي هذا السياق، تمثّل الدائرة المضاعفة الحالة النهائية للآلة. تقبل هذه الآلة سلاسل الدّخل الآتية:
يبين هذا الشكل الأول آلة المصباح السّابق وصفها:
من جهة ثانية، في بعض الآلات يمكن كذلك تحديد الحالات التي تنتهي عندها الآلة بنجاح، فيمكن إذن تسميتها الحالات القابلة أو النهائية. لنفرض مثلا أن لنا مصباحا آخر متطوّرا له ثلاث حالات للتشغيل: «ضعيف»، «متوسّط» و«قويّ»، ولدينا كذلك زران: أحدهما يقوم بإطفاء المصباح دائما فنسمي هذه العملية «أطفئ»، والآخر يزيد من شدّة المصباح فنسمّي تأثيره «اضغط». ينتقل المصباح بين حالات شدّة الضوء المختلفة بإرسال عمليّة «اضغط».
تساوي الآلات
ومن جهة أخرى، مع أن ذلك قد لا يكون واضحا للوهلة الأولى، إلا أن جميع أنواع الآلات الذاتية التشغيل السابقة لها نفس القوة الرياضية. أي يمكن تحويل أي آلة غير محددة مثلاً إلى آلة محدّدة تقبل نفس السلاسل والعكس صحيح. إلا أنه عادة تكون الآلة المحدّدة أكثر تعقيداً من الأنواع الأخرى.
وفي السياق ذاته، فمثلاً، الآلة التالية لها نفس قوة الآلة غير المحدّدة السابقة. يمكن التحقق من ذلك بسهولة بتجريب مجموعة من السلاسل.
مراجع
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟