रेगुलर एक्सप्रेशन
रेगुलर एक्सप्रेशन (regular expression) एक पाठ स्ट्रिंग है, जिससे स्ट्रिंगों के किसी समुच्चय का वर्णन किया जा सकता है। रेगुलर एक्सप्रेशन को हम परिमित ऑटोमेटा का वर्णन करने का एक सरल तरीका भी मान सकते हैं।
रेगुलर एक्सप्रेशन क्या है
अंकगणित में हम · और + जैसे प्रतीकों से (2 + 3) · 4 जैसे व्यंजक बनाते हैं। इस व्यंजक का मान निकालने पर हमें एक संख्या मिलती है। रेगुलर एक्सप्रेशन अक्षरों और कुछ विशेष प्रतीकों का एक अनुक्रम है, जैसे a(x ∪ y), जिसका मान निकालने पर एक (औपचारिक) भाषा मिलती है। व्यंजक (2 + 3) · 4 का परिणाम संख्या 20 है, रेगुलर एक्सप्रेशन a(x ∪ y) का परिणाम दो स्ट्रिंगों “ax”, “ay” का समुच्चय है।
पिछले रेगुलर एक्सप्रेशन a(x ∪ y) का मान हम कैसे निकालेंगे? प्रत्येक अक्षर वास्तव में उस अक्षर वाले एकल समुच्चय का संक्षिप्त रूप है, और छिपा हुआ गुणन स्ट्रिंगों का संयोजन है। रेगुलर एक्सप्रेशन को हम “पूरे रूप में” इस प्रकार लिख सकते हैं:
आगे हम मान इस प्रकार निकालेंगे: सम्मिलन {x} ∪ {y} से हमें भाषा {x,y} मिलती है। भाषाओं {a} और {x,y} के संयोजन से हमें भाषा {ax, ay} मिलती है।
प्रोग्रामिंग में रेगुलर एक्सप्रेशन का बहुत प्रयोग होता है और अधिकांश प्रोग्रामिंग भाषाओं में ये किसी न किसी रूप में उपलब्ध हैं। उदाहरण के लिए, इनसे यह जाँचा जाता है कि उपयोगकर्ता द्वारा लिखा गया पाठ कुछ मानदंडों पर खरा उतरता है या नहीं (जैसे, क्या यह मान्य ईमेल पता है, मान्य तिथि है आदि), और इनसे पाठ बदला भी जाता है (जैसे, हम पाठ में आने वाले सभी URL को क्लिक करने योग्य लिंक में बदलना चाह सकते हैं)।
रेगुलर एक्सप्रेशन के वास्तविक कार्यान्वयन प्रायः यहाँ बताए गए रेगुलर एक्सप्रेशन से अधिक शक्तिशाली होते हैं और थोड़ा भिन्न, परंतु मुख्यतः अधिक जटिल सिंटैक्स का प्रयोग करते हैं।
रेगुलर एक्सप्रेशन की परिभाषा
रेगुलर एक्सप्रेशन हम किसी वर्णमाला Σ पर परिभाषित करेंगे। तब हम कहते हैं कि रेगुलर एक्सप्रेशन है:
- a, जहाँ a ∈ Σ। अर्थात् वर्णमाला का अकेला अक्षर रेगुलर एक्सप्रेशन है।
- ϵ: रिक्त स्ट्रिंग, जिसे प्रोग्रामिंग में खाली उद्धरण चिह्नों “” से भी लिखते हैं।
- ∅: रेगुलर एक्सप्रेशन से रिक्त भाषा का वर्णन भी संभव होना चाहिए, इसलिए रिक्त भाषा रेगुलर एक्सप्रेशन है।
- (R1 ∪ R2), जहाँ R1, R2 रेगुलर एक्सप्रेशन हैं।
- (R1 ∘ R2), जहाँ R1, R2 रेगुलर एक्सप्रेशन हैं।
- (R∗), जहाँ R रेगुलर एक्सप्रेशन है।
बिंदु 4 के प्रतीक ∪ के स्थान पर हम खड़ी रेखा | का भी प्रयोग कर सकते हैं। प्रतीक ∘ के स्थान पर कुछ भी लिखना आवश्यक नहीं है। जैसे हम प्रायः गुणन का प्रतीक, मध्य बिंदु ·, सीधे नहीं लिखते, वैसे ही प्रायः संयोजन का प्रतीक ∘ भी नहीं लिखते। इसलिए ये रेगुलर एक्सप्रेशन एक जैसे हैं: a ∘ (b ∪ c) और a(b|c)।
अलग-अलग संक्रियक (operator) का क्या अर्थ है?
- ∪ या | भाषाओं का सम्मिलन दर्शाता है।
- ∘ भाषाओं का संयोजन दर्शाता है।
- ∗ भाषा का संवरक दर्शाता है।
उदाहरण:
- a सरल भाषा {a} दर्शाता है।
- a|b दो स्ट्रिंगों से बनी भाषा {a, b} दर्शाता है।
- a ∘ b भाषा {ab} दर्शाता है।
- a(b|c)d भाषा {abd, acd} दर्शाता है।
- a(b∗) उन सभी स्ट्रिंगों की भाषा दर्शाता है, जो अक्षर “a” से शुरू होती हैं और जिनके बाद कितनी भी बार अक्षर “b” आता है।
- (ab)∗ सभी स्ट्रिंगों {ϵ, ab, abab, ababab, …} की भाषा दर्शाता है।
- 0∗10∗ उन सभी द्विआधारी स्ट्रिंगों की भाषा दर्शाता है, जिनमें अंक 1 एक बार आता है, न कम न ज़्यादा। (ध्यान दीजिए कि इस व्यंजक को अधिक सटीक रूप से (0∗)1(0∗) लिखना चाहिए, परंतु जब संकेतन इनके बिना भी पढ़ने योग्य हो, तो हम कोष्ठक छोड़ सकते हैं।)
- Σ∗1Σ∗ उन सभी स्ट्रिंगों की भाषा दर्शाता है, जिनमें कम से कम एक बार 1 आता है।
- (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)∗ सभी प्राकृत संख्याओं की भाषा दर्शाता है।
आगे हम रेगुलर एक्सप्रेशन और परिमित ऑटोमेटा की तुल्यता दिखाएँगे: प्रत्येक रेगुलर एक्सप्रेशन के लिए, जिसका मान भाषा R है, एक ऐसा परिमित ऑटोमेटा A मौजूद है, जिसके लिए L(A) = R है, और इसका विलोम भी सत्य है।
स्रोत
विषय-सूची: रेगुलर एक्सप्रेशन, रेगुलर एक्सप्रेशन से ऑटोमेटा में रूपांतरण, व्यापकीकृत अनियतात्मक परिमित ऑटोमेटा, ऑटोमेटा से रेगुलर एक्सप्रेशन में रूपांतरण