🤘 👨🏿‍🌾 🧖🏿 चॉम्स्की जनरेटिंग ग्रामर 🐔 🔑 🏀

संक्षिप्त परिचय

यह पाठ एक पोस्ट का एक निरंतरता है जिसमें लेखक ने औपचारिक भाषा और व्याकरण की अवधारणाओं का वर्णन करने की कोशिश की है, बस और बिना जटिल गणितीय परिवर्तनों के। इस पाठ पर बहुत सी प्रतिक्रियाएँ आईं और लेखक ने खुद को अगली कड़ी लिखने के लिए बाध्य माना।

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

व्याकरण की परिभाषा उत्पन्न करना

व्याकरण एक औपचारिक भाषा का अंतिम विवरण है। एक औपचारिक भाषा, बदले में, एक परिमित वर्णमाला के पात्रों से बनी जंजीरों का एक मनमाना सेट है। यहां सेट की मनमानी को इस अर्थ में समझा जाता है कि यह अनंत, परिमित या खाली हो सकता है।

पिछली सदी के उत्तरार्ध के 50 के दशक में नोम चोम्स्की द्वारा जेनेरिक चॉम्स्की व्याकरणों की औपचारिकता शुरू की गई थी। कुछ ही समय में, इस औपचारिकता ने असाधारण लोकप्रियता प्राप्त की। कुछ समय के लिए, व्याकरण उत्पन्न करना एक रामबाण के रूप में माना जाता था - सभी प्रकार की भाषाओं को स्थापित करने के लिए एक सार्वभौमिक दृष्टिकोण, जिसमें प्राकृतिक भी शामिल हैं (यानी ऐसी भाषाएं जो लोग आपस में रोजमर्रा के संचार के लिए उपयोग करते हैं)। लेकिन समय ने दिखाया है कि प्राकृतिक भाषाओं का वर्णन करने के लिए सामान्य व्याकरण बहुत सुविधाजनक नहीं हैं। अब प्रोग्रामिंग भाषाओं और अन्य कंप्यूटर भाषाओं जैसी औपचारिक भाषाओं के वाक्य-विन्यास का वर्णन करने के लिए मुख्य रूप से जेनरेटर व्याकरण का उपयोग किया जाता है।

चॉम्स्की के उत्पन्न व्याकरण को "पीढ़ी के नियमों" (प्रस्तुतियों) के एक सेट के रूप में परिभाषित किया गया है। प्रत्येक नियम सिर्फ जंजीरों की एक जोड़ी है (w', w'') और व्याकरण द्वारा निर्दिष्ट भाषा की जंजीरों को उत्पन्न करने पर बाईं श्रृंखला को दाईं ओर से बदलना संभव बनाता है। इस कारण से, नियमों को आमतौर पर w' --> w'' रूप में लिखा जाता है, यह दर्शाता है कि विशेष रूप से क्या बदला जा सकता है। व्याकरण में नियमों का सेट गैर-रिक्त और परिमित होना चाहिए, और आमतौर पर लैटिन पी द्वारा निरूपित किया जाता है।

व्याकरण के नियमों में जंजीरों को दो वर्णों से बनाया जा सकता है: टर्मिनल वर्णों (टर्मिनलों) की वर्णमाला और गैर-टर्मिनल वर्णों (गैर-टर्मिनलों) की वर्णमाला। टर्मिनल वर्णमाला को टी द्वारा निरूपित किया जाता है। यह वर्णमाला वास्तव में औपचारिक भाषा की वर्णमाला से मेल खाती है जिसे यह व्याकरण परिभाषित करता है। "टर्मिनल" शब्द का अर्थ यह है कि बाईं ओर के व्याकरण के नियमों में ऐसी कोई श्रृंखला नहीं हो सकती है जो केवल टर्मिनल प्रतीकों से बनी हो। इसलिए, यदि प्रतिस्थापन के परिणामस्वरूप ऐसी श्रृंखला निकली, तो श्रृंखला बनाने की अगली प्रक्रिया बंद हो जाएगी (समाप्त)। गैर-सांकेतिक प्रतीकों का उपयोग मध्यवर्ती जंजीरों में किया जाता है। एक श्रृंखला बनाने के लिए एक एल्गोरिथ्म को परिभाषित करने में एक नॉनटर्मिनल का अर्थ बहुत अलग हो सकता है और आमतौर पर व्याकरण के प्रकार पर निर्भर करता है जिसमें इस प्रतीक का उपयोग किया जाता है। गैर-प्रतीकों का उपयोग करने के विभिन्न उदाहरणों पर नीचे चर्चा की जाएगी।

लेकिन एक गैर-प्रतीक चिन्ह का हमेशा एक ही अर्थ होता है - यह किसी भाषा की सभी श्रृंखलाओं को दर्शाता है। इस nonterminal को "उत्पन्न व्याकरण का प्रारंभिक nonterminal चरित्र" कहा जाता है और इसे आमतौर पर लैटिन S (शुरू या वाक्य) द्वारा दर्शाया जाता है। प्रत्येक उत्पन्न व्याकरण में आवश्यक रूप से एक नियम होना चाहिए, जिसके बाएं भाग में एक ही प्रारंभिक गैर-समरूपता होती है, अन्यथा इस व्याकरण में एक भी श्रृंखला उत्पन्न करना संभव नहीं होगा।

तो, चॉम्स्की का उत्पन्न व्याकरण एक चौगुना G = {N, T, P, S} , जहां

N , गैर-अक्षर वर्णों की अंतिम वर्णमाला है।
T - टर्मिनल प्रतीकों की अंतिम वर्णमाला (व्याकरण द्वारा निर्दिष्ट भाषा की वर्णमाला से मेल खाती है)।
P पीढ़ी के नियमों का एक सीमित सेट है।
S व्याकरण G का प्रारंभिक अप्रतिरोध्य है G

जनक व्याकरण भाषा

चॉम्स्की का उत्पन्न व्याकरण एक भाषा को पीढ़ी के नियमों के आधार पर एक व्याकरण के प्रारंभिक नॉनटर्मिनल से जंजीरों के क्रमपरिवर्तन के माध्यम से परिभाषित करता है। आइए हम इसका विशेष रूप से वर्णन करते हैं।

w' alpha w'' => w' beta w'' उत्पन्न करने के चरण में alpha उपचैन की जगह beta उपचैन को alpha --> beta पीढ़ी के नियम के अनुसार शामिल किया गया है। इस मामले में, स्पष्ट रूप से, श्रृंखला w' alpha w'' श्रृंखला w' beta w'' प्राप्त करते हैं। दूसरे शब्दों में, यदि कुछ व्याकरण के नियम में कुछ श्रृंखला और उसकी कुछ उप-श्रृंखलाएं हैं, तो हमें नियम के इस बाईं ओर को दाईं ओर से बदलने का पूरा अधिकार है। स्पॉनिंग चरणों के अंतिम अनुक्रम को स्पॉनिंग कहा जाता है। शून्य या अधिक प्राणियों को =>* द्वारा निरूपित किया जाएगा। पदनाम alpha =>* beta इंगित करता है कि beta श्रृंखला alpha श्रृंखला से पीढ़ी के नियमों के आधार पर क्रमबद्ध संख्याओं द्वारा प्राप्त की जाती है। इस अंकन में, यह हो सकता है कि प्रतिस्थापन (पीढ़ी) को कभी लागू नहीं किया गया है, इस मामले में alpha श्रृंखला beta के साथ मेल खाती है।

तो, उत्पन्न व्याकरण G = {N, T, P, S} की भाषा टर्मिनल प्रतीकों से बनी श्रृंखलाओं का एक समूह है और व्याकरण के प्रारंभिक प्रतीक से उत्पन्न होती है। गणितीय सूत्र इस प्रकार है: L = {w | S =>* w} L = {w | S =>* w} ।

समझाने के लिए, यहाँ दो सरल उदाहरण हैं।

एक बहुत ही सरल भाषा का एक उदाहरण

बता दें कि भाषा L में एक चेन होती है, जिसमें सिंगल सिंबल a । दूसरे शब्दों में, L = {a} । एक श्रृंखला उत्पन्न करने के लिए, एक नियम S --> a पर्याप्त है। इस व्याकरण में एकमात्र उत्पाद S => a ।

यह ध्यान दिया जाना चाहिए कि इस भाषा के लिए कोई व्यक्ति एक और गैर-प्रतीक चिह्न पेश कर सकता है, कह सकता है कि प्रतीक A , साथ ही नियम S --> A और A --> a । फिर एकमात्र परिणाम निम्नलिखित होगा: S => A => a । चूंकि गैर-व्याकरणिक व्याकरण की वर्णमाला हम मनमाने ढंग से चुनते हैं, इसलिए यह स्पष्ट हो जाता है कि इतनी सरल भाषा के लिए भी इस भाषा को परिभाषित करने वाले कई जनक व्याकरण हैं।

सरल अंकगणितीय अभिव्यक्ति भाषा

भाषा पर विचार करें A = {a+a, a+a+a, a+a+a+a, ...} । इस भाषा की श्रृंखलाएँ वर्णों के अनुक्रम हैं, जिन्हें + वर्णों द्वारा अलग किया जाता है। इस भाषा को बनाने के लिए नियम कैसे निर्धारित करें? ध्यान दें कि प्रत्येक भाषा श्रृंखला एक या अधिक श्रृंखलाओं +a बाद से शुरू होती +a । तदनुसार, यह विचार सबसे पहले प्रतीक को उत्पन्न करता a , और फिर इस प्रतीक के दाईं ओर एक या अधिक श्रृंखलाएँ संलग्न करके भाषा की प्रत्येक श्रृंखला प्राप्त की जाएगी। पीढ़ी के इन दो चरणों को एक दूसरे से अलग करने के लिए, हम नॉनटर्मिनल प्रतीक A परिचय देते हैं A फिर, हमें निम्नलिखित नियमों के साथ एक व्याकरण मिलता है: S --> aA, A --> +aA, A --> +a ।

उदाहरण के लिए, श्रृंखला a+a+a कैसे उत्पन्न करें, पर विचार करें। S => aA => a+aA => a+a+a । इस पीढ़ी में, सभी तीन नियमों को क्रमिक रूप से लागू किया गया था: S --> aA, A --> +aA, A --> +a ।

भाषा A में अनंत संख्या में जंजीर होती है, जिसका अर्थ है कि इस भाषा में श्रृंखला की लंबाई पर कोई प्रतिबंध नहीं है। असीमित लंबाई की जंजीरों को फैलाने का एकमात्र तरीका पुनरावर्ती स्पॉन नियमों का उपयोग करना है, अर्थात। नियम जिसमें दाईं ओर के नियम में उसका बायाँ भाग होता है। उपरोक्त उदाहरण में, यह नियम A --> +aA । बाईं ओर एक एकल चिह्न A की एक श्रृंखला है, जो दाएं पक्ष में भी निहित है। यह पुनरावृत्ति प्रतिस्थापन, बढ़ती, आवश्यक, उत्पन्न श्रृंखला की लंबाई में एक ही नियम को लगातार लागू करना संभव बनाती है। इंटरमीडिएट नियमों के माध्यम से भी पुन: अप्रत्यक्ष किया जा सकता है। उदाहरण के लिए, नियम A --> aBc, B --> deA श्रृंखला A के अप्रत्यक्ष पुनरावृत्ति को निर्दिष्ट करते हैं A

व्याकरण वर्ग

नोआम चॉम्स्की ने व्याकरण उत्पन्न करने के नियमों के रूप में प्रतिबंध लगाकर व्याकरण वर्गों (और संबंधित भाषा वर्ग) की शुरुआत की। व्याकरण के प्रत्येक वर्ग की अपनी वर्णनात्मक शक्ति होती है। व्याकरण के वर्ग की वर्णनात्मक शक्ति को कुछ वाक्यात्मक संबंधों के व्याकरण के नियमों में अभिव्यक्ति की संभावना के रूप में चित्रित किया जा सकता है। इस बात पर विचार करें कि व्याकरण वर्ग वाक्यविन्यास संबंधों को कैसे परिभाषित करता है।

व्याकरण प्रकार 3

व्याकरण का यह वर्ग उत्पन्न श्रृंखला के दायें या बायें किनारे से एक निश्चित संख्या में टर्मिनल प्रतीकों को जोड़कर जंजीरों को उत्पन्न करने के लिए एक एल्गोरिथम को परिभाषित करता है। जाहिर है, ऐसी पीढ़ी पद्धति के नियम A --> alpha B या A --> B alpha , जहां alpha टर्मिनल प्रतीकों से युक्त एक श्रृंखला है। इस स्थिति में, यदि एक मध्यवर्ती (उत्पन्न करने की प्रक्रिया में) चेन X1..Xn A , तो नियम A --> alpha B अनुसार प्रतिस्थापन श्रृंखला X1..Xn alpha B उदाहरण के लिए, नियमों के लिए S --> aaaA , A --> abcA और A --> bbb आप पीढ़ी को S => aaaA => aaaabcA => aaaabcbbb निर्दिष्ट कर सकते हैं।

टाइप 3 व्याकरणों द्वारा दिए गए वाक्यात्मक संबंध को "निकट होना" शब्द से निरूपित किया जा सकता है। यहाँ "पास" का अर्थ सीधे इसके बगल में है, अगर इसे कुछ पीढ़ी के नियम के दाईं ओर निर्दिष्ट किया गया है, और इसके बाद अप्रत्यक्ष रूप से संबंधित पीढ़ी के नियमों में गैर-प्रतीकों के माध्यम से।

गणितीय कठोरता के लिए, व्याकरण प्रकार 3 के नियमों में टर्मिनल प्रतीकों की स्ट्रिंग को दाईं ओर एक टर्मिनल प्रतीक के साथ कई नियमों में विभाजित किया गया है। उदाहरण के लिए, यदि कोई नियम A --> abcB , तो इसे निम्नलिखित नियमों द्वारा प्रतिस्थापित किया जा सकता है, जिसके परिणामस्वरूप आवेदन एक ही श्रृंखला उत्पन्न करता है: A --> a A1 , A1 --> b A2 , A2 --> cB । दूसरे शब्दों में, क्रमपरिवर्तन A => abcB क्रमपरिवर्तन A => a A1 => ab A2 => abcB । ऐसे व्याकरण, जहाँ नियम के दाहिने भाग में दायीं ओर गैर-प्रतीक चिन्ह होते हैं, दाएं-रेखीय व्याकरण कहलाते हैं, यदि दाहिने भाग में गैर-टर्मिनल चिन्ह टर्मिनल के बाईं ओर होता है, तो व्याकरण को वाम-रेखीय कहा जाता है।

उदाहरण के लिए, A = {a+a, a+a+a, a+a+a+a, ...} भाषा के लिए वाम-रेखीय व्याकरण सेट करें। टाइप 3 व्याकरण नियम, जैसा कि ऊपर चर्चा की गई है, इस प्रकार हैं: S --> aA, A --> +aA, A --> +a । यहां, श्रृंखलाओं को सही पर वर्णों की एक जोड़ी जोड़कर उत्पन्न किया जाता है। व्याकरण को बदलें ताकि वर्ण बाईं ओर जुड़ जाएं, और नॉनटर्मिनल वर्ण भी जोड़ दें ताकि हर बार जब आप केवल एक वर्ण जोड़ें। व्याकरण प्राप्त करें:
S --> Aa
A --> B+
B --> Aa
B --> a
यह है कि श्रृंखला की पीढ़ी a+a+a : a+a+a S => Aa => B+a => Aa+a => B+a+a => a+a+a ।

एक चौकस पाठक ने शायद देखा कि टाइप 3 व्याकरण एक जेनरेटर ऑटोमेटन के समान है, जिसमें गैर-व्याकरण के प्रतीक राज्यों की भूमिका निभाते हैं। इस व्याकरण की एक संभावित व्याख्या, वास्तव में, एक परिमित अवस्था मशीन है।

प्रसंग-मुक्त व्याकरण

प्रसंग-मुक्त व्याकरण में नियम के नियम हैं: A --> alpha । नियम के बाईं ओर एक वर्ण (निश्चित रूप से, नॉनटर्मिनल) होना चाहिए, और दाईं ओर टर्मिनल और नॉनटर्मिनल वर्ण (खाली एक सहित) की कोई भी श्रृंखला हो सकती है।

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

केएस व्याकरण की व्याख्या व्याकरणिक व्याकरण के रूप में की जा सकती है, अर्थात्। व्याकरण के प्रकार। इस मामले में व्याकरण के प्रतीकों को प्रकार के रूप में सोचा जा सकता है, और नियम फिर प्रकार के बीच पदानुक्रम संबंध को निर्दिष्ट करते हैं। गैर-प्रतीक चिह्न जटिल प्रकारों के रूप में कार्य करते हैं, और टर्मिनल प्रतीक परमाणु प्रकारों के रूप में कार्य करते हैं जिनमें उपप्रकार नहीं हो सकते हैं। केएस व्याकरण की यह व्याख्या बहुत लोकप्रिय है और अक्सर इसका उपयोग भाषा अनुवादक बनाने के लिए किया जाता है। लेकिन, केएस व्याकरण के वर्ग की स्थापना करने के लिए, चॉम्स्की का मतलब कुछ और था।

इस तथ्य के कारण कि केएस-व्याकरण जेनरेटिव है, यह एक भाषा की श्रृंखलाओं को उत्पन्न करने के लिए एक एल्गोरिथ्म (सख्ती से बोलना, एक एल्गोरिथ्म नहीं, बल्कि पथरी एक बहुभिन्नरूपी एल्गोरिदम) को परिभाषित करता है। यहां स्पैनिंग को न केवल मौजूदा चेन के दाएं या बाएं चेन को जोड़कर परिभाषित किया गया है, बल्कि मौजूदा एक के अंदर चेन को डालकर भी। सम्मिलन श्रृंखला में नॉनटर्मिनल प्रतीक को प्रतिस्थापित करके किया जाता है, जो कुछ नियम के दाईं ओर है, जिसके बाईं ओर यह nonterminal स्थित है। मान लीजिए कि aabBBACbbb श्रृंखला को aabBBaaaCbbb श्रृंखला में परिवर्तित किया जा सकता है यदि कोई नियम A --> aaa aabBBaaaCbbb है। इस अर्थ में, उत्पन्न श्रृंखला कुछ किनारे से समान रूप से नहीं बढ़ती है, लेकिन अंदर से किसी तरह "सूज" जाती है।

हम उदाहरण के साथ कही गई बातों को स्पष्ट करते हैं। भाषा पर विचार करें L = {a^nb^n | n = 1, 2, 3,...} L = {a^nb^n | n = 1, 2, 3,...} । अभिव्यक्ति a^n का मतलब है चरित्र को बार बार दोहराना a । इस प्रकार, भाषा L में फॉर्म ab, aabb, aaabbb , आदि की एक श्रृंखला शामिल है। इस भाषा के लिए केएस व्याकरण को परिभाषित करें। ऐसा करने के लिए, ध्यान दें कि भाषा श्रृंखला से आप प्रतीक को बाईं ओर पहली से बाईं ओर और प्रतीक b को दाईं ओर संलग्न करके एक और भाषा श्रृंखला प्राप्त कर सकते हैं। कहते हैं, अगर एक aabb श्रृंखला है, तो हम इसे से aaabbb श्रृंखला प्राप्त कर सकते हैं। यह टिप्पणी पीढ़ी का नियम S --> aSb (यह याद S --> aSb कि भाषा की श्रृंखलाएं व्याकरण के प्रारंभिक S --> aSb से उत्पन्न होती हैं और इसलिए, इस प्रतीक द्वारा निरूपित की जा सकती हैं)। एक श्रृंखला का एक विशेष मामला भी है जिसे छोटे लोगों में विभाजित नहीं किया जा सकता है - यह ab श्रृंखला है। हम अपनी पीढ़ी के लिए नियम S --> ab परिचय देते हैं। तो, भाषा के व्याकरण में नियम हैं: S --> aSb और S --> ab । आइए हम चेन जेनरेशन S => aSb => aaSbb => aaabbb : S => aSb => aaSbb => aaabbb सेट करें।

प्रतिबंध के बिना प्रसंग-संवेदनशील व्याकरण और व्याकरण

सीएस व्याकरण के नियमों में, पीढ़ी के नियम के बाएं हिस्से में गैर-प्रतीक चिह्न को उत्पन्न श्रृंखला में कहीं भी दाएं हिस्से में बदला जा सकता है, जहां भी यह प्रतीक होता है। लेकिन कभी-कभी मैं उन संदर्भों के बीच अंतर करना चाहूंगा जिनमें प्रतीक श्रृंखला में है, और कुछ मामलों में, प्रतीक को प्रतिस्थापित करते हैं, दूसरों में - नहीं। सीओपी व्याकरण के नियम इसकी अनुमति नहीं देते हैं, इसलिए, ऐसे मामलों के लिए, एक विशेष प्रकार के नियम आवश्यक हैं।

संदर्भ-संवेदी व्याकरण में फॉर्म w' A w'' --> w' alpha w'' नियम हैं w' A w'' --> w' alpha w'' । यहाँ w' और w'' चेन हैं (खाली हो सकती हैं) व्याकरण के टर्मिनल और नॉनटर्मिनल सिंबल से बनी होती हैं, alpha उसी सिम्बल की एक नॉनम खाली चेन है। दूसरे शब्दों में, नॉनटर्मिनल प्रतीक A को चेन w' के संदर्भ में चेन alpha द्वारा w' और w'' से बदल दिया जाता है।

KZ व्याकरण के साथ संबद्ध व्याकरण का एक और वर्ग है - गैर-लघु व्याकरण। ऐसे व्याकरण के नियमों में एक शर्त को पूरा करना होगा: दाईं ओर की लंबाई बाईं ओर की लंबाई से कम नहीं होनी चाहिए। चूंकि KZ व्याकरण के नियमों में alpha श्रृंखला के गैर-रिक्त होने की एक शर्त है, इसलिए ये व्याकरण गैर-लघु भी होते हैं। लेकिन, सबसे दिलचस्प बात यह है कि एक गैर-लघु व्याकरण द्वारा परिभाषित प्रत्येक भाषा के लिए, एक केजेड व्याकरण का आविष्कार किया जा सकता है जो समान भाषा को परिभाषित करता है। दूसरे शब्दों में, केज-व्याकरण और गैर-लघु व्याकरण द्वारा परिभाषित भाषाओं के वर्ग मेल खाते हैं।

गैर-लघु व्याकरण द्वारा परिभाषित भाषाओं के एक वर्ग को एकल करना क्यों आवश्यक है? तथ्य यह है कि ऐसी भाषाओं के लिए, आप एक मान्यता मशीन निर्दिष्ट कर सकते हैं। व्याकरण को पहचानना निम्नानुसार निर्मित है: एक इनपुट के रूप में एक श्रृंखला प्राप्त करना, क्रमबद्ध रूप से उत्पादों को बनाना, उन्हें उत्पन्न श्रृंखला की लंबाई के साथ क्रमबद्ध करना। क्योंकि व्याकरण छोटा नहीं है, तो इस तरह के उत्पादों का एक सीमित सेट होगा, और यदि उनके बीच दिए गए इनपुट श्रृंखला के साथ कोई मेल नहीं था, तो "नहीं।"

नियमों के प्रकार पर प्रतिबंध के बिना एक व्याकरण के लिए, सामान्य मामले में ऐसी मान्यता एल्गोरिथ्म का निर्माण नहीं किया जा सकता है। उत्पन्न श्रृंखला पीढ़ी की प्रक्रिया में एक समझौते, सूजन और अपस्फीति की तरह व्यवहार कर सकती है। इसलिए, एक श्रृंखला द्वारा उत्पन्न एक निश्चित लंबाई की उपलब्धि यह गारंटी नहीं देती है कि इनपुट को खिलाई गई श्रृंखला पीढ़ी की प्रक्रिया में आगे प्राप्त नहीं होगी।

क्या केजी भाषाएं वास्तव में अपनी कक्षा बना रही हैं? क्या यह वर्ग केएस भाषाओं के वर्ग के साथ मेल खाता है? दूसरे शब्दों में, क्या कोई ऐसी भाषा है जिसके लिए यह गारंटी है कि आप एक केएस व्याकरण निर्दिष्ट नहीं कर सकते हैं, लेकिन क्या आप एक KZ व्याकरण निर्दिष्ट कर सकते हैं? उत्तर: हां, ऐसी भाषाएं हैं। ऐसी भाषा का एक उदाहरण निम्न भाषा L = {ww} । इस भाषा की श्रृंखलाएँ कुछ वर्णमाला के ऊपर दो दोहराई जाने वाली श्रृंखलाओं से बनी हैं। यह साबित करने के लिए कि इस भाषा के लिए केएस व्याकरण का निर्माण असंभव है, हम यहां नहीं होंगे। KZ व्याकरण को निम्नलिखित विचार के आधार पर परिभाषित किया जा सकता है। पहले एक श्रृंखला w और एक गैर-प्रतीक चिह्न उत्पन्न करें, A कहो, अर्थात्। श्रृंखला को Aw । फिर श्रृंखला A माध्यम से वर्ण A आगे w , इस श्रृंखला के वर्णों की प्रतिलिपि बनाकर रास्ते में ले जाएं और फिर इन वर्णों को दाईं ओर ले जाएं। नीचे दिए गए उदाहरण में इसे लागू किया जाएगा।

भाषा के लिए एक व्याकरण निर्दिष्ट करने के एक उदाहरण पर विचार करें L = {a^n^2 | n = 1, 2, 3, ...} L = {a^n^2 | n = 1, 2, 3, ...} । इस भाषा की श्रृंखलाओं में अक्षर a , और इन वर्णों की संख्या एक प्राकृतिक संख्या का वर्ग है: 1, 4, 9, 25, आदि। हम प्रतिबंधों के बिना इस भाषा के लिए एक व्याकरण देंगे। श्रृंखला पीढ़ी निम्नलिखित चरणों से मिलकर बनेगी:

कुछ प्राकृतिक संख्या n लिए n वर्णों की पीढ़ी।
वर्णों की इस संख्या से उत्पन्न होकर n^2 वर्ण।
इन वर्णों को वर्णों में बदलें a ।

पहले चरण को लागू करने के लिए, नियम जोड़ें
S --> LS'R
S' --> AS'B
S' --> AB

पहला नियम सीमांकित L और R में उत्पन्न श्रृंखला को लपेटना है R हमें तीसरे चरण के निर्माण के कार्यान्वयन के लिए भविष्य में उनकी आवश्यकता होगी। शेष दो नियम केवल फॉर्म AA...ABB...B की एक श्रृंखला उत्पन्न करते हैं, जहां A और B अक्षरों की संख्या मेल खाती है।

अब आपको स्ट्रिंग AA...ABB...B पर आधारित n^2 वर्ण बनाने की आवश्यकता है AA...ABB...B यह एक सरल चाल के लिए बनाता है। वर्ण A माध्यम से प्रत्येक संक्रमण पर, वर्ण B बाईं ओर ले जाएं और A और वर्ण C उत्पन्न करें C सी अक्षर के माध्यम से, चरित्र A स्वतंत्र रूप से दाईं ओर, और चरित्र B बाईं ओर से गुजर सकता है। इस चरण के नियम इस प्रकार हैं:
AB --> BAC
AC --> CA
CB --> BC
जब B सभी वर्ण A के वर्णों को पार करते हुए, बाएँ किनारे पर पहुँचते हैं, C के वर्ण बिल्कुल n^2 ।

अब हमें अपने आप को L , A , B और R अक्षर से मुक्त करना होगा और वर्ण C को वर्ण a बदलना होगा। ऐसा करने के लिए, प्रतीक B सत्यानाश करें क्योंकि यह बाएं किनारे से गुजरता है, अर्थात। चरित्र L तदनुसार, हम दाहिने किनारे पर प्रतीक A साथ कार्य करते हैं। इस तरह की रणनीति को लागू करते समय, फॉर्म LCC....CR की एक श्रृंखला बनी रहेगी। L और R के प्रतीकों से छुटकारा पाने के लिए, हम बाएं सीमक को दाईं ओर ले जाना शुरू करते हैं और जब वे स्पर्श करते हैं, तो हम इन प्रतीकों को नष्ट कर देते हैं। उसी समय, प्रतीकों L से गुजरने पर, हम उन्हें प्रतीकों a में बदलते हैं।इस पीढ़ी के चरण के नियम इस प्रकार हैं।
LB --> L
AR --> R
LC --> aL
LR --> epsilon
यहाँ epsilonएक खाली श्रृंखला को दर्शाता है।

आइए चेन जेनरेशन का एक उदाहरण दें aaaa:

S => LS'R => LAS'BR => LAABBR => LABACBR => LBACACBR => LACACBR => LACABCR => LACBACCR => LABCACCR => LBACCACCR => LACCACCR => LCACACCR => LCCAACCR => LCCACACR => LCCACCAR => LCCACCR => LCCCACR => LCCCCAR => LCCCCR => aLCCCR => aaLCCR => aaaLCR => aaaaLR => aaaa

निष्कर्ष

लेखक को उम्मीद है कि बाद के उदाहरण ने पाठक को स्पष्ट रूप से दिखाया कि चॉम्स्की का जेनेरिक व्याकरण एक प्रकार का कार्यक्रम है जिसे इस व्याकरण द्वारा परिभाषित औपचारिक भाषा की श्रृंखला तैयार करने के लिए डिज़ाइन किया गया है। कार्यक्रम असाइनमेंट की भाषा क्रमशः विशिष्ट है, और "पीढ़ी कार्यक्रमों" (व्याकरण) के कार्यान्वयन के लिए उन्हें लिखने में अनुभव और एक निश्चित आदत की आवश्यकता होती है।

चॉम्स्की के उत्पन्न होने वाले व्याकरण गहरे विचारों पर आधारित हैं और यह आश्चर्य की बात नहीं है कि इस प्रकार के व्याकरण के कुछ उपवर्ग न केवल एक निश्चित प्रकार की भाषा उत्पन्न करते हैं, बल्कि गणितीय भाषा विज्ञान के अन्य वर्गों के विचारों के साथ भी अंतर करते हैं। इस तरह के वर्गों में श्रेणीबद्ध व्याकरण और स्वचालितता को मान्यता देना शामिल है। बेशक, इस पाठ में केवल मूल विचारों का वर्णन किया गया है, सामान्य व्याकरण का सिद्धांत व्यापक और गहरा है ताकि इसे एक लेख के ढांचे में वर्णित किया जा सके।

चॉम्स्की जनरेटिंग ग्रामर