Context-free closure, normal forms और membership
लक्ष्य और सीमाएँ
Closure properties सही ढंग से लगाएँ, CFG को Chomsky normal form की ओर बदलें और membership को कठिन grammar questions से अलग करें। CFL वह language है जिसे कोई CFG generate या कोई NPDA recognize करता है। सभी regular languages CFL हैं: right-linear grammar या stack को ignore करने वाला PDA पर्याप्त है। Inclusion strict है; {a^n b^n:n≥0} context-free लेकिन nonregular है।
1. Positive closure constructions
CFLs union, concatenation और Kleene star के लिए closed हैं। दो grammars के variables rename करके disjoint करें। पुराने starts S1,S2 और fresh S के साथ S→S1|S2 union, S→S1S2 concatenation तथा S→S1S|ε पहले grammar का star देते हैं। Languages का disjoint होना जरूरी नहीं।
CFL का regular language से intersection CFL है। PDA और DFA को साथ चलाएँ: finite control में दोनों states और PDA का एक stack रखें। Input symbol पर दोनों update; PDA ε-step पर DFA state न बदले। पूरा input consume होने पर दोनों acceptance conditions चाहिए। इसलिए CFL से regular language घटाने पर भी CFL मिलता है: L\R=L∩complement(R)।
2. Nonclosure के लिए counterexample
L1={a^n b^n c^k:n,k≥0} और L2={a^i b^n c^n:i,n≥0} दोनों CFL हैं: stack एक adjacent pair compare करता है, तीसरा block free है। Intersection {a^n b^n c^n:n≥0} है, जो CFL नहीं है; Lesson 7 pumping lemma से proof देगा। इसलिए दो arbitrary CFLs के intersection पर closure नहीं है।
Complement पर भी closure नहीं: यदि होता तो union closure और De Morgan law से intersection closure मिलता, जो contradiction है। Arbitrary difference पर भी closure नहीं, क्योंकि complement(L)=Σ\L और Σ एक CFL है। “Not closed” का अर्थ कुछ operands का result class के बाहर है, हर operation हमेशा fail नहीं। उदाहरण L∩L=L, CFL ही रहता है।
3. ε को स्पष्ट रखते हुए CNF
हमारी CNF convention में A→BC और A→a allowed हैं, जहाँ B,C variables और a terminal है। ε language में हो तो fresh start S0→ε भी allowed है, बशर्ते S0 किसी right side पर न आए। बाकी ε-rules और A→B unit rules हटती हैं। Standard conversion में fresh start; nullable variables हटाते समय alternatives जोड़ना; unit reachability से unit rules हटाना; useless variables हटाना; लंबे right sides में terminals isolate करना और दो से अधिक symbols वाले right sides split करना शामिल है। Correctness बनाए रखने पर exact order बदल सकता है।
हल, S→aSb|ε: fresh S0 तथा A→a,B→b लें। Rules S0→AC | AB | ε, S→AC | AB, C→SB रखें। AC से aSb और AB से shortest nonempty pair बनता है। S केवल n≥1 के a^n b^n देता है; S0 साथ में ε देता है। हर non-ε production CNF shape में है और S0 किसी right side पर नहीं। केवल S→ε हटाकर AB alternative न जोड़ने से सभी terminal derivations खो जाएँगी।
4. CYK membership तथा finite search
CNF grammar और nonempty input w की length n के लिए T[i,l] में substring start i, length l बनाने वाले variables रखें। T[i,1] में प्रत्येक A→w_i के लिए A रखें। हर split l=k+(l−k) पर A→BC, B∈T[i,k], C∈T[i+k,l−k] मिले तो A जोड़ें। S0∈T[1,n] होने पर accept। ε को start ε-rule से अलग जाँचें। यह finite dynamic program membership decide करता है; standard time O(n^3|P|) है।
उसी CNF में ab के लिए T[1,1]={A}, T[2,1]={B}। S0→AB और S→AB से T[1,2]={S0,S}; accept। aa में दूसरी cell में B नहीं है, इसलिए length two के लिए S0 नहीं बनता।
CFG emptiness भी decidable है: terminal strings बनाने वाले variables mark करें; फिर जिस rule में केवल terminals या पहले से marked variables हों उसका left variable mark करें। ε भी terminal string है। Start mark हो ठीक तभी language nonempty है। इससे दो CFGs की equivalence या grammar ambiguity decide नहीं होती; वे general problems undecidable हैं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. CFL L और regular R पर कौन हमेशा CFL रखता है?
A. L∩R B. किन्हीं दो CFLs का intersection C. किसी भी CFL का complement D. किन्हीं दो CFLs का difference
उत्तर: A
A: PDA–DFA product केवल एक stack लेता है।
B: Triple-equality counterexample इसे गलत करता है।
C: Complement closure से intersection closure आ जाता।
D: Σ* से CFL घटाना complement closure देता।
P02. Worked L1 और L2 का intersection क्या है?
A. abc* B. {a^n b^n c^n:n≥0} C. ∅ D. {a^n b^n:n≥0}
उत्तर: B
A: दोनों equalities साथ चाहिए।
B: a=b और b=c से तीनों counts equal हैं।
C: ε और abc common हैं।
D: Nonempty c blocks भी हैं।
P03. बताए CNF convention में कौन-सा rule allowed है?
A. A→aB B. A→BCD C. A→BC D. A→B
उत्तर: C
A: Mixed two-symbol right side CNF नहीं।
B: Binary splitting चाहिए।
C: Right पर दो variables valid CNF shape हैं।
D: यह unit rule है।
P04. aSb में nullable S हटाने पर AB क्यों जोड़ते हैं?
A. ba बनाने के लिए B. भीतर का S मिट जाने वाला case बचाने के लिए C. Fresh start पर ε असंभव करने के लिए D. दो recursive calls अनिवार्य करने के लिए
उत्तर: B
A: AB से ab, ba नहीं।
B: Nullable occurrence ε हो सकता है, तब ab बचता है।
C: Fresh start ε रख सकता है।
D: दो recursions की condition नहीं।
P05. Worked CNF में ab के लिए T[1,2] में क्या है?
A. केवल A B. केवल B C. S0 और S D. कोई variable नहीं
उत्तर: C
A: A केवल single a देता है।
B: B केवल single b देता है।
C: दोनों में AB production है।
D: AB rules ab बनाते हैं।
P06. CFG का कौन-सा general question decidable है?
A. दो CFGs की equivalence B. CFG की ambiguity C. दिए finite word की membership D. उसकी language की हर CFG ambiguous है या नहीं
उत्तर: C
A: General CFG equivalence undecidable है।
B: General CFG ambiguity undecidable है।
C: CNF और CYK terminating procedure देते हैं।
D: किसी arbitrary CFG की language inherently ambiguous है या नहीं, यह तय करना undecidable है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन