English  

كتب formal definition

اذا لم تجد ما تبحث عنه يمكنك استخدام كلمات أكثر دقة.

عرض المزيد

التعريف الشكلي (معلومة)


هناك تعريفان لنوعين مماثلين من NFA: NFA وNFA-epsilon. يعرف النموذج العادي بالمرتب الخماسي (Q, Σ, T, q0, F) الذي يتألف من

  • مجموعة محدودة من الحالات Q
  • مجموعة محدودة من رموز المدخلات Σ
  • دالة انتقال T : Q × Σ → P(Q)
  • حالة ابتدائية (أو بداية) q0 ∈ Q
  • مجموعة من الحالات F تتميز بأنها حالات قبول (أو نهائية) F ⊆ Q

P(Q) هنا تشير إلى المجموعة المضاعفة من Q، وفي NFA الذي يحتوي على حركات إبسلون (أو NFA-lambda أو NFA-epsilon) تستبدل دالة الانتقال بأخرى تقبل المتسلسلة الفارغة ε كأحد مدخلاتها، بالتالي T : Q × (Σ ∪{ε}) → P(Q). يمكن إثبات أن NFA العادي والـ NFA الذي يحتوي على حركات إبسلون متكافئين ، فيمكن إنشاء أحدهما باستخدام الآخر بحيث يقبل كلاهما نفس اللغة.

المصدر: wikipedia.org