यह निर्धारित करना कि रेगेक्स किसी अन्य

Question

का सबसेट है या नहीं, मेरे पास नियमित अभिव्यक्ति का एक बड़ा संग्रह है, जब मिलान किया गया है तो एक विशेष http हैंडलर कॉल करें। पुराने रेगेक्स में से कुछ पहुंच योग्य नहीं हैं (उदा। a.c* ⊃ abc*) और मैं उन्हें छीनना चाहता हूं।

क्या कोई लाइब्रेरी है जो दो रेगेक्स की इच्छा बताती है कि दूसरा दूसरा सबसेट है या नहीं?

मुझे यकीन नहीं था कि यह पहली बार निर्णायक था (यह एक अलग नाम से रोक समस्या की तरह गंध लगाया गया था)। लेकिन यह it's decidable बाहर निकलता है।

Answer 1

गणित अनुभाग में एक उत्तर है: https://math.stackexchange.com/questions/283838/is-one-regular-language-subset-of-another।

बुनियादी विचार:

• कंप्यूट न्यूनतम DFA दोनों भाषाओं के लिए।
• दोनों स्वचालित एम 1 और एम 2 के क्रॉस उत्पाद की गणना करें, जिसका अर्थ है कि प्रत्येक राज्य में एक जोड़ी होती है [एम 1, एम 2] जहां एम 1 एम 1 से होता है और एम 2 से एम 2 से सभी संभावित संयोजनों के लिए होता है।
• नया संक्रमण एफ 12 है: एफ 12 ([एम 1, एम 2], एक्स) => [एफ 1 (एम 1, एक्स), एफ 2 (एम 2, एक्स)]। इसका मतलब यह है कि अगर एम 1 में एम 1 में एम 1 में परिवर्तन होता है, तो एक्स पढ़ने के दौरान एक्स और एम 2 में राज्य एम 2 से एम 2 तक x पढ़ते समय एम 12 में एम 1 में एक संक्रमण होता है [एम 1, एम 2] से [एम 1 ', एम 2' ] एक्स पढ़ने के दौरान।
• अंत में आप पहुंच योग्य राज्यों में देखो:
  • अगर वहाँ एक जोड़ी है [स्वीकार करने को खारिज,] [, खारिज accapting] तो M2 एम 1 के एक सबसेट
  • अगर वहाँ एक जोड़ी है नहीं है तो एम 1 M2
  की

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

Answer 2

Trying to find the complexity of this problem lead me to this paper.

समस्या की औपचारिक परिभाषा के भीतर पाया जा सकता है: यह आम तौर पर कहा जाता है शामिल किए जाने के समस्या

आर के लिए शामिल किए जाने की समस्या है, के लिए दिए गए दो भाव r परीक्षण करने के लिए है, आर '∈ आर, चाहे आर ⊆ आर'।

कागज कुछ महान जानकारी (सारांश: सभी लेकिन सबसे सरल भाव काफी जटिल हैं) है कि, हालांकि शामिल किए जाने की समस्या के बारे में जानकारी के लिए खोज एक सीधे वापस StackOverflow की ओर जाता है। उस उत्तर में पहले से ही a paper describing a passable polynomial time algorithm का लिंक था जिसमें बहुत से सामान्य मामलों को शामिल करना चाहिए।

Answer 3

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

दूसरी तरफ, यदि नियमित अभिव्यक्ति सैद्धांतिक अर्थ में "सत्य" होती है, जिसमें केवल परिमित, वैकल्पिकता और क्लेन स्टार को एक सीमित वर्णमाला के साथ तारों पर तब्दील किया जाता है, साथ ही इन पर सामान्य वाक्य रचनात्मक चीनी (चरित्र वर्ग, +,?, आदि), तो एक साधारण बहुपद समय एल्गोरिदम है।

मैं तुम्हें पुस्तकालयों को नहीं दे सकता है, लेकिन इस:

For each pair of regexes r and s for languages L(r) and L(s) 
    Find the corresponding Deterministic Finite Automata M(r) and M(s) 
    Compute the cross-product machine M(r x s) and assign accepting states 
     so that it computes L(r) - L(s) 
    Use a DFS or BFS of the the M(r x s) transition table to see if any 
     accepting state can be reached from the start state 
    If no, you can eliminate s because L(s) is a subset of L(r). 
    Reassign accepting states so that M(r x s) computes L(s) - L(r) 
    Repeat the steps above to see if it's possible to eliminate r 

एक DFA में एक regex परिवर्तित आम तौर पर एक गैर नियतात्मक आटोमैटिक मशीन प्राप्त करने के लिए थॉम्पसन के निर्माण का उपयोग करता है। यह सब्सट्रेट निर्माण का उपयोग कर डीएफए में परिवर्तित हो जाता है। क्रॉस-उत्पाद मशीन एक और मानक एल्गोरिदम है।

यह सब 1 9 60 के दशक में काम किया गया था और अब यह किसी भी अच्छे अंडरग्रेड कंप्यूटर विज्ञान सिद्धांत पाठ्यक्रम का हिस्सा है। विषय के लिए सोने का मानक Hopcroft and Ullman, Automata Theory है।

Answer 4

मुझे एक पायथन रेगेक्स लाइब्रेरी मिली जो सेट ऑपरेशंस प्रदान करती है।

http://github.com/ferno/greenery

सबूत Sub ⊆ Sup ⇔ Sub ∩ ¬Sup is {} कहते हैं।

import sys 
from greenery.lego import parse 

subregex = parse(sys.argv[1]) 
supregex = parse(sys.argv[2]) 

s = subregex&(supregex.everythingbut()) 
if s.empty(): 
    print("%s is a subset of %s"%(subregex,supregex)) 
else: 
    print("%s is not a subset of %s, it also matches %s"%(subregex,supregex,s) 

उदाहरण:

subset.py abcd.* ab.* 
abcd.* is a subset of ab.* 

subset.py a[bcd]f* a[cde]f* 
a[bcd]f* is not a subset of a[cde]f*, it also matches abf* 

पुस्तकालय क्योंकि जैसा कि अन्य उत्तर आप को यह करने के लिए आदेश में कम से कम DFA उपयोग करने की आवश्यकता में उल्लेख किया मजबूत नहीं हो सकता है मैं अजगर पुस्तकालय के साथ इस लागू कर सकते हैं काम। मुझे यकीन नहीं है कि ferno's लाइब्रेरी गारंटी देता है (या कर सकता है)।

एक तरफ के रूप में: लाइब्रेरी के साथ उलटा या सरलीकृत की गणना करने के लिए खेलना बहुत मजेदार है।
a(b|.).*a.+ को सरल बनाता है। जो बहुत कम है।
abf* के विपरीत ([^a]|a([^b]|bf*[^f])).*|a? है। अपने साथ आने की कोशिश करो!