औपचारिक भाषाएँ
औपचारिक भाषा (formal language) उस भाषा की संकल्पना का एक प्रकार का व्यापकीकरण है, जिससे हम रोज़मर्रा के जीवन में परिचित हैं।
आधारभूत संकल्पनाएँ
शुरुआत में औपचारिक भाषा को आप एक सामान्य भाषा, जैसे हिंदी, की तरह सोच सकते हैं। ऐसी भाषा किससे बनती है? शब्दों से, जिन्हें हम आगे जोड़कर वाक्य बनाते हैं। वाक्यों में हमारी रुचि नहीं होगी, केवल शब्दों में होगी। शब्द किससे बनते हैं? वर्णमाला के अक्षरों से। इसलिए हम वर्णमाला से शुरू करते हैं।
वर्णमाला (alphabet) कोई भी अरिक्त समुच्चय है। वर्णमाला के अवयवों को प्रतीक कहते हैं। हिंदी की बात करें, तो यह देवनागरी की सामान्य वर्णमाला होगी: सभी स्वर और व्यंजन, मात्राएँ तथा अनुस्वार, चंद्रबिंदु, हलंत जैसे चिह्न। यदि हम हिंदी के बजाय, उदाहरण के लिए, संख्याओं का वर्णन करना चाहें, तो वर्णमाला में सभी दस अंक होंगे। वर्णमाला को प्रायः संकेत Σ से दर्शाते हैं।
स्ट्रिंग (string), जिसे शब्द भी कहते हैं, किसी वर्णमाला Σ के प्रतीकों का परिमित अनुक्रम है। उदाहरण के लिए, यदि वर्णमाला Σ= {a,b,c,d,e,…, z} है, तो अनुक्रम “namaste” या “kitab” स्ट्रिंग हैं, परंतु “café” (हमारे पास अक्षर “é” नहीं है), “Rahul” (अक्षर “R” नहीं है) या “shubh din” (रिक्ति नहीं है) स्ट्रिंग नहीं हैं। स्ट्रिंग की लंबाई उन प्रतीकों की संख्या है, जिनसे स्ट्रिंग बनी है।
स्ट्रिंगों का संयोजन (concatenation): यदि दो स्ट्रिंग a = a1a2… an और b = b1b2… bm हैं, तो उनके संयोजन से स्ट्रिंग ab = a1a2… anb1b2… bm बनती है। उदाहरण: स्ट्रिंगों “namaste” और “kitab” के संयोजन से स्ट्रिंग “namastekitab” बनती है। संयोजन को या तो छोटे वृत्त से दर्शाते हैं, अर्थात् a ∘ b, या किसी संकेत से नहीं दर्शाते और स्ट्रिंगों को बिना किसी विशेष संकेत के बस एक के बाद एक लिख देते हैं।
रिक्त स्ट्रिंग को ε से दर्शाते हैं। यह वह स्ट्रिंग है, जिसकी लंबाई शून्य है। यदि स्ट्रिंग a = a1… an का रिक्त स्ट्रिंग ε से संयोजन करें, तो हमें फिर से स्ट्रिंग a मिलती है। अर्थात् a ∘ ε = a होता है।
वर्णमाला Σ का संवरक उन सभी स्ट्रिंगों का समुच्चय है, जिन्हें हम वर्णमाला Σ से बना सकते हैं, रिक्त स्ट्रिंग सहित। संवरक को Σ∗ से दर्शाते हैं। द्विआधारी वर्णमाला Σ= {0, 1} के लिए
कभी-कभी वर्णमाला का धनात्मक संवरक भी प्रयोग करते हैं। इसमें भी वे सभी स्ट्रिंग होती हैं, जिन्हें वर्णमाला से बनाया जा सकता है, केवल रिक्त स्ट्रिंग नहीं होती। धनात्मक संवरक को Σ+ से दर्शाते हैं और Σ+ = Σ∗ ∖ {ε} होता है।
वर्णमालाओं के उदाहरण
-
आइए, हिंदी वाले उदाहरण पर लौटें। हिंदी का प्रत्येक शब्द उस वर्णमाला के संवरक में मिलेगा, जिसमें देवनागरी के सभी स्वर, व्यंजन, मात्राएँ और चिह्न हों (और शायद योजक चिह्न “-” भी)। यदि इस वर्णमाला में रिक्ति और विराम चिह्न (अल्पविराम, पूर्ण विराम “।”, विस्मयादिबोधक चिह्न, प्रश्नचिह्न, …) भी जोड़ दें, तो संवरक से हमें वे सभी वाक्य मिलेंगे, जिन्हें हम हिंदी में बना सकते हैं। स्वाभाविक है कि इस संवरक में “कखग झञट ठडढ़ ङ्ञ्ण्ह!!!।??। ।।!?।?।फफ” जैसे वाक्य भी होंगे, जो फिर भी कुछ लंबे और उबाऊ भाषणों से ज़्यादा सार्थक हैं।
-
यदि हमारी वर्णमाला में सभी अंक हों, Σ= {0, 1, …, 9}, तो संवरक में सभी प्राकृत संख्याएँ होंगी — और कुछ और भी। उसमें शून्य से शुरू होने वाली संख्याएँ भी होंगी, जैसे 00054, अकेला शून्य भी, और साथ ही रिक्त स्ट्रिंग भी, जो स्वाभाविक रूप से कोई संख्या नहीं है।
-
वर्णमाला अरिक्त होनी चाहिए, इसलिए सबसे छोटी वर्णमाला में कम से कम एक प्रतीक होता है। उदाहरण के लिए, वर्णमाला Σ= {!} का संवरक Σ∗ = {ε, !, !!, !!!, !!!!, …} होगा, अर्थात् स्ट्रिंगों का ऐसा समुच्चय, जिसमें प्रत्येक n ∈ W के लिए एक स्ट्रिंग है, जिसमें n विस्मयादिबोधक चिह्न हैं, और संवरक में इनके अलावा कोई स्ट्रिंग नहीं होगी।
-
मान लीजिए Σ= {qw,c} है। यह बहुत अनोखी वर्णमाला है, क्योंकि इसमें स्ट्रिंग qw है। ऐसा संकेतन प्रायः प्रयोग नहीं किया जाता, क्योंकि यह उलझाने वाला और अजीब है, परंतु हम इसे ऐसे सोच सकते हैं कि अक्षरों “q” और “w” को आपस में चिपका दिया गया है और वे मिलकर एक ही चिह्न बनाते हैं। तब स्ट्रिंग “qw” को हम प्रतीक “qw” के रूप में देख सकते हैं। यदि इस प्रतीक से हम स्ट्रिंग “qwcqw” बनाएँ, तो इस स्ट्रिंग की लंबाई तीन होगी — यह प्रतीकों “qw”, “c” और “qw” से बनी होगी। ऐसी वर्णमालाएँ बहुत कम मिलती हैं, परंतु ऐसी स्थितियाँ होती हैं, जिनमें कई प्रतीकों से बने ऐसे प्रतीकों की ज़रूरत पड़ती है। (देवनागरी में संयुक्ताक्षर “क्ष” भी कुछ ऐसा ही है।)
औपचारिक भाषा
वर्णमाला Σ पर (औपचारिक) भाषा Σ∗ का कोई भी उपसमुच्चय है। इसलिए वर्णमाला Σ पर भाषा L के लिए L ⊆ Σ∗ होता है। भाषाओं के उदाहरण:
-
पिछले भाग में हमने अंकों की वर्णमाला Σ= {0, 1, …, 9} परिभाषित की थी। इसका संवरक केवल अंकों से बनी सभी स्ट्रिंगें हैं। यदि हम यह नियम जोड़ दें कि स्ट्रिंग शून्य से शुरू नहीं हो सकती और रिक्त नहीं हो सकती, तो हमें प्राकृत संख्याओं का समुच्चय ℕ मिलता है। संबंध ℕ ⊆ Σ∗ सत्य है, इसलिए ℕ वर्णमाला Σ पर एक भाषा है।
-
अंकों के पिछले समुच्चय में हम ऋण चिह्न “-” भी जोड़ सकते हैं, जिससे Σ= {0, 1, …, 9, −} हो जाता है। संवरक में वे सभी स्ट्रिंगें हैं, जो अंकों या ऋण चिह्न से बनी हैं। इसका अर्थ है कि संवरक में “12-84-”, “1-5-8” या “-” जैसी स्ट्रिंगें भी हैं। पूर्णांकों की भाषा ℤ हम तीन नियम जोड़कर बनाते हैं:
- ऋण चिह्न स्ट्रिंग में या तो बिल्कुल नहीं आता या स्ट्रिंग की शुरुआत में आता है।
- स्ट्रिंग का पहला अंक शून्य नहीं हो सकता, स्ट्रिंग “0” को छोड़कर।
- प्रत्येक स्ट्रिंग में कम से कम एक अंक होना चाहिए।
यह समुच्चय पूर्णांकों के समुच्चय का वर्णन करता है और समुच्चय Σ∗ का उपसमुच्चय है — इसलिए यह वर्णमाला Σ पर एक भाषा है।
-
मान लीजिए Σ= {0, 1} है। तब संवरक में शून्यों और इकाइयों से बनी सभी स्ट्रिंगें हैं। इस वर्णमाला पर भाषा L को हम, उदाहरण के लिए, उन सभी स्ट्रिंगों के समुच्चय के रूप में परिभाषित कर सकते हैं, जिनमें अंक 1 तीन बार आता है, न कम न ज़्यादा। हम और रचनात्मक भी हो सकते हैं और कह सकते हैं कि भाषा L उन सभी स्ट्रिंगों का समुच्चय है, जो docx फ़ाइल का मान्य प्रारूप हैं (वही, जो Word से निकलता है)।
-
द्विआधारी वर्णमाला Σ= {0, 1} पर ही रहते हैं। अक्षरों की प्रत्येक स्ट्रिंग (सामान्य अक्षर, जो आपके कीबोर्ड पर हैं) को द्विआधारी रूप, अर्थात् शून्यों और इकाइयों में, बदला जा सकता है, और वापस भी, उदाहरण के लिए ASCII सारणी की सहायता से (या अधिक सटीक रूप से — ASCII सारणी अक्षरों को संख्याओं में बदलती है और दाशमिक पद्धति की संख्याओं को द्विआधारी पद्धति में बदला जा सकता है)। इस तरह हम उन सभी स्ट्रिंगों की भाषा परिभाषित कर सकते हैं, जो मान्य ईमेल पते हैं, और यह फिर भी द्विआधारी वर्णमाला पर एक भाषा होगी।
भाषाओं का संयोजन (concatenation): भाषाओं का भी संयोजन किया जा सकता है। परिभाषा समुच्चयों के कार्तीय गुणन जैसी होगी। मान लीजिए दो भाषाएँ L1 और L2 हैं। उनके संयोजन L1 ∘ L2 से हमें एक नई भाषा मिलती है, जिसे इस प्रकार परिभाषित करते हैं:
अर्थात् हम भाषा L1 की सभी स्ट्रिंगें लेते हैं और प्रत्येक का भाषा L2 की सभी स्ट्रिंगों से संयोजन करते हैं। उदाहरण: मान लीजिए
तब:
अब तक भाषाओं का वर्णन करने के लिए हमने सामान्य भाषा का प्रयोग किया, यानी शब्दों में बताया कि भाषा कैसी होनी चाहिए। यह बहुत अव्यावहारिक है, इसलिए किसी भाषा को परिभाषित करने के अधिक औपचारिक तरीके अपनाए जाते हैं। इनमें पहला है व्याकरण (grammar)।