औपचारिक प्रसंग नि: शुल्क व्याकरण संदर्भ नि: शुल्क भाषा से

Question

कैसे एक औपचारिक संदर्भ मुक्त व्याकरण निम्न भाषा के लिए उत्पन्न किया जा सकता:

{ai bjck | i != j or j != k}

मैं प्रस्तुतियों निम्नलिखित है लेकिन यह समझ में नहीं कर सकते हैं:

 S->AX | YC      unequal b’s c’s or a’s b’s 

    A-> aA | e      0 or more A’s 

    C -> cC |e      0 or more c’s 

    B -> bB | e     0 or more B’s 

    X -> bXc | bB | cC    equal b’s, c’s then 1+ b’s, 
            1+C’s (i.e. unequal b’s and c’s) 

    Y -> aYb | bB | aA    unequal a’s b’s 

क्या कोई मुझे इस समस्या को समझने और हल करने में मदद कर सकता है?

Answer 1

भाषा L = {ai bj ck | i != j or j != k} को L = L1 U L2 जैसे L1 = {ai bj ck | i != j } और L1 = {ai bj ck | j != k } के रूप में लिखा जा सकता है। numberOf(a)

एल में प्रतीक c केवल इस शर्त पर कोई बाधा नहीं है है नहीं होना चाहिए numberOf(b) के बराबर है। या तो numberof(a)>numberOf(b)याnumberof(a)<। numberOf(b)। तो इस भाषा के लिए व्याकरण होना चाहिए:

L1 => EX    // L1 is start variable 
E => aEb | A | B 
X => C |^
A => aA | a 
B => bB | b 
C => cC | c 

ऊपर व्याकरण में ई का उपयोग कर हम anEbn के पैटर्न में a और b की संख्या के बराबर उत्पन्न कर सकते हैं, तो सजा के रूप में इस भावुक कन्वर्ट करने के लिए या तो E करने के द्वारा बदल दिया गया है B या A जो ai bj के साथ i != j के साथ फॉर्म में एक स्ट्रिंग उत्पन्न करता है, X का उपयोग करके c की संख्या ai bj पैटर्न पर पर्याप्त हो सकती है।

इस व्याकरण समझने के लिए पढ़ें: Tips for creating Context free grammar और Why the need for terminals? Is my solution sufficient enough?

इसी तरह एल के लिए वहाँ प्रतीक a केवल इस शर्त पर कोई बाधा numberOf(b) नहीं होना चाहिए numberOf(c) के बराबर रहा है। या तो numberof(b)>numberOf(c)याnumberof(b)<। numberOf(c)। एक नई शुरूआत चर S और दो नए उत्पादन नियमों S => L1 | L2 हम L = {ai bj ck | i != j or j != k} भाषा के लिए व्याकरण हो जाता है शुरू करने

L2 => YF    // L2 is start variable 
F => bFc | B | C 
Y => A |^
A => aA | a 
B => bB | b 
C => cC | c 

अब इस व्याकरण के दोनों का उपयोग कर: तो इस भाषा के लिए व्याकरण होना चाहिए।