मैथमैटिका

Question

में नियमित अभिव्यक्ति को सरल बनाएं मैंने हाल ही में नियमित अभिव्यक्तियों को कुशल बनाने और सरल बनाने के लिए लगभग Kleene algebra पाया।

मुझे आश्चर्य है कि क्या यह गणित जैसे किसी भी कम्प्यूटेशनल सॉफ्टवेयर प्रोग्राम में बनाया गया है? यूनियनों और बड़े अभिव्यक्तियों के संयोजन के लिए एक कम्प्यूटेशनल टूल होना बहुत अच्छा होगा और कंप्यूटर उन्हें सरल बना देगा।

यदि आप इस बीजगणित के साथ किसी भी कार्यक्रम से अवगत नहीं हैं, तो क्या आप ऐसे किसी प्रोग्राम को जानते हैं जो अपने इंजन को नए बीजगणित के साथ विस्तारित करने की अनुमति देता है?

Answer 1

http://www.maplesoft.com/msw/program/MSW04FinalProgram.pdf पर, यह कहा गया है:

परिमित ऑटोमेटा के सिद्धांत के बुनियादी परिणामों में से एक प्रसिद्ध क्लीन प्रमेय, जिसमें कहा गया है कि एक भाषा एक परिमित automaton द्वारा स्वीकार्य है यदि और केवल यदि इसे नियमित अभिव्यक्ति द्वारा दर्शाया जा सकता है।

और

नियमित अभिव्यक्ति की एल्गोरिथम उपचार का मुख्य कठिनाई तथापि, उनके सरलीकरण। हालांकि कई पहचान नियमित अभिव्यक्तियों से संबंधित हैं, उदाहरण के लिए, क्लेन बीजगणित के नियम , नियमित अभिव्यक्तियों की सरलीकरण समस्या को हल करने के लिए के लिए एक प्रभावी एल्गोरिदम मौजूद नहीं है।

और

परिस्थितियों में, एक ही रास्ता छोड़ दिया नियमित अभिव्यक्ति को सरल बनाने के लिए अनुमानी एल्गोरिदम विकसित करना है। aut पैकेज के लिए, यह पेपर मेपल प्रक्रियाओं को रेखांकित करता है, रैबर्सब और रेक्सपैंड।

मुझे आश्चर्य है कि क्लेन बीजगणित एल्गोरिदम के खुले स्रोत कार्यान्वयन मौजूद हैं या नहीं।