परस्पर अनन्य नियमित अभिव्यक्ति

Question

यदि मेरे पास नियमित अभिव्यक्तियों की एक सूची है, तो क्या यह निर्धारित करने का एक आसान तरीका है कि उनमें से कोई भी एक ही स्ट्रिंग के लिए एक मैच वापस नहीं करेगा?

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

ऐसा लगता है कि यह बहुत मुश्किल (शायद असंभव?) निश्चित साबित करने के लिए किया जाएगा, लेकिन मैं इस विषय पर किसी भी काम को खोजने के लिए प्रतीत नहीं कर सकते हैं।

कारण मैं पूछता हूं कि मैं एक टोकनज़र पर काम कर रहा हूं जो regexes स्वीकार करता है, और मैं यह सुनिश्चित करना चाहता हूं कि एक समय में केवल एक टोकन इनपुट के सिर से मेल खा सके।

Answer 1

आप शुद्ध नियमित अभिव्यक्ति (कोई backreferences या अन्य सुविधाओं के कारण उन्हें विषय से मुक्त या अधिक जटिल भाषाओं पहचान करने के लिए) के साथ काम कर रहे हैं, तो आप क्या पूछना संभव है। आप क्या कर सकते हैं प्रत्येक रेगेक्स को डीएफए में परिवर्तित कर सकते हैं, फिर (चूंकि नियमित भाषाएं छेड़छाड़ के नीचे बंद होती हैं) उन्हें एक डीएफए में जोड़ती है जो को दो भाषाओं के चौराहे को पहचानती है। यदि उस डीएफए के पास प्रारंभिक स्थिति से एक स्वीकार्य स्थिति का पथ है, तो वह स्ट्रिंग दोनों इनपुट रेगेक्सन द्वारा स्वीकार की जाती है।

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

यदि आप विस्तारित रेगेक्स वाक्यविन्यास के साथ काम कर रहे हैं, तो सभी दांव बंद हैं: संदर्भ-मुक्त भाषा चौराहे के नीचे बंद नहीं हैं, इसलिए यह विधि काम नहीं करेगी।

Answer 2

Wkipedia article on regular expressions राज्य

यह एक एल्गोरिथ्म जो दिए गए दो नियमित अभिव्यक्ति के लिए निर्णय लेता है कि वर्णित भाषाओं अनिवार्य रूप से समान हैं लिखने के लिए संभव है, एक न्यूनतम नियतात्मक परिमित स्थिति मशीन के लिए प्रत्येक अभिव्यक्ति को कम कर देता है, और निर्धारित करता है कि वे आइसोमोर्फिक (समतुल्य) हैं।

लेकिन आगे नहीं संकेत देता है।

बेशक

आसान तरीका आप के बाद कर रहे हैं परीक्षण का एक बहुत चलाने के लिए है - लेकिन हम सभी सबूत के एक तरीके के रूप में परीक्षण की कमियों को जानते हैं।

Answer 3

आप केवल नियमित अभिव्यक्ति को देखकर ऐसा नहीं कर सकते हैं।

मामले ऐसे हैं जिनमें [0-9] और [0-9]+ है पर विचार करें। वे स्पष्ट रूप से अलग अभिव्यक्ति हैं, लेकिन जब स्ट्रिंग "1" पर लागू होते हैं, तो वे दोनों एक ही परिणाम उत्पन्न करते हैं। स्ट्रिंग "11" पर लागू होने पर वे अलग-अलग परिणाम उत्पन्न करते हैं।

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