نظام انتقالي

الموسوعة الحرة

في علم الحاسوب النظري ، يُعرف نظام الانتقال بأنه آلة حالة قد تحتوي على عدد لا نهائي من الحالات. ويُستخدم لوصف السلوك المحتمل للأنظمة المنفصلة . ويتكون من حالات وانتقالات بينها، والتي يمكن تصنيفها بتصنيفات مختارة من مجموعة محددة؛ وقد يظهر التصنيف نفسه في أكثر من انتقال. إذا كانت مجموعة التصنيفات أحادية ، فإن النظام يكون في جوهره غير مصنف، ويمكن حينها استخدام تعريف أبسط يحذف التصنيفات.

تتطابق أنظمة الانتقال رياضياً مع أنظمة إعادة الكتابة المجردة (كما هو موضح بالتفصيل في هذه المقالة) والرسوم البيانية الموجهة . وهي تختلف عن الأوتوماتا ذات الحالات المحدودة في عدة جوانب:

  • إن مجموعة الحالات ليست بالضرورة محدودة، أو حتى قابلة للعد.
  • إن مجموعة التحولات ليست بالضرورة محدودة، أو حتى قابلة للعد.
  • لم يتم تحديد حالة "بداية" أو حالات "نهائية".

يمكن تمثيل أنظمة الانتقال كرسوم بيانية موجهة.

التعريف الرسمي

بشكل رسمي، نظام الانتقال هو زوج(S،تي){\displaystyle (S,T)}أينS{\displaystyle S}هي مجموعة من الولايات وتي{\displaystyle T}، علاقة الانتقال ، هي مجموعة فرعية منS×S{\displaystyle S\times S}نقول إن هناك انتقالاً من حالةص{\displaystyle p}للتصريحq{\displaystyle q}لو(ص،q)∈تي{\displaystyle (p,q)\in T}، ورمز لهص→q{\displaystyle p\rightarrow q}.

نظام الانتقال المسمى هو مجموعة مرتبة(S،Λ،تي){\displaystyle (S,\Lambda ,T)}أينS{\displaystyle S}هي مجموعة من الحالات،Λ{\displaystyle \Lambda }هي مجموعة من التصنيفات، وتي{\displaystyle T}، علاقة الانتقال المصنفة ، هي مجموعة فرعية منS×Λ×S{\displaystyle S\times \Lambda \times S}نقول إن هناك انتقالاً من حالةص{\displaystyle p}للتصريحq{\displaystyle q}مع ملصقα{\displaystyle \alpha }إذا(ص،α،q)∈تي{\displaystyle (p,\alpha ,q)\in T}ودل عليه

ص→αq.{\displaystyle p\xrightarrow {\alpha } q\,.}

يمكن أن تمثل التصنيفات أشياء مختلفة تبعًا للغة المستخدمة. تشمل الاستخدامات الشائعة للتصنيفات تمثيل المدخلات المتوقعة، والشروط التي يجب أن تتحقق لتفعيل الانتقال، أو الإجراءات التي يتم تنفيذها أثناء الانتقال. وقد طُرحت أنظمة الانتقالات المصنفة في الأصل كأنظمة انتقالات مُسماة . [ 1 ]

حالات خاصة

  • إذا، لأي شيء معينص{\displaystyle p}وα{\displaystyle \alpha }، لا يوجد سوى صف واحد(ص،α،q){\displaystyle (p,\alpha ,q)}فيتي{\displaystyle T}ثم يقول المرء ذلكα{\displaystyle \alpha }حتمية ( لـص{\displaystyle p}).
  • إذا، لأي شيء معينص{\displaystyle p}وα{\displaystyle \alpha }يوجد على الأقل صف واحد(ص،α،q){\displaystyle (p,\alpha ,q)}فيتي{\displaystyle T}ثم يقول المرء ذلكα{\displaystyle \alpha }قابل للتنفيذ (لـص{\displaystyle p}).

صياغة الجبر المشترك

يمكن إعادة صياغة التعريف الرسمي على النحو التالي. أنظمة انتقال الحالة المصنفة علىS{\displaystyle S}مع ملصقات منΛ{\displaystyle \Lambda }يتوافق بشكل مباشر مع الدوالS→P(Λ×S){\displaystyle S\to {\mathcal {P}}(\Lambda \times S)}، أينP{\displaystyle {\mathcal {P}}}هو دالة مجموعة القوى (المتغيرة) . في ظل هذا التناظر.(S،Λ،تي){\displaystyle (S,\Lambda ,T)}يتم إرسالها إلىξتي:S→P(Λ×S){\displaystyle \xi _{T}:S\to {\mathcal {P}}(\Lambda \times S)}، كما هو محدد بواسطة

ص↦{(α،q)∈Λ×S|ص→αq}{\displaystyle p\mapsto \{\,(\alpha ,q)\in \Lambda \times S\mid p\xrightarrow {\alpha } q\,\}}.

بمعنى آخر، نظام انتقال الحالة المصنف هو جبر مشترك للدالةP(Λ×-){\displaystyle P(\Lambda \times {-})}.

العلاقة بين نظام الانتقال المسمى وغير المسمى

توجد علاقات عديدة بين هذه المفاهيم. بعضها بسيط، مثل ملاحظة أن نظام الانتقال المُصنَّف، حيث تتكون مجموعة التصنيفات من عنصر واحد فقط، يُكافئ نظام الانتقال غير المُصنَّف. مع ذلك، ليست كل هذه العلاقات بديهية بنفس القدر.

مقارنة مع أنظمة إعادة الكتابة المجردة

ككائن رياضي، يُعد نظام الانتقال غير المُصنَّف مطابقًا لنظام إعادة الكتابة المجرد (غير المُفهرس) . إذا اعتبرنا علاقة إعادة الكتابة مجموعةً مُفهرسةً من العلاقات، كما يفعل بعض الباحثين، فإن نظام الانتقال المُصنَّف يُكافئ نظام إعادة الكتابة المجرد حيث تكون الفهارس هي التصنيفات. مع ذلك، يختلف محور الدراسة والمصطلحات. ففي نظام الانتقال، يُهتم بتفسير التصنيفات كأفعال، بينما في نظام إعادة الكتابة المجرد، ينصب التركيز على كيفية تحويل الكائنات (إعادة كتابتها) إلى كائنات أخرى. [ 2 ]

الإضافات

في التحقق من النموذج ، يتم أحيانًا تعريف نظام الانتقال ليشمل وظيفة تسمية إضافية للحالات أيضًا، مما ينتج عنه مفهوم يشمل بنية كريپكي . [ 3 ]

لغات الفعل هي امتدادات لأنظمة الانتقال، وتضيف مجموعة من المترجمين F ، ومجموعة من القيم V ، ودالة تربط F × S بـ V. [ 4 ]

انظر أيضاً

مراجع

  1. ↑ روبرت م. كيلر (يوليو 1976) " التحقق الرسمي من البرامج المتوازية "، اتصالات ACM ، المجلد 19 ، العدد 7 ، الصفحات 371-384.
  2. ^ مارك بيزيم، جي دبليو كلوب، Roel de Vrijer ("Terese")، أنظمة إعادة كتابة المصطلح ، مطبعة جامعة كامبريدج، 2003، ISBN 0-521-39115-6الصفحات 7-8.
  3. ^ كريستيل باير . جوست بيتر كاتوين (2008). مبادئ فحص النماذج . مطبعة معهد ماساتشوستس للتكنولوجيا. ص. 20. رقم ISBN  978-0-262-02649-9.
  4. ↑ مايكل جيلفوند، فلاديمير ليفشيتز (1998) "لغات العمل"، لينشوبينغ المقالات الإلكترونية في علوم الحاسوب والمعلومات ، المجلد 3 ، العدد 16 .