DFA minimization, closure और decision procedures
लक्ष्य
दो states की future information कब समान है, यह पहचानें; complete DFA minimize करें; product construction से language questions हल करें। सभी complements fixed alphabet Σ पर हैं। Language regular ठीक तभी है जब कोई DFA उसे recognize करता है; NFA और classical regular expression भी यही class देते हैं।
1. सभी suffixes से equivalence
p,q equivalent हैं यदि हर z∈Σ* के लिए δ(p,z) final ठीक तभी है जब δ(q,z) final है। एक distinguishing suffix inequivalence सिद्ध करता है। दोनों का final या nonfinal होना जरूरी है, लेकिन पर्याप्त नहीं। Minimal accessible DFA का size बताने से पहले unreachable states हटाएँ।
Partition refinement को F और Q\F से शुरू करें; empty block हटाएँ। किसी symbol पर अलग blocks में जाने वाले states को split करें। Stable होने तक दोहराएँ। एक block के states का future acceptance समान है, इसलिए हर block एक state बनता है। Complete minimal accessible DFA state names बदलने तक unique है।
हल: alphabet {0,1}, states A,B,C,D; start A; finals C,D। A:0→B,1→C; B:0→B,1→D; C:0→B,1→C; D:0→B,1→D। चारों reachable हैं। शुरुआती blocks {A,B},{C,D} stable हैं: 0 पहले block और 1 दूसरे में जाता है। इसलिए minimal DFA में दो states हैं और language अंत में 1 वाली strings है। A और B तक आने के paths अलग हैं, लेकिन future behavior समान है।
2. Distinguishable prefixes से lower bound
L={w∈{a}*:|w|, m से divisible है}, m≥1 लें। Prefixes ε,a,…,a^(m−1) देखें। अलग residues i,j के लिए a^((m−i) mod m) जोड़ें। पहले की length m से divisible होती है; दूसरे की नहीं। इसलिए m अलग states जरूरी हैं। Residue-counter में m states पर्याप्त भी हैं, इसलिए exact minimum m है। केवल एक construction का state count upper bound देता है; exactness के लिए lower bound चाहिए।
सामान्यतः x~L y iff हर z के लिए xz∈L iff yz∈L। Myhill–Nerode theorem के अनुसार L regular ठीक तभी है जब finitely many equivalence classes हों; उनकी संख्या minimal complete DFA का size है। {a^n b^n:n≥0} में a^i prefixes को b^i से अलग कर सकते हैं, इसलिए infinitely many classes हैं।
3. Closure की constructions
Same alphabet के M1,M2 DFAs के product states (p,q) दोनों को track करते हैं और हर symbol पर दोनों update होते हैं। Intersection में दोनों final, union में कम-से-कम एक final, symmetric difference में ठीक एक final चाहिए। अधिकतम |Q1||Q2| states हैं, लेकिन minimum इतना होना जरूरी नहीं। L1\L2 में पहला final और दूसरा nonfinal चाहिए।
Regular languages union, intersection, complement, difference, concatenation, star और reversal के लिए closed हैं। Concatenation/star/reversal में ε-NFA सुविधाजनक है; DFA चाहिए तो determinize करें। DFA arrows उलटने से सामान्यतः NFA मिलता है; कई starting choices को fresh ε-start से handle करें। वह अपने आप DFA नहीं बनता।
4. Decision procedures और witness
DFA emptiness graph reachability है: start से कोई final reachable है? हाँ तो path के labels witness देते हैं। Language finite ठीक तभी है जब ऐसा directed cycle न हो जो start से reachable हो और जिससे final तक पहुँचा जा सके। DFA edges symbols consume करती हैं, इसलिए ऐसा cycle बार-बार लेकर arbitrarily long accepted words मिलते हैं।
दो DFAs की equivalence उनके symmetric-difference product की emptiness है। Unary alphabet में M1 even length और M2 length divisible by 3 accept करे। ε दोनों में, a किसी में नहीं, लेकिन aa केवल M1 में है। इसलिए aa counterexample है और languages अलग हैं। केवल कुछ strings जाँचना equality का proof नहीं; exhaustive construction चाहिए।
गलतियाँ
- Complement के लिए total transitions और common alphabet चाहिए।
- Unreachable final से language nonempty नहीं होती।
- Reachable cycle से final तक न पहुँच सकें तो वह infinitude नहीं सिद्ध करता।
- Equivalent automata के sizes अलग हो सकते हैं; minimal complete accessible versions के sizes समान होते हैं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. दो states equivalent होने के लिए किन suffixes पर उनका future acceptance समान होना चाहिए?
A. उनके नाम B. केवल ε C. हर संभव suffix D. केवल length one के suffixes
उत्तर: C
A: Names से language तय नहीं होती।
B: केवल समान finality पर्याप्त नहीं।
C: यही future equivalence की definition है।
D: लंबे suffixes अलग कर सकते हैं।
P02. Worked four-state DFA कितने states में minimize होता है?
A. 1 B. 2 C. 3 D. 4
उत्तर: B
A: 1 accept और ε reject है, एक state पर्याप्त नहीं।
B: Stable blocks {A,B} और {C,D} हैं।
C: तीसरा future behavior नहीं है।
D: Equivalent states merge हो सकती हैं।
P03. Unary length 5 से divisible हो तो minimum complete DFA states?
A. 4 B. 5 C. 6 D. 32
उत्तर: B
A: पाँच residues pairwise distinguishable हैं।
B: पाँच residues construction और lower bound दोनों देते हैं।
C: Total counter को extra sink नहीं चाहिए।
D: Subset bound यहाँ संबंधित नहीं है।
P04. DFA language infinite ठीक कब है, जब cycle:
A. Graph में कहीं भी हो B. केवल start से reachable हो C. केवल final तक पहुँच सके D. Start से reachable हो और final तक पहुँच सके
उत्तर: D
A: Unreachable या dead cycle accepted words नहीं देता।
B: Cycle से acceptance संभव न हो।
C: Cycle unreachable हो सकता है।
D: Consuming cycle दोहराकर final तक जाएँ।
P05. किस product final condition की nonemptiness inequivalence बताती है?
A. दोनों components final हों B. कोई component final न हो C. ठीक एक component final हो D. दूसरा कुछ भी हो, पहला final हो
उत्तर: C
A: यह intersection जाँचता है।
B: यह shared rejection जाँचता है।
C: Witness एक language में है, दूसरी में नहीं।
D: यह दूसरी language को अनदेखा करता है।
P06. Even unary length और 3 से divisible length को कौन अलग करता है?
A. ε B. a C. aa D. aaaaaa
उत्तर: C
A: दोनों zero length accept करते हैं।
B: दोनों length one reject करते हैं।
C: Length two केवल even machine accept करती है।
D: दोनों length six accept करते हैं।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन