Context-free grammars, derivations और ambiguity
लक्ष्य और notation
Grammars बनाना, उनकी language सिद्ध करना और grammar ambiguity को language की property से अलग करना सीखें। CFG G=(V,Σ,P,S) में finite variables V, उनसे disjoint terminal alphabet Σ, finite productions P और start S है। हर A→α rule में एक variable A को α∈(V∪Σ)* से बदलते हैं। Empty α को ε लिखते हैं। Sentential form में variables हो सकते हैं; L(G) का word केवल terminals वाला होता है और S से finitely many steps में बनता है।
Leftmost derivation हमेशा सबसे बाएँ बचा variable बदलती है; rightmost सबसे दायाँ बदलती है। Parse tree hierarchical rule choices रखता है, independent occurrences को expand करने का समयक्रम नहीं। Leaves को बाएँ से दाएँ पढ़ने पर word मिलता है; ε कोई symbol नहीं जोड़ता।
1. हल और दोनों दिशाओं का proof
L={a^n b^n:n≥0} के लिए S→aSb | ε लें। उदाहरण S⇒aSb⇒aaSbb⇒aabb। हर recursive rule बाएँ एक a और दाएँ एक b जोड़ता है। k recursive steps के बाद a^k S b^k है; ε लगाने पर a^k b^k मिलता है। इसलिए हर generated word L में है। उलटे, recursive rule n बार और फिर ε लगाने से हर a^n b^n मिलता है। दोनों दिशाएँ मिलकर equality सिद्ध करती हैं; केवल examples देना पर्याप्त नहीं।
{a^i b^j:i,j≥0} के लिए S→AB, A→aA|ε, B→bB|ε लें। यहाँ counts independent हैं। S→aSb|ε की जगह independent variables देने से language बदल जाती है: अब abbb भी बनता है।
2. अलग expansion orders ambiguity नहीं हैं
S→AB, A→a, B→b में S⇒AB⇒aB⇒ab और S⇒AB⇒Ab⇒ab केवल expansion order में अलग हैं; parse tree समान है। Grammar ambiguous है यदि किसी terminal word के कम-से-कम दो distinct parse trees हों; बराबर अर्थ में दो leftmost derivations अथवा दो rightmost derivations हों। एक leftmost और एक rightmost derivation मिलना पर्याप्त नहीं।
E→E+E | EE | id में id+idid के दो trees हैं। एक में root production E→E+E है और grouping id+(idid), इसलिए top-level operator + है; दूसरे में root production E→EE है और grouping (id+id)*id, इसलिए top-level operator * है। दोनों parse trees का root label स्वयं variable E है। Grammar precedence और associativity तय नहीं करता। Evaluation rules जोड़ने पर उपयुक्त values के लिए अलग अर्थ मिल सकते हैं।
3. Expression grammar सुधारें
E→E+T|T, T→TF|F, F→(E)|id लें। Multiplication terms के अंदर है, इसलिए addition से tighter binding है; हर operator level की left recursion left associativity देती है। id+idid में root production E→E+T है और अंतिम T, T*F बनता है। Parentheses से precedence को स्पष्ट रूप से बदल सकते हैं। यह repair intended ordinary expression language रखते हुए parse structure तय करता है।
एक ambiguous grammar देखकर language को inherently ambiguous न कहें। Inherent ambiguity का अर्थ है उस language की हर CFG ambiguous है। उदाहरण {a^n b^n:n≥0} की ऊपर दी grammar unambiguous है, भले कोई redundant ambiguous grammar भी लिख दे।
4. Cases से grammar बनाना
L={a^i b^j c^k:i=j या j=k; i,j,k≥0} को दो cases में बाँटें। S→XC | AY, X→aXb|ε, C→cC|ε, A→aA|ε, Y→bYc|ε। पहले branch में a,b counts बराबर; दूसरे में b,c counts बराबर हैं। a^n b^n c^n दोनों cases में आता है, इसलिए इस grammar में दो trees हैं। यह इस construction की ambiguity सिद्ध करता है; केवल इससे किसी भी alternative unambiguous grammar का न होना सिद्ध नहीं होता।
सावधानियाँ
- CFG rule का left side ठीक एक variable है।
- Membership के लिए variables हटकर terminal word मिलना जरूरी है।
- Exact language का दावा करने पर दोनों inclusions सिद्ध करें।
- Grammar ambiguity और inherent ambiguity के quantifiers अलग हैं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. S→aSb|ε कौन-सी language बनाता है?
A. ab B. {a^n b^n:n≥0} C. {a^n b^n:n≥1} D. {a^n b^(2n):n≥0}
उत्तर: B
A: Counts independent नहीं हैं।
B: हर recursion एक-एक जोड़ता है और ε से n=0 मिलता है।
C: Grammar ε भी बनाता है।
D: Rule एक b जोड़ता है, दो नहीं।
P02. केवल independent expansion order में अलग derivations क्या दिखाती हैं?
A. Grammar निश्चित रूप से ambiguous है B. Language non-context-free है C. इनसे अकेले ambiguity का निष्कर्ष नहीं निकलता D. हर word के दो trees हैं
उत्तर: C
A: दोनों एक tree दिखा सकती हैं।
B: Order context-freeness नहीं बदलता।
C: Distinct trees या एक ही direction की दो derivations चाहिए।
D: यहाँ अलग trees सिद्ध नहीं हैं।
P03. Ambiguous expression grammar में id+id*id के top-level operators क्या हो सकते हैं?
A. केवल + B. केवल * C. + तथा * दोनों D. केवल id
उत्तर: C
A: * top-level operator भी संभव है।
B: + top-level operator भी संभव है।
C: दो groupings में + और * दोनों top-level operators संभव हैं।
D: पूरा word एक id नहीं है।
P04. E→E+T|T और T→T*F|F में कौन tighter bind करता है?
A. + B. * C. दोनों की precedence अनियंत्रित है D. कोई operator नहीं आ सकता
उत्तर: B
A: Addition पूरे terms जोड़ता है।
B: Multiplication terms के अंदर है।
C: Variable levels precedence तय करते हैं।
D: दोनों operators rules में हैं।
P05. L की inherent ambiguity का अर्थ?
A. L की कोई एक CFG ambiguous है B. L की हर CFG ambiguous है C. L में infinite words हैं D. L की कोई CFG नहीं है
उत्तर: B
A: एक खराब grammar language property तय नहीं करता।
B: सभी CFGs वाला universal quantifier जरूरी है।
C: Infinite language unambiguous हो सकती है।
D: यह term context-free languages पर लागू है।
P06. S→AB,A→aA|ε,B→bB|ε से कौन-सा word बनता है?
A. ba B. abab C. abbb D. baba
उत्तर: C
A: b के बाद a नहीं आ सकता।
B: दूसरा a block order तोड़ता है।
C: Independent counts एक a और तीन b देते हैं।
D: यहाँ क्रम alternates है, a-block फिर b-block नहीं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन