6
समकक्ष हैं या नहीं, मैं यह पता लगाने की कोशिश कर रहा हूं कि एल्गोरिदम दो भाषाओं को एल 1 और एल 2 दिया जा रहा है यह निर्धारित करने के लिए कि वे बराबर हैं (एल 1 = एल 2) ।एक एल्गोरिदम खोजने की कोशिश कर रहा है जो 2 नियमित अभिव्यक्तियों को लेता है और बताता है कि वे
यह आश्चर्य की बात के रूप में मैं मिल गया है एक साथ आने के लिए मुश्किल है, हालांकि मैं बहुत यकीन है कि यह पहली बार एक DFA में परिवर्तित किया और फिर एक न्यूनतम DFA उनमें से प्रत्येक को कम की जरूरत है कर रहा हूँ ..
इसके अलावा, मुझे पता है कि यदि एल 1 - एल 2 और एल 2 - एल 1 खाली हैं, तो एल 1 = एल 2।
कोई भी सिद्धांत के साथ अच्छा है?
पढ़ें http://en.wikipedia.org/wiki/Regular_expression#Deciding_equivalence_of_regular_expressions – Gumbo
पहले से ही पढ़ा गया है ... और कुछ मिला? – John
@ गम्बो: वह लिंक सैद्धांतिक (गणितीय) मॉडल के लिए निश्चित रूप से है; वास्तविक रेगेक्स भाषाएं बहुत समृद्ध हैं और संरचनाएं शामिल हैं (विशेष रूप से पीछे संदर्भ) का अर्थ है कि वे अब/नियमित नहीं हैं। यह निश्चित रूप से केवल समस्या को कठिन बनाता है :-( – Richard