मैं साबित करने के लिए कोशिश कर रहा हूँ निम्नलिखित:मैं कैसे साबित कर सकता हूं कि चॉम्स्की सामान्य फॉर्म में व्युत्पन्न 2 एन -1 चरणों की आवश्यकता है?
तो जी एक प्रसंग चोमस्की सामान्य फार्म में नि: शुल्क व्याकरण है, तो किसी भी स्ट्रिंग के लिए डब्ल्यू n लंबाई ≥ 1 के एल (G) अंतर्गत आता है, यह वास्तव में 2n की आवश्यकता है डब्ल्यू के व्युत्पन्न करने के लिए -1 कदम।
मैं इसे साबित करने के बारे में कैसे जाऊं?
एक संकेत के रूप में - के बाद से चोमस्की सामान्य फार्म में हर उत्पादन या तो प्रपत्र
एस → एबी, nonterminals ए और बी के लिए, या रूप
एस → एक्स, के लिए टर्मिनल एक्स है,
फिर एक स्ट्रिंग पाने निम्नलिखित तरीके से काम करेगा:
लागू करने प्रस्तुतियों कश्मीर से k करने के लिए + 1, जब से तुम +1 nonterminal का शुद्ध लाभ के लिए दो nonterminals (+2) के साथ एक nonterminal (-1) की जगह nonterminals की संख्या में वृद्धि होगी। एक nonterminal के साथ अपनी शुरुआत के बाद से, इसका मतलब है कि आपको पहले फॉर्म के एन -1 प्रोडक्शन करना होगा। इसके बाद आपको nonterminals को टर्मिनल में बदलने के लिए दूसरे फॉर्म की आवश्यकता होती है, जिसमें कुल एन + (एन -1) = 2 एन -1 प्रस्तुतियां होती हैं।
यह दिखाने के लिए कि आपको बिल्कुल की आवश्यकता है, मैं विरोधाभास द्वारा सबूत करने का सुझाव दूंगा और यह दिखाऊंगा कि आप इसे किसी भी या कम से कम नहीं कर सकते हैं। एक संकेत के रूप में, प्रत्येक प्रकार के प्रोडक्शंस की संख्या गिनने का प्रयास करें और दिखा रहा है कि यदि यह 2 एन -1 नहीं है, तो स्ट्रिंग बहुत छोटा है, या आपके पास अभी भी nonterminals शेष रहेगा।
आशा है कि इससे मदद मिलती है!
: क्या आप बता सकते हैं कि हमें पहले फॉर्म के एन -1 प्रस्तुतियों को क्यों करने की आवश्यकता है। – justin
ज़रूर! परिणामी स्ट्रिंग में प्रत्येक टर्मिनल अंततः एक गैर-टर्मिनल लेने और फॉर्म ए -> ए के कुछ उत्पादन के माध्यम से इसे टर्मिनल में विस्तारित करके बनाया जाता है। इसका मतलब है कि, किसी बिंदु पर, कुल एन nonterminals उत्पादन किया जाना है। उनमें से एक प्रारंभ प्रतीक से मुक्त आता है। प्रत्येक बार जब आप फॉर्म ए -> बीसी का उत्पादन करते हैं, तो आपको एक और nonterminal मिलता है। इसलिए, आपको फॉर्म ए -> बीसी के एन-1 प्रस्तुतियों को करने की आवश्यकता है ताकि आप एन-1 अतिरिक्त रूप से आवश्यक nonterminals बना सकें। – templatetypedef
: ओह क्या आप कहने का मतलब है कि 'एन -1' अभिव्यक्ति का '-1' आता है क्योंकि उनमें से एक प्रारंभ प्रतीक से मुक्त होता है? – justin