नियमित अभिव्यक्तियों के लिए एल्गोरिदम -

Question

पर संयोजन या मैं नियमित रूप से अभिव्यक्ति तारों को पार्स करने के लिए एक सी ++ एप्लिकेशन विकसित कर रहा हूं और उसके बाद कुछ गणना करता हूं। क्या कोई मौजूदा एल्गोरिदम है जो लंबाई एल के तारों की संख्या एन को आउटपुट कर सकता है जिसे किसी दिए गए रेगेक्स द्वारा (a|ab)* | (aa|bb)* द्वारा पहचाना जा सकता है? या क्या कोई गणितीय सूत्र है जिसका उपयोग मैं फैक्टोरियल को शामिल करने के लिए कर सकता हूं? मैं बस स्ट्रिंग्स की संख्या एन प्राप्त करना चाहता हूं जिसे किसी दिए गए नंबर एल के लिए ऐसे रेगेक्स वाक्यांशों द्वारा पहचाना जा सकता है। (a|ab)* के लिए उदाहरण रेगेक्स द्वारा लंबाई 5 (एल) के कितने तारों को पहचाना जा सकता है। मुझे लगता है कि जवाब 5 होगा। लेकिन एल की उच्च संख्या के लिए मैं सोच रहा था कि क्या कोई एल्गोरिदम या गणित अभिव्यक्तियां हैं जो इसकी गणना कर सकती हैं।

Answer 1

मैट्रिक्स एक्सपोनिएशन पर आधारित एक कुशल एल्गोरिदम है जिसका उपयोग आप इन संख्याओं की गणना के लिए कर सकते हैं।

मैं केवल उच्च स्तर का विवरण देने जा रहा हूं, कोड नहीं।

1. सबसे पहले, आप, कंप्यूटर विज्ञान की नींव से एक प्रसिद्ध तुल्यता उपयोग करने के लिए है कि एक (सरल) रेगुलर एक्सप्रेशन एक परिमित राज्य मशीन के बराबर है चाहता हूँ।

   (याद रखें कि एक परिमित राज्य मशीन, अनिवार्य रूप से एक प्रवाह चार्ट है, जिसमें प्रत्येक नोड से, आपके वर्णमाला में प्रत्येक अक्षर के लिए कुछ विशेष नोड (या शायद यह एक लूप) के लिए एक लेबल वाला किनारा होता है। इसके अतिरिक्त, राज्यों के कुछ उप-समूह को "स्वीकृति सेट" कहा जाता है, और प्रवाह चार्ट में कुछ विशेष राज्य प्रारंभिक स्थिति है। एक स्ट्रिंग को परिमित राज्य मशीन में पथ शुरू करने के लिए कहा जाता है, प्रारंभिक स्थिति में शुरू होता है और लेबल के बाद उत्तराधिकार में किनारों। मशीन accepts एक स्ट्रिंग अगर अंतिम स्थिति स्वीकृति सेट में है, और rejects एक स्ट्रिंग अन्यथा है। एक शास्त्रीय निर्माण से पता चलता है कि किसी भी नियमित अभिव्यक्ति से हम समान आकार की एक सीमित राज्य मशीन बना सकते हैं, और किसी भी परिमित से राज्य मशीन हम समान आकार की नियमित अभिव्यक्ति बना सकते हैं। कोई भी भाषा (उप सभी परिमित तारों का सेट) जो नियमित अभिव्यक्ति के अनुरूप होता है उसे "नियमित" कहा जाता है और एक भाषा नियमित होती है और केवल तभी जब यह एक सीमित राज्य मशीन से मेल खाती है।)

   उदाहरण के लिए, यदि मेरे पास वर्णमाला {a,b,c} है, और नियमित अभिव्यक्ति (a|b)*, यह दो राज्यों वाली मशीन से मेल खाती है। प्रारंभ स्थिति में a लेबल वाला लूप होता है, जो b लेबल वाला एक लूप होता है, और दूसरे राज्य में c लेबल वाला एक तीर होता है। दूसरे राज्य में तीन लूप हैं, इसलिए यदि आप वहां जाते हैं तो आप फंस जाते हैं। स्वीकृति सेट में केवल प्रारंभिक स्थिति होती है।

   आपके कार्यक्रम का पहला चरण एक नियमित अभिव्यक्ति को एक संबंधित परिमित राज्य मशीन में परिवर्तित करना है। (ऐसा हो सकता है कि कुछ मौजूदा रेगेक्स लाइब्रेरी पहले से ही यह करती है, मुझे लगता है कि पीसीआरई हो सकता है, हालांकि मुझे यकीन नहीं है।)

2. एक सीमित राज्य मशीन को देखते हुए, मैं एक संबंधित स्टोकास्टिक मैट्रिक्स बनाना चाहता हूं। इस मैट्रिक्स में, हमारे पास प्रत्येक राज्य के लिए एक पंक्ति है, और प्रत्येक राज्य के लिए एक कॉलम है, और प्रत्येक प्रविष्टि एक संभावना है। प्रविष्टि p_{i,j} प्रविष्टि (i,j) पर, संभावना के बराबर है कि यदि मैं i पर हूं, और मैंने एक यादृच्छिक पत्र पढ़ा है, तो मैं अगले j पर जाता हूं। इसलिए उदाहरण मैं दे दी है के लिए, मैट्रिक्स

   [2/3 1/3]
   [0 1]

3. आप तो मैट्रिक्स घातांक का उपयोग कर लंबाई k, के तार के बारे में जानना चाहते हैं, गणना है मैट्रिक्स M^k जहां M ऊपर संभावित संभाव्यता मैट्रिक्स है।

4. अंत में, यदि q प्रारंभ स्थिति है, स्वीकृति सेट में प्रत्येक राज्य s के लिए सभी प्रविष्टियां M^k_{q, s} जोड़ें। इन संभावनाओं का योग संभावना के बराबर है कि नियमित अभिव्यक्ति द्वारा k की एक यादृच्छिक स्ट्रिंग स्वीकार की जाती है। इसलिए, आप N^k द्वारा गुणा करके इस तरह के तारों की संख्या प्राप्त कर सकते हैं जहां N आपके वर्णमाला में अक्षरों की संख्या है।

मुझे लगता है कि इस एल्गोरिथ्म के अस्तित्व मुश्किल नहीं है, लेकिन यह या तो तुच्छ नहीं है, मैं एक बार गणना वर्ग के एक सिद्धांत में एक अंतिम परीक्षा में एक अतिरिक्त क्रेडिट समस्या के रूप में इस का एक कठिन संस्करण दे दी है। मैं इसके किसी भी मौजूदा कार्यान्वयन के बारे में नहीं जानता, जानने में दिलचस्पी होगी।

कुछ महत्वपूर्ण गति-अप है कि आप निष्क्रिय तरीके से ऐसा करते हैं, जब आप मैट्रिक्स एक्सपोनिएशन का उपयोग करते हैं। यह आपको इसे बड़े k के लिए जल्दी से करने की अनुमति देता है।

मुझे नहीं पता कि एक और अधिक कुशल, अनुमानित समाधान है, तो यह दिलचस्प होगा। मुझे लगता है कि यादृच्छिक नमूना हमेशा आपको कुछ देगा लेकिन मैट्रिक्स M या कुछ के एकवचन मूल्य अपघटन करने के आधार पर शायद कुछ प्रकार का स्पेक्ट्रल एल्गोरिदम है।

नोट: यदि आप वास्तव में इसे कार्यान्वित करना चाहते हैं, तो मुझे लगता है कि आपको फ़्लोटिंग पॉइंट नंबरों का उपयोग नहीं करना चाहिए, मैट्रिक्स M वास्तव में पूर्णांक का मैट्रिक्स होना चाहिए। असल में आप इसे N से गुणा करेंगे जहां N आपके वर्णमाला में अक्षरों की संख्या है। और आप बाद में N^k द्वारा राशि गुणा छोड़ देंगे। मुझे लगता है कि संभावनाओं का उपयोग करना समझना आसान है, लेकिन उस संस्करण में, M^k_{i,j} सिर्फ number of paths from i to j of length k की गणना करेगा।

नोट: जैसा कि टिप्पणियों में बताया गया है, यह एल्गोरिदम किसी भी निश्चित नियमित अभिव्यक्ति के लिए k की बिट्स की संख्या में बहुपद है, इसलिए यह k के लिए भी अच्छा है। यह सबसे खराब मामले में घातीय है हालांकि नियमित अभिव्यक्ति के आकार में - बड़े और जटिल नियमित अभिव्यक्तियों को संभालने के लिए, यदि आप इस विधि का उपयोग करना चाहते हैं तो आपको किसी प्रकार का डीएफए न्यूनतमकरण का उपयोग करना चाहिए। प्रश्न में दिखाए गए सरल नियमित अभिव्यक्तियों के लिए, मुझे लगता है कि यह ठीक होना चाहिए।