نظرية الأوتوماتا ، الأوتوماتا المحدودة
يتم تحديد الهيكل والتصميم ومبدأ تشغيل الآلات المختلفة إلى حد كبير من خلال الغرض الوظيفي. يميز بين الآلات التكنولوجية ، والنقل ، والحاسوبية ، والعسكرية وغيرها. يتم تقديم مجمعات آلية كاملة مصممة لأداء العمليات التكنولوجية المعقدة على نطاق واسع في مختلف الصناعات. تم تصميم وبناء Automata بحيث يؤدي وظائف منطقية مختلفة (آلات منطقية).
نظرية الأوتوماتا — قسم علم التحكم الآليالتي نشأت تحت تأثير متطلبات تكنولوجيا أجهزة الكمبيوتر الرقمية وآلات التحكم. الأوتوماتا المنفصلة المدروسة في نظرية الأوتوماتا هي نماذج مجردة للأنظمة الحقيقية (التقنية والبيولوجية) التي تعالج المعلومات (الرقمية) المنفصلة في خطوات زمنية منفصلة.
تعتمد نظرية الأوتوماتا على مفاهيم رياضية دقيقة تضفي الطابع الرسمي على الأفكار البديهية حول أداء (سلوك) الآلة وبنيتها (الهيكل الداخلي).
في هذه الحالة ، يُفهم تحويل المعلومات دائمًا على أنه عملية تقوم بتحويل تسلسلات الإدخال المكونة من أحرف من الأبجدية المدخلة إلى تسلسلات إخراج مكونة من أحرف من الأبجدية الناتجة.
يستخدم على نطاق واسع جهاز المنطق الرياضي والجبر ونظرية الاحتمالات والتوافقية ونظرية الرسم البياني.
نمت مشكلة نظرية الأوتوماتا في بعض أجزائها (النظرية البنيوية للأوتوماتا) من نظرية دارات اتصال الترحيلالتي بدأت تتشكل في أواخر الثلاثينيات. شامل طرق الجبر المنطقي.
في النظرية الهيكلية للأوتوماتا ، تمت دراسة أنواع مختلفة من المخططات ، مصممة لوصف كيفية إنشاء أوتوماتيكية معقدة من مكونات أبسط (عناصر) متصلة بشكل صحيح في نظام.
اتجاه آخر ، يسمى النظرية المجردة للأوتوماتا ، يدرس سلوك الأوتوماتا (أي طبيعة تحويل المعلومات التي تقوم بها) ، بينما يستخرج من تفاصيل هيكلها الداخلي ، ونشأ في الخمسينيات.
في إطار النظرية المجردة للأتمتة ، يتم استنفاد محتوى مفهومي "التشغيل الآلي" و "الآلة" بشكل أساسي من خلال الوصف القياسي لتحويل المعلومات الذي يتم تنفيذه بواسطة إنسان آلي. يمكن أن يكون هذا التحول حتميًا ، ولكنه قد يكون أيضًا احتماليًا بطبيعته.
الأكثر دراسة هي الآلات الحتمية (الأوتوماتا) ، والتي تشمل الأوتوماتا المحدودة - الهدف الرئيسي للدراسة في نظرية الأوتوماتا.
تتميز آلة الحالة المحدودة بكمية محدودة من الذاكرة (عدد الحالات الداخلية) ويتم تعريفها باستخدام وظيفة الانتقال.مع بعض المثالية المعقولة ، يمكن اعتبار جميع الآلات الرياضية الحديثة وحتى الدماغ ، من وجهة نظر أدائها ، على أنها آلية محدودة.
تُستخدم المصطلحات "آلة متسلسلة" و "Milly automaton" و "Moore automaton" في الأدبيات (وليس بشكل موحد من قبل جميع المؤلفين) كمرادفات لمصطلح "أوتوماتيكي محدود" أو للتأكيد على ميزات معينة في وظائف الانتقال لمحدود إنسان.
إن Automata ذات الذاكرة غير المحدودة هي آلة Turing قادرة على إجراء (من المحتمل) أي تحويل فعال للمعلومات. نشأ مفهوم "آلة تورينج" قبل مفهوم "آلة الحالة المحدودة" ودُرس بشكل أساسي في نظرية الخوارزميات.
ترتبط نظرية الأوتوماتا المجردة ارتباطًا وثيقًا بالنظريات الجبرية المعروفة ، على سبيل المثال نظرية شبه المجموعة. من وجهة نظر تطبيقية ، فإن النتائج التي تميز تحويل المعلومات في إنسان آلي من حيث حجم الذاكرة هي موضع اهتمام.
هذا هو الحال ، على سبيل المثال ، في مشاكل التجارب على الأتمتة (أعمال إي إف مور ، وما إلى ذلك) ، حيث يتم الحصول على معلومات أو أخرى حول وظائف الانتقال الخاصة بالآلة أو حول سعة ذاكرتها من نتائج التجارب.
مهمة أخرى هي حساب فترات تسلسلات الإخراج ، بناءً على المعلومات المتاحة حول حجم ذاكرة الجهاز الآلي وفترات تسلسل الإدخال.
من الأهمية بمكان تطوير طرق لتقليل ذاكرة آلات الحالة المحدودة ودراسة سلوكها في بيئات عشوائية.
في نظرية الأوتوماتا المجردة ، فإن مشكلة التوليف هي التالية.من حيث بعض اللغات الرسمية بوضوح ، تتم كتابة الشروط لسلوك الإنسان الآلي المصمم (للحدث الممثل في الإنسان الآلي). في هذه الحالة ، من الضروري تطوير طرق وفقًا لكل شرط مكتوب:
1) معرفة ما إذا كانت هناك آلة حالة بحيث تلبي المعلومات التي يتم تحويلها من خلالها هذا الشرط ؛
2) إذا كانت الإجابة بنعم ، فسيتم إنشاء وظائف الانتقال لآلة الحالة المحدودة أو تقدير حجم ذاكرتها.
يفترض حل مهمة التوليف في مثل هذه الصياغة الإنشاء الأولي للغة ملائمة لتسجيل ظروف التشغيل لجهاز آلي باستخدام خوارزميات ملائمة للانتقال من التسجيل إلى الوظائف متعدية.
في النظرية البنيوية للأوتوماتا ، تتمثل مشكلة التوليف في بناء سلسلة من العناصر من نوع معين والتي تحقق أتمتة محدودة تعطى من خلال وظائفها الانتقالية. في هذه الحالة ، عادةً ما يذكرون بعض معايير الأمثل (على سبيل المثال ، الحد الأدنى لعدد العناصر) ويسعون للحصول على مخطط مثالي.
كما اتضح لاحقًا ، فإن هذا يعني أن بعض الأساليب والمفاهيم التي تم تطويرها مسبقًا فيما يتعلق بدارات اتصال الترحيل قابلة للتطبيق على دوائر من نوع آخر.
فيما يتعلق بتطوير التقنيات الإلكترونية ، فإن الأكثر انتشارًا هي المخططات من العناصر الوظيفية (شبكات منطقية). حالة خاصة من الشبكات المنطقية هي شبكات عصبية مجردة ، تسمى عناصرها الخلايا العصبية.
تم تطوير العديد من طرق التوليف ، اعتمادًا على نوع الدوائر وتحويل المعلومات المقصود منها (توليف أجهزة الترحيل).
ينظر -تصغير الدوائر التوافقية ، خرائط كارنو ، تركيب الدارات
آلة الدولة المحدودة - نموذج رياضي لنظام تحكم بحجم ذاكرة ثابت (غير قادر على الزيادة أثناء التشغيل).
مفهوم آلة الحالة المحدودة هو تجريد رياضي يميز الخصائص العامة لمجموعة من أنظمة التحكم (على سبيل المثال ، جهاز مرحل متعدد الحلقات). تتمتع كل هذه الأنظمة بسمات مشتركة من الطبيعي قبولها على أنها تعريف الإنسان المحدود.
يحتوي كل جهاز آلي مكتمل على مدخل يتعرض للتأثيرات الخارجية والعناصر الداخلية. لكل من عناصر الإدخال والعناصر الداخلية ، هناك عدد ثابت من الحالات المنفصلة التي يمكنهم اتخاذها.
يحدث التغيير في حالات الإدخال والعناصر الداخلية في لحظات منفصلة من الوقت ، وتسمى الفترات الفاصلة بينها علامات التجزئة. يتم تحديد الحالة الداخلية (حالة الأجزاء الداخلية) في نهاية الشريط بالكامل من خلال الحالة الداخلية وحالة الإدخال في بداية الشريط.
يمكن اختزال جميع التعريفات الأخرى للإنسان المنتهي إلى هذه الخاصية ، لا سيما التعريفات التي تفترض أن الأوتوماتيكي المحدود له ناتج يعتمد على الحالة الداخلية للأوتوماتون في وقت معين.
من حيث هذه الخاصية ، فإن طبيعة المدخلات والحالات الداخلية لا علاقة لها بوصف آلي كامل. بدلاً من المدخلات والحالات ، يمكنك فقط النظر إلى أرقامهم بترقيم عشوائي.
سيتم تعيين جهاز الحالة إذا تم تحديد اعتماد رقم حالته الداخلية على رقم الحالة الداخلية السابقة ورقم حالة الإدخال السابقة. يمكن أن تكون هذه المهمة في شكل جدول نهائي.
هناك طريقة شائعة أخرى لتعريف الإنسان الآلي الكامل وهي بناء ما يسمى بـ مخططات الانتقال. غالبًا ما يُطلق على حالات الإدخال اسم ببساطة المدخلات ، والحالات الداخلية هي ببساطة حالات.
يمكن أن تكون آلة الحالة المحدودة نموذجًا لكل من الأجهزة التقنية وبعض الأنظمة البيولوجية. من النوع الأول Automata ، على سبيل المثال ، أجهزة الترحيل وأجهزة الكمبيوتر الإلكترونية المختلفة ، بما في ذلك. وحدات تحكم منطقية قابلة للبرمجة.
في حالة جهاز الترحيل ، يتم لعب دور حالات الإدخال من خلال مجموعات من حالات العناصر الحساسة لجهاز الترحيل (كل مجموعة من هذه الحالات هي "حالة معقدة" ، تتميز بإشارة إلى جميع العناصر الحساسة لـ هذه الحالات المنفصلة التي لديهم في لحظة معينة). وبالمثل ، فإن مجموعات حالات العناصر الوسيطة لجهاز الترحيل تعمل كحالات داخلية.
وحدة التحكم المنطقية القابلة للبرمجة (PLC) هي مثال على جهاز إجراء الترحيل الذي يمكن تسميته بآلة حالة قائمة بذاتها.
في الواقع ، بمجرد إدخال البرنامج في PLC وبدء وحدة التحكم في الحساب ، فإنه لا يتعرض للتأثيرات الخارجية ويتم تحديد كل حالة لاحقة تمامًا من خلال حالتها السابقة. يمكننا أن نفترض أن الإدخال له نفس الحالة في كل دورة ساعة.
على العكس من ذلك ، فإن أي آلة ذات حالة محدودة لديها حالة الإدخال الوحيدة الممكنة تسمى بشكل طبيعي مستقلة ، لأنه في هذه الحالة لا تحمل البيئة الخارجية أي معلومات تتحكم في سلوكها.
أنظر أيضا:
استخدام أنظمة المعالجات الدقيقة في الهندسة الكهربائية على سبيل المثال لاستخدام PLC