آلات الحالات المنتهية – إشارة المرور والأوتومات الحتمي وغير الحتمي واللغات النمطية

ماذا تعرض

لآلة الحالات المنتهية مجموعة منتهية من الحالات، وحالة بداية، وأبجدية مدخلات، وانتقالات على الصورة: حالة + رمز → الحالة التالية. وهي لا تتذكر شيئًا سوى حالتها الحالية. تُصدر آلة ميلي مخرجاتها على الانتقالات، وتربط آلة مور المخرجات بالحالات، أما آلة القبول فتجيب بنعم أو لا: هل تنتمي الكلمة إلى لغة ما؟ واللغات التي تقبلها الأوتومات المنتهية هي بالضبط اللغات النمطية، التي تصفها أيضًا التعابير النمطية والقواعد النمطية. ويمكن تحويل كل NFA إلى DFA مكافئ ببناء المجموعات الجزئية.

طريقة الاستخدام

في وضع «آلة ذات مخرجات» اختر «آلة نموذجية» وانقر «خطوة» أو «تشغيل» لإدخال رموز الشريط واحدًا تلو الآخر؛ وترسل أزرار الرموز أحداثًا إضافية. في وضع «آلة القبول» اختر «أوتومات نموذجي»، واكتب «كلمة الإدخال» وتتبّعها خطوة بخطوة، ثم استخدم «اختبار» أو «اعرض الكلمات المقبولة». افتح «تحرير الآلة» لإضافة الحالات وسحبها وربطها، أو انقر «تحويل NFA إلى DFA».

المعاملات القابلة للتغيير

• الوضع آلة ذات مخرجات, آلة القبول
• آلة نموذجية (وضع آلة ذات مخرجات) إشارة المرور, آلة البيع, البوابة الدوارة
• أوتومات نموذجي (وضع آلة القبول) DFA: أعداد ثنائية تقبل القسمة على 3, NFA: كلمات تنتهي بـ ab, DFA: كلمات تنتهي بـ ab, DFA: عدد زوجي من الآحاد (بت التماثل)
• كلمة الإدخال (فارغة = كلمة نموذجية)
• سرعة التشغيل 0.5–4 رمز/ثانية
• فتح لوحة تحرير الآلة

أسئلة للاستكشاف

1. ما تفاصيل إشارة المرور الحقيقية التي حُذفت من النموذج، ولماذا يُعد ذلك مقبولًا؟
2. هل يقبل أوتومات القابلية للقسمة على 3 الكلمة 110، وما الحالات التي يمر بها خطوة بخطوة؟
3. لماذا يحتاج NFA الكلمات المنتهية بـ ab إلى انتقالات أقل من DFA المكافئ له؟