نظرية التشغيل الذاتي أو نظرية الآلات ذاتية التشغيل أو نظرية الآلات المجرّدة (الإنجليزية: Automata Theory) هي نظرية تهتم بتعريف و دراسة خواص الآلات الحاسوبية المجرّدة. تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل العديد من العمليات الحاسوبيّة في وقتنا الحالي، و تستخدم بكثرة كأداة للبرهان الرياضي الحاسوبي، لذلك فهي تعتبر من أهمّ ركائز علوم الحاسوب النظرية و الأنظمة المنهجية.
فهرس |
تعتبر الآلة ذاتية التشغيل نموذجاً رياضيا للآلات المجرّدة؛ وهي آلات لها حالات مختلفة، تبدأ في حالة معيّنة ثم تنتقل من حالة إلى أخرى تبعاً لعوامل خارجيّة، تُمثَّل كسلسلة من الرموز الداخلة. يُقرأ الدخل رمزاً فرمزاً حتى تتوقف الآلة عند الانتهاء، أو عند حصول خطأ.
تستعمل نظرية الآلات الذاتية التشغيل في علوم الحاسوب في حلول كثيرة منها:
يبين هذا الشكل الأول آلة المصباح السّابق وصفها:
تبدأ الآلة في حالة "منطفئ" و لذلك هناك السهم "ابدأ" الذي يشير لهذه الحالة. تسمّى الدوائر المرسومة حالات، جمع "حالة"، كلّ حالة تصف وضع المصباح في وقت ما. تمثل الأسهم الظاهرة ما يسمّى بالدّخل، و هذا بدوره يمثّل التأثيرات الخارجية على الآلة، فلدينا هنا رمز دخْل واحد يسمى "اضغط"، يقوم بنقل الآلة بين حالتي الانطفاء و الاشتغال.
في بعض الآلات يمكن أيضا تحديد الحالات التي تنتهي عندها الآلة بنجاح، فيمكن إذن تسميتها الحالات القابلة أو النهائية. لنفرض مثلا أن لنا مصباحا آخر متطوّرا له ثلاث حالات للتشغيل: "ضعيف"، "متوسّط" و "قويّ"، و لدينا أيضا زرين: أحدهما يقوم بإطفاء المصباح دائما فنسمي هذه العملية "أطفئ"، و الآخر يزيد من شدّة المصباح فنسمّي تأثيره "اضغط". ينتقل المصباح بين حالات شدّة الضوء المختلفة بإرسال عمليّة "اضغط".
إذا أردنا جعل هدفنا هو تشغيل المصباح إلى أقصى قوة يمكن تمثيله بالشّكل التّالي:
تمثّل الدائرة المضاعفة الحالة النهائية للآلة. تقبل هذه الآلة سلاسل الدّخل الآتية:
لأنها تنتهي كلها عند الحالة النهائية. لكنها لا تقبل السلاسل التالية:
لأنها تنتهي عند حالات غير نهائية.
أولا سنقوم بتعريف الآلة الذاتية التشغيل المحدّدة، و هي الآلة التي تكون دائما في حالة واحدة بعد قراءة أي رمز دخْل معيّن، وذلك لأنه عند كل حالة لا يوجد سوى نقلة واحدة لكل رمز دخْل. هناك أيضا الآلات غير المحدّدة، سيتم التفصيل في الفرق بين الإثنين في الأقسام التالية.
تعرّف الآلة الذاتية التشغيل المحدّدة A رياضيات بأنها خماسية بحيث أن:
في مثال المصباح المتقدّم السابق لدينا:
هناك ثلاث أنواع للآلات الذاتية التشغيل:
كما ذكرنا سابقا فإن الآلات الذاتية التشغيل المحدّدة (بالإنجليزية Determinisic Finite State Automaton أو باختصار DFA) تكون دائما في حالة واحدة فقط مهما كانت سلسلة الدخل التي قامت بتصريفها، و ذلك لأنه لا توجد سوى نقلة واحدة لكل رمز دخل عند كل حالة.
كل الأمثلة السابقة هي آلات محدّدة.
الآلات غير المحدّدة (بالإنجليزية Nondeterminisic Finite State Automaton أو باختصار NFA) هي آلات يمكن أن تكون في حالات محتملة عدّة عند كل لحظة، حيث يمكن لها أن تشتغل في جهات عدّة عند كلّ رمز دخل. يتم تحديد الاتجاه المناسب خطوة بعد خطوة عند كل رمز كلما رفض اتجاه ما هذا الرمز.
تكون الآلة غير المحدّدة في حالة نهائية (أي حالة قبول) إذا كانت أي من الحالات المحتملة الحالية حالة قبول.
الشكل التالي يوضح آلة غبر محدّدة. لاحظ أن هذه الآلة تقبل كل السلاسل المتكونة من الأرقام 0 و 1 و المنتهية بالسلسلة 1-0 (تُقرأ السلسلة من اليمين إلى اليسار). لاحظ انه في الحالة ح0، عند إدخال الرمز 1 هناك حالتين محتملتين هما ح0 نفسها و ح1.
رياضيا التعريف هو نفس تعريف الآلة المحددة مع اختلاف و حيد في الدالة. الدالة δ للآلة المحددة تنتج حالة واحدة فقط عند كل ثنائية حالة و رمز، أما دالة الآلة غير المحددة فتنتج مجموعة من الحالات. يمكن استبدال العنصر الثالث في قائمة التعريف السابقة بالتعريف:
يرمز إلى مجموعة كل المجموعات التي يمكن تكوينها من عناصر المجموعة Q.
بالإنجليزية Nondeterministic finite automata with ε transitions أو ε-NFA.
هذه الآلات مشابهة للآلات غير المحددة مع إمكانية تنقلها من حالة إلى أخرى من دون إدخال أي رمز. يرمز للتنقل المعدوم بـ ε. و هذا يعني أن الآلة يمكن أن تكون في مجموعة الحالات التي يمكن التنقل إليها من الحالة الحالية باستعمال هذا الرمز.
مع أن ذلك قد لا يكون واضحا للوهلة الأولى، إلا أن جميع أنواع الآلات الذاتية التشغيل السابقة لها نفس القوة الرياضية. أي يمكن تحويل أي آلة غير محددة مثلا إلى آلة محدّدة تقبل نفس السلايل و العكس صحيح. إلا أنه عادة تكون الآلة المحدّدة أكثر تعقيدا من الأنواع الأخرى.
فمثلا، الآلة التالية لها نفس قوة الآلة غير المحدّدة السابقة. يمكن التحقق من ذلك بسهولة بتجريب مجموعة من السلاسل.
فروع المعلوماتية |
الحقول الأساسية للمعلوماتية |
تحرير |
---|---|---|
معلوماتية نظرية | تحسيب | خوارزميات | نظرية المعلومات | نظرية الأتمتة | نظرية المخططات | نظرية التعقيد | تعمية | لغات شكلية | استمثال | بناء المترجمات البرمجية | نظرية أنظمة التشغيل | نظرية قواعد البيانات | نظرية التعمية | طريقة شكلية | تحسيب طبيعي | |
معلوماتية عملية | أنظمة تشغيل | حوسبة | رسوميات الحاسب | قواعد بيانات | بنى بيانات | برمجة | |
معلوماتية تقنية | تكنولوجيا المعلومات | شبكات الحاسب | عتاد الحاسب | أمن الحاسب | اختراق الحاسب | |
معلوماتية تطبيقية | أنظمة معلومات | معلوماتية حيوية | معلوماتية جيولوجية | كيمياء حاسوبية | فيزياء حاسوبية | معلوماتية اقتصادية | وسائط متعددة | |
ذكاء اصطناعي | تعلم آلي | معلوماتية عصبونية | طرق التصنيف | لغويات حاسوبية | |
برمجيات | لغات البرمجة | برمجيات حرة | برمجيات تجارية | |
أنظمة التشغيل | دوس | ويندوز | يونكس | لينكس | ماك أو إس | نتوير | تاريخ أنظمة تشغيل الحاسوب | |
عتاد الحاسب | وحدة المعالجة المركزية | ذاكرة الحاسب | القرص الصلب | اللوحة الأم |