नियमित अभिव्यक्ति समतुल्यता

Question

क्या यह पता लगाने का कोई तरीका है कि दो मनमानी नियमित अभिव्यक्ति समकक्ष हैं या नहीं? मुझे जटिल समस्या की तरह लग रहा है, लेकिन कुछ डीएफए सरलीकरण तंत्र या कुछ हो सकता है?

Answer 1

तुल्यता परीक्षण करने के लिए आप के लिए भाव minimal DFAs गणना और उनकी तुलना कर सकते हैं ।

Answer 2

इन दो Perlmonks धागे इस सवाल पर चर्चा (विशेष रूप से, blokhead की प्रतिक्रियाओं पढ़ें):

• Comparative satisfiability of regexps
• Testing regex equivalence

Answer 3

समानता की साक्ष्य नियमित अभिव्यक्तियों के शास्त्रीय गुणों में से एक है। (नायब यह नहीं रखता है यदि आप वास्तव में तकनीकी रूप से nonregular superlanguage पर्ल नियमित अभिव्यक्ति या कुछ अन्य के बारे में बात कर रहे हैं।)

सामान्यीकृत परिमित ऑटोमेटा एक करने के लिए अपने आर ई चालू

और बी, फिर एक नया automaton एबी ऐसी है कि निर्माण ए के स्वीकार्य राज्यों में बी के प्रारंभिक राज्यों में शून्य संक्रमण हैं, और बी के स्वीकार्य राज्य उलटे हुए हैं। यह आपको एक automaton देता है जो बी द्वारा स्वीकार किए गए सभी स्ट्रिंग को स्वीकार करता है, बी

बी-ए के लिए ऐसा ही करें, और शुद्ध एफए दोनों को कम करें। यदि एक एफए के पास प्रारंभिक राज्य से कोई स्वीकार्य राज्य सुलभ नहीं है तो यह खाली भाषा स्वीकार करता है। यदि आप दिखा सकते हैं कि एबी और बीए दोनों खाली हैं, तो आपने दिखाया है कि ए = बी

Edit हे, मुझे विश्वास नहीं है कि किसी ने भी वहां बड़ी त्रुटि देखी - एक जानबूझकर, - - पी

वर्णित ऑटोमाटा एबी उन तारों को स्वीकार करेगा जिनकी पहली छमाही ए द्वारा स्वीकार की जाती है और जिसका दूसरा आधा बी द्वारा स्वीकार नहीं किया जाता है वांछित एबी एक छोटी सी चालक प्रक्रिया है। मैं इसे अपने सिर के ऊपर से नहीं सोच सकता, लेकिन मुझे पता है कि यह अच्छी तरह से परिभाषित है (और संभवतः बी में राज्यों को स्वीकार करने और बी में गैर-स्वीकार्य राज्यों के उत्पादों का प्रतिनिधित्व करने के लिए राज्य बनाने में शामिल है)।

Answer 4

यह वास्तव में नियमित अभिव्यक्तियों से आपका क्या मतलब है इस पर निर्भर करता है। जैसा कि अन्य पोस्टर ने इंगित किया है, दोनों अभिव्यक्तियों को उनके न्यूनतम डीएफए में कम करना चाहिए, लेकिन यह केवल शुद्ध नियमित अभिव्यक्तियों के लिए काम करता है।

असली दुनिया regex libs (विशेष रूप से बैकरेक्शंस) में उपयोग की जाने वाली कुछ संरचनाएं उन्हें उन भाषाओं को व्यक्त करने की शक्ति देती हैं जो नियमित नहीं हैं, इसलिए डीएफए एल्गोरिदम उनके लिए काम नहीं करेगा। उदाहरण के लिए रेगेक्स: ([a-z]*) \1 एक स्पेस (a a और b b) से अलग शब्द के डबल अवसर से मेल खाता है लेकिन b a और न ही a b)। यह एक सीमित automaton द्वारा बिल्कुल पहचाना नहीं जा सकता है।