الأوتوماتون الحتمي المحدود

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 44 صور
الموسوعة الحرة

مثال على آلة حالة محدودة حتمية تقبل فقط الأعداد الثنائية التي هي مضاعفات العدد 3. الحالة S0 هي حالة البداية وحالة القبول في آن واحد. على سبيل المثال، السلسلة "1001" تؤدي إلى تسلسل الحالات S0 ، S1 ، S2 ، S1 ، S0 ، وبالتالي تُقبل.

في نظرية الحوسبة ، وهي فرع من علوم الحاسوب النظرية ، تُعرف الآلة المحدودة الحتمية ( DFA ) - والمعروفة أيضًا باسم المُستقبِل المحدود الحتمي ( DFA )، أو آلة الحالة المحدودة الحتمية ( DFSM )، أو آلة الحالة المحدودة الحتمية ( DFSA ) - بأنها آلة حالة محدودة تقبل أو ترفض سلسلة معينة من الرموز، من خلال المرور بتسلسل حالات مُحدد بشكل فريد بواسطة السلسلة. [ 1 ] تشير كلمة "حتمية" إلى تفرد عملية الحساب. في سعيهما لإيجاد أبسط النماذج لتمثيل آلات الحالة المحدودة، كان وارن ماكولوتش ووالتر بيتس من أوائل الباحثين الذين قدموا مفهومًا مشابهًا للآلات المحدودة في عام 1943. [ 2 ] [ 3 ]

يوضح الشكل آلة حالة محدودة حتمية باستخدام مخطط الحالة . في هذه الآلة، توجد ثلاث حالات: S0 و S1 و S2 ( مُمثلة بيانيًا بدوائر). تستقبل الآلة سلسلة محدودة من الأصفار والآحاد كمدخلات. لكل حالة، يوجد سهم انتقال يؤدي إلى الحالة التالية لكل من 0 و1. عند قراءة رمز، تنتقل الآلة بشكل حتمي من حالة إلى أخرى باتباع سهم الانتقال. على سبيل المثال، إذا كانت الآلة حاليًا في الحالة S0 وكان رمز الإدخال الحالي هو 1، فإنها تنتقل بشكل حتمي إلى الحالة S1 . تحتوي الآلة على حالة بدء (مُمثلة بيانيًا بسهم قادم من العدم) حيث تبدأ العمليات الحسابية، ومجموعة من حالات القبول (مُمثلة بيانيًا بدائرتين) التي تُساعد في تحديد نجاح العملية الحسابية.

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

تم تعميم الأوتوماتا المحدودة الحتمية (DFAs) لتشمل الأوتوماتا المحدودة غير الحتمية (NFAs) ، والتي قد تحتوي على عدة أسهم تحمل نفس التسمية بدءًا من حالة معينة. باستخدام طريقة بناء مجموعة القوى ، يمكن ترجمة كل أوتوماتا محدودة غير حتمية إلى أوتوماتا محدودة حتمية تتعرف على نفس اللغة. تتعرف كل من الأوتوماتا المحدودة الحتمية والأوتوماتا المحدودة غير الحتمية على مجموعة اللغات المنتظمة بدقة . [ 1 ]

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

الآلة المحدودة الحتمية M هي مجموعة خماسية ، ( Q ، Σ، δ ، q0 ، F ) ، تتكون من

  • مجموعة محدودة من الحالات Q
  • مجموعة محدودة من رموز الإدخال تسمى الأبجدية Σ
  • دالة انتقالية δ  : Q × Σ → Q
  • حالة أولية (أو حالة بداية)q0∈سؤال{\displaystyle q_{0}\in Q}
  • مجموعة من الحالات المقبولة (أو النهائية)F⊆سؤال{\displaystyle F\subseteq Q}

ليكن w = a₁ a₂ ... aₙ سلسلةً على الأبجدية Σ . يقبل الأوتوماتون M السلسلة w إذا وُجد تسلسل من الحالات، r₀ ، r₁ ، ... ، rₙ ، في Q بالشروط التالية :

  1. r 0 = q 0
  2. r i +1 = δ ( r i , a i +1 ) , لـ i = 0, ..., n − 1
  3. رن∈F{\displaystyle r_{n}\in F}.

بعبارة أخرى، ينص الشرط الأول على أن الآلة تبدأ من حالة البداية q₀ . وينص الشرط الثاني على أنه عند إعطاء كل حرف من السلسلة w ، ستنتقل الآلة من حالة إلى أخرى وفقًا لدالة الانتقال δ . أما الشرط الأخير فينص على أن الآلة تقبل w إذا تسبب آخر إدخال لـ w في توقفها في إحدى حالات القبول. وإلا، يُقال إن الآلة ترفض السلسلة. مجموعة السلاسل التي تقبلها الآلة M هي اللغة التي تتعرف عليها ، ويُرمز لهذه اللغة بـ L ( M ) .

يُعرف نظام الأوتوماتون المحدود الحتمي بدون حالات قبول وبدون حالة بداية باسم نظام الانتقال أو شبه الأوتوماتون .

للحصول على مقدمة أكثر شمولاً للتعريف الرسمي، انظر نظرية الأوتوماتا .

مثال

المثال التالي هو لآلة حتمية محدودة M ، مع أبجدية ثنائية، والتي تتطلب أن يحتوي المدخل على عدد زوجي من الأصفار.

مخطط الحالة لـ M

M = ( Q , Σ, δ , q 0 , F ) حيث

0
1
S 1S 2S 1
S 2S 1S 2

تمثل الحالة S1 وجود عدد زوجي من الأصفار في المدخلات حتى الآن، بينما تشير الحالة S2 إلى وجود عدد فردي. لا يؤثر وجود الرقم 1 في المدخلات على حالة الآلة. عند انتهاء المدخلات، ستُظهر الحالة ما إذا كانت المدخلات تحتوي على عدد زوجي من الأصفار أم لا. إذا كانت المدخلات تحتوي على عدد زوجي من الأصفار، فستنتهي الآلة M في الحالة S1 ، وهي حالة قبول، وبالتالي سيتم قبول سلسلة المدخلات.

اللغة التي يتعرف عليها M هي اللغة المنتظمة المعطاة بالتعبير المنتظم(1*) (0 (1*) 0 (1*))* ، حيث *يمثل نجمة كلين ، على سبيل المثال، 1*يشير إلى أي عدد (ربما صفر) من الواحدات المتتالية.

الاختلافات

كامل وغير كامل

وفقًا للتعريف أعلاه، فإن الآلات المحدودة الحتمية تكون دائمًا كاملة : فهي تحدد من كل حالة انتقالًا لكل رمز إدخال.

على الرغم من أن هذا هو التعريف الأكثر شيوعًا، إلا أن بعض المؤلفين يستخدمون مصطلح "الآلة المحدودة الحتمية" لمفهوم مختلف قليلاً: وهي آلة تحدد انتقالًا واحدًا على الأكثر لكل حالة ولكل رمز إدخال؛ ويُسمح لدالة الانتقال بأن تكون جزئية . [ 5 ] عندما لا يتم تحديد أي انتقال، تتوقف هذه الآلة.

الأتمتة المحلية

الآلة المحلية هي آلة حتمية محدودة، وليست بالضرورة كاملة، حيث تؤدي جميع الحواف التي تحمل نفس التسمية إلى رأس واحد. تقبل الآلات المحلية فئة اللغات المحلية ، وهي اللغات التي يُحدد فيها انتماء كلمة ما إلى اللغة بواسطة "نافذة منزلقة" طولها اثنان على تلك الكلمة. [ 6 ] [ 7 ]

الرسم البياني لمايهيل على الأبجدية A هو رسم بياني موجه بمجموعة رؤوس A ومجموعات فرعية من الرؤوس تحمل تسميات "بداية" و"نهاية". اللغة التي يقبلها الرسم البياني لمايهيل هي مجموعة المسارات الموجهة من رأس البداية إلى رأس النهاية: وبالتالي، يعمل الرسم البياني كآلة. [ 6 ] فئة اللغات التي تقبلها الرسوم البيانية لمايهيل هي فئة اللغات المحلية. [ 8 ]

العشوائية

عند تجاهل حالتي البداية والقبول، يمكن اعتبار آلة الحالة المحدودة المحددة (DFA) ذات n حالة وأبجدية بحجم k بمثابة رسم بياني موجه ذي n رأس، حيث يمتلك كل رأس k قوسًا خارجيًا مرقمة من 1 إلى k ( رسم بياني موجه k- خارج). من المعروف أنه عندما يكون k ≥ 2 عددًا صحيحًا ثابتًا، فإنه باحتمالية عالية، يكون أكبر مكون متصل بقوة (SCC) في مثل هذا الرسم البياني الموجه k- خارج، والذي يتم اختياره عشوائيًا، خطيًا ويمكن الوصول إليه من جميع الرؤوس. [ 9 ] كما ثبت أنه إذا سُمح لـ k بالزيادة مع زيادة n ، فإن الرسم البياني الموجه بأكمله يمر بانتقال طوري للاتصال القوي، مشابهًا لنموذج إردوش-ريني للاتصال. [ 10 ]

في آلة الحالة المحدودة العشوائية (DFA)، يكون الحد الأقصى لعدد الرؤوس التي يمكن الوصول إليها من رأس واحد قريبًا جدًا من عدد الرؤوس في أكبر شبكة متصلة ذات درجة واحدة (SCC) باحتمالية عالية. [ 9 ] [ 11 ] وينطبق هذا أيضًا على أكبر رسم بياني فرعي مستحث ذي درجة داخلية دنيا تساوي واحدًا، والذي يمكن اعتباره نسخة موجهة من شبكة أحادية النواة . [ 10 ]

خصائص الإغلاق

يتعرف الأوتوماتون العلوي الأيسر على لغة جميع السلاسل الثنائية التي تحتوي على ظهور واحد على الأقل للرقم "00". ويتعرف الأوتوماتون السفلي الأيمن على جميع السلاسل الثنائية التي تحتوي على عدد زوجي من الرقم "1". أما الأوتوماتون السفلي الأيسر، فهو ناتج ضرب الأوتوماتونين السابقين، ويتعرف على تقاطع اللغتين.

إذا كانت الآلات ذات الحالة المحدودة (DFAs) تتعرف على اللغات الناتجة عن تطبيق عملية ما على اللغات التي تتعرف عليها هذه الآلات، فإن الآلات ذات الحالة المحدودة تُعتبر مغلقة في ظل هذه العملية. وتُغلق الآلات ذات الحالة المحدودة في ظل العمليات التالية.

في أبحاث تعقيد الحالات ، تم تحديد بنية مثلى لكل عملية فيما يتعلق بعدد الحالات . وبما أن الأوتوماتا المحدودة الحتمية ( DFAs ) مكافئة للأوتوماتا المحدودة غير الحتمية (NFA)، فإنه يمكن إثبات هذه الإغلاقات باستخدام خصائص إغلاق الأوتوماتا المحدودة غير الحتمية.

كأحادية انتقالية

يمكن اعتبار تشغيل آلة الحالة المحدودة المحددة (DFA) بمثابة سلسلة من تركيبات صيغة عامة جدًا لدالة الانتقال مع نفسها. هنا نقوم بإنشاء تلك الدالة.

بالنسبة لرمز إدخال معينأ∈Σ{\displaystyle a\in \Sigma }يمكن للمرء أن يبني دالة انتقاليةدلتاأ:سؤال→سؤال{\displaystyle \delta _{a}:Q\rightarrow Q}من خلال تحديددلتاأ(q)=دلتا(q،أ){\displaystyle \delta _{a}(q)=\delta (q,a)}للجميعq∈سؤال{\displaystyle q\in Q}(تُسمى هذه الحيلة "الكاري "). من هذا المنظور،دلتاأ{\displaystyle \delta _{a}}"تؤثر" على حالة في Q لإنتاج حالة أخرى. يمكن للمرء بعد ذلك النظر في نتيجة تركيب الدوال المطبقة بشكل متكرر على الدوال المختلفةدلتاأ{\displaystyle \delta _{a}}،دلتاب{\displaystyle \delta _{b}}وهكذا. بالنظر إلى زوج من الأحرفأ،ب∈Σ{\displaystyle a,b\in \Sigma }، يمكن للمرء تعريف دالة جديدةدلتا^أب=دلتاأ∘دلتاب{\displaystyle {\widehat {\delta}}_{ab}=\delta _{a}\circ \delta _{b}}، أين∘{\displaystyle \circ }يشير إلى تركيب الدوال.

من الواضح أن هذه العملية يمكن أن تستمر بشكل متكرر، مما يعطي التعريف التكراري التالي لـدلتا^:سؤال×Σ⋆→سؤال{\displaystyle {\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q}:

دلتا^(q،ϵ)=q{\displaystyle {\widehat {\delta }}(q,\epsilon )=q}، أينϵ{\displaystyle \epsilon }هي سلسلة فارغة و
دلتا^(q،wأ)=دلتاأ(دلتا^(q،w)){\displaystyle {\widehat {\delta }}(q,wa)=\delta _{a}({\widehat {\delta }}(q,w))}، أينw∈Σ*،أ∈Σ{\displaystyle w\in \Sigma ^{*},a\in \Sigma }وq∈سؤال{\displaystyle q\in Q}.

دلتا^{\displaystyle {\widehat {\delta }}} يتم تعريفها لجميع الكلماتw∈Σ*{\displaystyle w\in \Sigma ^{*}}. سلسلة من DFA هي عبارة عن تسلسل من تركيباتدلتا^{\displaystyle {\widehat {\delta }}}مع نفسه.

يُشكّل تركيب الدوال المتكرر شبه زمرة . بالنسبة لدوال الانتقال، تُعرف هذه الشبه زمرة باسم شبه زمرة الانتقال ، أو أحيانًا باسم شبه زمرة التحويل . ويمكن عكس عملية البناء أيضًا: بالنظر إلىدلتا^{\displaystyle {\widehat {\delta }}}يمكن للمرء إعادة بناءدلتا{\displaystyle \delta }وبالتالي فإن الوصفين متكافئان.

المزايا والعيوب

تُعدّ آلات الحالة المحدودة الحتمية (DFAs) من أكثر نماذج الحوسبة عمليةً، إذ توجد خوارزمية بسيطة تعمل في زمن خطي ومساحة ثابتة، وتُتيح محاكاة آلة الحالة المحدودة الحتمية على تدفق من المدخلات. كما توجد خوارزميات فعّالة لإيجاد آلة حالة محدودة حتمية تتعرف على:

  • مكمل اللغة التي يتعرف عليها جهاز DFA معين.
  • الاتحاد/التقاطع بين اللغات التي تتعرف عليها آلتان حتميتان محددتان.

نظرًا لإمكانية اختزال آلات الحالة المحدودة المحددة (DFAs) إلى شكل معياري ( آلات الحالة المحدودة المحددة الدنيا )، توجد أيضًا خوارزميات فعالة لتحديد ما يلي:

  • هل تقبل الآلة المحددة الحتمية أي سلاسل نصية (مشكلة الفراغ)؟
  • هل تقبل الآلة المحددة الحتمية جميع السلاسل (مشكلة الشمولية)؟
  • هل تتعرف آلتان من نوع DFA على نفس اللغة (مشكلة المساواة)؟
  • ما إذا كانت اللغة التي يتعرف عليها DFA مدرجة في اللغة التي يتعرف عليها DFA آخر (مشكلة الإدراج)
  • آلة الحالة المحدودة المحددة ذات الحد الأدنى من الحالات للغة منتظمة معينة (مسألة التصغير)

تُعادل الآلات المحدودة الحتمية (DFAs ) الآلات المحدودة غير الحتمية (NFAs) من حيث القدرة الحاسوبية. ويعود ذلك إلى أن أي آلة محدودة حتمية هي أيضًا آلة محدودة غير حتمية، وبالتالي يمكن للآلة المحدودة غير الحتمية القيام بما تقوم به الآلة المحدودة الحتمية. كذلك، عند استخدام بنية مجموعة القوى مع آلة محدودة غير حتمية، يمكن بناء آلة محدودة حتمية تتعرف على نفس اللغة التي تتعرف عليها الآلة المحدودة غير الحتمية، على الرغم من أن عدد حالات الآلة المحدودة الحتمية قد يكون أكبر بكثير من عدد حالات الآلة المحدودة غير الحتمية. [ 15 ] [ 16 ] ومع ذلك، على الرغم من أن الآلات المحدودة غير الحتمية تُكافئ الآلات المحدودة الحتمية حسابيًا، فإن المشكلات المذكورة أعلاه لا تُحل بالضرورة بكفاءة للآلات المحدودة غير الحتمية أيضًا. تُعد مشكلة عدم الشمولية للآلات المحدودة غير الحتمية مسألة كاملة من فئة PSPACE، نظرًا لوجود آلات محدودة غير حتمية صغيرة ذات أقصر كلمة رفض بحجم أُسّي. تكون الآلة المحدودة الحتمية شاملة إذا وفقط إذا كانت جميع حالاتها حالات نهائية، ولكن هذا لا ينطبق على الآلات المحدودة غير الحتمية. تُعتبر مسائل المساواة والشمول والتقليل مسائل كاملة في فضاء PSPACE أيضاً، لأنها تتطلب تكوين مكمل آلة الحالة المحدودة غير القطعية (NFA)، مما ينتج عنه تضخم أسي في الحجم. [ 17 ]

من جهة أخرى، تتمتع آلات الحالة المحدودة بقدرة محدودة للغاية على التعرف على اللغات التي تستطيع تمييزها؛ فالعديد من اللغات البسيطة، بما في ذلك أي مسألة تتطلب مساحة أكبر من ثابتة لحلها، لا يمكن التعرف عليها بواسطة آلة الحالة المحدودة الحتمية (DFA). المثال الكلاسيكي للغة بسيطة الوصف لا تستطيع أي آلة حالة محدودة حتمية التعرف عليها هي لغة الأقواس أو لغة ديك ، أي اللغة التي تتكون من أقواس متقابلة بشكل صحيح مثل الكلمة "(()())". وبشكل بديهي، لا تستطيع أي آلة حالة محدودة حتمية التعرف على لغة ديك لأنها غير قادرة على العد: تحتاج آلة شبيهة بآلة الحالة المحدودة الحتمية إلى حالة لتمثيل أي عدد ممكن من الأقواس "المفتوحة حاليًا"، مما يعني أنها ستحتاج إلى عدد غير محدود من الحالات. مثال آخر أبسط هو اللغة التي تتكون من سلاسل نصية على شكل a n b n لعدد محدود ولكنه عشوائي من a ، متبوعًا بعدد مماثل من b . [ 18 ]

تحديد الكلمات المصنفة باستخدام DFA

بالنظر إلى مجموعة من الكلمات الإيجابيةS+⊂Σ*{\displaystyle S^{+}\subset \Sigma ^{*}}ومجموعة من الكلمات السلبيةS-⊂Σ*{\displaystyle S^{-}\subset \Sigma ^{*}}يمكن للمرء إنشاء آلة حتمية محدودة تقبل جميع الكلمات منS+{\displaystyle S^{+}}ويرفض جميع الكلمات منS-{\displaystyle S^{-}}تُسمى هذه المشكلة تحديد DFA (التوليف، التعلم). في حين أنه يمكن بناء بعض DFA في وقت خطي، فإن مشكلة تحديد DFA بأقل عدد من الحالات هي مشكلة NP-كاملة. [ 19 ] تم اقتراح أول خوارزمية لتحديد DFA بأقل عدد من الحالات بواسطة Trakhtenbrot و Barzdin [ 20 ] وتُسمى خوارزمية TB . ومع ذلك، تفترض خوارزمية TB أن جميع الكلمات منΣ{\displaystyle \Sigma }يتم احتواء ما يصل إلى طول معين إما فيS+∪S-{\displaystyle S^{+}\cup S^{-}}.

وفي وقت لاحق، اقترح ك. لانغ امتدادًا لخوارزمية TB لا يستخدم أي افتراضات حولS+{\displaystyle S^{+}}وS-{\displaystyle S^{-}}خوارزمية تراكس بار . [ 21 ] ومع ذلك، لا تضمن تراكس بار الحد الأدنى لحجم آلة الحالة المحدودة المُنشأة. في عمله [ 19 ] ، اقترح إي إم غولد أيضًا خوارزمية استدلالية لتحديد آلة الحالة المحدودة ذات الحد الأدنى. تفترض خوارزمية غولد أنS+{\displaystyle S^{+}}وS-{\displaystyle S^{-}}يجب أن تحتوي على مجموعة خصائص اللغة المنتظمة؛ وإلا، فإن آلة الحالة المحدودة المحددة (DFA) المُنشأة ستكون غير متسقة إما معS+{\displaystyle S^{+}}أوS-{\displaystyle S^{-}}تتضمن خوارزميات تحديد DFA البارزة الأخرى خوارزمية RPNI، [ 22 ] وخوارزمية دمج الحالات القائمة على الأدلة Blue-Fringe، [ 23 ] وWindowed-EDSM. [ 24 ] ويتجه بحث آخر نحو تطبيق الخوارزميات التطورية : فقد سمحت خوارزمية تصنيف الحالات الذكية التطورية [ 25 ] بحل مشكلة تحديد DFA المعدلة حيث بيانات التدريب (مجموعات)S+{\displaystyle S^{+}}وS-{\displaystyle S^{-}}) مشوشة بمعنى أن بعض الكلمات تُنسب إلى فئات خاطئة.

خطوة أخرى إلى الأمام تُعزى إلى تطبيق خوارزميات حل مشكلة SAT بواسطة مارجين جيه إتش هيول وإس. فيروير: حيث تُختزل مشكلة تحديد DFA الأدنى إلى تحديد قابلية إرضاء صيغة منطقية. [ 26 ] الفكرة الرئيسية هي بناء مُستقبِل شجرة بادئة مُعززة ( شجرة تحتوي على جميع كلمات الإدخال مع التصنيفات المُقابلة) استنادًا إلى مجموعات الإدخال، واختزال مشكلة إيجاد DFA معج{\displaystyle C}الولايات لتلوين رؤوس الشجرة بـج{\displaystyle C}يتم تحديد الحالات بطريقة تجعل الآلة الناتجة حتمية ومتوافقة مع الحالات التي يتم فيها دمج الرؤوس ذات اللون الواحد في حالة واحدة.S+{\displaystyle S^{+}}وS-{\displaystyle S^{-}}على الرغم من أن هذا النهج يسمح بإيجاد آلة الحالة المحدودة الحتمية (DFA) ذات الحد الأدنى، إلا أنه يعاني من تضخم أُسّي في وقت التنفيذ مع ازدياد حجم بيانات الإدخال. لذلك، تم لاحقًا تحسين خوارزمية هيول وفيروير الأولية بإضافة عدة خطوات من خوارزمية EDSM قبل تنفيذ خوارزمية حل SAT: خوارزمية DFASAT. [ 27 ] يسمح هذا بتقليل مساحة البحث للمسألة، ولكنه يؤدي إلى فقدان ضمان الحد الأدنى. وقد اقترح أوليانتسيف وآخرون [ 28 ] طريقة أخرى لتقليل مساحة البحث باستخدام مُسندات جديدة لكسر التناظر تعتمد على خوارزمية البحث بالعرض أولًا : حيث يتم تقييد حالات آلة الحالة المحدودة الحتمية المطلوبة ليتم ترقيمها وفقًا لخوارزمية البحث بالعرض أولًا التي يتم تشغيلها من الحالة الأولية. يقلل هذا النهج مساحة البحث عن طريقج!{\displaystyle C!}عن طريق إزالة الأوتوماتا المتماثلة.

النماذج المكافئة

آلات تورينج للقراءة فقط تتحرك لليمين

آلات تورينغ للقراءة فقط ذات الحركة اليمنى هي نوع خاص من آلات تورينغ التي تتحرك يمينًا فقط؛ وهي تُعادل تقريبًا آلات الحالة المحدودة المحددة (DFAs). [ 29 ] التعريف القائم على شريط لانهائي أحادي هو سباعي الترتيب .

م=⟨سؤال،Γ،ب،Σ،دلتا،q0،F⟩،{\displaystyle M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle ,}

أين

سؤال{\displaystyle Q}هي مجموعة محدودة من الحالات ؛
Γ{\displaystyle \Gamma }هي مجموعة محدودة من أبجدية/رموز الشريط ؛
ب∈Γ{\displaystyle b\in \Gamma }هو الرمز الفارغ (الرمز الوحيد المسموح بظهوره على الشريط بشكل لا نهائي في أي خطوة أثناء الحساب)؛
Σ{\displaystyle \Sigma }، مجموعة فرعية منΓ{\displaystyle \Gamma }باستثناء b ، هي مجموعة رموز الإدخال ؛
دلتا:سؤال×Γ→سؤال×Γ×{R}{\displaystyle \delta :Q\times \Gamma \to Q\times \Gamma \times \{R\}}هي دالة تسمى دالة الانتقال ، و R هي حركة إلى اليمين (إزاحة إلى اليمين)؛
q0∈سؤال{\displaystyle q_{0}\in Q}هي الحالة الابتدائية ؛
F⊆سؤال{\displaystyle F\subseteq Q}هي مجموعة الحالات النهائية أو المقبولة .

تقبل الآلة دائمًا لغة منتظمة. يجب أن يوجد عنصر واحد على الأقل من المجموعة F ( حالة التوقف ) حتى تكون اللغة غير فارغة.

مثال على آلة تورينج للقراءة فقط ذات 3 حالات ورمزين

الحالة الحالية أالحالة الحالية بالحالة الحالية ج
رموز الشريطكتابة الرموزنقل الشريطالولاية التاليةكتابة الرموزنقل الشريطالولاية التاليةكتابة الرموزنقل الشريطالولاية التالية
0 1 Rب 1 Rأ 1 Rب
1 1 Rج 1 Rب 1 شمال وقف
سؤال={أ،ب،ج،وقف}؛{\displaystyle Q=\{A,B,C,{\text{HALT}}\};}
Γ={0،1}؛{\displaystyle \Gamma =\{0,1\};}
ب=0{\displaystyle b=0}، "فارغ"؛
Σ=∅{\displaystyle \Sigma =\varnothing }، مجموعة فارغة؛
دلتا={\displaystyle \delta =}انظر الجدول أعلاه؛
q0=أ{\displaystyle q_{0}=A}، الحالة الأولية؛
F={\displaystyle F=}مجموعة العناصر الفردية للحالات النهائية:{وقف}{\displaystyle \{{\text{HALT}}\}}.

انظر أيضاً

ملحوظات

  1. 1 2 هوبكروفت، موتواني وأولمان 2006 .
  2. ↑ ماكولوتش وبيتس 1943 .
  3. ↑ رابين وسكوت 1959 .
  4. ↑ باي، جينا ر.؛ كلي، برايان؛ شريستا، نيشال؛ تشابمان، كارل؛ رايت، سيمون؛ ستولي، كاثرين ت. (2019). "استكشاف الأدوات والاستراتيجيات المستخدمة أثناء مهام تركيب التعبيرات النمطية" . في: غيهينيوك، يان-غايل؛ خوم، فوتس؛ سارو، فيديريكا (محررون). وقائع المؤتمر الدولي السابع والعشرين لفهم البرامج، ICPC 2019، مونتريال، كيبيك، كندا، 25-31 مايو 2019. IEEE / ACM. ص 197-208 . doi : 10.1109/ICPC.2019.00039 . ISBN  978-1-7281-1519-1.
  5. ↑ موجنسن، توربن إيجيديوس (2011). "التحليل المعجمي". مقدمة في تصميم المترجمات . مواضيع جامعية في علوم الحاسوب. لندن: سبرينغر. ص 12. doi : 10.1007/978-0-85729-829-4_1 . ISBN  978-0-85729-828-7.
  6. 1 2 لوسون 2004 ، ص. 129.
  7. ↑ ساكاروفيتش 2009 ، ص 228.
  8. ↑ لوسون 2004 ، ص 128.
  9. 1 2 غروشو، أ.أ. (1973). "التوزيعات الحدية لخصائص معينة لرسوم بيانية للآلات العشوائية". الملاحظات الرياضية لأكاديمية العلوم في الاتحاد السوفيتي . 4 : 633-637 . doi : 10.1007/BF01095785 . S2CID 121723743 . 
  10. 1 2 كاي، شينغ شي؛ ديفروي، لوك (أكتوبر 2017). "بنية الرسم البياني لآلة حتمية مختارة عشوائيًا". الهياكل والخوارزميات العشوائية . 51 (3): 428-458 . arXiv : 1504.06238 . doi : 10.1002/rsa.20707 . S2CID 13013344 . 
  11. ↑ كارايول، أرنو؛ نيكود، سيريل (فبراير 2012). توزيع عدد الحالات المتاحة في آلة حتمية عشوائية . STACS'12 (الندوة التاسعة والعشرون حول الجوانب النظرية لعلوم الحاسوب). المجلد 14. باريس، فرنسا. الصفحات 194-205 .  
  12. ↑ هوبكروفت وأولمان 1979 ، ص 59-60.
  13. 1 2 3 روز، جين ف. (1968). "الإغلاقات التي تحافظ على التناهي في عائلات اللغات". مجلة علوم الحاسوب والنظم . 2 (2): 148-168 . doi : 10.1016/S0022-0000(68)80029-7 .
  14. 1 2 سبانير، إي . (1969). "القواعد واللغات". المجلة الرياضية الأمريكية الشهرية . 76 (4): 335-342 . doi : 10.1080/00029890.1969.12000214 . JSTOR 2316423. MR 0241205 .  
  15. ↑ ساكاروفيتش 2009 ، ص 105.
  16. ↑ لوسون 2004 ، ص 63.
  17. ↑ إسبارزا إيستاون، فرانسيسكو خافيير؛ سيكرت، سالومون؛ بلوندين، مايكل (16 نوفمبر 2016). "العمليات والاختبارات على المجموعات: التنفيذ على الأوتوماتا المحددة" (ملف PDF) . الأوتوماتا واللغات الرسمية 2017/18 . مؤرشف من الأصل (ملف PDF) في 8 أغسطس 2018.
  18. ↑ لوسون 2004 ، ص 46.
  19. 1 2 غولد، إي إم (1978). "تعقيد تحديد هوية الأوتوماتون من البيانات المعطاة". المعلومات والتحكم . 37 (3): 302-320 . doi : 10.1016/S0019-9958(78)90562-4 .
  20. ↑ دي فريس، أ. (28 يونيو 2014). الأوتوماتا المحدودة: السلوك والتركيب . إلسيفير. ISBN 9781483297293.
  21. ↑ لانغ، كيفن ج. (1992). "يمكن تعلم نماذج DFA العشوائية تقريبًا من أمثلة موحدة متفرقة". وقائع ورشة العمل السنوية الخامسة حول نظرية التعلم الحسابي - COLT '92 . الصفحات 45-52 . doi : 10.1145/130385.130390 . ISBN  089791497X. S2CID 7480497 . 
  22. ↑ أونسينا، ج.؛ غارسيا، ب. (1992). "استنتاج اللغات المنتظمة في وقت تحديث متعدد الحدود". التعرف على الأنماط وتحليل الصور . سلسلة في الإدراك الآلي والذكاء الاصطناعي. المجلد 1. الصفحات 49-61 . doi : 10.1142/9789812797902_0004 . ISBN   978-981-02-0881-3.
  23. ↑ لانغ، كيفن جيه؛ بيرلموتر، باراك أ؛ برايس، رودني أ. (1998). "نتائج مسابقة تعلم آلات الحالة المحدودة المحددة (DFA) من أبادينغو وخوارزمية جديدة لدمج الحالات قائمة على الأدلة". الاستدلال النحوي (ملف PDF) . سلسلة محاضرات في علوم الحاسوب. المجلد 1433. الصفحات 1-12 . doi : 10.1007/BFb0054059 . ISBN   978-3-540-64776-8.
  24. ↑ أدريانز، بيتر؛ فيرناو، هينينغ؛ زانين، مينو فان (23 سبتمبر 2002). ما وراء EDSM | وقائع الندوة الدولية السادسة حول الاستدلال النحوي: الخوارزميات والتطبيقات . سبرينغر. ص 37-48 . ISBN  9783540442394.
  25. ↑ لوكاس، إس إم؛ رينولدز، تي جيه (2005). "تعلم الأوتوماتا المحدودة الحتمية باستخدام خوارزمية تطورية ذكية لتصنيف الحالات". معاملات IEEE في تحليل الأنماط والذكاء الآلي . 27 (7): 1063-1074 . doi : 10.1109/TPAMI.2005.143 . PMID 16013754. S2CID 14062047 .  
  26. ↑ هيول، إم جيه إتش (2010). "تحديد دقيق للآلات المحددة الحتمية باستخدام حلول SAT". الاستدلال النحوي: النتائج النظرية والتطبيقات . الاستدلال النحوي: النتائج النظرية والتطبيقات. المؤتمر الدولي للاستدلال النحوي 2010. سلسلة محاضرات في علوم الحاسوب. المجلد 6339، الصفحات 66-79 . doi : 10.1007/978-3-642-15488-1_7 . ISBN   978-3-642-15487-4.
  27. ↑ هيول، مارين جيه إتش ؛ فيروير، سيكو (2013). "توليف نماذج البرمجيات باستخدام حلول الإرضاء" . هندسة البرمجيات التجريبية . 18 (4): 825-856 . doi : 10.1007/s10664-012-9222-z . hdl : 2066/103766 . S2CID 17865020 . 
  28. ↑ أوليانتسيف، فلاديمير؛ زاكيرزيانوف، إيليا؛ شاليتو، أناتولي (2015). "مسندات كسر التناظر القائمة على خوارزمية البحث في العرض أولاً لتحديد الأوتوماتا المحددة". نظرية اللغة والأوتوماتا وتطبيقاتها . سلسلة محاضرات في علوم الحاسوب. المجلد 8977. الصفحات 611-622 . doi : 10.1007/978-3-319-15579-1_48 . ISBN   978-3-319-15578-4.
  29. ↑ ديفيس، مارتن؛ رون سيغال؛ إيلين ج. ويوكر (1994). الطبعة الثانية: الحوسبة، والتعقيد، واللغات والمنطق: أساسيات علوم الحاسوب النظرية (الطبعة الثانية ). سان دييغو: أكاديميك برس، هاركورت، بريس وشركاه. ISBN  0-12-206382-1.

مراجع

للمزيد من القراءة