मैंने यहां कुछ टिप्पणियां देखी हैं जो उल्लेख करती हैं कि आधुनिक नियमित अभिव्यक्तियां नियमित भाषा में क्या प्रदर्शित की जा सकती हैं। यह कैसा है?आधुनिक नियमित अभिव्यक्ति बोलियां नियमित नहीं हैं?
आधुनिक नियमित अभिव्यक्तियों की कौन सी विशेषताएं नियमित नहीं हैं? उदाहरण सहायक होंगे।
(\w*)\s\1
(शब्द पात्रों के एक समूह, एक अंतरिक्ष चरित्र के बाद से मेल खाता है और फिर एक ही समूह पहले से मिलान) जैसे:: hello hello मैच, hello world नहीं करता '
पहली बात यह है कि मन में आता है backreferences है टी।
यह निर्माण नियमित नहीं है (यानी: regular grammar द्वारा उत्पन्न नहीं किया जा सकता है)।
\((a*|(?R))*\)
यह (से संतुलित कोष्ठक और "एक" एस के किसी भी संयोजन मैच के लिए इस्तेमाल किया जा सकता:
एक अन्य विशेषता यह पर्ल कम्पैटिबल RegExp (PCRE) कि नियमित रूप से नहीं है द्वारा समर्थित पुनरावर्ती पैटर्न हैं wikipedia)
कुछ बैकरेरेंस नियमित भाषा में किए जा सकते हैं। उदाहरण के लिए '(।) X \ 1' एक नियमित भाषा को परिभाषित करता है:" अक्ष "," बीएक्सबी ", आदि। मेरा मानना है कि यह केवल तभी होता है जब क्लेन बंद हो जाता है कि बैक्रेरेंस भाषा अनियमित बनाते हैं। – Gabe
आपको वहां की जगह की आवश्यकता नहीं है। '(। *) \ 1' करेगा। – Nabb
@Nabb: '.' '\ w * \ s' – BoltClock
एक निर्धारिती या नोडेटर्मिनिस्टिक सीमित परिमित नियमित नियमित अभिव्यक्तियों द्वारा वर्णित नियमित भाषाओं को पहचानता है। नियमित अभिव्यक्ति की परिभाषा सरल है। एस वर्णमाला बनें। फिर खाली सेट, खाली स्ट्रिंग, और एस के प्रत्येक तत्व नियमित अभिव्यक्तियां हैं (एस से अधिक)। u और v नियमित अभिव्यक्तियों को दें। तब संघ (यू | वी), संयोजन (यूवी), और बंद (यू *) यू और के वीसे अधिक नियमित अभिव्यक्ति एस हैं। यह परिभाषा नियमित भाषाओं तक आसानी से बढ़ा दी जाती है। कोई अन्य अभिव्यक्ति एक नियमित अभिव्यक्ति नहीं है। जैसा कि बताया गया है, कुछ बैक-रेफरेंस एक उदाहरण हैं। नियमित भाषाओं और अभिव्यक्तियों पर विकिपीडिया पेज अच्छे संदर्भ हैं।
संक्षेप में, कुछ "नियमित अभिव्यक्ति" नियमित नहीं होते हैं क्योंकि उन्हें पहचानने के लिए किसी विशेष प्रकार का कोई automaton नहीं बनाया जा सकता है। उदाहरण के लिए, भाषा
{एक^मैं b^मैं: मैं < = 0}
नियमित नहीं है। ऐसा इसलिए है क्योंकि स्वीकार्य automaton को असीमित कई राज्यों की आवश्यकता होगी, लेकिन नियमित भाषाओं को स्वीकार करने वाले एक automaton के पास राज्यों की सीमित संख्या होनी चाहिए।
मूल प्रश्न से निर्णय लेते हुए, मुझे पूरा यकीन है कि वह नियमित और गैर-नियमित भाषाओं के बीच भेद को समझता है। उनका सवाल यह है कि आधुनिक "नियमित अभिव्यक्ति" कार्यान्वयन की विशेषताएं नियमित रूप से ऐसी भाषाओं को परिभाषित नहीं करती हैं, और इसलिए सूचीबद्ध सूचीबद्ध संचालन का उपयोग करके किसी भी तरीके से व्यक्त नहीं की जा सकती हैं। –
शायद मुझे और अधिक बारीकी से पढ़ना चाहिए! किसी भी मामले में, मुझे नहीं लगता कि मैंने कोई नुकसान पहुंचाया है। – danportin
'a^i b^i' निश्चित रूप से अनियमित है (यह एक डीसीएफजी है), लेकिन क्या हम वास्तव में प्रोग्रामिंग भाषाओं के" नियमित अभिव्यक्तियों "का उपयोग करके इसे व्यक्त कर सकते हैं? – Nabb
उदाहरण के एक जोड़े:
/my (group)/.match("my group")[1] आउटपुट "समूह" होगा। किसी समूह में कुछ संग्रहीत करने के लिए बाहरी संग्रहण की आवश्यकता होती है, जो एक सीमित automaton नहीं है।(?<MYGROUP>.)* "।" के कई कैप्चर कर सकता है। एक ही समूह में।(?<MYGROUP>test) एक स्टैक को धक्का देता है, जबकि (?<-MYGROUP>) एक स्टैक पॉप करता है।(?<FIRSTGROUP-LASTGROUP>) है जो LASTGROUP को पॉप करता है और FIRSTGROUP स्टैक पर LASTGROUP अनुक्रमणिका के बाद कैप्चर को धक्का देता है। इसका उपयोग असीमित नेस्टेड निर्माणों से मेल खाने के लिए किया जा सकता है जो निश्चित रूप से एक सीमित automato की शक्ति से परे है एन।शायद अन्य अच्छे उदाहरण मौजूद हैं :-) आप आगे Regex के और संतुलित समूहीकरण और परिमित ऑटोमेटा से इस प्रकार उच्च आदेश ऑटोमेटा के साथ संयोजन में बाहरी ढेर के कार्यान्वयन विवरण में से कुछ में interessted रहे हैं, तो मैं एक बार दो छोटे लेख लिखा था इस पर (http://www.codeproject.com/KB/recipes/Nested_RegEx_explained.aspx और http://www.codeproject.com/KB/recipes/RegEx_Balanced_Grouping.aspx)।
वैसे भी - finitieness या नहीं - मैं blieve शक्ति है कि इस अतिरिक्त सामान नियमित भाषाओं के लिए लाता है कि महान :-)
बीआर। मोर्टन
ग्रुपिंग और कैप्चरिंग ऐसी विशेषताएं नहीं हैं जो भाषा अनियमित बनाती हैं - वे जो भी करते हैं वह मेटाडेटा प्रदान करती है, भाषा की अभिव्यक्ति को नहीं बदलती है। स्पष्ट रूप से कुछ भी जिसमें स्टैक शामिल है (जैसे बैकरेन्फर) अनियमित भाषाओं के लिए बनाते हैं। – Gabe
यह शायद एक समुदाय विकी होना चाहिए –
@webdestroya: मैं सीडब्ल्यू समझ सकता हूं, लेकिन SO पर क्यों नहीं? – BoltClock
@NullUser - क्या यह एक सुंदर व्यक्तिपरक प्रश्न नहीं है? –