Context Free Languages and Pushdown Automata MCQ Quiz in हिन्दी - Objective Question with Answer for Context Free Languages and Pushdown Automata - मुफ्त [PDF] डाउनलोड करें

सही उत्तर ​प्रतिच्छेदन है। 

Key Points
CFG की क्लास को प्रतिच्छेदन के अंतर्गत संवृत्त क्यों नहीं किया जाता है:

• प्रतिच्छेदन की परिभाषा: दो भाषाओं L1 और L2 का प्रतिच्छेदन उन सभी स्ट्रिंग्स का समूह होता है, जो L1 और L2 दोनों में हैं।
• सीएफजी नियमित भाषाएँ उत्पन्न कर सकते हैं: एक नियमित भाषा एक ऐसी भाषा होती है, जिसे एक सीमित अवस्था ऑटोमेटन द्वारा उत्पन्न किया जा सकता है।
• सीएफजी और एक नियमित भाषा का प्रतिच्छेदन: सीएफजी और एक नियमित भाषा का प्रतिच्छेदन हमेशा एक नियमित भाषा होता है।
• नियमित भाषाएँ हमेशा संदर्भ-मुक्त नहीं होती हैं: ऐसी नियमित भाषाएँ होती हैं, जिन्हें सीएफजी द्वारा उत्पन्न नहीं किया जा सकता है।
• इसलिए, दो सीएफजी का प्रतिच्छेदन सीएफजी नहीं हो सकता है: यदि सीएफजी में से एक नियमित भाषा उत्पन्न करता है जिसे सीएफजी द्वारा उत्पन्न नहीं किया जा सकता है, तो दो सीएफजी का प्रतिच्छेदन भी सीएफजी नहीं होगा।
• उदाहरण:
  • CFG G1: भाषा {a^n b^n उत्पन्न करता है | n ≥ 0}
  • CFG G2: भाषा {b^n a^n उत्पन्न करता है | n ≥ 0}
  • G1 और G2 का प्रतिच्छेदन: {a^n b^n | n ≥ 0} ∩ {b^n a^n | n ≥ 0} = {a^n b^n | n ≥ 0}
  • {a^n b^n | n ≥ 0} एक नियमित भाषा है, जिसे CFG द्वारा उत्पन्न नहीं किया जा सकता है।

इसलिए, G1 और G2 का प्रतिच्छेदन CFG नहीं होता है।

सही उत्तर ε है। 

Key Points

• स्ट्रिंग ऑपरेशन के संदर्भ में, आइडेंटिटी एलिमेंट को आम तौर पर एप्म्टी स्ट्रिंग द्वारा दर्शाया जाता है, जिसे अक्सर ε (एप्सिलॉन) के रूप में दर्शाया जाता है। आइडेंटिटी एलिमेंट  वह एलिमेंट  होता है, जो एक निश्चित एलिमेंट  में किसी अन्य एलिमेंट  के साथ जुड़ने पर दूसरे एलिमेंट  को बदलता नहीं है।
• दी गई स्ट्रिंग्स u = '1101' और v = '0001' है, हम देख सकते हैं कि किसी भी स्ट्रिंग को रिक्त स्ट्रिंग ε के साथ संयोजित करने से मूल स्ट्रिंग नहीं बदलती है। इसलिए, स्ट्रिंग संयोजन के लिए पहचान अवयव ε है।

सही उत्तर विकल्प 2 है।

संकल्पना:

एक व्याकरण जो किसी वाक्य के लिए एक से अधिक पार्स ट्री उत्पन्न करता है उसे संदिग्ध कहा जाता है।

व्युत्पत्ति ट्री की संख्या के आधार पर, संदर्भ-मुक्त व्याकरण दो प्रकारों में उप-विभाजित है:

संदिग्ध व्याकरण:

एक संदर्भ-मुक्त व्याकरण को संदिग्ध कहा जाता है यदि दिए गए इनपुट स्ट्रिंग के लिए एक से अधिक व्युत्पत्ति ट्री मौजूद हैं, यानी एक सबसे बायाँ (लेफ्टमोस्ट) व्युत्पन्न ट्री (एलएमडीटी) या सबसे दायाँ (राइटमोस्ट) व्युत्पन्न ट्री (आरएमडीटी) से अधिक।

सबसे बाईं (लेफ्टमोस्ट) व्युत्पत्ति:

प्रत्येक चरण पर सबसे बाएं गैर-टर्मिनल का विस्तार करके एक स्ट्रिंग प्राप्त करने की प्रक्रिया को सबसे बाईं व्युत्पत्ति कहा जाता है।

सबसे दाईं (राइटमोस्ट) व्युत्पत्ति:

प्रत्येक चरण में सबसे दाहिने गैर-टर्मिनल का विस्तार करके एक स्ट्रिंग प्राप्त करने की प्रक्रिया को सबसे दाहिनी व्युत्पत्ति कहा जाता है।

उदाहरण :

हम इस व्याकरण पर विचार करें: E -> E+E | id

स्ट्रिंग = id+id+id

असंदिग्ध व्याकरण:

एक संदर्भ-मुक्त व्याकरण को असंदिग्ध व्याकरण कहा जाता है यदि वहाँ एक और केवल एक व्युत्पत्ति ट्री या पार्स ट्री मौजूद है।

उदाहरण :

S → AB | aaB

A → a | Aa

B → b

अत: सही उत्तर असंदिग्ध है।

Additional Information

• एक नियमित भाषा एक ऐसी भाषा है जिसे नियमित अभिव्यक्ति या नियतात्मक या गैर-नियतात्मक परिमित ऑटोमेटा या अवस्था मशीनों के साथ व्यक्त किया जा सकता है।
• एक संदर्भ-संवेदनशील व्याकरण (सीएसजी) एक औपचारिक व्याकरण है जिसमें किसी भी उत्पादन नियमों के बाएं हाथ और दाएं हाथ टर्मिनल और गैर-टर्मिनल प्रतीकों के संदर्भ से घिरे हो सकते हैं।

सही उत्तर विकल्प 1 है।

संकल्पना:

विकल्प 1: दो संदर्भ-मुक्त भाषाओं का मिलन संदर्भ-मुक्त है।

सत्य, संदर्भ-मुक्त भाषाओं का मिलन हमेशा एक संदर्भ-मुक्त भाषा का निर्माण करता है। दो संदर्भ-मुक्त भाषाओं का संघ संचालन बंद है इसलिए हम दो संदर्भ-मुक्त भाषाओं के पुश-डाउन ऑटोमेटा को डिज़ाइन कर सकते हैं।

विकल्प 2: दो संदर्भ-मुक्त भाषाओं का प्रतिच्छेदन संदर्भ-मुक्त है।

असत्य, संदर्भ-मुक्त भाषाओं के प्रतिच्छेदन से संदर्भ-मुक्त भाषा नहीं बनेगी। दो संदर्भ-मुक्त भाषाओं का प्रतिच्छेदन संचालन बंद नहीं है इसलिए हम दो संदर्भ-मुक्त भाषाओं के पुश-डाउन ऑटोमेटा को डिज़ाइन नहीं कर सकते हैं।

विकल्प 3: दो संदर्भ-मुक्त भाषाओं का पूरक संदर्भ-मुक्त है।

असत्य, संदर्भ-मुक्त भाषाओं के पूरक से संदर्भ-मुक्त भाषा नहीं बनेगी। दो संदर्भ-मुक्त भाषाओं का पूरक संचालन बंद नहीं है इसलिए हम दो संदर्भ-मुक्त भाषाओं के पुश-डाउन ऑटोमेटा को डिज़ाइन नहीं कर सकते हैं।

विकल्प 4: यदि कोई भाषा संदर्भ-मुक्त है तो इसे हमेशा एक नियतात्मक पुशडाउन ऑटोमेटन द्वारा स्वीकार किया जा सकता है।

असत्य, यदि कोई भाषा नियतात्मक पुशडाउन ऑटोमेटा है तो उसे हमेशा संदर्भ-मुक्त भाषा द्वारा स्वीकार किया जा सकता है। नियतात्मक पुशडाउन ऑटोमेटा संदर्भ-मुक्त भाषा का एक सबसेट है, लेकिन संदर्भ-मुक्त भाषा नियतात्मक पुशडाउन ऑटोमेटा का सबसेट नहीं है।

इसलिए सही उत्तर दो संदर्भ-मुक्त भाषाओं का मिलन संदर्भ-मुक्त है।

Additional Information बंद गुण:

	नियमित	DCFL	CFL	CSL	पुनरावर्ती	REL
मिलन	Y	N	Y	Y	Y	Y
प्रतिच्छेदन	Y	N	N	Y	Y	Y
पूरक	Y	Y	N	Y	Y	N
अंतर	Y	N	N	Y	Y	N
प्रीफिक्स	Y	Y	Y	Y	Y	Y
सफिक्स	Y	Y	Y	Y	Y	Y
सबस्ट्रिंग	Y	Y	Y	Y	Y	Y
श्रृखंलाबद्धीकरण	Y	N	Y	Y	Y	Y
परिवर्तन	Y	N	Y	Y	Y	Y
क्लेन क्लोजर	Y	N	Y	Y	Y	Y
सकारात्मक बंद	Y	N	Y	Y	Y	Y
सबसेट	N	N	N	N	N	N
प्रतिस्थापन	Y	N	Y	N	N	Y
समरूपता	Y	N	Y	N	N	Y
विपरीत समरूपता	Y	Y	Y	Y	N	Y
Y = बंद N = बंद नहीं

विकल्प 2) सही है।

विश्लेषण:-

एक अभिव्यक्ति जिसमें स्वतंत्र रूप से तीन या अधिक चर की गिनती और तुलना शामिल है, एक प्रसंग-मुक्त भाषा नहीं है, क्योंकि एक स्टैक एक समय में केवल दो चर की तुलना की अनुमति देता है।

उदाहरण 1 - L = { aⁿbⁿcⁿ } प्रसंग मुक्त नहीं है। अन्य उदाहरण,

L = { aⁱb^jc^k | i > j > k } प्रसंग मुक्त नहीं है।

इस प्रकार, anbncn प्रसंग मुक्त व्याकरण (कान्टेक्सट फ्री ग्रामर) नहीं है।

Key Points

• एक रेखीय व्याकरण एक प्रसंग ​मुक्त व्याकरण है जिसमें इसके प्रत्येक रचना के दायीं ओर अधिकतम एक अंकेतर(नाॅन-टर्मिनल) होता है।
• एक पुनरावर्ती प्रसंग-मुक्त व्याकरण जिसमें कोई बेकार नियम नहीं है, अनिवार्य रूप से एक अनंत भाषा का निर्माण करता है।

​ Additional Informationप्रसंग-मुक्त व्याकरण:- प्रसंग-मुक्त व्याकरण(CFGS)प्रसंग-मुक्त भाषाओं का वर्णन करने के लिए उपयोग की जाती है। एक प्रसंग-मुक्त व्याकरण स्ट्रिंग के पैटर्न उत्पन्न करने के लिए उपयोग किए जाने वाले पुनरावर्ती नियमों का एक समूह है। प्रसंग-मुक्त व्याकरण सभी नियमित भाषाओं और अधिक का वर्णन कर सकती है, लेकिन यह सभी संभावित भाषाओं का वर्णन नहीं कर सकती है।

संकल्पना:

एक नियमित भाषा का यूनियन और एक नियतात्मक संदर्भ मुक्त भाषा (DCFL) एक DCFL है।

व्याख्या:

कथन I: सत्य।

L = {an |n ≥ 0} ∪ {anbn| n ≥ 0}

{an |n ≥ 0} एक नियमित भाषा है और {anbn| n ≥ 0} एक DCFL है और इसलिए, वहाँ एक DCFL होगा।

कथन II: असत्य।

L DCFL है तो यह CFL भी है।

कथन III: सत्य 

L किसी भी संख्या में लुक हेड के लिए LL(k) नहीं हो सकता है। LL(k) निर्णायक रूप से यह भेद नहीं कर सकता है कि पार्स की जाने वाली स्ट्रिंग aⁿ से है या anbn से है। दोनों का एक सामान्य उपसर्ग है।

संकल्पना:

S → aSa | bSb | a | b {a, b, aaa, bbb, aba, bab, abbba, ababa,….) जैसे स्ट्रिंग्स उत्पन्न करता है जो सभी विषम लंबाई वाले पैलिंड्रोम का सेट है।

विषम लंबाई के पैलिंड्रोम का उदाहरण.

स्ट्रिंग: ababa

विकल्प 1: गलत

स्ट्रिंग: "aa" (स्वीकृत नहीं)

एक ही प्रतीक के साथ शुरू और समाप्त होता है लेकिन दिए गए व्याकरण द्वारा स्वीकार नहीं किया जाता है

विकल्प 2 और 4: गलत

स्ट्रिंग: "aa" (स्वीकृत नहीं)

दिए गए व्याकरण द्वारा भी लंबाई का पैलिंड्रोम स्वीकार नहीं किया जाता है

अवधारणाएं:

संचालन जिसके तहत प्रसंग मुक्त भाषा बंद नहीं है: प्रतिच्छेदन, पूरकता, सेट अंतर

संचालन जिसके तहत प्रसंग मुक्त भाषा बंद है: संघ, क्लेन क्लोजर और श्रृंखलन ।

नियमित भाषा के साथ प्रतिच्छेदन के तहत प्रसंग मुक्त भाषा बंद है।

व्याख्या:

L1 एक नियमित भाषा है और L2 एक प्रसंग-मुक्त भाषा है।
प्रत्येक नियमित भाषा प्रसंग-मुक्त भाषा है।

विकल्प 1: प्रसंग-मुक्त भाषा

\({L_1}.{L_2}\) यह प्रसंग-मुक्त भाषा है क्योंकि यह श्रृंखलन  के तहत बंद है।

विकल्प 2: प्रसंग-मुक्त भाषा

L1 ∪ L2 यह प्रसंग-मुक्त भाषा है क्योंकि यह संघ के तहत बंद है।

विकल्प 3:  प्रसंग मुक्त भाषा

\({L_1} \cap \;{L_2}\) यह प्रसंग-मुक्त भाषा है क्योंकि नियमित भाषा के साथ प्रतिच्छेदन के तहत प्रसंग-मुक्त भाषा बंद है।

विकल्प 4:   प्रसंग-मुक्त भाषा नहीं हो सकती है

L1 - L2 यह प्रसंग-मुक्त भाषा नहीं हो सकती है क्योंकि यह पूरक के तहत बंद नहीं है।

अवधारणा: संदर्भ मुक्त भाषाओं का गुण है:

संदर्भ-मुक्त भाषाएँ संघ और अंतर के तहत बंद हैं, लेकिन पूरक और सर्वनिष्ठ के तहत बंद नहीं हैं।

व्याख्या:

विकल्प 1) L1 ∪ L2 संदर्भ-मुक्त है

चूंकि यूनियन के तहत संदर्भ-मुक्त भाषाएं बंद हैं। तो यह सही है।

विकल्प 2).  L̅1 संदर्भ-मुक्त है

L1 एक संदर्भ मुक्त भाषा है। गुण के अनुसार, इसका पूरक संदर्भ-मुक्त नहीं हो सकता।

विकल्प 3) L1 – R संदर्भ-मुक्त है

चूंकि नियमित भाषा के साथ संदर्भ-मुक्त भाषा का अंतर संदर्भ-मुक्त है। तो, यह सही है।

विकल्प 4) L1 ∩ L2 संदर्भ-मुक्त है

इसने संदर्भ-मुक्त भाषा संपत्ति का उल्लंघन किया। दो सीएफएल का प्रतिच्छेदन सीएफएल नहीं है। तो, यह गलत है।

दिए गए व्याकरण से उत्पन्न भाषा है

L = { ϵ, aa, aaaa, aaaaaa, …, bb, bbbb, bbbbbb,… abba, baab … }

विकल्प 1: an bm n ≥  1, m ≥  1 है

उत्पन्न सबसे छोटी स्ट्रिंग: ab  (n = 1, m = 1 )

L में स्ट्रिंग: ab नहीं है। इसलिए, विकल्प 1 गलत है

विकल्प 2: विषम लंबाई का पैलिंड्रोम

विषम लंबाई का पैलिंड्रोम, स्ट्रिंग: a

L में कोई विषम लंबाई वाली स्ट्रिंग नहीं है। इसलिए, विकल्प 2 गलत है

विकल्प 3: am bn n ≥ 0, m ≥ 0 है

उत्पन्न स्ट्रिंग: a   (n = 1, m = 0)

L में स्ट्रिंग: a नहीं है। इसलिए, विकल्प 3 गलत है

विकल्प  4: सम लम्बाई पैलिंड्रोम

भाषा L में सभी लंबाई वाले पैलिंड्रोम होते हैं। इसलिए विकल्प 4 सही है

संकल्पना:

संघ, श्रृंखलन और क्लेन क्लोजर (स्टार) के तहत संदर्भ मुक्त भाषाएं बंद हैं

CFL सर्वनिष्ठ के तहत बंद हैं और पूरकीकरण के तहत बंद नहीं हैं

उदाहरण:

L1 = pn qn rm | m, n > 0 → CFL

L2 = pm qn rn  | m, n > 0 → CFL

L = pn qn rm ∩ pm qn rn  | m, n > 0. L = pn qn rn यह निम्नगामी स्वचालित यंत्र द्वारा स्वीकार नहीं किया जाता है और इसलिए यह CFL नहीं है। और इसलिए यह सर्वनिष्ठ के तहत बंद नहीं है।

महत्वपूर्ण बिंदु:

प्रसंग मुक्त्त भाषाएँ	केवल निर्धारणात्मक प्रसंग मुक्त भाषाएँ
निम्न के तहत बंद संघ श्रृंखलन  क्लेन क्लोजर समरूपता व्यत्क्रम समरूपता भाषा का उत्क्रमण नियमित भाषा के साथ सर्वनिष्ठ	निम्न के तहत बंद पूरकीकरण व्यत्क्रम समरूपता
निम्न के तहत बंद नही है पूरकीकरण सर्वनिष्ठ	निम्न के तहत बंद नही है संघ सर्वनिष्ठ श्रृंखलन  क्लेन क्लोजर समरूपता भाषा का उत्क्रमण

संकल्पना

एक प्रसंग मुक्त व्याकरण को अस्पष्ट व्याकरण कहा जाता है यदि यह एक से अधिक पद व्याख्या वृक्ष (व्युत्पत्ति वृक्ष) उत्पन्न करता है या जब एक से अधिक एक ही वाक्य या निवेश के लिए सबसे अधिक व्युत्पत्ति या दाएं सबसे अधिक व्युत्पत्ति छोड़ता है।

व्याख्या:

व्याकरण S → aSbS|a|b|

यह संदिग्धार्थक है

श्रृंखला aabb के लिए:

एकल श्रृंखला के लिए दो व्युत्पत्ति वृक्ष बनाये गए हैं और इसलिए यह संदिग्धार्थक है

संकल्पना:
एक व्याकरण G = (V, T, S, P) को प्रसंग संवेदी कहा जाता है यदि सभी प्रस्तुतियाँ x → y के रूप की हों जहाँ x, y, (V U T)+ और |x| ≤ | y|

प्रसंग संवेदी व्याकरण से उत्पन्न भाषाएं संवेदी संवेदी भाषा के रूप में जानी जाती हैं।

भाषाओं और उनके स्वचलन के बीच संबंध।

व्याख्या:

• प्रसंग संवेदी भाषाओं को रेखीय परिबद्ध स्वचल प्ररूप की सहायता से पहचाना जाता है। एक रेखीय परिबद्ध स्वचलन में एक अपरिबद्ध टेप होता है, लेकिन ट्यूरिंग मशीन की तुलना में टेप का उपयोग करने योग्य हिस्सा प्रतिबंधित होता है।
• रेखीय परिबद्ध स्वचल प्ररूप में, दो अंत्य चिह्न होते हैं [बायाँ अंत्य चिह्न, दायाँ अंत्य चिह्न]। पाठन लेखन शीर्ष इन चिह्नों के बाएँ या दाएँ नहीं जा सकता।

भाषा L = {an bn cn: n > = 1}

• इसे रेखीय परिबद्ध स्वचल प्ररूप द्वारा स्वीकार किया जाता है। यह एक प्रसंग संवेदनशील भाषा है। एक अधोसंभर स्वचलप्ररूप इस भाषा को स्वीकार नहीं कर सकता।

चूंकि, इसके लिए एक से अधिक स्टैक की आवश्यकता होती है जो रेखीय परिबद्ध स्वचल प्ररूप में उपलब्ध होता है। इसमें प्रत्येक a, b और c को क्रमशः x, y और z द्वारा प्रतिस्थापित किया जाता है। अंत में, मूल प्रतीकों की जाँच की जाती है कि वे फिर से लिखे गए हैं या नहीं।

संकल्पना:

परिमित मेमोरी के कारण परिमित स्थिति मशीन सभी प्रसंग मुक्त भाषाओं को नहीं पहचान सकती है। इसलिए, एक और मशीन की आवश्यकता है जिसमें सहायक मेमोरी हो और सभी प्रसंग मुक्त भाषाओं को स्वीकार कर सके।

व्याकरण और उनके ऑटोमेशन के बीच संबंध।

 

व्याख्या:

एक उदाहरण पर विचार करें: भाषा L = {an bn: n> = 0}

• यहां n सीमित नहीं है, सीमित मेमोरी के साथ गिनती संभव नहीं है, इस मामले में असीमित गिनती क्षमता की आवश्यकता है। हम प्रसंग मुक्त भाषाओं या व्याकरण को स्वीकार करने के लिए एक सहायक मेमोरी यानी स्टैक वाले पुश डाउन ऑटोमेटा का उपयोग करते हैं।
• परिमित ऑटोमेटा द्वारा स्वीकार की जाने वाली सभी भाषाओं को नियमित भाषा के रूप में जाना जाता है। नियमित भाषाओं को उत्पन्न करने वाला व्याकरण नियमित व्याकरण है। तो, एक पुश डाउन ऑटोमेटा नियमित और प्रसंग मुक्त दोनों भाषाओं को स्वीकार करता है।

कथन I: सही 

L₁​ = {a^n+m bⁿ a^m | n, m ≥ 0} = {a^m aⁿ bⁿ a^m | n, m ≥ 0} 

उपरोक्त भाषा को नियतात्मक अधोसंभर स्वचालन (DPDA) द्वारा अस्वीकृत किया गया है और इसलिए यह संदर्भ मुक्त भाषा (CFL) है। 

वर्णन:

• इनपुट के रूप में आने वाले सभी a को आगे बढ़ाइए और जब b इनपुट के रूप में आता है, तो स्टैक के शीर्ष से “n” b के लिए a की “n” संख्या को दर्शाए। 
• जब फिर से a इनपुट के रूप में आता है, तो इनपुट के रूप में आने वाले a की “m” संख्या के लिए स्टैक के शीर्ष से सभी a (a की “m” संख्या) को बाहर दर्शाए। 

चूँकि हमारे पास L₁​ के लिए नियतात्मक अधोसंभर स्वचालन (DPDA) हो सकता है, इसलिए हम यह कह सकते हैं कि L​_1,​ CFL है। 

कथन II: गलत

L₂​ = {a^n+m b^n+m a^n+m |n, m ≥ 0} = {a^p b^p a^p | p ≥ 0} जहाँ n + m = p

उपरोक्त भाषा को अधोसंभर स्वचालन (PDA) द्वारा स्वीकृत नहीं किया गया है और इसलिए यह सन्दर्भ-मुक्त भाषा (CFL) नहीं है।