مقدمه عن نظرية الآلات المجرّدة - Automata Theory

2013-07-11

التعريف

هي نظرية تهتم بتعريف ودراسة خواص الآلات الحاسوبية المجرّدة. تاريخيّا دُرست قضايا هذه النظرية كتصوّر للحساب الإلكتروني قبل ظهور الحواسيب الحديثة لكنّها أثبتت قدرتها على تمثيل العديد من العمليات الحاسوبيّة في وقتنا الحالي، وتستخدم بكثرة كأداة للبرهان الرياضي الحاسوبي، لذلك فهي تعتبر من أهمّ ركائز علوم الحاسوب النظرية والأنظمة المنهجية.

مثال آلة بسيطة ذاتية التشغيل

لنفرض مثلا أننا نريد تمثيل مصباح كهربائي بسيط يمكن إطفاؤه وتشغيله بالضغط على زر إلكتروني. يمكن تمثيل حالتي المصباح المنطفئة والمشتغلة بالحالتين "منطفئ" و"مشتغل" على التّرتيب. يبقى المصباح في إحدى الحالتين حتى يقوم أحدهم بالضغط على الزر ليتحوّل المصباح إلى الحالة الأخرى.

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

اضف وصف الصورة هنا

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

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

اضف وصف الصورة هنا

تمثّل الدائرة المضاعفة (قوي) الحالة النهائية للآلة (أي حاله محاطه بدائرتين فهي حاله هائيه). تقبل هذه الآلة سلاسل الدّخل الآتية:

  • اضغط-اضغط-اضغط
  • أطفئ-اضغط-اضغط-اضغط-اضغط
  • اضغط-اضغط-اضغط-أطفئ-اضغط-اضغط-اضغط

    لأنها تنتهي كلها عند الحالة النهائية. لكنها لا تقبل السلاسل التالية:

    • اضغط-اضغط-اضغط-أطفئ
    • اضغط-أطفئ-اضغط-اضغط

لأنها تنتهي عند حالات غير نهائية أي لا نستطيع أن نصل إلى الحاله النهائيه

هذه مقدمه بسيطه عن ماهيه نظريه الآلات المجردة، و سوف نقوم بشرح جميع المفاهيم و التعريف الرياضي للآلات الذاتية التشغيل مع الأمثله.

المصدر :

  • Introduction to the Theory of Computation - Michael Sipser
  • نظریة الحوسبة - د. أيمن حمارشه
  • ويكيبيديا
4


محمد عنيني
محمد عنينيمنذ 3 سنوات

موضوع رائع ومبسط.. مشكور أخ رمزي.

في انتظار التتمة :)

1

رمزي القريني
رمزي القرينيمنذ 3 سنوات

بإذن الله

1

بلال العفوري
بلال العفوريمنذ 3 سنوات

هل يمكن ان تفيدنا نظرية الآلات في تصميم الدوائر الالكترونية المنطقية ؟

1

GHOmar
GHOmarمنذ 3 سنوات

@بلال نعم في تصميم Sequential Logic Circuits https://en.wikipedia.org/wiki/Finite-state_machine#Hardware_applications

1

مؤيد السعدي
مؤيد السعديمنذ 3 سنوات

أظن أن الأمر بالعكس. الآلات المجردة FSM هي الحاجة (التي هي أم الإختراع) أي هي تفيد في تقسيم المطلوب إلى مراحل وخطوات يتم الانتقال بطريقة محددة لكنها لا تستخدم في تصميم الدوائر بل بالعكس يمكن محاكاتها بالدوائر .

وهي فكرة مجردة في عقول الرياضيين تماما مثل آلة تورنج (لكن آلة تورنج أقوى منها) https://en.wikipedia.org/wiki/Turing_machine

بمعنى أنا لدي فكرة كتبتها على شكل DFA هذا لا يعني بالضرورة أني سرت خطوة واحدة في تصميم الدارة الخاصة بها.

إن كنت مهتما بمجال تصميم الدوائر والرقائق عليك استعمال لغات وصف العتاد HDL مثل Verilog و VHDL

https://en.wikipedia.org/wiki/Verilog https://en.wikipedia.org/wiki/VHDL

1

Test User