Nullability (रेगुलर एक्सप्रेशन)

Question

ब्रज़ोज़ोवस्की के "रेगुलर एक्सप्रेशन के संजात" में और अन्य स्थानों पर समारोह δ (आर) λ लौटने अगर एक आर नल है, और ∅ अन्यथा, जैसे कि निम्न खंड शामिल हैं:

δ(R1 + R2) = δ(R1) + δ(R2) 
δ(R1 · R2) = δ(R1) ∧ δ(R2) 

जाहिर है, अगर दोनों आर 1 और R2 तो व्यर्थ कर रहे हैं (आर 1 · R2) नल है, और यदि या तो आर 1 या R2 तो व्यर्थ है (R1 + R2) व्यर्थ है। यह स्पष्ट नहीं है कि उपर्युक्त खंडों का क्या मतलब है। मेरी पहली सोचा, मानचित्रण (+), (·), या नियमित रूप से सेट करने के लिए बूलियन संचालन, अतर्कसंगत है आधार मामले में के बाद से,

δ(a) = ∅ (for all a ∈ Σ) 
δ(λ) = λ 
δ(∅) = ∅ 

और λ एक सेट नहीं है (और न ही एक सेट वापसी प्रकार है δ, जो एक नियमित अभिव्यक्ति है)। इसके अलावा, यह मानचित्रण इंगित नहीं किया गया है, और इसके लिए एक अलग संकेत है। मैं शून्यता को समझता हूं, लेकिन मैं δ की परिभाषा में योग, उत्पाद और बूलियन संचालन की परिभाषा पर खो गया हूं: λ या ∅ δ (आर 1) से वापस कैसे आते हैं ∧ δ (आर 2), उदाहरण के लिए , δ (आर 1 · आर 2) की परिभाषा में?

Answer 1

मुझे लगता है कि आप लेखक द्वारा उठाए गए तर्कसंगत स्वतंत्रताओं से बाहर निकल रहे हैं। Δ (आर) का रिटर्न प्रकार निश्चित रूप से एक सेट है, या बल्कि एक भाषा है। आप परिभाषा को देखें, तो:

आप देख सकते हैं वापसी प्रकार में असंगतता है कि वहाँ, औपचारिक रूप से λ एक तत्व है, लेकिन ∅ खाली भाषा है ... यह क्या लिखा होना चाहिए है:

तथ्य यह है कि लेखक दोनों रिक्त स्ट्रिंग के साथ-साथ ही रिक्त स्ट्रिंग युक्त भाषा आगे क्लीन तारा ऑपरेटर के बारे में उनकी परिभाषा इसका सबूत है के लिए λ का उपयोग करता है:

स्पष्ट रूप से, अंतिम भाग होना चाहिए यदि हम पैडेंटिक बनना चाहते हैं।

यह देखते हुए कि δ (आर) का रिटर्न प्रकार एक सेट है, या बल्कि एक भाषा है, आपके द्वारा दिए गए समीकरण सही अर्थ देते हैं और आपने जो वर्णन किया है उसे व्यक्त करते हैं।

Answer 2

मुझे लगता है कि आप क्रमशः + और ^ को बूलियन or और and पर मानचित्र करने का अधिकार रखते थे। यह दो पंक्तियों आप प्रत्यावर्तन (योग) और संयोजन (उत्पाद) के साथ सौदा उद्धृत की तरह दिखता है:

δ(R1 + R2) = δ(R1) + δ(R2) 

प्रत्यावर्तन अगर R1 व्यर्थ है R1 और R2 की व्यर्थ है, R2 व्यर्थ है, या R1 और R2 दोनों शून्य हैं।

δ(R1 · R2) = δ(R1) ∧ δ(R2) 

संयोजन R1 और R2 की केवल व्यर्थ है यदि R1 और R2 दोनों व्यर्थ कर रहे हैं।

इन नियमों के एक हास्केल कार्यान्वयन के लिए here देखें।

Answer 3

(मैं ब्रज़ोजोस्की द्वारा आलेख को बेहतर समझने के लिए लेख में नहीं देख सकता), लेकिन मैं इस नोटेशन को समझने के 2 तरीके सुझा सकता हूं (नोटेशन के साथ मिलकर, मैं देखता हूं, कोई नहीं है प्रश्न: इस परिभाषा की इच्छित समझ अच्छी तरह से समझी जाती है):

1) परिभाषा के बाईं ओर, हमारे पास नियमित अभिव्यक्तियों के लिए केवल "वाक्य रचनात्मक" पैटर्न हैं। दाईं ओर, हम सेट का उत्पादन करते हैं; याद रखें, एक नियमित अभिव्यक्ति एक भाषा (एक सेट) को इंगित करने का एक तरीका है, और इसलिए परिभाषा को लिखने का यह तरीका समझ में आता है: दाईं ओर, हम केवल कुछ (सरल) नियमित अभिव्यक्तियों का उपयोग करने के लिए संक्षिप्त तरीके के रूप में उपयोग करते हैं सेट। यानी, ∅ का अर्थ है खाली भाषा (खाली सेट), और λ (यदि नियमित अभिव्यक्ति के रूप में का अर्थ है) का मतलब है कि केवल खाली शब्द (इस तत्व के साथ सेट) वाली भाषा है।

ऑपरेशन बस सेट पर संचालन हैं: शायद संघ, और चौराहे।

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

2) हम पहले स्थान पर, सही पर नियमित अभिव्यक्तियां बनाते हैं, लेकिन लेखक ने उन परिचालनों को बढ़ाया है जो नियमित रूप से वेज के साथ अभिव्यक्तियां बनाते हैं, जिनमें भाषाओं के चौराहे के अर्थशास्त्र होते हैं।