الأوتومات المنتهي غير الحتمي المعمم
الأوتومات المنتهي غير الحتمي المعمم (generalized NFA)، واختصاره GNFA، أوتومات غير حتمي لا تقتصر انتقالاته على رموز الأبجدية، بل يمكن أن تحمل تعبيراً نمطياً.
تعريف GNFA
سنحتاج إلى GNFA في خوارزمية تحويل الأوتومات المنتهي إلى تعبير نمطي. فالأوتومات GNFA إذن هو NFA معرَّفة انتقالاته بتعابير نمطية. وهذا مثال على GNFA:
نرى مثلاً أنّ من الحالة q2 يخرج انتقال إلى الحالة qf، وهو موسوم بالتعبير النمطي a∗ b. ومن الشروط الأخرى التي يجب أن يحققها GNFA:
- يجب أن يكون للحالة الابتدائية q0 انتقال إلى كل الحالات الأخرى. ونرى في الشكل أنّ من الحالة q0 تخرج انتقالات إلى كل الحالات الأخرى.
- يوجد في GNFA حالة نهائية واحدة فقط، ولكل الحالات الأخرى انتقال إليها. وكما نرى في الشكل، لكل الحالات سهم يتجه إلى qf.
- يجب ألّا تكون الحالة الابتدائية هي الحالة النهائية نفسها. ولذلك يكون لكل GNFA حالتان على الأقل.
- يجب أن يكون لكل الحالات الأخرى، ما عدا الحالة الابتدائية والحالة النهائية، انتقالات إلى كل الحالات الأخرى ما عدا الحالة الابتدائية والحالة النهائية، ومنها الحلقات (الانتقال من الحالة qi إلى الحالة qi).
تحويل NFA العادي إلى GNFA
إذا كان لدينا NFA ما، فتحويله إلى GNFA بسيط.
- ننشئ حالة ابتدائية جديدة qs، وننشئ منها انتقال إبسيلون إلى الحالة الابتدائية الأصلية.
- ننشئ حالة نهائية جديدة qf، ونرسم من كل الحالات النهائية الأصلية انتقالات إبسيلون إلى الحالة qf. ونجعل الحالات النهائية الأصلية حالات عادية.
- إذا وُجد في مكان ما انتقال متعدد (أي إذا كنا ننتقل من الحالة q1 إلى الحالة q2 بالرمز 0 وبالرمز 1 أيضاً)، دمجنا هذه القواعد في تعبير نمطي واحد، ووصلنا كل الرموز الأصلية بعامل الاتحاد (أي نسم السهم بالتعبير النمطي 0|1).
- إذا نقص الأوتومات انتقال ينبغي أن يكون فيه بحسب التعريف، أنشأناه ووسمناه بالتعبير النمطي ∅. ولا نغيّر بذلك اللغة التي يقبلها الأوتومات، لأنّ مثل هذا الانتقال لا يُنفَّذ أبداً.
ويمكننا أن نستعمل هذا الأوتومات لتحويل الأوتومات إلى تعبير نمطي.
المحتويات: التعابير النمطية, تحويل التعبير النمطي إلى أوتومات, الأوتومات المنتهي غير الحتمي المعمم, تحويل الأوتومات إلى تعبير نمطي