व्यापकीकृत अनियतात्मक परिमित ऑटोमेटा
व्यापकीकृत अनियतात्मक परिमित ऑटोमेटा (generalised non-deterministic finite automaton), संक्षेप में 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 लिखिए)।
- यदि ऑटोमेटा में कोई ऐसा संक्रमण नहीं है, जो परिभाषा के अनुसार होना चाहिए, तो उसे बनाइए और उस पर रेगुलर एक्सप्रेशन ∅ लिखिए। इससे ऑटोमेटा द्वारा स्वीकृत भाषा नहीं बदलती, क्योंकि ऐसा संक्रमण कभी होता ही नहीं।
इस ऑटोमेटा का प्रयोग हम ऑटोमेटा को रेगुलर एक्सप्रेशन में बदलने के लिए कर सकते हैं।
विषय-सूची: रेगुलर एक्सप्रेशन, रेगुलर एक्सप्रेशन से ऑटोमेटा में रूपांतरण, व्यापकीकृत अनियतात्मक परिमित ऑटोमेटा, ऑटोमेटा से रेगुलर एक्सप्रेशन में रूपांतरण