क्या सभी नियमित अभिव्यक्ति रोकें?

Question

क्या कोई नियमित अभिव्यक्ति है जो कुछ इनपुट स्ट्रिंग के लिए हमेशा के लिए एक खोज की खोज करेगी?

Answer 1

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

किसी भी औपचारिक नियमित अभिव्यक्ति का निर्धारण एक निर्धारित फार्माइट ऑटोमाटा में किया जा सकता है। एक डीएफए एक समय में इनपुट एक चरित्र को पढ़ता है, और, इनपुट के अंत में, आप या तो एक स्वीकार्य स्थिति में या एक स्वीकार्य स्थिति में हैं। अगर राज्य स्वीकार कर रहा है, तो इनपुट नियमित अभिव्यक्ति से मेल खाता है। अन्यथा, यह नहीं करता है।

अब, अधिकांश "नियमित अभिव्यक्ति" पुस्तकालय उन चीजों का समर्थन करते हैं जो नियमित अभिव्यक्ति नहीं हैं, जैसे कि पीछे संदर्भ।जब तक आप उन सुविधाओं से दूर रहते हैं, और एक सीमित इनपुट है, तो आप को रोक दिया जाता है। यदि आप नहीं करते ... आप जो भी उपयोग कर रहे हैं उसके आधार पर, आपको रोकथाम की गारंटी नहीं दी जा सकती है। पर्ल मनमाने ढंग से कोड डालने की अनुमति देता है, उदाहरण के लिए, और मनमाने ढंग से, ट्यूरिंग-मशीन समकक्ष कोड को रोकने की गारंटी नहीं है।

अब, यदि इनपुट अनंत है, तो मामूली नियमित अभिव्यक्तियां पाई जा सकती हैं जो कभी नहीं रुकतीं। उदाहरण के लिए, ".*"।

Answer 2

आपके द्वारा वर्णित अर्थ में नहीं, आप कुछ बहुत ही अक्षम नियमित अभिव्यक्तियां प्राप्त कर सकते हैं जो संसाधनों का भार लेते हैं और रेगेक्स इंजन को मारने के अंत में, यह रोकना उतना ही नहीं है।

मुझे नहीं लगता कि वास्तव में रोकना वास्तव में यहां लागू होता है, क्योंकि इस पोस्ट के अन्य टिप्पणीकारों ने इतनी स्पष्टता से बताया है। http://en.wikipedia.org/wiki/Halting_problem

Answer 3

this question के अनुसार, प्रत्येक नियमित अभिव्यक्ति रोकती है।

Answer 4

मुझे कल्पना है, नियमित अभिव्यक्ति को ढूंढना संभव नहीं है जो रोक नहीं है।

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

जब तक एल्गोरिदम का उपयोग नहीं किया जाता है, तब तक बेवकूफ (कई बार मामलों पर जा रहा है), मिलान किए गए उपसमूहों की संख्या भी सीमित होगी।

तो, यह रुक जाएगा।

Answer 5

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

उदाहरण के लिए, यदि भाषा में * बी स्वीकार किया जाता है, और आपके पास 'ए' की असीमित लंबी स्ट्रिंग है, तो हाँ, रेगेक्स कभी नहीं रुक जाएगा। व्यावहारिक रूप से, हालांकि, यह असंभव है।

Answer 6

औपचारिक रेगेक्स वास्तव में तारों को पार्स करने के लिए एक निर्धारक परिमित automaton का वर्णन करने का एक तरीका है। रेगेक्स "मैचों" अगर डीएफए इनपुट के अंत में एक स्वीकार्य राज्य में हवादार हो जाता है। चूंकि डीएफए अनुक्रमिक रूप से इसके इनपुट को पढ़ता है, इसलिए यह हमेशा इनपुट के अंत तक पहुंचने पर रोक देगा, और चाहे कोई मैच है या नहीं, यह जांचने की बात है कि डीएफए की कौन सी स्थिति रुकती है।

सबस्ट्रिंग मिलान प्रभावी रूप से वही है, स्ट्रिंग के एक पठन-थ्रू के अंत में रुकने के लिए मजबूर होने के बजाय, डीएफए को इसके बजाय प्रत्येक संभावित सबस्ट्रिंग को पढ़ने के बाद रोकना होगा - अभी भी एक सीमित मामला। (हां, अधिकांश रेगेक्स इंजन इसे डीएफए में हर संभव सबस्ट्रिंग को फेंकने की तुलना में थोड़ा अधिक अनुकूलित तरीके से कार्यान्वित करते हैं - लेकिन अवधारणात्मक रूप से यह सीमा अभी भी वहां है)।

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

Answer 7

हां।

एक नियमित अभिव्यक्ति को एक सीमित राज्य मशीन द्वारा प्रदर्शित किया जा सकता है। हर बार जब आप परमाणु इनपुट प्राप्त करते हैं, तो यह ज्ञात स्थिति में संक्रमण के लिए किसी भी अच्छी तरह से परिभाषित एफएसएम का कारण बन जाएगा।

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

http://en.wikipedia.org/wiki/Finite_state_machine

Answer 8

डैनियल जवाब के +1: सभी परिमित आदानों का कारण सही regex के (जैसे कि, backreferences या अन्य गैर-regex सुविधाओं के बिना) को रोकने के लिए, और regex के DFAs के बराबर हैं।

बोनस: नियमित अभिव्यक्ति मिलान आसान और तेज़ जा सकता है (लेकिन जावा, पर्ल, PHP, अजगर, रूबी, में धीमी है ...)

http://swtch.com/~rsc/regexp/regexp1.html

ध्यान दें कि दो रेखांकन लेख के शीर्ष में वाई-अक्ष पर अलग-अलग पैमाने हैं: एक सेकंड है, दूसरा माइक्रोसेकंड है!