नियमित अभिव्यक्तियों की शक्ति क्या है?

Question

जैसा कि नाम से पता चलता है कि हम सोच सकते हैं कि नियमित अभिव्यक्ति केवल नियमित भाषाओं से मेल खा सकती है। लेकिन अभ्यास में नियमित रूप से उपयोग किए जाने वाले नियमित अभिव्यक्तियों में ऐसी सामग्री होती है जो मुझे यकीन नहीं है कि उनके सैद्धांतिक समकक्षों के साथ कार्यान्वित करना संभव है। उदाहरण के लिए आप बैक-रेफरेंस का अनुकरण कैसे करेंगे? तो प्रश्न उठता है: अभ्यास में उपयोग किए जाने वाले नियमित अभिव्यक्तियों की सैद्धांतिक शक्ति क्या है? क्या आप {(a^n)(b^n)|n>=0} से मिलान करने के तरीके के बारे में सोच सकते हैं? {(a^n)(b^n)(c^n)|n>=0} के बारे में क्या?

Answer 1

आपके प्रश्न का उत्तर है, "नियमित अभिव्यक्ति" भाषाएं जो बैक-रेफरेंस की अनुमति देती हैं न तो नियमित हैं और न ही संदर्भ मुक्त हैं। (दूसरे शब्दों में, जैसा कि आपने बताया है, आप नियमित भाषा के साथ बैक-रेफरेंस अनुकरण नहीं कर सकते हैं, न ही सीएफएल के साथ।) वास्तव में, विकिपीडिया का कहना है कि हम अभ्यास में उपयोग की जाने वाली "नियमित अभिव्यक्ति" भाषाओं में से कई हैं NP-Complete:

वापस संदर्भ की एक असीम संख्या के साथ मिलान पैटर्न, के रूप में कई आधुनिक उपकरण द्वारा समर्थित, एन पी-सम्पूर्ण (देखें, [11] प्रमेय 6.2) है।

जैसा कि अन्य ने सुझाव दिया है, नियमित रूप से कंप्यूटर भाषाओं और पुस्तकालयों में समर्थित नियमित अभिव्यक्ति भाषाएं औपचारिक भाषा सिद्धांत में नियमित अभिव्यक्तियों से एक अलग जानवर हैं। Larry Wall wrote पर्ल के संबंध में "regexes,"

'नियमित अभिव्यक्ति' [...] केवल मामूली असली नियमित भाव से संबंधित हैं। फिर भी, शब्द पैटर्न मिलान इंजन की क्षमताओं के साथ बढ़ गया है, इसलिए मैं भाषाई आवश्यकता से लड़ने की कोशिश करने जा रहा हूं।मैं, तथापि, आम तौर पर उन्हें "regexes"

आप से पूछा कॉल करेंगे,

आप एक तरह से मिलान करने के लिए {(एक^n) (ख^n) के बारे में सोच सकते हैं | n> = 0}? {(ए^एन) (बी^एन) (सी^एन) | एन> = 0} के बारे में क्या?

मैं यहाँ यकीन नहीं है अगर आप चाहे सैद्धांतिक नियमित अभिव्यक्ति भाषाओं "वर्ग की भाषा" मिलान कर सकते हैं परीक्षण करने के लिए कोशिश कर रहे हैं, या आप एक (व्यावहारिक) में एक कार्यान्वयन ढूंढ रहे हों regex भाषा। जावा रेगेक्स के लिए Here's the proof why the former is not possible; और here's a long explanation and implementation of the latter।

Answer 2

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

आपके प्रश्न के साथ समस्या यह है कि आप एक व्यावहारिक स्थिति में विशेष रूप से विकसित सैद्धांतिक परिदृश्य को लागू करने के लिए कह रहे हैं, जो लगभग हमेशा आपदा में समाप्त होता है।

तो मेरा जवाब एक गैर-उत्तर का प्रकार है, जिसमें मैं कह रहा हूं कि आपको जवाब देने के लिए विस्तारित नियमित अभिव्यक्तियों के बारे में पूछने के लिए प्रश्न को फिर से लिखना होगा।

संसाधनों के एक जोड़े है कि इस मामले में मदद कर सकता है:

Helpful wikipedia article

Similar StackOverflow question

Good book with a chapter on this topic

मैं भी मेरा उत्तर बना रही हूँ किसी और के लिए एक समुदाय विकी है जो करना चाहता है विचार की इस पंक्ति में योगदान।