نظام حالة الانتقال
المحتويات
تعريفًا بالموضوع، يعرّف نظام حالة انتقال في المعلوماتية النظرية على أنه آلة افتراضية تستعمل في الاحتساب. تحتوي هذه الآلة على مجموعة من الحالات والانتقالات بين هذه الحالات، من الممكن تعريف مجموعة من العناوين وعنونة الانتقالات بها، من الممكن أن يستعمل العنوان لأكثر من انتقال واحد. لا يتم عنونة النظام في حال احتوت مجموعة العناوين على عنصر واحد فقط، ومن الممكن استخدام تعريف بسيط للنظام يتم به حذف العناوين. وتعرض الأقسام التالية جوانب أخرى من الموضوع.
من جانب آخر، في أوتومات الحالة المنتهية يتم التمييز بين حالة «بداية» وحيدة، ومجموعة من حالات «النهاية».
من الممكن تمثيل نظام حالة-انتقال كـبيان موجه.
وفي هذا الصدد، ليس من الضروري أن تكون مجموعة الانتقالات منتهيةً، أو حتى قابلةً للعد في أنظمة حالة-انتقال.
وفي السياق ذاته، تتطابق أنظمة حالة انتقال رياضيات مع أنظمة إعادة الكتابة المجردة. بالمقابل فهي تختلف عن أوتومات الحالة المنتهية بعدة أمور:
إضافةً إلى ذلك، ليس من الضروري أن تكون مجموعة الحالات منتهيةً، أو حتى قابلةً للعد في أنظمة حالة-انتقال.
تعريف المصطلح
كذلك، نظام الانتقال المسمى الصف هو (S, Λ, →) حيث S هي مجموعة من الحالات، Λ هي مجموعة من التسميات و → هي علاقة بالتحولات المسمى (أي مجموعة فرعية من S × Λ × S). (p,α,q) ∈ → مكتوب على النحو:
ومن ناحية أخرى، إذا، بالنسبة لأي p و α معين، لا يوجد سوى مجموعة واحدة (p ،α ،q) في →، ثم يقول أحدهم أن α حتمية (لـ p). في حالة وجود p و α معينين، يوجد على الأقل صف واحد (p,α,q) في →، ثم يقول أحدهم أن α قابل للتنفيذ (لـ p).
ومن جهة أخرى، يمكن إعادة صياغة ذلك من حيث نظرية الفئات. كل نظام انتقال الحالة المسمى هي تقابل من إلى المجموعة الجزئية مفهرسة بواسطة مكتوب كـ , معرفة بواسطة .
وفي هذا السياق، من الناحية الرسمية، فإن النظام الانتقالي هو زوج (S, →) حيث S هي مجموعة من الحالات و → هي علاقة انتقالات الحالة (أي مجموعة فرعية من S × S). يتم كتابة الانتقال من الحالة p إلى الحالة q، أي (p, q) ∈ →، على النحو p → q.
وعلى صعيد آخر، لذا فإن نظام الانتقال المسمى بالعلامة هو F-Coalgebra للممر .
إضافةً إلى ذلك، ويمثل الانتقال من الحالة p إلى الحالة q مع التسمية α. يمكن أن تمثل التصنيفات أشياء مختلفة اعتمادًا على اللغة محل الاهتمام. تتضمن الاستخدامات النموذجية للعلامات تمثيل المدخلات المتوقعة، أو الشروط التي يجب أن تكون صحيحة لبدء النقل، أو الإجراءات التي يتم تنفيذها أثناء النقل. تم تقديم أنظمة الانتقال المسمى في الأصل كنظم انتقال مسماة.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟