✖

रेगुलर एक्सप्रेशन से ऑटोमेटा में रूपांतरण

हम दिखाएँगे कि किसी भी रेगुलर एक्सप्रेशन को अनियतात्मक परिमित ऑटोमेटा में कैसे बदला जाता है।

उदाहरण

एल्गोरिद्म का वर्णन करने से पहले हम एक उदाहरण पर दिखाएँगे कि हमें करना क्या है। मान लीजिए यह रेगुलर एक्सप्रेशन है: a(b|c)x∗। रेगुलर एक्सप्रेशन जो भाषा जनित करता है, उसका शब्दों में वर्णन इस प्रकार होगा: वे स्ट्रिंगें, जो अक्षर “a” से शुरू होती हैं, जिसके बाद या तो अक्षर “b” या “c” आता है और फिर कितनी भी बार अक्षर “x”। क्या हम ऐसा ऑटोमेटा बना सकते हैं, जो यह भाषा स्वीकार करे? हाँ, देखिए:

स्पष्ट है कि यह ऑटोमेटा वही भाषा स्वीकार करता है। इसलिए स्वाभाविक प्रश्न उठता है: क्या प्रत्येक रेगुलर एक्सप्रेशन के लिए ऐसा ऑटोमेटा मौजूद है, जो वह भाषा स्वीकार करे? हाँ, मौजूद है।

रेगुलर एक्सप्रेशन को ऑटोमेटा में बदलने के एल्गोरिद्म का वर्णन

हम मानते हैं कि इनपुट पर रेगुलर एक्सप्रेशन R है। रेगुलर एक्सप्रेशन वाले पिछले भाग से हम जानते हैं कि रेगुलर एक्सप्रेशन के कुल छह भिन्न रूप हो सकते हैं। इसलिए हम छह भिन्न स्थितियाँ अलग करते हैं:

  1. किसी प्रतीक a ∈ Σ के लिए R = a। अर्थात् रेगुलर एक्सप्रेशन उस वर्णमाला Σ का केवल एक प्रतीक है, जिस पर हम काम कर रहे हैं। एक प्रतीक a को स्वीकार करने वाला ऑटोमेटा ऐसा दिखेगा:

  2. R = ϵ, रिक्त स्ट्रिंग। रिक्त स्ट्रिंग को स्वीकार करने वाला ऑटोमेटा ऐसा दिखेगा:

  3. R = ∅, वह रेगुलर एक्सप्रेशन, जो रिक्त भाषा जनित करता है। ऐसी भाषा को पहचानने वाला ऑटोमेटा यह है:

  4. R = R1 ∪ R2, जहाँ R1, R2 रेगुलर एक्सप्रेशन हैं। हम जानते हैं कि रेगुलर भाषाओं का सम्मिलन फिर से रेगुलर भाषा है और हम ऐसी भाषा को स्वीकार करने वाला ऑटोमेटा बना सकते हैं। दूसरे शब्दों में, हम मानते हैं कि हमारे पास ऐसे ऑटोमेटा हैं, जो व्यंजकों R1 और R2 द्वारा जनित भाषाएँ पहचानते हैं, और उनकी सहायता से हम ऐसा ऑटोमेटा बनाते हैं, जो व्यंजक R1 ∪ R2 द्वारा जनित भाषा स्वीकार करता है। उदाहरण: यदि R1 = a और R2 = ϵ हो, तो विधि के अनुसार हमें यह ऑटोमेटा मिलता है:

  5. R = R1 ∘ R2, जहाँ R1, R2 रेगुलर एक्सप्रेशन हैं। स्थिति पिछले बिंदु जैसी ही है। रेगुलर भाषाओं का संयोजन रेगुलर भाषा है, इसलिए हम ऐसी भाषा को स्वीकार करने वाला ऑटोमेटा बना सकते हैं। इसलिए यदि R1 = a, R2 = b हो, तो संयोजन ऐसा दिखेगा:

  6. R=(R1∗), जहाँ R1 रेगुलर एक्सप्रेशन है। हम फिर जानते हैं कि रेगुलर भाषा का संवरक रेगुलर भाषा है। इसलिए यदि R = a∗ हो, तो ऑटोमेटा ऐसा दिखेगा:

इन बिंदुओं को क्रमशः लागू करके हम पूरे रेगुलर एक्सप्रेशन को परिमित ऑटोमेटा में बदल देते हैं।

पूरा उदाहरण

आइए, रेगुलर एक्सप्रेशन (a|bc)∗ को बदलें। क्रमशः हमें ये ऑटोमेटा मिलते हैं:

यह परिणामी ऑटोमेटा वह भाषा स्वीकार करता है, जिसे रेगुलर एक्सप्रेशन (a|bc)∗ जनित करता है। स्वाभाविक है कि ऑटोमेटा बेहद जटिल है और निश्चित रूप से कहीं सरल ऑटोमेटा मौजूद है, जो वही भाषा स्वीकार करता है। इसके लिए हम NFA को DFA में बदलने के एल्गोरिद्म का प्रयोग कर सकते हैं और फिर ऑटोमेटा का न्यूनीकरण कर सकते हैं।

स्रोत

विषय-सूची: रेगुलर एक्सप्रेशन, रेगुलर एक्सप्रेशन से ऑटोमेटा में रूपांतरण, व्यापकीकृत अनियतात्मक परिमित ऑटोमेटा, ऑटोमेटा से रेगुलर एक्सप्रेशन में रूपांतरण