जांचें कि क्या दिया गया रेगेक्स कुछ भी मेल खाता है

Question

क्या यह जांचना संभव है कि कोई नियमित नियमित अभिव्यक्ति किसी स्ट्रिंग से मेल खाती है या नहीं? विशेष रूप से, मैं एक फ़ंक्शन matchesEverything($regex) ढूंढ रहा हूं जो सत्य iff $regex किसी भी स्ट्रिंग से मेल खाता है।

मुझे लगता है कि यह पूछने के बराबर है, "एक रेगेक्स r दिया गया है, क्या ऐसी स्ट्रिंग मौजूद है जो r से मेल नहीं खाती है?" और मुझे नहीं लगता कि यह "सभी तारों" के सेट पर सीमा लगाए बिना हल करने योग्य है। यानी, अगर मुझे लगता है कि तारों में कभी भी "blahblah" नहीं होगा, तो मैं बस जांच सकता हूं कि r "blahblah" से मेल खाता है या नहीं। लेकिन क्या होगा यदि ऐसी कोई सीमा नहीं है? मैं सोच रहा हूं कि क्या इस समस्या को हल किया जा सकता है अगर रेगेक्स r.* के बराबर है।

Answer 1

यही आपके प्रश्न का उत्तर नहीं है, लेकिन उम्मीद है कि एक छोटे से बताता है कि क्यों एक सरल जवाब मिलना मुश्किल है:

पहले, शब्द 'regex' थोड़ा संदिग्ध है, इसलिए केवल स्पष्ट करने के लिए, हम है:

• "सख्त" नियमित अभिव्यक्तियां, जो निर्धारिती परिमित automatons (DFAs) के बराबर होती हैं।
• पर्ल-संगत नियमित अभिव्यक्ति (पीसीआरई), जो घड़ियों और सीटों जैसे गुच्छे, बैकरेन्फर इत्यादि का एक गुच्छा जोड़ते हैं। इन्हें अन्य भाषाओं में भी पाइथन और जावा जैसे कार्यान्वित किया जाता है।
• वास्तविक पर्ल नियमित अभिव्यक्तियां, जो ?{...} निर्माण के माध्यम से मनमाने ढंग से पर्ल कोड सहित और भी पागल हो सकती हैं।

मुझे लगता है कि यह समस्या सख्त नियमित अभिव्यक्तियों के लिए हल करने योग्य है। आप केवल संबंधित डीएफए का निर्माण करते हैं और उस ग्राफ को खोजते हैं कि यह देखने के लिए कि क्या एक स्वीकार्य स्थिति का कोई पथ है या नहीं। लेकिन यह 'असली दुनिया' regex के लिए मदद नहीं करता है, जो आमतौर पर पीसीआरई है।

मुझे नहीं लगता कि पीसीआरई ट्यूरिंग-पूर्ण है (हालांकि मुझे नहीं पता - यह प्रश्न भी देखें: Are Perl regexes turing complete?)। अगर ऐसा होता, तो मुझे लगता है कि जिम गैरीसन ने टिप्पणी की थी, यह मूल रूप से रोकथाम की समस्या है। यह कहा गया है कि, उन्हें उपरोक्त विधि को बेकार बनाने के लिए, उन्हें डीएफए में बदलने में आसान नहीं है ...

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

?{...} के साथ एक वास्तविक पर्ल रेगेक्स निश्चित रूप से ट्यूरिंग-पूर्ण है, इसलिए ड्रैगन हैं, और मुझे लगता है कि आप भाग्य से बाहर हैं।