- تُستخدم الآلات المحدودة للتعرف على الأنماط.
- يأخذ سلسلة الرمز كمدخل ويغير حالته وفقًا لذلك. عندما يتم العثور على الرمز المطلوب، يحدث الانتقال.
- في وقت الانتقال، يمكن للأوتوماتا إما الانتقال إلى الحالة التالية أو البقاء في نفس الحالة.
- الأوتوماتية المحدودة لها حالتان، قبول الدولة أو رفض الدولة . عندما تتم معالجة سلسلة الإدخال بنجاح، ويصل الجهاز إلى حالته النهائية، فسوف يقبل.
التعريف الرسمي لـ FA
الإنسان الآلي المحدود عبارة عن مجموعة من 5 صفوف (Q، ∑، δ، q0، F)، حيث:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
نموذج الأتمتة المحدودة:
يمكن تمثيل الآلات المتناهية عن طريق شريط الإدخال والتحكم المحدود.
شريط الإدخال: إنه شريط خطي يحتوي على عدد معين من الخلايا. يتم وضع كل رمز إدخال في كل خلية.
السيطرة المحدودة: يقرر التحكم المحدود الحالة التالية عند تلقي مدخلات معينة من شريط الإدخال. يقرأ قارئ الشريط الخلايا واحدة تلو الأخرى من اليسار إلى اليمين، وفي المرة الواحدة تتم قراءة رمز إدخال واحد فقط.
أنواع الأوتوماتا:
هناك نوعان من الأتمتة المحدودة:
- DFA (أتمتة حتمية محدودة)
- NFA (أتمتة محدودة غير حتمية)
1. دي إف إيه
يشير DFA إلى أتمتة حتمية محدودة. الحتمية تشير إلى تفرد الحساب. في DFA، ينتقل الجهاز إلى حالة واحدة فقط لحرف إدخال معين. لا يقبل DFA النقل الفارغ.
2. نفا
NFA لتقف على أتمتة محدودة غير حتمية. يتم استخدامه لنقل أي عدد من الحالات لمدخل معين. يمكنه قبول الخطوة الفارغة.
بعض النقاط المهمة حول DFA وNFA:
- كل DFA هو NFA، لكن NFA ليس DFA.
- يمكن أن تكون هناك حالات نهائية متعددة في كل من NFA وDFA.
- يتم استخدام DFA في التحليل المعجمي في المترجم.
- NFA هو أكثر من مفهوم نظري.