एक व्याकरण द्वारा उत्पन्न भाषा
व्याकरण से उत्पन्न होने वाले सभी तारों के समुच्चय को उस व्याकरण से उत्पन्न भाषा कहा जाता है। एक व्याकरण द्वारा उत्पन्न भाषाG औपचारिक रूप से परिभाषित एक सबसेट है
एल (जी) = {डब्ल्यू | डब्ल्यू ∈ S *, एस ⇒ जी W}
अगर L(G1) = L(G2), व्याकरण G1 व्याकरण के समतुल्य है G2।
उदाहरण
अगर कोई व्याकरण है
जी: एन = {एस, ए, बी} टी = {ए, बी} पी = {एस → एबी, ए → ए, बी → →}
यहाँ S पैदा करता है AB, और हम बदल सकते हैं A द्वारा a, तथा B द्वारा b। यहां, केवल स्वीकृत स्ट्रिंग हैab, अर्थात,
L (G) = {ab}
उदाहरण
मान लीजिए हमारे पास निम्नलिखित व्याकरण है -
जी: एन = {एस, ए, बी} टी = {ए, बी} पी = {एस → एबी, ए → ए | ए, बी → बी बी | बी} |
इस व्याकरण द्वारा उत्पन्न भाषा -
L (G) = {ab, a 2 b, ab 2 , a 2 b 2 , ………}
= {a m b n | m m 1 और n} 1}
एक भाषा का निर्माण एक व्याकरण का निर्माण
हम कुछ भाषाओं पर विचार करेंगे और इसे एक व्याकरण G में परिवर्तित करेंगे जो उन भाषाओं का निर्माण करता है।
उदाहरण
Problem- मान लीजिए, L (G) = {a m b n | m m 0 और n> 0}। हमें व्याकरण का पता लगाना होगाG जो पैदा करता है L(G)।
Solution
चूंकि L (G) = {a m b n | m m 0 और n> 0}
स्वीकृत स्ट्रिंग्स के सेट को फिर से लिखा जा सकता है -
L (G) = {b, ab, bb, aab, abb, ……। ”
यहां, स्टार्ट सिंबल को कम से कम एक 'बी' लेना होता है, जिसमें किसी भी संख्या में 'ए' शामिल होता है।
स्ट्रिंग सेट को स्वीकार करने के लिए {b, ab, bb, aab, abb, ……।}, हमने प्रोडक्शंस लिए हैं:
एस → एएस, एस → बी, बी → बी और बी → बीबी
S → B → b (स्वीकृत)
S → B → bB → bb (स्वीकृत)
S → aS → aB → ab (स्वीकृत)
एस → एएस → एएएस → एएबी → एएबी (स्वीकृत)
S → aS → aB → abB → abb (स्वीकृत)
इस प्रकार, हम उत्पादन सेट द्वारा उत्पन्न भाषा द्वारा एल (जी) में हर एक स्ट्रिंग को स्वीकार कर सकते हैं।
इसलिए व्याकरण -
G: ({S, A, B}, {a, b}, S, {S → aS | B, B → b | bB}) |
उदाहरण
Problem- मान लीजिए, L (G) = {a m b n | m> 0 और n} 0}। हमें व्याकरण G का पता लगाना होगा जो L (G) का उत्पादन करता है।
Solution -
चूंकि L (G) = {a m b n | m> 0 और n} 0}, स्वीकृत स्ट्रिंग्स के सेट को फिर से लिखा जा सकता है -
L (G) = {a, aa, ab, aaa, aab, abb, ……।}
यहाँ, स्टार्ट सिंबल को कम से कम एक 'a' और उसके बाद n सहित किसी भी संख्या में 'b' लेना है।
स्ट्रिंग सेट को स्वीकार करने के लिए {a, aa, ab, aaa, aab, abb, ……।}, हमने उत्पाद ले लिए हैं -
एस → एए, ए → एए, ए → बी, बी → बीबी, बी → λ
S → AA → aB → aλ → a (स्वीकृत)
एस → एए → एएए → एएबी → एएस्टन → एए (स्वीकृत)
S → AA → aB → abB → abλ → ab (स्वीकृत)
एस → एए → एएए → एएएएए → एएएबी → एएएस्टन → एएए (स्वीकृत)
एस → एए → एएए → एएबी → एएबीबी → एबॉन → एब (स्वीकृत)
S → AA → aB → abB → abbB → abbλ → abb (स्वीकृत)
इस प्रकार, हम उत्पादन सेट द्वारा उत्पन्न भाषा द्वारा एल (जी) में हर एक स्ट्रिंग को स्वीकार कर सकते हैं।
इसलिए व्याकरण -
जी: ({एस, ए, बी}, {ए, बी}, एस, {एस → एए, ए → ए | बी, बी → λ | bB}) |