✖

الأوتومات المنتهي غير الحتمي

كان الأوتومات المنتهي الذي عرضناه في الفصول السابقة (نختصره FA أو DFA) حتمياً دائماً، أي كان واضحاً في كل لحظة ما سيفعله الأوتومات. وننظر الآن في مفهوم أعم هو الأوتومات المنتهي غير الحتمي (non-deterministic finite automaton، ونختصره NFA)، وفيه يمكن أن توجد انتقالات تخرج من الحالة نفسها للرمز نفسه.

مثال تمهيدي

لننظر إلى مخطط الأوتومات الآتي:

ما الغريب فيه؟ أنّ من العقدة q0 تخرج حافتان للرمز 0. فإذا حاولنا أن نقبل الكلمة 001، فقد يبدو أنّ الأوتومات لن يعرف أيبقى في الحالة q0 أم يتبع الانتقال إلى q1. ومثل هذا الأوتومات غير حتمي.

الحتمية بهذا المعنى تعني أنه في كل موقف يكون واضحاً ما سيفعله الأوتومات، ولا مجال فيه للالتباس. فللأوتومات الحتمي انتقال واحد فقط لكل حالة ولكل رمز. أما عدم الحتمية فتعني الالتباس، إذ قد تخرج من الحالة الواحدة للرمز نفسه ثلاثة انتقالات مثلاً.

فكيف يقرر الأوتومات إذن؟ يختار الأوتومات غير الحتمي دائماً (ونقول أحياناً «يخمّن») الانتقال الذي يؤدي إلى قبول الكلمة، إن كان ذلك ممكناً.

إذا أدخلنا إلى الأوتومات الكلمة 001، فأمامه هذه الإمكانات للتعامل معها:

q0→q0→q0→q0q0→q0→q1→q2

إضافة إلى الإمكانات التي لا يقرأ فيها الكلمة كلها. في الإمكانية الأولى بقي دائماً في الحالة q0، وهذا مسموح له بالتأكيد، فقواعد الانتقال تسمح بذلك. وفي الفرع الثاني تجرّأ على الانتقال إلى حالات أخرى حتى وصل في النهاية إلى الحالة q2 وهي حالة نهائية. في هذا الفرع يقبل الأوتومات الكلمة. والأوتومات غير الحتمي يختار تلقائياً دائماً الفرع الذي يقبل فيه الكلمة، إن وُجد مثل هذا الفرع.

فكيف يختار تلقائياً الفرع «المناسب»؟ يمكننا أن نتخيل أنّ الأوتومات غير الحتمي يجرّب كل الفروع الممكنة، فإذا وجد فرعاً يقبل فيه الكلمة قبلها. وكيف يجرّب كل الفروع؟ ببساطة، عندما يكون في حالة يخرج منها للرمز الحالي n حافة، ينسخ الأوتومات نفسه n مرة، وتسلك كل نسخة طريقاً مختلفاً. وبذلك نمرّ تدريجياً بكل الإمكانات.

تمثيل حساب الأوتومات بشجرة

نعدّل الأوتومات السابق تعديلاً طفيفاً:

بقيت عدم الحتمية في الحالة الأولى. كان الأوتومات السابق يقبل كل الكلمات التي تنتهي بالسلسلة 01، أما هذا الأوتومات المعدَّل فيقبل كل الكلمات التي تحتوي على الكلمة الجزئية 01. فهو يقبل مثلاً الكلمة 101 أو 0101. ويمكننا بسهولة أن نمثّل كل فروع الحساب بشجرة، فشجرة الكلمة 01010 مثلاً يمكن أن تكون كما يلي:

نكون في البداية في الحالة الابتدائية q0، وفي المدخلات الكلمة 01010، وأول رمز لم يُقرأ هو 0. من الحالة q0 يخرج انتقالان للرمز 0 إلى الحالتين q0 و q1. فيكون لهذه العقدة في الشجرة ابنان: q0 و q1. ثم نقرأ الرمز 1، ولا التباس هنا، فننتقل إلى الحالتين q0 و q2. ثم نقرأ الرمز 0، فيظهر الالتباس مرة أخرى في الفرع الأيسر، فنقسم الحساب إلى فرعين آخرين: نبقى في أحدهما مرة أخرى في q0، وننتقل في الآخر إلى q1. وهكذا.

نلاحظ أنّ فرعين ينتهيان في الحالة q2، وهي الحالة النهائية. فيوجد فرعان من فروع الحساب يستطيع بهما الأوتومات أن يقبل الكلمة المعطاة، ولذلك يقبل هذا الأوتومات الكلمة 01010. ويمكننا أن نجرّب إنشاء شجرة مشابهة للكلمة 1000.

إما أن يبقى الحساب في الحالة q0، وإما أن ينتقل إلى الحالة q1، لكنه لا يجد من هناك طريقاً يتابع فيه، لأنّ المدخلات أصفار كلها، وللحالة q1 انتقال للرمز 1 وحده. لا ينتهي أي فرع من فروع الحساب في حالة نهائية، إذن لا يقبل الأوتومات الكلمة 1000.

انتقالات إبسيلون

يمكننا في الأوتومات غير الحتمية أن نستعمل أيضاً انتقالات إبسيلون (epsilon transitions). وهي انتقالات يمكننا تنفيذها أياً كان الرمز في المدخلات، ودون أن نقرأ أي رمز من الكلمة. فكيف نكتب أوتوماتاً غير حتمي يقبل الكلمة الفارغة، وكل الكلمات المكوّنة من الآحاد وحدها، والكلمات التي على الصورة (10)n، أي 10 و 1010 و…؟

قسمنا الأوتومات إلى «أوتوماتين جزئيين». الأعلى يتعرّف على الكلمات المكوّنة من 1، والأسفل يتعرّف على الكلمات التي على الصورة (10)n. لنجرّب قبول الكلمة 111. يكون الأوتومات في البداية في الحالة q0 وفي مدخلاته الكلمة 111. وبما أنّ لديه انتقالات إبسيلون، فيمكنه أن يقرر الانتقال إلى الحالة q1 أو q2 بحسب ما يناسبه. ونرى أنّ الانتقال إلى الحالة q1 هو ما يناسبه، فينتقل إليها. وتبقى في مدخلاته مع ذلك الكلمة 111 كاملة! ولا يبدأ بقراءة رموز الكلمة إلا الآن، فينتقل من الحالة q1 إلى q1 مرة بعد مرة حتى يقرأ الكلمة كلها ويقبلها.

ولو حاولنا قبول الكلمة 1010، لانتقل الأوتومات في البداية إلى الحالة q2، ولبدأ معالجة الرموز من هناك، ولقبل الكلمة أيضاً.

أما الكلمة 1100 فمهما فعل الأوتومات بها، فلا سبيل له إلى قبولها.

تسهّل علينا انتقالات إبسيلون وعدم الحتمية العمل كثيراً. فمثلاً برهان أنّ اتحاد لغتين منتظمتين لغة منتظمة أيضاً يمكن كتابته بانتقالات إبسيلون أبسط بكثير مما في حالة الأوتومات المنتهية الحتمية. كان لدينا في ذلك البرهان مثالان على هذين الأوتوماتين

و

ثم أنشأنا أوتوماتاً منتهياً حتمياً يقبل اتحاد اللغتين. أما بانتقالات إبسيلون فيمكننا إنشاء هذا الأوتومات كما يلي:

أي نضيف حالة ابتدائية جديدة، يخرج منها انتقالا إبسيلون إلى الحالتين الابتدائيتين للأوتوماتين الأصليين، وهذا كل شيء. ويقرر الأوتومات بصورة غير حتمية أيحاول قبول الكلمة بأحد «الأوتوماتين الجزئيين» أم بالآخر.

تعريف الأوتومات غير الحتمي

عرضنا الفرق بين الأوتومات المنتهي الحتمي والأوتومات المنتهي غير الحتمي، ولم يبقَ إلا أن نصوغه صياغة صورية. عرّفنا الأوتومات المنتهي الحتمي بأنه خماسية ⟨Q, Σ, δ, q0, F⟩، حيث Q مجموعة الحالات، و Σ الأبجدية، و δ دالة الانتقال، و q0 الحالة الابتدائية، و F مجموعة الحالات النهائية. والشيء الوحيد الذي يتغيّر في تعريف الأوتومات غير الحتمية هو تعريف دالة الانتقال.

في النسخة الحتمية كانت الدالة تعيد عند الاستدعاء δ(q, w) حالة واحدة فقط، أما في النسخة غير الحتمية فيمكن أن تعيد عدة حالات، إذا عُرّف للرمز الواحد أكثر من انتقال. ولأننا نحتاج إلى تعريف انتقالات إبسيلون أيضاً، نرمز للمجموعة Σ ∪ {ε} بالرمز Σε، أي Σε = Σ ∪ {ε}. ونعرّف الدالة δ إذن بأنها

δ:Q×Σε→2Q

يرمز 2Q إلى مجموعة القوة، أي مجموعة كل المجموعات الجزئية من المجموعة Q. والصياغة الصورية للحساب تشبه كثيراً ما في الأوتومات المنتهية الحتمية. فتشكيل الأوتومات هو مرة أخرى الثنائي ⟨q, w⟩ ∈ Q × Σ∗. والخطوة الحسابية ↦ علاقة على مجموعة التشكيلات تحقق

⟨qi,w0w1…wn⟩↦⟨qj,w1…wn⟩,

إذا وفقط إذا كان qj ∈ δ(qi, w0). في هذه الجملة يكمن الفرق الأكبر. ففي الأوتومات الحتمية كتبنا هذا الشرط على الصورة qj = δ(qi, w0)، لأنّ الدالة δ كانت تعيد دائماً حالة واحدة. أما النسخة غير الحتمية من دالة الانتقال فتعيد مجموعة من الحالات، ولذلك يظهر هنا الرمز ∈. ونرمز مرة أخرى للانغلاق الانعكاسي والمتعدي للعلاقة بالرمز ↦ ∗. ونقول إنّ الأوتومات يقبل الكلمة w إذا وفقط إذا وُجدت qf ∈ F بحيث

⟨q0,w⟩↦∗⟨qf,ε⟩.

المصادر

المحتويات: الأوتومات المنتهي, الأوتومات الكامل, الأوتومات المنتهي غير الحتمي, محاكاة الأوتومات غير الحتمي, تحويل NFA إلى DFA