الأوتومات المنتهي
الأوتومات المنتهي أو الآلة المنتهية (finite state machine أو finite automaton) نموذج حسابي لحاسوب بدائي، يتكوّن من عدد من الحالات وعدد من الانتقالات، ويستطيع أن يقبل الكلمة المعطاة له أو أن يرفضها.
مثال تمهيدي
نصف الأوتومات المنتهي وصفاً غير صوري بمخطط الحالات (مخطط الانتقال) الذي يمثّله:
يتكوّن الأوتومات من حالات، وهي في الشكل الحالات الثلاث المستديرة q0 و q1 و q2. وبين هذه الحالات انتقالات، وهي الأسهم. ويجب أن تكون في الأوتومات حالة ابتدائية، وهي هنا الحالة q0. ونمثّل الحالة الابتدائية عادةً بسهم يتجه إليها ولا يخرج من أي حالة. وفي الأوتومات عادةً أيضاً حالة نهائية نرسمها بخط مزدوج، وهي في الشكل الحالة q2.
الأوتومات المبني بهذه الطريقة يقبل كلمات معيّنة. فنُدخل إليه كلمات، ويحاول هو أن يقبلها. فإذا قبلها أجاب «نعم»، وإذا لم يقبلها أجاب «لا». يحاول أوتوماتنا قبول كلمات مكوّنة من الحروف «a, b, c»، فلنجرّب مثلاً الكلمة «abbc».
نبدأ من الحالة الابتدائية q0، وفي المدخلات الكلمة «abbc». ثم نتبع الأسهم.
نقرأ الكلمة كالمعتاد من اليسار إلى اليمين، أي نأخذ أولاً الرمز «a». السهم الخاص بالمدخل «a» يتجه إلى الحالة q1، فننتقل إليها ونحذف الرمز «a» من الكلمة. فتبقى في المدخلات الكلمة «bbc»:
السهم الخاص بالمدخل «b» يعود إلى العقدة q1. نحذف الحرف الأول مرة أخرى فتبقى في المدخلات الكلمة «bc». ونبقى مرة أخرى في الحالة q1. وأخيراً تبقى في المدخلات الكلمة «c». ومن الحالة q1 يرسلنا السهم الخاص بالمدخل «c» إلى الحالة q2.
استنفدنا الآن كل حروف كلمة المدخلات، ونحن في الحالة q2 وهي حالة نهائية. إذن يقبل هذا الأوتومات المنتهي الكلمة «abbc».
لو لم نكن في النهاية في حالة قبول، لما قبل الأوتومات الكلمة. وكذلك لا يقبل الأوتومات الكلمة إذا وصلنا إلى حالة لا نجد فيها انتقالاً نتبعه. فبالمدخل «ab» مثلاً نصل إلى الحالة q1 ونتوقف فيها، فالأوتومات لا يقبل هذه الكلمة. ولو جرّبنا الكلمة «aabbc» لما نجحنا أيضاً، لأنه لا يخرج من الحالة q1 سهم للحرف «a».
يُستعمل الأوتومات المنتهي إذن للتعرّف على مجموعة من الكلمات. ويمكننا في التطبيق أن نستعمله مثلاً لمعرفة ما إذا كانت كلمة المدخلات عنوان بريد إلكتروني صالحاً.
تعريف الأوتومات المنتهي
علينا أن نصوغ هذا التصور الحدسي للأوتومات المنتهي صياغة صورية، لكي نتمكن من التعامل مع الأوتومات بصورة أفضل.
نقول إنّ الأوتومات المنتهي (الحتمي) هو خماسية ⟨Q, Σ, δ, q0, F⟩، حيث
- Q مجموعة منتهية من الحالات،
- Σ (سيغما الكبيرة) الأبجدية (مجموعة منتهية من الرموز أو الحروف)،
- δ: Q × Σ ⟶ Q دالة الانتقال،
- q0 ∈ Q الحالة الابتدائية،
- F ⊆ Q مجموعة الحالات النهائية (حالات القبول).
لنعد إلى الأوتومات السابق،
يمكننا أن نقول إنّ مجموعة الحالات Q تضم ثلاث حالات Q = {q0, q1, q2}. وتحتوي الأبجدية Σ على الحروف التي نكوّن منها الكلمات التي سيقبلها الأوتومات أو يرفضها. والأرجح أنها هنا الأبجدية Σ= {a, b, c}، لكن يمكن أن تكون أيضاً أي مجموعة شاملة لها. والحالة الابتدائية q0 هي الحالة q0، ولا تغيير في ذلك. أما مجموعة الحالات النهائية في هذا الأوتومات فتضم حالة واحدة فقط F = {q2}.
ونقصد بدالة الانتقال الأسهم الثلاثة التي تحمل الحروف. وإذا بدا الرمز δ: Q × Σ ⟶ Q مربكاً، فهو يعني فقط أنّ δ دالة (أو بالأحرى تطبيق) تأخذ وسيطين: حالة من Q وحرفاً من Σ، وتعيد عند استدعائها حالة جديدة. ويمكننا أن نعرّف دالة الانتقال عندنا بجدول كما يلي:
فإذا استدعينا δ(q1, c)، طبّقنا السطر الثالث وأعادت الدالة الحالة q2، كما في المخطط. أي إذا كنا في الحالة q1 وفي المدخلات الحرف «c»، فإننا ننتقل إلى الحالة q2. وقبل أن نعرّف صورياً معنى أن يقبل الأوتومات كلمة ما، سنعتمد على الفهم الحدسي لهذا المفهوم ونعرض أمثلة أخرى.
أمثلة أخرى
-
أنشئ أوتوماتاً يعمل على الأبجدية الثنائية، أي Σ= {0, 1}، ولا يقبل إلا الكلمات التي تنتهي بالرقم 1. فهو يقبل مثلاً الكلمات 1 و 01 و 000001 و 0101011.
لأوتوماتنا حالتان: الحالة الابتدائية q0 والحالة النهائية q1. كلما كان في المدخلات الرقم 1 انتقلنا إلى الحالة النهائية q1 وبقينا فيها. وعلى العكس، إذا كان في المدخلات الرقم 0 انتقلنا إلى الحالة غير النهائية q0 وبقينا فيها أيضاً.
-
أنشئ أوتوماتاً على الأبجدية الثنائية لا يقبل إلا الكلمات التي يختلف حرفها الأول عن حرفها الأخير.
ينقسم الأوتومات منذ الخطوة الأولى إلى «أوتوماتين جزئيين». فإذا بدأت الكلمة بالصفر دخل الأوتومات الجزء الأيسر وبقي فيه، وإذا بدأت بالواحد انتقل إلى الجزء الأيمن. وبعد ذلك يسير الأمر كالمعتاد: إذا كنا في الجزء الأيسر وفي المدخلات 1، ننتقل إلى الحالة النهائية ونبقى فيها. وإذا كان في المدخلات 0، ننتقل إلى الحالة q1 وهي ليست نهائية.
وعلى خلاف الأوتومات السابقة، لهذا الأوتومات أكثر من حالة نهائية، أي F = {q3, q4}.
-
أنشئ أوتوماتاً على الأبجدية الثنائية لا يقبل إلا الكلمات التي لا تحتوي على صفرين متتاليين.
هذا الأوتومات مثير للاهتمام لسببين: الأول أنه يقبل الكلمة الفارغة. فيمكننا أن نُدخل إليه الكلمة الفارغة، فيقبلها إذا كانت الحالة الابتدائية حالة نهائية أيضاً، وهذا ما حدث في هذا الأوتومات. وهذا صحيح، لأنّ الكلمة الفارغة كلمة لا تحتوي على صفرين متتاليين. والأمر الثاني أنّ كل حالات هذا الأوتومات نهائية. فالحالة الوحيدة التي لا يقبل فيها الكلمة هي ألّا يخرج من الحالة أي انتقال. ويحدث ذلك في الحالة q1 التي ليس لها انتقال للرقم 0، لأنّ الكلمة عندئذٍ ستحتوي على صفرين متتاليين.
-
أنشئ أوتوماتاً على الأبجدية {-,+,.,0,1,…,9} لا يقبل إلا الكلمات التي تمثّل عدداً. أي إما عدداً صحيحاً مثل 2 و 548 و 98263، وإما عدداً عشرياً مثل 5584.48 و 3.14، ولكلٍّ منهما أيضاً صورة سالبة بإشارة الطرح -2 و -548 و -3.14، وصورة بإشارة الجمع الصريحة، أي +2 و +548 و +3.14. ويجب في الوقت نفسه أن نستطيع كتابة العدد 0.123 على الصورة .123 فقط (دون الصفر في البداية)، ومع الإشارتين كلتيهما. ونعتمد ترميزاً مساعداً: بدلاً من كتابة عشرة انتقالات للأرقام العشرة، نستعمل الرمز N.
-
أنشئ أوتوماتاً على الأبجدية الثنائية لا يقبل إلا الكلمات التي على الصورة 0n1n، أي الكلمات التي تبدأ بعدد معيّن من الأصفار يتبعها العدد نفسه من الآحاد. ومن أمثلة هذه الكلمات 0011 و 00001111 و 01.
لا يمكن إنشاء مثل هذا الأوتومات، لأننا لا نستطيع أن «نتذكر» عدد الأصفار في أي مكان. فسيكون علينا أن ننشئ عدة «أوتومات جزئية» كما في المثال الثاني، لكنّ عددها سيكون لا نهائياً، أوتوماتاً جزئياً لكل قيمة من قيم n.
الصياغة الصورية لحساب الأوتومات
عرّفنا صورياً الأوتومات المنتهي نفسه. وعلينا بعد ذلك أن نعرّف ما يفعله هذا الأوتومات فعلاً، أي نعرّف حساب الأوتومات.
تشكيل الأوتومات (configuration): نقول إنّ الثنائي ⟨q, w⟩ ∈ Q × Σ∗ تشكيل للأوتومات، حيث q الحالة الحالية التي يوجد فيها الأوتومات، و w الجزء الذي لم يُقرأ بعد من الكلمة. ويرمز Σ∗ إلى انغلاق الأبجدية Σ، أي مجموعة كل الكلمات التي يمكن تكوينها من حروف الأبجدية Σ. ومن عناصر الانغلاق أيضاً الكلمة الفارغة التي نرمز لها بالرمز ε.
إذا كان لدينا الأوتومات ⟨Q, Σ, δ, q0, F⟩ ونحاول أن نقبل الكلمة w، فإنّ الأوتومات يكون في التشكيل الابتدائي ⟨q0, w⟩. فإذا عدنا إلى الأوتومات
وأردنا أن نقبل الكلمة w = abbc، فإنّ التشكيل الابتدائي يكون ⟨q0, abbc⟩.
الخطوة الحسابية نعرّفها بأنها علاقة ↦ بين المجموعتين (Q × Σ∗) × (Q × Σ∗)، أي بين تشكيلات الأوتومات. ليمثّل w = w0w1… wn الجزء الذي لم يُقرأ بعد من الكلمة w. عندئذٍ نقول إنّ الثنائيين ⟨q1, w0w1… wn⟩ و ⟨q2, w1… wn⟩ مرتبطان بالعلاقة ↦، ونكتب
إذا وفقط إذا كان δ(q1, w0) = q2. ولنعد إلى مثالنا: التشكيل الابتدائي هو ⟨q0, abbc⟩. ونرى من المخطط أنّ المدخل «a» ينقلنا إلى الحالة q1. فيمكننا أن نكتب
لأنّ δ(q0, a) = q1. وبذلك نفّذنا خطوة حسابية واحدة: نظرنا إلى الحالة التي يجب أن ننتقل إليها بالمدخل المعطى (وهو الحرف الأول من الجزء الذي لم يُقرأ بعد من الكلمة)، فانتقلنا إليها وحذفنا الحرف الأول من الجزء غير المقروء. فحصلنا على تشكيل جديد.
الانغلاق الانعكاسي والمتعدي لعلاقة الخطوة الحسابية نرمز له بالرمز ↦ ∗. فإذا كتبنا K1 ↦ ∗ K2، حيث K1, K2 تشكيلان للأوتومات، فمعنى ذلك أننا نستطيع أن نصل من التشكيل K1 إلى التشكيل K2 بعدة خطوات حسابية، أي توجد متتالية منتهية من التشكيلات تحقق:
فمثلاً لدينا في أوتوماتنا ⟨q0, abbc⟩ ↦ ∗ ⟨q1,bc⟩، لأننا إذا نفّذنا خطوتين حسابيتين بقيت لنا الكلمة «bc» وبقينا في الحالة q1. أي توجد متتالية التشكيلات الآتية:
يقبل الأوتومات الكلمة w إذا وفقط إذا وُجدت qf ∈ F بحيث
والحالة q2 حالة نهائية، q2 ∈ F.
اللغة التي يقبلها الأوتومات هي مجموعة كل الكلمات التي يقبلها. ونرمز للغة الأوتومات A بالرمز L(A). إذن L(A) ⊆ Σ∗ و
اللغة المنتظمة (regular language) هي اللغة التي يقبلها أوتومات منتهٍ ما.
يكون الأوتوماتان المنتهيان متكافئين إذا قبلا اللغة نفسها. أي يكون الأوتوماتان A1 و A2 متكافئين إذا كان L(A1) = L(A2).
المصادر
المحتويات: الأوتومات المنتهي, الأوتومات الكامل, الأوتومات المنتهي غير الحتمي, محاكاة الأوتومات غير الحتمي, تحويل NFA إلى DFA