عرض مصدر نظرية التشغيل الذاتي

{{بطاقة تخصص
|صنف فرعي من=
|جزء من = مبادئ نظريات التشغيل الرياضية
|يمتهنه = 
|مجال = النظريات الرياضيات
|موضوع=
|تاريخ =
|مؤسس=
}}
'''نظرية التشغيل الذاتي''' أو نظرية الآلات ذاتيـة التشغـيل والحركة أو نظـرية الآلات المجـرّدة {{إنج|Automata Theory}} هي [[نظرية]] تـهتم بتعريف ودراسـة خواص الآلات [[حاسوب|الحاسوبية]] المجرّدة.<ref>{{استشهاد بكتاب|الأخير=Yan|الأول=Song Y.|عنوان=An Introduction to Formal Languages and Machine Computation|سنة=1998|ناشر=World Scientific Publishing Co. Pte. Ltd.|مكان=Singapore|صفحات=155–156|مسار=https://books.google.com/books?id=ySOwQgAACAAJ| مسار أرشيف = https://web.archive.org/web/20191217052026/https://books.google.com/books?id=ySOwQgAACAAJ | تاريخ أرشيف = 17 ديسمبر 2019 }}</ref><ref>[http://people.cs.aau.dk/~srba/courses/MCS-07/TA.pdf ''Timed automata'']. {{Webarchive|url=https://web.archive.org/web/20200313182304/http://people.cs.aau.dk/~srba/courses/MCS-07/TA.pdf |date=13 مارس 2020}}</ref><ref>[https://planetmath.org/encyclopedia/CartesianClosedCategory.html Cartesian closed category]{{webarchive |url=https://web.archive.org/web/20111116215852/http://planetmath.org/encyclopedia/CartesianClosedCategory.html |date=November 16, 2011 }} {{وصلة مكسورة|تاريخ=2020-10-13|bot=JarBot}}</ref> تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل العديد من العمليات الحـاسوبيّة الأسـاسية فـي وقتـنا الحالي ، وتستخدم بكثـرة كـأداة تنفيذ ظواهر [[برهان رياضي|البرهان الرياضي]] الحاسوبي، لذلك تعتبر من أهمّ ركائز<nowiki/>[[علم الحاسوب النظري|علوم الحاسوب النظرية]] والتطبيقة.

== آلة ذاتية التشغيل ==
{{مفصلة|آلة ذاتية التشغيل}}
تعتبر الآلة ذاتية التشغيل [[نموذج رياضي|نموذجاً رياضياً]] للآلات المجرّدة؛ وهي آلات لها حالات مختلفة، تبدأ في حالة معيّنة ثم تنتقل من حالة إلى أخرى تبعاً لعوامل خارجيّة، تُمثَّل كسلسلة من الرموز الأساسية المتداخلة. يُقرأ الداخل رمزاً فرمزاً حتى تتوقف الآلة عند الانتهاء، أو عند حصول خطأ.

== استعمالات النظرية ==
تستعمل نظرية الآلات الذاتية التشغيل في [[علم المعلومات|علوم الحاسوب]] في حلول كثيرة منها:
* تطوير برامج للتّحقق من صحة وسلامة [[إلكترونيات رقمية|الدّارات الرقمية]].
* الانتاج (التركيبي) لمعظم [[مصرف (حوسبة)|مصرّفات]] [[لغة برمجة|لغات البرمجة]]؛ أي المكوّن الذي يهتمّ بتحليل وقطع النصّ الدّاخل ([[نص برمجي مصدري|مصدر البرنامج]]) إلى وحدات منطقية؛ كأسماء [[متغير (توضيح)|المتغيرات]]، و[[عدد|الأعداد]] و[[تبثر|التنقيط]].[[متغير (توضيح)|المتغيرات]]، و[[عدد|الأعداد]] و[[تبثر|التنقيط]].
* برامج لتحليل صفحات كثيرة من [[إنترنت|الإنترنت]]، والبحث عن كلمات معينة أو رسم جداول المدفوعات أوهياكل النماذج الصناعية.
* برامج للتحقّق من صحّة موارد البرامج الأخرى، فيما يعرف بالتحقق من هيكلة دفع النموذج (Model Checking).
* برامج محاكي التنسيق بين المتشابهات والوحدات الرياضية لنظريات الالآت ذاتية التشغيل.

== مثال آلة بسيطة ذاتية التشغيل ==
* لنفرض مثلا أننا نريد تمثيل [[مصباح]] [[كهرباء|كهربائي]] بسيط يمكن إطفاؤه وتشغيله بالضغط على [[زر]] إلكتروني. يمكن تمثيل حالتي المصباح المنطفئة والمشتغلة بالحالتين «''منطفئ''» و«''مشتغل''» على التّرتيب. يبقى المصباح في إحدى الحالتين حتى يقوم أحدهم بالضغط على الزر ليتحوّل المصباح إلى الحالة الأخرى.

يبين هذا الشكل الأول آلة المصباح السّابق وصفها:

[[ملف:Automaton-ar.png|بدون|تصغير|300بك|آلة ذاتية التشغيل تمثّل المصباح.]]

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

في بعض الآلات يمكن أيضا تحديد الحالات التي تنتهي عندها الآلة بنجاح، فيمكن إذن تسميتها الحالات القابلة أو النهائية. لنفرض مثلا أن لنا مصباحا آخر متطوّرا له ثلاث حالات للتشغيل: «''ضعيف''»، «''متوسّط''» و«''قويّ''»، ولدينا أيضا زران: أحدهما يقوم بإطفاء المصباح دائما فنسمي هذه العملية «''أطفئ''»، والآخر يزيد من شدّة المصباح فنسمّي تأثيره «''اضغط''». ينتقل المصباح بين حالات شدّة الضوء المختلفة بإرسال عمليّة «اضغط».

إذا أردنا جعل هدفنا هو تشغيل المصباح إلى أقصى قوة يمكن تمثيله بالشّكل التّالي:

[[ملف:Automaton2-ar.png|بدون|تصغير|500بك|آلة ذاتية التشغيل تمثّل مصباحا متطورا.]]

تمثّل الدائرة المضاعفة الحالة النهائية للآلة. تقبل هذه الآلة سلاسل الدّخل الآتية:
* ''اضغط-اضغط-اضغط''
* ''أطفئ-اضغط-اضغط-اضغط-اضغط''
* ''اضغط-اضغط-اضغط-أطفئ-اضغط-اضغط-اضغط''

لأنها تنتهي كلها عند الحالة النهائية. لكنها لا تقبل السلاسل التالية:
* ''اضغط-اضغط-اضغط-أطفئ''
* ''اضغط-أطفئ-اضغط-اضغط''

لأنها تنتهي عند حالات غير نهائية.

== التعريف الرياضي للآلات الذاتية التشغيل ==
أولا سنقوم بتعريف الآلة الذاتية التشغيل المحدّدة، وهي الآلة التي تكون دائما في حالة واحدة بعد قراءة أي رمز دخْل معيّن، وذلك لأنه عند كل حالة لا يوجد سوى نقلة واحدة لكل رمز دخْل. هناك أيضا [[#آلات ذاتية التشغيل غير محددة|الآلات غير المحدّدة]]، سيتم التفصيل في الفرق بين الإثنين في الأقسام التالية.

تعرّف الآلة الذاتية التشغيل المحدّدة <math>A</math> [[رياضيات]] بأنها خماسية <math>\langle Q, \Sigma, \delta, q_0, F\rangle</math> بحيث أن:

# <math>Q</math> هي [[مجموعة (توضيح)|مجموعة]] محدودة من الحالات.
# <math>\Sigma</math> هي [[مجموعة (توضيح)|مجموعة]] محدودة من رموز الدخْل.
# <math>\delta</math> هي [[دالة]] للنقل (أو التحول) معرفة بـ <math>\delta:Q \times \Sigma \rightarrow Q</math>، يكون مدخلها [[مثنوية|ثنائية]] من حالة (<math>q</math>) ورمز دخل (<math>a</math>)، ومخرجها حالة (<math>q\prime</math>)، أي <math>\delta(q,a)=q\prime</math>.
# <math>q_0</math> هي حالة البدأ التي يبدأ منها التشغيل، وهي تنتمي إلى المجموعة <math>Q</math>.
# <math>F</math> هي مجموعة من الحالات النهائية، وهي مجموعة محتواة في <math>Q</math>.

=== مثال المصباح المتقدم ===

في مثال المصباح المتقدّم السابق لدينا:
# مجموعة الحالات <math>Q</math> هي {''منطفئ''، ''ضعيف''، ''متوسط''، ''قوي''}.
# مجموع رموز الدخل <math>\Sigma</math> هي {''أطفئ''، ''اضغط''}.
# تم تمثيل الدالة <math>\delta</math> في الشكل السابق بالأسهم التي تنتقل من حالة إلى أخرى، ويمكن تعداد هذه الدالّة:
#* (''منطفئ''، ''أطفئ'') <math>\leftarrow</math> ''منطفئ''
#* (''منطفئ''، ''اضغط'') <math>\leftarrow</math> ''ضعيف''
#* (''ضعيف''، ''أطفئ'') <math>\leftarrow</math> ''منطفئ''
#* (''ضعيف''، ''اضغط'') <math>\leftarrow</math> ''متوسط''
#* (''متوسط''، ''أطفئ'') <math>\leftarrow</math> ''منطفئ''
#* (''متوسط''، ''اضغط'') <math>\leftarrow</math> ''قوي''
#* (''قوي''، ''أطفئ'') <math>\leftarrow</math> ''منطفئ''
#* (''قوي''، ''اضغط'') <math>\leftarrow</math> ''قوي''
# حالة البدء <math>q_0</math> هي ''منطفئ''.
# مجموعة الحالات النهائية <math>F</math> هي [[مجموعة (توضيح)|مجموعة]] وحيدة [[عنصر (توضيح)|العنصر]] وهي: {''قوي''}.

== أنواع الآلات الذاتية التشغيل ==
هناك ثلاث أنواع للآلات الذاتية التشغيل:
=== 1- آلات ذاتية التشغيل (حتمية) ===
كما ذكرنا سابقا فإن [[أتمتة محدودة قطعية|الآلات الذاتية التشغيل الحتمية]] ([[اللغة الإنجليزية|بالإنجليزية]] Determinisic Finite State Automaton أو باختصار DFA) تكون دائما في حالة واحدة فقط مهما كانت سلسلة الدخل التي قامت بتصريفها، وذلك لأنه لا توجد سوى نقلة واحدة لكل رمز دخل عند كل حالة.

كل الأمثلة السابقة هي [[أتمتة محدودة قطعية|آلات محدّدة]].

=== 2- آلات ذاتية التشغيل (غير محددة) ===
الآلات غير المحدّدة ([[اللغة الإنجليزية|بالإنجليزية]] Nondeterminisic Finite State Automaton أو باختصار NFA) هي آلات يمكن أن تكون في حالات محتملة عدّة عند كل لحظة، حيث يمكن لها أن تشتغل في جهات عدّة عند كلّ رمز دخل. يتم تحديد الاتجاه المناسب خطوة بعد خطوة عند كل رمز كلما رفض اتجاه ما هذا الرمز.

تكون الآلة غير المحدّدة في حالة نهائية (أي حالة قبول) إذا كانت أي من الحالات المحتملة الحالية حالة قبول.

'''مثال آلة غير محدّدة «لا حتمية»'''

الشكل التالي يوضح آلة غير محدّدة. لاحظ أن هذه الآلة تقبل كل السلاسل المتكونة من الأرقام 0 و1 والمنتهية بالسلسلة 1-0 (تُقرأ السلسلة من اليمين إلى اليسار). لاحظ انه في الحالة ''ح0''، عند إدخال الرمز ''1'' هناك حالتان محتملتان هما ''ح0'' نفسها و''ح1''.

[[ملف:nfa-ar.png|بدون|تصغير|400px|آلة ذاتية التشغيل غير محددة.]]

'''التعريف الرياضي'''

[[رياضيات|رياضياً]] التعريف هو نفس تعريف الآلة المحددة مع اختلاف وحيد في [[دالة|الدالة]]. الدالة <math>\delta</math> للآلة المحددة تنتج حالة واحدة فقط عند كل ثنائية حالة ورمز، أما [[دالة]] الآلة غير المحددة فتنتج [[مجموعة (توضيح)|مجموعة]] من الحالات. يمكن استبدال العنصر الثالث في قائمة التعريف السابقة بالتعريف:

* <math>\delta</math> هي دالّة للنقل (أو التحول) معرفة بـ <math>\delta:Q \times \Sigma \rightarrow \mathcal{P}(Q)</math>، يكون مدخلها ثنائية من حالة (<math>q</math>) ورمز دخل (<math>a</math>)، ومخرجها مجموعة حالات (<math>Q\prime</math>) تنتمي إلى المجموعة (<math>Q</math>)، أي <math>\delta(q,a)=Q\prime</math>.

يرمز <math>\mathcal{P}(Q)</math> إلى ناتج كل المجموعات التي يمكن تكوينها من عناصر المجموعة <math>Q</math>.

'''مثال الآلة غير المحددة السابق'''

# مجموعة الحالات <math>Q</math> هي { ''ح0''، ''ح1''، ''ح2''}.
# مجموع رموز الدخل <math>\Sigma</math> هي {''0''، ''1''}.
# الدالة <math>\delta</math>:
#* (''ح0''، ''0'') <math>\leftarrow</math> {''ح0''}
#* (''ح0''، ''1'') <math>\leftarrow</math> {''ح0'', ''ح1''}
#* (''ح1''، ''0'') <math>\leftarrow</math> {''ح2''}
# حالة البدأ <math>q_0</math> هي ''ح0''.
# مجموعة الحالات النهائية <math>F</math> هي مجموعة وحيدة العنصر وهي: {''ح2''}.

=== 3- آلات ذاتية التشغيل غير محددة بنقلات معدومة الرمز ===
[[اللغة الإنجليزية|بالإنجليزية]] Nondeterministic finite automata with ε transitions أو ε-NFA.

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

== تساوي الآلات ==
مع أن ذلك قد لا يكون واضحا للوهلة الأولى، إلا أن جميع أنواع الآلات الذاتية التشغيل السابقة لها نفس القوة الرياضية. أي يمكن تحويل أي آلة غير محددة مثلاً إلى آلة محدّدة تقبل نفس السلاسل والعكس صحيح. إلا أنه عادة تكون الآلة المحدّدة أكثر تعقيداً من الأنواع الأخرى.

فمثلاً، الآلة التالية لها نفس قوة [[آلة|الآلة]] غير المحدّدة السابقة. يمكن التحقق من ذلك بسهولة بتجريب مجموعة من السلاسل.

[[ملف:dfa-ar.png|بدون|تصغير|400px|آلة ذاتية التشغيل محددة مساوية للآلة السابقة.]]

== مراجع ==

{{مراجع}}

== وصلات خارجية ==

* [http://www.swisseduc.ch/informatik/exorciser/index.html Exorciser (بالألمانية)]

{{علم الحاسوب}}
{{معلوماتية}}
{{الرياضيات الصناعية والتطبيقية}}
{{شريط بوابات|تقانة المعلومات|علم الحاسوب|لسانيات|منطق}}
{{ضبط استنادي}}
{{روابط شقيقة}}

[[تصنيف:نظرية التشغيل الذاتي|*]]
[[تصنيف:علم الحاسوب|علم الحاسوب]]