Nondeterminism, epsilon closure और regular expressions
लक्ष्य और notation
ε-NFA को DFA में बदलें और finite automata को regular expressions से जोड़ें। NFA में एक symbol पर zero, one या कई transitions हो सकती हैं। ε-transition input नहीं खाती। Word तभी accept है जब कम-से-कम एक finite path पूरा input consume करके final state में खत्म हो। बाकी failing या infinite ε-paths इस witness को रद्द नहीं करते। Nondeterminism existential choice है, probability नहीं; सभी branches का accept होना जरूरी नहीं।
1. ε-NFA से subset construction
States s,p,f, start s और final f लें। ε:s→p है; p पर a-loop और b→f है; f पर b-loop है; बाकी transitions empty हैं। Language a*b+ है। ε-closure(S) में S से zero या अधिक ε-steps से पहुँचने वाले सभी states हैं, इसलिए S भी इसमें है।
DFA start closure({s})={s,p} है। Subset T से symbol c पर पहले सभी states की c-transitions का union लें, फिर result का ε-closure लें। Subset तभी final है जब उसका NFA final set से intersection nonempty हो। Reachable subsets {s,p}, {p}, {f}, ∅ हैं। {s,p} तथा {p} से a पर {p}, b पर {f}; {f} से a पर ∅, b पर {f}; ∅ दोनों symbols पर स्वयं में रहता है। केवल {f} final है। इसलिए aab accept, ba reject और ε reject है।
n-state NFA के अधिकतम 2^n subsets हो सकते हैं, ∅ सहित। कई unreachable या equivalent हो सकते हैं। यह upper bound है, हर conversion की exact संख्या नहीं। Correctness invariant: w पढ़ने के बाद subset में ठीक वे NFA states हैं जिन तक w consume करके तथा ε-moves लेकर पहुँच सकते हैं। इसलिए दोनों acceptance tests समान हैं।
2. Regular expression का अर्थ
Base expressions ∅, ε और alphabet के symbols हैं। R|S union, RS concatenation और R* zero-or-more repetitions दर्शाता है। Precedence: star, concatenation, union; parentheses इसे बदलते हैं। यहाँ + का अर्थ one-or-more repetitions है, union नहीं। a*b+ में zero या अधिक a, फिर कम-से-कम एक b है।
{0,1} पर (0|1)01 ठीक अंत में 01 वाली strings देता है। 0|10 में single 0 या 1 के बाद zero या अधिक 0 हैं; यह (0|1)0* नहीं है। R|R=R, Rε=R तथा R∅=∅ हैं। सामान्यतः RS≠SR और (R|S)≠R|S। R=a,S=b लेने पर ab पहले में है, a अथवा b* में नहीं।
3. Expressions और automata की equivalence
Induction से ε-NFA बनाएँ: union के लिए नया branching start; concatenation में पहले fragment के finals से दूसरे के start तक ε-edges; star में zero repetitions तथा अगले repetition के लिए लौटने की सुविधा। Subset construction मिलाकर हर regular expression का DFA मिलता है।
उलटी दिशा में generalized automaton की edges को expressions से label करें। State k हटाते समय बाकी हर i→j label को R_ij | R_ik (R_kk)* R_kj करें; उस elimination step के पुराने labels इस्तेमाल करें। Path या तो k से बचता है या k तक जाता, वहाँ zero या अधिक loops करता और बाहर आता है। जरूरत पर fresh start/final जोड़ें, जिन्हें eliminate नहीं करते। इससे हर finite automaton का regular expression बनता है।
हल: i→j=c, i→k=a, k→k=b, k→j=d होने पर नया label c|ab*d है। इसमें c तथा ad भी हैं; b-loop कम-से-कम एक बार चलना जरूरी नहीं।
सावधानियाँ
- Start पर और हर consumed symbol के बाद ε-closure लें।
- एक accepting branch पर्याप्त है, लेकिन पूरा input consume होना चाहिए।
- NFA finals उलटकर complement सामान्यतः नहीं मिलता; पहले determinize करें।
- ε एक empty word है; ∅ में कोई word नहीं।
- Programming regex के backreferences यहाँ के classical regular-expression syntax में नहीं हैं।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें।
P01. NFA में एक accepting और एक rejecting full-input branch है। परिणाम?
A. स्वीकार B. अस्वीकार C. अपरिभाषित D. केवल equiprobable branches होने पर स्वीकार
उत्तर: A
A: एक witness पर्याप्त है।
B: Rejecting branch acceptance रद्द नहीं करती।
C: Existential definition से परिणाम तय है।
D: NFA semantics में probabilities नहीं हैं।
P02. Worked ε-NFA का start subset क्या है?
A. {s} B. {p} C. {s,p} D. {f}
उत्तर: C
A: ε से पहुँचने वाला state छूटता है।
B: Closure में original state भी है।
C: Input से पहले s और p reachable हैं।
D: f के लिए b consume करना पड़ता है।
P03. n-state NFA से subset construction में अधिकतम क्या मिलता है?
A. n states B. 2n states C. n! states D. 2^n states
उत्तर: D
A: कुछ NFA को n से अधिक DFA states चाहिए।
B: यह general subset bound नहीं।
C: Subsets permutations नहीं हैं।
D: हर state subset में हो या न हो सकती है।
P04. 0|10* में कौन-सी string है?
A. 00 B. 101 C. 100 D. ε
उत्तर: C
A: अलग alternative केवल एक 0 है।
B: 1 के बाद केवल zeros हैं।
C: 1 के बाद दो zeros चुनें।
D: कोई alternative ε नहीं देता।
P05. बताए c,a,b,d labels में k हटाने पर क्या मिलेगा?
A. cabd B. c|ab*d C. (c|a)bd D. ab+d
उत्तर: B
A: Alternatives concatenate नहीं होते।
B: Direct path या k पर कितने भी loops लें।
C: Direct c के बाद भी b और d अनिवार्य करता है।
D: c छूटता है और b अनिवार्य हो जाता है।
P06. NFA finals flip करने से complement क्यों गलत हो सकता है?
A. NFA infinite input पढ़ते हैं B. Existential acceptance उलटने से universal rejection नहीं बनता C. NFA में final states नहीं हो सकतीं D. हर NFA ε accept करता है
उत्तर: B
A: यहाँ inputs finite हैं।
B: एक word के final तथा nonfinal दोनों endpoints हो सकते हैं।
C: Final states NFA definition का भाग हैं।
D: ε acceptance reachable finals पर निर्भर है।
स्रोत और दायरा
यह 2026 course के बताए भाग का पाठ है, पूरे Theory of Computation syllabus की समाप्ति नहीं। सभी गणनात्मक उदाहरण और प्रश्न मौलिक हैं। 2027 की पूर्णता का दावा नहीं।
प्रगति सहेजने के लिए साइन इन करें। साइन इन