उत्पादन (कंप्यूटर विज्ञान)

कंप्यूटर विज्ञान में एक उत्पादन या उत्पादन नियम एक 'पुनर्लेखन नियम' है जो एक प्रतीक प्रतिस्थापन को निर्दिष्ट करता है जिसे नए प्रतीक अनुक्रमों को उत्पन्न करने के लिए पुनरावर्ती रूप से निष्पादित किया जा सकता है। प्रस्तुतियों का एक सीमित सेट $P$ एक औपचारिक व्याकरण (विशेष रूप से एक उत्पादक व्याकरण) के विनिर्देशन में मुख्य घटक है। अन्य घटक परिमित समुच्चय हैं $N$ गैर-टर्मिनल प्रतीकों का, एक परिमित सेट (वर्णमाला के रूप में जाना जाता है) $\Sigma$ टर्मिनल प्रतीकों की संख्या जो विसंधित है से सेट करता है $N$ और एक विशिष्ट प्रतीक $S\in N$ वह प्रारंभ प्रतीक है।

एक अप्रतिबंधित व्याकरण में, एक उत्पादन रूप का होता है $u\to v$, कहाँ $u$ और $v$ टर्मिनलों और गैर-टर्मिनलों के मनमाने तार हैं, और $u$ खाली स्ट्रिंग नहीं हो सकता। अगर $v$ खाली स्ट्रिंग है, इसे प्रतीक द्वारा दर्शाया गया है $\epsilon$, या $\lambda$ (दाईं ओर खाली रहने के बजाय)। तो प्रोडक्शंस कार्टेशियन उत्पाद के सदस्य हैं

$V^{*}NV^{*}\times V^{*}=(V^{*}\setminus \Sigma ^{*})\times V^{*}$,

कहाँ $V:=N\cup \Sigma$ शब्दावली है, ${}^{*}$ क्लेन स्टार ऑपरेटर है, $V^{*}NV^{*}$ जुड़ाव इंगित करता है, $\cup$ संघ (सेट सिद्धांत) को दर्शाता है, और $\setminus$ पूरक (सेट सिद्धांत) को दर्शाता है। अगर हम स्टार्ट सिंबल को अंदर आने की अनुमति नहीं देते हैं $v$ (दाईं ओर का शब्द), हमें बदलना होगा $V^{*}$ द्वारा $(V\setminus \{S\})^{*}$ कार्तीय उत्पाद प्रतीक के दाईं ओर। चॉम्स्की पदानुक्रम में अन्य प्रकार के औपचारिक व्याकरण एक उत्पादन का गठन करने पर अतिरिक्त प्रतिबंध लगाते हैं। विशेष रूप से एक संदर्भ-मुक्त व्याकरण में, उत्पादन के बाईं ओर एक एकल गैर-टर्मिनल प्रतीक होना चाहिए। तो प्रोडक्शंस फॉर्म के हैं:

$N\to (N\cup \Sigma )^{*}$

व्याकरण पीढ़ी

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

उदाहरण के लिए, मान लें कि वर्णमाला में शामिल हैं $a$ और $b$, प्रारंभ प्रतीक के साथ $S$, और हमारे पास निम्नलिखित नियम हैं:

1. $S\rightarrow aSb$

2. $S\rightarrow ba$

फिर हम साथ शुरू करते हैं $S$, और उस पर लागू करने के लिए कोई नियम चुन सकते हैं. यदि हम नियम 1 चुनते हैं, तो हम प्रतिस्थापित करते हैं $S$ साथ $aSb$ और स्ट्रिंग प्राप्त करें $aSb$. यदि हम नियम 1 को फिर से चुनते हैं, तो हम प्रतिस्थापित करते हैं $S$ साथ $aSb$ और स्ट्रिंग प्राप्त करें $aaSbb$. यह प्रक्रिया तब तक दोहराई जाती है जब तक कि हमारे पास केवल वर्णमाला के प्रतीक न हों (अर्थात, $a$ और $b$). यदि हम अब नियम 2 चुनते हैं, तो हम प्रतिस्थापित करते हैं $S$ साथ $ba$ और स्ट्रिंग प्राप्त करें $aababb$, और कर दिए गए हैं। हम प्रतीकों का उपयोग करके विकल्पों की इस श्रृंखला को और संक्षेप में लिख सकते हैं: $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aababb$. व्याकरण की भाषा उन सभी स्ट्रिंग्स का समूह है जो इस प्रक्रिया का उपयोग करके उत्पन्न की जा सकती हैं: $\{ba,abab,aababb,aaababbb,\dotsc \}$.

यह भी देखें

• औपचारिक व्याकरण
• परिमित ऑटोमेटा
• जनरेटिव व्याकरण
• एल प्रणाली
• पुनर्लेखन नियम
• बैकस-नौर रूप (संदर्भ-मुक्त व्याकरण की प्रस्तुतियों को लिखने के लिए एक संक्षिप्त रूप।)
• वाक्यांश संरचना नियम
• पोस्ट कैनोनिकल सिस्टम (एमिल पोस्ट की प्रोडक्शन सिस्टम- गणना का एक मॉडल।)