Languages और deterministic finite automata
लक्ष्य और conventions
किस language के लिए machine को क्या याद रखना है, इससे DFA बनाएँ। पूर्वज्ञान sets और functions हैं। Alphabet Σ symbols का finite set है। String symbols का finite क्रम है; ε की length शून्य है। Σ* में ε सहित सभी finite strings हैं। Language, Σ* का कोई subset है। Empty language ∅ में कोई string नहीं; {ε} में एक string है। यहाँ automaton पूरा input पढ़ने के बाद acceptance तय करता है।
A और B के लिए AB={xy:x∈A,y∈B} है। Concatenation सामान्यतः commutative नहीं है। A^0={ε} और A* सभी n≥0 के A^n का union है। इसलिए ∅={ε}, लेकिन ∅A=∅। Complement निकालते समय universe चाहिए: यहाँ दिए alphabet पर Σ\A लेते हैं।
1. DFA की परिभाषा
DFA=(Q,Σ,δ,q0,F), जहाँ Q finite nonempty states, δ:Q×Σ→Q total function, q0 start और F⊆Q final states हैं। Drawing में missing edge को rejecting sink तभी मानें जब convention दिया हो। δ(q,ε)=q तथा δ(q,wa)=δ(δ(q,w),a)। Accepted language {w:δ(q0,w)∈F} है। बीच में final state आने से string accept नहीं होती। ε ठीक तभी accept है जब q0∈F।
हर state को अब तक पढ़े prefix की एक invariant property दें। पूरा prefix याद करना जरूरी नहीं; भविष्य के किसी suffix का परिणाम तय करने जितनी जानकारी पर्याप्त है।
2. हल: 1 की संख्या even हो
Alphabet {0,1} में E का अर्थ अब तक even 1 और O का अर्थ odd 1 रखें। Start और accepting state E है। 0 पर state न बदले; 1 पर E↔O करें। 1011 का trace E→O→O→E→O है, इसलिए reject। 101 का trace E→O→O→E है, इसलिए accept।
Correctness proof prefix length पर induction से है। ε में शून्य 1 हैं, इसलिए शुरुआत में invariant सही है। 0 पढ़ने पर parity समान और 1 पढ़ने पर उलटती है। Transitions भी यही करते हैं। इसलिए हर prefix के बाद invariant सही है और final E ठीक इच्छित condition बताता है। Proof दोनों दिशाएँ देता है: सभी सही words accept तथा सभी गलत words reject होते हैं।
3. हल: अंत में 01 हो
Target 01 का prefix बनने वाला current prefix का सबसे लंबा suffix याद करें। A, B, C क्रमशः ε, 0, 01 दर्शाते हैं। Start A; केवल C final। Transitions: A में 0→B,1→A; B में 0→B,1→C; C में 0→B,1→A। 001 का trace A→B→B→C है। 010 का trace A→B→C→B है, इसलिए reject। दो symbols बाद C मिलना early acceptance नहीं है।
तीनों states जरूरी हैं: suffix 1, B को A और C से अलग करता है; suffix ε, C को A से अलग करता है। यदि एक common suffix दो prefixes पर अलग acceptance देता है, वे एक DFA state में नहीं पहुँच सकते।
4. Fixed modulus से counting
Unary language {a^n:n mod 3=1} के लिए q0,q1,q2 में length का residue रखें। हर a पर q0→q1→q2→q0 cycle; q1 final है। Language infinite होने पर भी memory finite है। इसके विपरीत आगे exact equality मिलाने के लिए unbounded count याद रखना finite-state power से बाहर हो सकता है। केवल infinite strings होने से nonregular निष्कर्ष न निकालें: a* infinite और regular है।
गलतियाँ और तरीका
- Alphabet, start, finals और प्रत्येक transition स्पष्ट करें।
- ε, shortest accepted string और एक near miss जाँचें।
- कुछ traces की जगह invariant का proof दें।
- State count memory categories है; alphabet size symbols की संख्या है; दोनों accepted strings की संख्या नहीं हैं।
- DFA complement के लिए पहले transition function total बनाएँ, फिर finals उलटें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. किस language में ठीक एक string है?
A. ∅ B. {ε} C. {0,1}* D. ∅{a}
उत्तर: B
A: ∅ में कोई string नहीं।
B: केवल empty string इसका element है।
C: इसमें infinite strings हैं।
D: ∅ के साथ concatenation empty रहता है।
P02. Even-1s DFA में 11010 कहाँ समाप्त होता है?
A. E, स्वीकृत B. O, स्वीकृत C. E, अस्वीकृत D. O, अस्वीकृत
उत्तर: D
A: तीन 1 हैं, even नहीं।
B: O final नहीं है।
C: E final होता, लेकिन यहाँ नहीं पहुँचते।
D: तीन 1 से O मिलता है और reject होता है।
P03. Suffix-01 DFA कौन-सा word accept करता है?
A. 010 B. 001 C. ε D. 11
उत्तर: B
A: अंतिम suffix 10 है।
B: अंत 01 है और C मिलता है।
C: Start A final नहीं।
D: अंत 11 है और A मिलता है।
P04. ∅* क्या है?
A. ∅ B. {ε} C. हर Σ के लिए Σ* D. {∅}
उत्तर: B
A: Zero-fold concatenation से ε मिलता है।
B: केवल A^0={ε} का योगदान है।
C: Nonempty word नहीं बन सकता।
D: ∅ language है, empty word नहीं।
P05. Complete DFA ε ठीक कब accept करता है?
A. हर state final है B. Alphabet खाली है C. Start state final है D. एक self-loop है
उत्तर: C
A: पर्याप्त है, आवश्यक नहीं।
B: Alphabet खाली होना finality तय नहीं करता।
C: Input नहीं पढ़ते, start पर रहते हैं।
D: Loop final state पर होना जरूरी नहीं।
P06. Residue-3 DFA q0 से शुरू और q1 पर accept करता है। कौन-सी length accept है?
A. 6 B. 8 C. 9 D. 10
उत्तर: D
A: 6 mod 3=0।
B: 8 mod 3=2।
C: 9 mod 3=0।
D: 10 mod 3=1।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन