यह वीडियो थ्योरी ऑफ कंप्यूटेशन (TOC) के संपूर्ण पाठ्यक्रम को सेमेस्टर परीक्षा के दृष्टिकोण से कवर करता है, जिसमें मूल अवधारणाओं से लेकर ट्यूरिंग मशीन तक के सभी महत्वपूर्ण विषय शामिल हैं।
परिचय और सिलेबस ⏱ 0:00
•वीडियो में संपूर्ण थ्योरी ऑफ कंप्यूटेशन (TOC) को सेमेस्टर परीक्षा के दृष्टिकोण से पढ़ाया गया है।•यह सामग्री विभिन्न कॉलेजों और विश्वविद्यालयों के पाठ्यक्रम के आधार पर तैयार की गई है, जो 95% से अधिक सिलेबस से मेल खाती है।•वीडियो में पाँच अध्याय (चैप्टर) शामिल हैं, तथा पेशेवर नोट्स का लिंक विवरण में दिया गया है।•प्लेसमेंट या प्रतियोगी परीक्षाओं के लिए भी यह मददगार है।मूल अवधारणाएँ: सिंबल, अल्फाबेट, स्ट्रिंग और लैंग्वेज ⏱ 3:09
•TOC कंप्यूटेशनल शक्ति, समस्या समाधान की सीमाओं और एल्गोरिदम की दक्षता का अध्ययन है।•भाषा को परिभाषित करने की चार-चरण प्रक्रिया: सिंबल → अल्फाबेट → स्ट्रिंग → लैंग्वेज।•फॉर्मल लैंग्वेज, स्ट्रिंग्स का समुच्चय (सेट) है; यह प्राकृतिक भाषा से भिन्न होती है।•TOC और फॉर्मल लैंग्वेज (टॉफल) एक ही विषय को दो दृष्टिकोणों से देखते हैं: ऑटोमेटा (मशीन) और लैंग्वेज (व्याकरण)।प्रमुख संकल्पनाएँ और परिभाषाएँ ⏱ 20:01
•सिग्मा (Σ) शक्ति k (Σ^k) उन सभी संभावित स्ट्रिंग्स का समुच्चय है जिनकी लंबाई ठीक k है; Σ^0 में केवल एप्सिलॉन (ε) (लंबाई 0 की स्ट्रिंग) शामिल है, जो खाली सेट (∅) से भिन्न है।•क्लीन क्लोज़र (Σ) सभी लंबाई (0 से अनंत तक) की सभी स्ट्रिंग्स का समुच्चय है, जो Σ के प्रतीकों से बनी होती हैं; यह ब्रह्मांडीय समुच्चय के रूप में कार्य करता है, और प्रत्येक भाषा Σ का उपसमुच्चय है। धनात्मक क्लोज़र (Σ+) Σ* के समान है, लेकिन इसमें लंबाई 0 (ε) शामिल नहीं है, केवल लंबाई 1 से शुरू होती है।•ऑटोमेटा (singular: ऑटोमेटन) मानवीय हस्तक्षेप के बिना कार्य करने वाली स्व-संचालित प्रणाली है; यह नियमों के एक समूह के अनुसार सूचना, ऊर्जा और पदार्थ को परिवर्तित और संचारित करता है।•परिमित ऑटोमेटा (Finite Automata) परिमित अवस्थाओं वाला एक मॉडल है; यह स्ट्रिंग्स में पैटर्न पहचानता है, जैसे लेक्सिकल विश्लेषण और पार्सिंग में; इसे औपचारिक रूप से पांच टुपल्स (Q, Σ, δ, q0, F) द्वारा परिभाषित किया जाता है।DFA डिज़ाइन और महत्व ⏱ 35:58
•DFA (नियतात्मक परिमित ऑटोमेटा) परिमित ऑटोमेटा का एक विशेष रूप है, जिसका अध्ययन पाठ्यक्रम में 90-95% होता है, जबकि मूर और मीली मशीनें (आउटपुट वाले) शेष 5-10% बनाती हैं। प्रत्येक वर्ष DFA डिज़ाइन पर 1-2 प्रश्न आते हैं।•DFA डिज़ाइन की चरण-दर-चरण विधि: (1) सबसे छोटी संभव स्ट्रिंग को स्वीकार करें (उदाहरण: 'abb' से शुरू होने वाली स्ट्रिंग्स के लिए 'abb' स्वीकार करें), (2) मशीन को पूर्ण बनाएं, अर्थात हर अवस्था में प्रत्येक इनपुट प्रतीक के लिए संक्रमण होना चाहिए, (3) अमान्य स्ट्रिंग्स को डेड स्टेट (dead state) में भेजें, जहां से वे बाहर नहीं निकल सकतीं और स्वीकार नहीं होतीं।डीएफए डिज़ाइन के तीन प्रकार और महत्वपूर्ण अवलोकन ⏱ 40:03
•इस खंड में तीन अलग-अलग प्रकार के डीएफए डिज़ाइन किए गए: स्टार्टिंग से शर्त (जैसे 'ab' से शुरू), एंडिंग से शर्त (जैसे 'bab' से अंत), और सबस्ट्रिंग शर्त (जैसे 'aba' कहीं भी)।•पहले प्रकार में डेड स्टेट और फाइनल स्टेट पर लूप का उपयोग किया गया, दूसरे में डेड स्टेट नहीं बनाया गया बल्कि फाइनल से वापस जाना पड़ता है, तीसरे में न तो डेड स्टेट है और न ही वापसी, केवल लूप लगाए गए।•डेड स्टेट तब उपयोगी होता है जब शर्त स्टार्टिंग में हो और एक बार विफल होने पर दोबारा संभव न हो, जबकि एंडिंग शर्त में गड़बड़ी पर वापस जाना पड़ता है, जैसे 'bab' के बाद 'a' आने पर।•सबस्ट्रिंग के मामले में 'aba' के बाद कोई भी प्रतीक आ सकता है, फाइनल स्टेट पर ही रुक सकते हैं, क्योंकि पैटर्न कहीं भी मिल सकता है।डीएफए की आधारभूत परिभाषा, अभ्यावेदन और स्वीकृति ⏱ 51:53
•डीएफए को 5-टपल (K, Σ, δ, s, F) द्वारा परिभाषित किया जाता है: K स्टेट्स का समुच्चय, Σ इनपुट प्रतीक, δ ट्रांज़िशन फ़ंक्शन, s प्रारंभिक अवस्था, F अंतिम अवस्थाएँ (शून्य या कई हो सकती हैं)।•एक भाषा रेगुलर कहलाती है यदि उसे किसी डीएफए द्वारा स्वीकार किया जा सके; यह परिभाषा आगे विस्तार से समझी जाएगी।•डीएफए का ब्लॉक डायग्राम: टेप (सेल्स में विभाजित, बाएँ और दाएँ एंड मार्कर), रीड हेडर (एक समय में एक प्रतीक पढ़ता है, दाएँ चलता है), और फाइनाइट कंट्रोल यूनिट (ट्रांज़िशन तय करती है)। यह परीक्षा में 10 अंकों का प्रश्न हो सकता है।•डीएफए का अभ्यावेदन तीन तरीकों से: ट्रांज़िशन स्टेट डायग्राम, ट्रांज़िशन टेबल, और ट्रांज़िशन आईडी (जैसे q0 पर 'a' → q1)। स्वीकृति तब होती है जब पूरी स्ट्रिंग पढ़ने के बाद अंतिम अवस्था पर हॉल्ट करें; अन्यथा अस्वीकृत।डीएफए डिज़ाइन पैटर्न: स्टार्टिंग/एंडिंग, सबस्ट्रिंग, लंबाई ⏱ 60:03
•डीएफए डिज़ाइन के लिए पहले सबसे छोटी स्वीकृत स्ट्रिंग को स्वीकार करें, फिर मशीन को पूर्ण करें (जैसे 'a' से शुरू और 'a' पर समाप्त होने वाली स्ट्रिंग के लिए सबसे छोटी 'a' है)।•'स्टार्ट्स एंड एंड्स विद ए' के लिए, 'a' पर फाइनल स्टेट में लूप, 'b' के लिए अस्थायी स्टेट, और 'a' आने पर फाइनल पर वापसी; 'b' से शुरू होने वाली स्ट्रिंग के लिए डेड स्टेट।•'स्टार्ट्स एंड एंड्स विद सेम सिम्बल' के लिए दो अलग सेक्शन (एक a के लिए, एक b के लिए), प्रत्येक में फाइनल स्टेट पर लूप, और दूसरे सिम्बल के लिए अस्थायी स्टेट; कुछ स्टेट्स को मर्ज किया जा सकता है।•'एंडिंग विद डिफरेंट सिम्बल' के लिए a से शुरू करके b पर समाप्त, और b से शुरू करके a पर समाप्त; इन्हें मर्ज नहीं करना चाहिए।•'सबस्ट्रिंग' पैटर्न में ट्रिपल ए या ट्रिपल बी कहीं भी आ सकता है, इसलिए एक बार ट्रिपल मिलने पर लूप और स्टेट मर्ज करके 6 स्टेट्स में DFA बनता है।•'लंबाई' वाले पैटर्न में, स्टेट चेंज करके लंबाई याद रखते हैं: 'लेंथ एग्जैक्टली 3' के लिए 4 स्टेट्स (q0 से q3), 'लेंथ एट मोस्ट 3' के लिए q3 पर लूप, और 'लेंथ >= 3' के लिए q3 पर लूप, 4 से अधिक लंबाई पर डेड स्टेट।DFA डिज़ाइन पैटर्न की मूल बातें ⏱ 80:05
•लंबाई 0 स्वीकार्य होने पर प्रारंभिक अवस्था को अंतिम बनाया जाता है।•अलग-अलग लंबाई (1, 2, 3) के लिए राज्यों की संख्या बढ़ती जाती है, और अनावश्यक लंबाई के लिए डेड स्टेट बनाया जाता है।•"लंबाई कम से कम 3" जैसे पैटर्न में लूप का उपयोग करके आगे की सभी लंबाई स्वीकार की जा सकती है।विशिष्ट प्रतीक गिनती पैटर्न ⏱ 82:38
•"संख्या a बिल्कुल 2" के लिए: पहले 2 a पर राज्य बदलें, फिर b पर लूप, अतिरिक्त a के लिए डेड स्टेट।•"संख्या a कम से कम 2" में 2 a के बाद a और b दोनों पर लूप।•"संख्या a अधिकतम 2" में प्रारंभिक अवस्था अंतिम होगी, 2 से अधिक a पर डेड स्टेट।मॉड्यूलो (शेष) पैटर्न ⏱ 85:10
•"लंबाई 0 mod 3" जैसे पैटर्न के लिए, शेष 0, 1, 2 के लिए 3 राज्य बनाएं; इनपुट प्रतीक पर राज्य बदलें, और वांछित शेष वाले राज्य को अंतिम बनाएं।•"लंबाई 1 mod 4" के लिए 4 राज्य चाहिए; साइकिल चलाकर सभी स्वीकार्य स्ट्रिंग्स (लंबाई 1, 5, 9, 13, ...) स्वीकार होंगी।•"संख्या a 0 mod 2" जैसे पैटर्न में केवल a पर राज्य बदलें, b पर लूप, और शेष 0 वाले राज्य को अंतिम बनाएं।दूसरा प्रतीक पैटर्न ⏱ 90:22
•"दूसरा प्रतीक बाएं से a" के लिए: पहला प्रतीक कुछ भी, दूसरा a होना चाहिए; उसके बाद लूप।•"दूसरा अंतिम प्रतीक दाएं से b" के लिए: 2^2 = 4 राज्य चाहिए; ट्रिक के अनुसार, स्वीकार्य प्रतीक (b) को दूसरे कॉलम में रखें, अस्वीकार्य (a) को पहले कॉलम में, और निचले आधे राज्यों को अंतिम बनाएं।सम-विषम संयुक्त पैटर्न (ग्रिड विधि) ⏱ 97:03
•"a की संख्या सम और b की संख्या सम" जैसे पैटर्न के लिए, क्षैतिज रूप से a की समता और लंबवत रूप से b की समता को दर्शाते हुए 2x2 ग्रिड बनाएं।•a पर क्षैतिज राज्य बदलें, b पर लंबवत राज्य बदलें।•"a सम या b सम" (या) के लिए, केवल वही राज्य गैर-अंतिम होगा जहां दोनों विषम हों।डीएफए से एनएफए तक: अवधारणा और निर्माण ⏱ 100:06
•डीएफए में हर स्टेट पर हर इनपुट के लिए एक ही यूनिक मूव होता है, लेकिन एनएफए में एक स्टेट पर एक सिंबल के लिए कई मूव्स या कोई मूव नहीं हो सकता।•एनएफए का उद्देश्य: डीएफए बनाना कठिन हो तो पहले एनएफए बनाएं, फिर उसे डीएफए में बदलें; एनएफए डिज़ाइन करना आसान है, लेकिन वे सीधे इंप्लीमेंट नहीं होते।•एनएफए में स्वीकृति की परिभाषा: स्ट्रिंग स्वीकार होती है यदि कम से कम एक ऐसा मूव हो जो इनिशियल स्टेट से शुरू होकर फाइनल स्टेट पर समाप्त हो; हर मूव स्वीकार नहीं होता, लेकिन कोई भी इनवैलिड स्ट्रिंग स्वीकार नहीं हो सकती।•एनएफए के निर्माण के उदाहरण: "स्टार्टिंग विद", "एंडिंग विद", "सबस्ट्रिंग", और "स्टार्टिंग एंड एंडिंग विद सेम सिंबल" पैटर्न के लिए सीधे लूप और स्ट्रेट लाइन से मशीन बनाई जा सकती है।एनएफए डिज़ाइन और डीएफए से तुलना ⏱ 120:06
•इस सेगमेंट में शुरुआत में बताया गया कि कैसे स्टार्टिंग और एंडिंग सिंबल अलग-अलग होने वाली स्ट्रिंग्स के लिए एनएफए आसानी से डिज़ाइन किया जा सकता है। ट्रिपल ए या ट्रिपल बी जैसे पैटर्न के लिए भी सिंपल एनएफए बनाए जा सकते हैं।•डीएफए की तुलना में एनएफए अधिक लचीला है, और हर डीएफए एक एनएफए है, लेकिन हर एनएफए डीएफए नहीं है। एनएफए को डीएफए में बदला जा सकता है, और दोनों की भाषा स्वीकार करने की शक्ति समान है।•एनएफए में हर स्टेट पर हर सिंबल के लिए ट्रांजीशन परिभाषित करना ज़रूरी नहीं है, और एक स्टेट से कई ट्रांजीशन हो सकते हैं। एनएफए सिर्फ वैध स्ट्रिंग्स पर प्रतिक्रिया करता है, डेड स्टेट का कोई कॉन्सेप्ट नहीं होता।एनएफए से डीएफए में रूपांतरण (सबसेट कंस्ट्रक्शन) ⏱ 125:41
•एनएफए को डीएफए में बदलने की प्रक्रिया को सबसेट कंस्ट्रक्शन कहते हैं। पहले एनएफए की ट्रांजीशन टेबल बनाई जाती है, फिर उसी टेबल को डीएफए के हिसाब से फिर से लिखा जाता है, जहाँ एक से अधिक स्टेट्स को एक सिंगल स्टेट के रूप में मिलाया जाता है।•रूपांतरण के दौरान इनिशियल स्टेट वही रहती है, और नए स्टेट्स तब बनते हैं जब किसी सिंबल के लिए कई स्टेट्स का यूनियन होता है। डीएफए में हर स्टेट के लिए हर सिंबल पर ट्रांजीशन होना चाहिए, इसलिए डेड स्टेट भी बनाई जा सकती है।•फाइनल स्टेट वे होंगी जिनमें एनएफए की फाइनल स्टेट शामिल हो। उदाहरण के लिए, यदि एनएफए की फाइनल स्टेट q2 है, तो डीएफए की सभी स्टेट्स जिनमें q2 शामिल है, फाइनल होंगी।•यदि एनएफए में n स्टेट्स हैं, तो डीएफए में स्टेट्स की संख्या 1 से लेकर 2^n के बीच हो सकती है। उदाहरण के लिए, यदि एनएफए में 5 स्टेट्स हैं, तो डीएफए में अधिकतम 32 स्टेट्स हो सकते हैं।एनएफए और नल ट्रांजीशन, नल क्लोजर, और एनएफए-टू-डीएफए रूपांतरण ⏱ 140:08
•एनएफए में नल (ε) ट्रांजीशन जोड़ने से मशीन की शक्ति नहीं बदलती; बिना इनपुट सिंबल कंज्यूम किए स्टेट बदल सकते हैं।•नल क्लोजर: किसी स्टेट से केवल नल ट्रांजीशन के माध्यम से सभी पहुंच योग्य स्टेट्स; हर स्टेट का नल क्लोजर स्वयं को शामिल करता है।•एनएफए को डीएफए में बदलते समय स्टेट्स की संख्या और इनपुट सिंबल अपरिवर्तित रहते हैं; नए डीएफए के अंतिम स्टेट्स वे हैं जिनके नल क्लोजर में मूल एनएफए के अंतिम स्टेट मौजूद हैं।•उदाहरण: q0 से q7 तक के स्टेट्स वाले एनएफए में, q5 और q6 भी अंतिम बन जाते हैं क्योंकि उनके नल क्लोजर में q7 है।मूर और मिली मशीनें: परिभाषा, विशेषताएँ, और आउटपुट तंत्र ⏱ 153:10
•मूर और मिली मशीनें डीएफए के विशेष प्रकार हैं जो भाषा स्वीकार करने के बजाय आउटपुट उत्पन्न करती हैं।•इनमें कोई अंतिम स्टेट नहीं होता, इसलिए डेड स्टेट की अवधारणा भी अनुपस्थित होती है।•दोनों की शक्ति बराबर है; मूर पहले आई, मिली बाद में अधिक अनुकूलित रूप में।•मूर मशीन में आउटपुट केवल वर्तमान स्टेट पर निर्भर करता है; इसे 6-टुपल (Q, Σ, Δ, δ, q0, λ) द्वारा परिभाषित किया जाता है, जिसमें Δ आउटपुट अल्फाबेट है और λ आउटपुट फंक्शन है।•मूर मशीन आउटपुट स्टार्ट होते ही (यानी, नल स्ट्रिंग पर) उत्पन्न करती है; जैसे-जैसे हर स्टेट पर पहुँचते हैं, वहाँ का आउटपुट मिलता है।मूर और मीली मशीन का सारांश ⏱ 160:11
•मूर मशीन में आउटपुट स्टेट से जुड़ा होता है, जिससे इनपुट की लंबाई n होने पर आउटपुट की लंबाई n+1 होती है और यह null string पर भी प्रतिक्रिया देती है।•मीली मशीन में आउटपुट ट्रांज़ीशन से जुड़ा होता है, जिससे इनपुट और आउटपुट की लंबाई समान (n) रहती है और यह null string पर प्रतिक्रिया नहीं देती।•मूर से मीली में रूपांतरण सरल है: जिस स्टेट पर पहुँचते हैं उसका आउटपुट ट्रांज़ीशन पर लिख देते हैं, स्टेट्स की संख्या समान रहती है।•मीली से मूर में रूपांतरण में स्टेट्स की संख्या बढ़ सकती है; यदि किसी स्टेट के अलग-अलग आउटपुट हैं, तो उसे आउटपुट के आधार पर दो स्टेट्स में विभाजित करना पड़ता है।मूर और मीली मशीन का सारांश ⏱ 180:15
•मूर को मीली में बदलना आसान है, जबकि मीली से मूर में बदलना थोड़ा तार्किक है।•मूर मशीन में आउटपुट लंबाई n+1 है जबकि मीली में n है; मूर null स्ट्रिंग पर प्रतिक्रिया देता है, मीली नहीं देता।•आउटपुट स्ट्रिंग की आवश्यकता होती है, स्वीकृति की नहीं; डेड स्टेट की कोई अवधारणा नहीं; दोनों नियतात्मक हैं।DFA का न्यूनीकरण ⏱ 181:48
•DFA न्यूनीकरण का लक्ष्य राज्यों की संख्या कम करना है, लेकिन भाषा स्वीकृति क्षमता बदलनी नहीं चाहिए।•किसी भी नियमित भाषा के लिए न्यूनीकरण के बाद एक अद्वितीय DFA प्राप्त होता है।•अनुत्पादक अवस्थाएँ हटाई जाती हैं: मृत अवस्था (जिससे अंतिम स्थिति तक नहीं पहुँच सकते), अगम्य अवस्था (प्रारंभिक अवस्था से नहीं पहुँच सकते), और समतुल्य अवस्थाएँ (जो समान व्यवहार करती हैं)।•समतुल्य अवस्थाओं की पहचान के लिए, उन्हें समूहों में विभाजित करें और प्रत्येक इनपुट प्रतीक पर उनके संक्रमणों की जाँच करें; यदि वे एक ही समूह में जाते हैं तो वे समतुल्य हैं।रेगुलर एक्सप्रेशन का परिचय और महत्व ⏱ 201:49
•रेगुलर एक्सप्रेशन भाषा को दर्शाने की एक विधि है, जो फाइनाइट ऑटोमेटा और रेगुलर ग्रामर के समान शक्ति रखती है।•रेगुलर लैंग्वेज की दो परिभाषाएँ: यदि भाषा फाइनाइट ऑटोमेटा द्वारा स्वीकार की जाती है, या रेगुलर ग्रामर द्वारा उत्पन्न होती है, तो वह रेगुलर है। एक्सप्रेशन भी इसे दर्शाता है।•रेगुलर एक्सप्रेशन केवल रेगुलर लैंग्वेज के डोमेन में होते हैं, PDA या ट्यूरिंग मशीन में नहीं।बुनियादी संक्रियाएँ, उदाहरण और समानता ⏱ 207:22
•तीन मौलिक अभिव्यक्तियाँ: कोई प्रतीक (जैसे a), एप्सिलॉन (ε), और फाई (∅)। इन्हें प्रिमिटिव रेगुलर एक्सप्रेशन कहते हैं।•ऑपरेटर: संयोजन (डॉट), यूनियन/चॉइस (+), कीन क्लोजर (*), पॉज़िटिव क्लोजर (+) — प्राथमिकता: ब्रैकेट > क्लोजर > संयोजन > यूनियन।•दो रेगुलर एक्सप्रेशन समान कहलाते हैं यदि वे समान भाषा दर्शाते हैं; एक भाषा के लिए कई एक्सप्रेशन संभव हैं, पर एक एक्सप्रेशन केवल एक भाषा दर्शाता है।•उदाहरण: 'a+b' का अर्थ है a या b की पसंद; '(a+b)*' सभी संभव स्ट्रिंग्स उत्पन्न करता है; लंबाई 3 के लिए '(a+b)^3' का अर्थ है तीन बार संयोजन।रेगुलर एक्सप्रेशन: पैटर्न और गुण ⏱ 220:18
•इस खंड में रेगुलर एक्सप्रेशन (RE) की मदद से विभिन्न पैटर्न जनरेट करने की प्रक्रिया समझाई गई, जैसे कि लंबाई 0 से 3 तक के स्ट्रिंग्स, और बाद में (a + b)* जैसे संकेतन से किसी भी लंबाई के स्ट्रिंग्स।•विशेष पैटर्न जैसे कि "दूसरा प्रतीक b होना चाहिए" को (a + b) b (a + b) के रूप में लिखा गया, और "दाईं ओर से चौथा प्रतीक a होना चाहिए" को (a + b) a (a + b)^3 के रूप में।•0 mod 3, 0 mod 4 जैसे मॉड्यूलर पैटर्न को (a + b)^3 और (a + b)^4 (a + b)^3 जैसे एक्सप्रेशन से कैप्चर किया गया। a की संख्या 3 से विभाज्य होने के पैटर्न के लिए b (a b a b a b)* जैसा एक्सप्रेशन बनाया गया।•रेगुलर एक्सप्रेशन के गुण: क्लोज़र (यूनियन, कॉन्कैटेनेशन, क्लीन स्टार, पॉज़िटिव क्लोज़र के अंतर्गत), साहचर्य (यूनियन और कॉन्कैटेनेशन के लिए), तत्समक (ε कॉन्कैटेनेशन के लिए, ∅ यूनियन के लिए), क्रम-विनिमय (यूनियन के लिए लागू, कॉन्कैटेनेशन के लिए नहीं), और वितरण (कॉन्कैटेनेशन यूनियन पर वितरित होता है, लेकिन यूनियन कॉन्कैटेनेशन पर नहीं)।फाइनाइट ऑटोमेटा से रेगुलर एक्सप्रेशन में रूपांतरण ⏱ 236:56
•इस खंड में फाइनाइट ऑटोमेटा (FA) से रेगुलर एक्सप्रेशन बनाने की विधि पर चर्चा की गई, जिसमें आर्डन के प्रमेय का उल्लेख है।•सरल उदाहरणों के माध्यम से दिखाया गया कि कैसे FA की संरचना से सीधे RE लिखा जा सकता है, जैसे कि प्रारंभिक अवस्था से अंतिम अवस्था तक के पथों को मिलाकर।रेगुलर एक्सप्रेशन और आर्डन थ्योरम की मुख्य बातें ⏱ 240:18
•मशीन से एक्सप्रेशन बनाते समय साइकिलों के बीच कोई क्रम नहीं होता, इसलिए 'ए*' और 'बीसी' को अलग-अलग चॉइस के रूप में लिखें, कॉन्कैटिनेट न करें।•ट्रांज़िशन ग्राफ में स्ट्रिंग्स या एक्सप्रेशन लिखने की अनुमति है, लेकिन अस्थायी रूप से हम सिर्फ पैटर्न लिखना सीख रहे हैं।•आर्डन थ्योरम केवल DFA पर काम करता है, NFA या ε-NFA पर नहीं।•हर स्टेट के लिए समीकरण बनाएं: r = q + rp, और समाधान r = qp* होता है। फिर इसे आगे के समीकरणों में प्रतिस्थापित करें।आर्डन थ्योरम का अभ्यास और ट्रांज़िशन ग्राफ ⏱ 260:18
•आर्डन थ्योरम से DFA/NFA के लिए समीकरण हल करके रेगुलर एक्सप्रेशन निकाला गया; उदाहरण में a और b पर आधारित मशीन के लिए अंतिम समाधान a b (a + b) आया।•ट्रांज़िशन ग्राफ NFA का सामान्यीकरण है, जिसमें एक से अधिक प्रारंभिक अवस्थाएँ और एज पर स्ट्रिंग लिखी जा सकती हैं, लेकिन इसकी शक्ति DFA/NFA के समान है; इसे null transition से एकल प्रारंभिक अवस्था में बदला जा सकता है।क्लोज़र प्रॉपर्टी, पिजनहोल सिद्धांत और पंपिंग लेम्मा ⏱ 268:50
•क्लोज़र प्रॉपर्टी: रेगुलर भाषाएँ यूनियन, कॉन्केटनेशन, क्लीन स्टार, कॉम्प्लीमेंट, रिवर्स, प्रीफिक्स, सफ़िक्स, इंटरसेक्शन आदि के अंतर्गत बंद हैं; प्रूफ रेगुलर एक्सप्रेशन या NFA की मदद से किया जा सकता है।•पिजनहोल सिद्धांत: यदि n वस्तुओं को m कंटेनरों में रखा जाए और n > m, तो कम से कम एक कंटेनर में एक से अधिक वस्तु होंगी; यह गणित और कंप्यूटर विज्ञान में महत्वपूर्ण है।•पंपिंग लेम्मा: यह सिद्ध करने के लिए प्रयोग होता है कि कोई भाषा नियमित नहीं है; यदि कोई भाषा नियमित है तो उसे पंपिंग लेम्मा संतुष्ट करना चाहिए, लेकिन इसका विलोम सत्य नहीं है; उदाहरण: a^n b^n भाषा के लिए नियमित एक्सप्रेशन नहीं बनाया जा सकता, इसलिए यह अनियमित है।पम्पिंग लेम्मा का उपयोग और गैर-नियमित भाषा का प्रमाण ⏱ 280:18
•पम्पिंग लेम्मा का उपयोग करते हुए, स्ट्रिंग को u, v, w में विभाजित करके v को बार-बार दोहराने पर, यदि परिणामी स्ट्रिंग भाषा में नहीं है, तो भाषा गैर-नियमित सिद्ध होती है।•शर्तें: |uv| ≤ n, |v| ≥ 1, और सभी i ≥ 0 के लिए uv^i w भाषा में होना चाहिए।•उदाहरण: a^m b^n (m < n) गैर-नियमित है, क्योंकि तुलना की आवश्यकता है, और परिमित ऑटोमेटा में स्मृति नहीं होती।•नियमित भाषा के लिए पम्पिंग लेम्मा विफल होने पर वह गैर-नियमित सिद्ध होती है।निर्णायकता (Decidability) और नियमित भाषाओं के गुण ⏱ 280:18
•समस्या दो प्रकार की होती हैं: हल करने योग्य (solvable) और अनसुलझी (unsolvable); हल करने योग्य समस्याओं के लिए एल्गोरिदम या प्रमाण होता है।•निर्णायक (decidable) का अर्थ है कि समस्या को हल करने में लगने वाले समय का अनुमान लगाया जा सकता है; अनिर्णायक (undecidable) में ऐसा नहीं होता।•नियमित भाषाओं के लिए छह गुण निर्णायक हैं: रिक्तता (emptiness), गैर-रिक्तता (non-emptiness), परिमितता (finiteness), अनंतता (infiniteness), सदस्यता (membership), और समानता (equality)।•इन्हें परिमित ऑटोमेटा के अध्ययन से निर्धारित किया जा सकता है, जैसे अप्राप्य अवस्थाओं को हटाकर अंतिम अवस्था की जाँच करना।व्याकरण का परिचय और औपचारिक परिभाषा ⏱ 280:18
•व्याकरण (grammar) भाषा का प्रतिनिधित्व करने का एक पैटर्न है, जैसे नियमित अभिव्यक्ति या परिमित ऑटोमेटा।•उदाहरण: उत्पादन नियम S → 0S1 और S → ε से भाषा {0^n 1^n | n ≥ 0} उत्पन्न होती है।•औपचारिक व्याकरण चार टुपल (V, Σ, P, S) से परिभाषित होता है: V (चर), Σ (टर्मिनल), P (उत्पादन नियम), और S (प्रारंभ प्रतीक)।•टर्मिनल (जैसे 0, 1) अंतिम प्रतीक हैं; गैर-टर्मिनल (जैसे S) को प्रतिस्थापित किया जा सकता है, और प्रारंभ प्रतीक S से शुरू करके व्युत्पत्ति की जाती है।ग्रामर की मूल अवधारणाएं और भाषा निर्माण ⏱ 300:19
•प्रोडक्शन रूल अल्फा → बीटा होता है, बायाँ पक्ष (अल्फा) का दायें पक्ष (बीटा) से प्रतिस्थापन होता है; बायें पक्ष में कम से कम एक नॉन-टर्मिनल होना आवश्यक है, दायाँ पक्ष कोई भी स्ट्रिंग हो सकता है (टर्मिनल, नॉन-टर्मिनल, या दोनों का संयोजन)।•ग्रामर चार टपल (V, Σ, P, S) से परिभाषित होता है: V नॉन-टर्मिनल (कैपिटल सिंबल), Σ टर्मिनल (स्मॉल केस), P प्रोडक्शन रूल (अल्फा→बीटा), और S स्टार्ट सिंबल (एक विशेष नॉन-टर्मिनल, हर ग्रामर में एक ही होता है)।•टर्मिनल और नॉन-टर्मिनल के बीच कोई उभयनिष्ठ (इंटरसेक्शन) नहीं होता; भाषा की स्ट्रिंग्स केवल टर्मिनल से बनती हैं, नॉन-टर्मिनल माध्यम हैं।•ग्रामर एक 'जनरेटर' है (मशीन 'एक्सेप्टर' की तरह); यह स्टार्ट सिंबल से शुरू करके प्रोडक्शन लागू करते हुए स्ट्रिंग्स जनरेट करता है। दो ग्रामर तभी बराबर माने जाते हैं जब वे समान भाषा जनरेट करें (टर्मिनल/नॉन-टर्मिनल की संख्या मायने नहीं रखती)।ग्रामर उदाहरण और चॉम्स्की पदानुक्रम का परिचय ⏱ 306:23
•ग्रामर समझने के लिए छोटे उदाहरण बनाकर प्रोडक्शन को बार-बार लागू करना चाहिए; विभिन्न केस से पैटर्न की पहचान होती है, जैसे a^n b^n, a^n b^m (जहाँ n≥0, m≥1), a^n b^n a^n जैसी भाषाएँ बनती हैं।•चॉम्स्की पदानुक्रम (Chomsky Hierarchy) में 4 प्रकार के ग्रामर होते हैं: टाइप 0 (फ्री/अनरेस्ट्रिक्टेड), टाइप 1 (कॉन्टेक्स्ट-सेंसिटिव), टाइप 2 (कॉन्टेक्स्ट-फ्री), और टाइप 3 (रेगुलर)।•टाइप 0 सबसे शक्तिशाली होता है (रिकर्सिव एन्यूमरेबल भाषा, ट्यूरिंग मशीन द्वारा स्वीकृत); टाइप 1 को लीनियर-बाउंड ऑटोमेटा, टाइप 2 को पुशडाउन ऑटोमेटा (PDA), और टाइप 3 को फाइनाइट ऑटोमेटा (FA) द्वारा स्वीकार किया जाता है।•इस सेगमेंट में टाइप 0 (ग्रामर) और टाइप 2 (कॉन्टेक्स्ट-फ्री) पर ध्यान दिया जाएगा; टाइप 1 सिलेबस में शामिल नहीं है। नोम चॉम्स्की (जन्म 1930 के आसपास) भाषा सिद्धांत के अलावा 150 से अधिक पुस्तकों के लेखक हैं, जिनमें राजनीति, मीडिया, और उदारवाद जैसे विषय शामिल हैं।चॉम्स्की पदानुक्रम और व्याकरण के प्रकार ⏱ 320:21
•टाइप 0 (अप्रतिबंधित) व्याकरण: कोई प्रतिबंध नहीं; केवल बायीं ओर कम से कम एक गैर-टर्मिनल होना चाहिए।•टाइप 1 (संदर्भ-संवेदनशील): लंबाई बढ़ाने वाला/गैर-संकुचनशील; अल्फा की लंबाई ≤ बीटा की लंबाई; अपवाद: S → ε अनुमत।•टाइप 2 (संदर्भ-मुक्त): बायीं ओर एकल गैर-टर्मिनल; पुशडाउन ऑटोमेटा द्वारा स्वीकृत।•टाइप 3 (नियमित): बायीं ओर एकल गैर-टर्मिनल; दायीं ओर एक गैर-टर्मिनल (अत्यंत बाएँ या दाएँ स्थिति में) और कोई भी टर्मिनल; अन्यथा नियमित नहीं।नियमित व्याकरण से व्यंजक और मशीन ⏱ 332:47
•नियमित व्याकरण से नियमित व्यंजक लिखने की विधि: अवयवों को तोड़कर चरणबद्ध रूप से व्यंजक बनाना।•उदाहरण: A → 0A | 1A | 0 | 1 के लिए व्यंजक (0+1)* (0+1) या समतुल्य।•व्याकरण से सीधे मशीन बनाने की विधि: प्रारंभ स्थिति से शुरू कर, प्रत्येक उत्पादन के लिए संक्रमण बनाना; अंतिम स्थिति तक पहुँचना।•व्याकरण, व्यंजक और मशीन तीनों एक ही भाषा को दर्शाते हैं; किसी भी एक से दूसरे में परिवर्तन संभव है।रेगुलर ग्रामर से FA निर्माण और रिवर्स प्रक्रिया ⏱ 340:22
•राइट रेगुलर ग्रामर से सीधे फाइनाइट ऑटोमेटा (FA) बनाया जा सकता है; लेफ्ट और राइट रेगुलर की शक्ति समान है, इसलिए लेफ्ट रेगुलर को भी राइट में बदला जा सकता है।•FA से ग्रामर बनाना: प्रत्येक स्टेट के आउटगोइंग ट्रांज़िशन को प्रोडक्शन में बदलें; फाइनल स्टेट के लिए ε-प्रोडक्शन जोड़ें।•रेगुलर एक्सप्रेशन, रेगुलर ग्रामर, FA, और रेगुलर लैंग्वेज — ये सभी एक ही काम के अलग-अलग तरीके हैं; K4 पूर्ण ग्राफ की तरह सभी आपस में जुड़े हैं।डेरिवेशन, सेंटेंशल फॉर्म, और एम्बिग्युटी ⏱ 346:32
•डेरिवेशन: स्टार्ट सिंबल से शुरू करके प्रोडक्शन का उपयोग करते हुए स्ट्रिंग तक पहुंचना; इसका ग्राफिकल रूप डेरिवेशन ट्री (पार्स ट्री/सिंटेक्स ट्री) कहलाता है।•सेंटेंशल फॉर्म: स्टार्ट सिंबल से अंतिम टर्मिनल स्ट्रिंग तक के बीच के सभी मध्यवर्ती रूप।•लेफ्ट मोस्ट डेरिवेशन: हर स्टेप पर सबसे बायां नॉन-टर्मिनल एक्सपैंड करना; राइट मोस्ट डेरिवेशन में सबसे दायां नॉन-टर्मिनल एक्सपैंड होता है।•एम्बिग्युटी: यदि किसी स्ट्रिंग के लिए एक से अधिक डेरिवेशन ट्री हों, तो ग्रामर एम्बिग्युस है; अन-एम्बिग्युस ग्रामर में हमेशा एक ही ट्री बनता है, चाहे लेफ्ट या राइट मोस्ट डेरिवेशन अपनाएँ।एम्बिग्युटी की पहचान और सरलीकरण ⏱ 350:42
•एम्बिग्युटी टाइप 2 (कॉन्टेक्स्ट-फ्री) ग्रामर में होती है; टाइप 3 (रेगुलर) ग्रामर कभी एम्बिग्युस नहीं होता।•चेतावनी: एम्बिग्युटी ग्रामर की समस्या है, लैंग्वेज की नहीं; कुछ लैंग्वेजेस इन्हेरेंटली एम्बिग्युस होती हैं — उनके लिए कोई अन-एम्बिग्युस ग्रामर नहीं लिखा जा सकता (उदाहरण: रोहित पारेख ने 1961 में प्रमाणित किया)।•कोई एल्गोरिदम नहीं है जो यह बता सके कि दिया गया CFG एम्बिग्युस है या नहीं — यह एक अनडिसाइडेड प्रॉब्लम है।•ट्रिक: यदि ग्रामर में किसी नॉन-टर्मिनल के लिए लेफ्ट और राइट रिकर्सन दोनों हों, तो ग्रामर निश्चित रूप से एम्बिग्युस है।•सरलीकरण का उद्देश्य: यूजलेस सिंबल, यूनिट प्रोडक्शन, और नल प्रोडक्शन हटाकर ग्रामर को कंपाइलर-फ्रेंडली और कुशल बनाना।व्याकरण सरलीकरण: नल, इकाई और अनुपयोगी प्रतीक ⏱ 360:22
•नल प्रोडक्शन को हटाने का तर्क: कंपाइलर को नल प्रोडक्शन पसंद नहीं है, क्योंकि जब डेरिवेशन के दौरान कोई पैटर्न अचानक गायब हो जाता है, तो फॉलो फंक्शन का उपयोग करना पड़ता है।•नल प्रोडक्शन हटाते समय, प्रत्येक प्रोडक्शन के दाईं ओर नॉन-टर्मिनल को एप्सिलॉन से बदलकर नए प्रोडक्शन जोड़ने पड़ते हैं।•यदि भाषा में एप्सिलॉन स्ट्रिंग है, तो एक नया स्टार्ट सिंबल जोड़कर एप्सिलॉन को यूनियन के रूप में प्रस्तुत किया जाता है, ताकि मूल व्याकरण में एप्सिलॉन प्रवेश न करे।•यूनिट प्रोडक्शन (एकल नॉन-टर्मिनल से एकल नॉन-टर्मिनल) को समाप्त करने के लिए, सीधे नॉन-टर्मिनल को उसके विकल्पों से बदलें।•अनुपयोगी प्रतीक: वे प्रतीक जो स्टार्ट सिंबल से अप्राप्य हैं (अनरीचेबल) या जिनसे टर्मिनल स्ट्रिंग नहीं बनती (डेड) हटा दिए जाते हैं।चोम्स्की नॉर्मल फॉर्म (CNF) ⏱ 375:17
•सामान्य रूप से, व्याकरण को कंपाइलर-अनुकूल बनाने के लिए सामान्यीकृत किया जाता है; पहले सरलीकरण, फिर सामान्यीकरण।•CNF में प्रत्येक प्रोडक्शन या तो दो नॉन-टर्मिनल या एक टर्मिनल के रूप में होना चाहिए।•CNF में बदलने के लिए, नए नॉन-टर्मिनल जोड़े जाते हैं (जैसे A के लिए α, B के लिए β) और मिश्रित प्रोडक्शन को अलग किया जाता है।सीएनएफ से स्ट्रिंग डिराइवेशन और ग्रेब नॉर्मल फॉर्म ⏱ 380:24
•यदि ग्रामर सीएनएफ में है और लंबाई n की स्ट्रिंग डिराइव करते हैं, तो ठीक 2n−1 सेंटेंशल फॉर्म्स (स्टेप्स) लगते हैं।•ग्रेब नॉर्मल फॉर्म (जीएनएफ) में हर प्रोडक्शन एक नॉन-टर्मिनल से एक टर्मिनल के बाद नॉन-टर्मिनल्स की स्ट्रिंग देता है; सीएनएफ से अधिक लिबरल।•जीएनएफ में लंबाई n की स्ट्रिंग के लिए ठीक n सेंटेंशल फॉर्म्स चाहिए, क्योंकि हर स्टेप एक टर्मिनल जनरेट करता है।•जीएनएफ में कन्वर्ट करते समय उदाहरण से दिखाया कि नए नॉन-टर्मिनल लेकर प्रोडक्शन्स को मॉडिफाई किया जाता है।पुश डाउन ऑटोमेटा (पीडीए) का परिचय और 7-टपल परिभाषा ⏱ 387:34
•पीडीए, फाइनाइट ऑटोमेटा (एफए) + स्टैक है; इसका उपयोग कॉन्टेक्स्ट-फ्री लैंग्वेज (सीएफएल) स्वीकार करने के लिए।•नॉन-डिटरमिनिस्टिक पीडीए की शक्ति डिटरमिनिस्टिक पीडीए से अधिक है (एफए या ट्यूरिंग मशीन के विपरीत)।•सीएफएल दो श्रेणियाँ: डीसीएफएल (डिटरमिनिस्टिक पीडीए द्वारा स्वीकृत) और सीएफएल (नॉन-डिटरमिनिस्टिक)।•पीडीए की 7-टपल परिभाषा: (Q, Σ, Γ, δ, q0, Z0, F) — इसमें Γ (टा) स्टैक सिंबल्स का सेट, Z0 स्पेशल स्टैक सिंबल (अंडरफ्लो पहचानने के लिए), और δ में तीन इनपुट (स्टेट, इनपुट, स्टैक-टॉप) लेकर स्टेट और स्टैक-टॉप रिप्लेसमेंट (पुश/पॉप/स्किप) देता है।•ट्रांज़िशन रिप्रेजेंटेशन: पुश में स्टैक-टॉप के ऊपर नया सिंबल जोड़ते हैं, पॉप में नया स्टैक-टॉप ε (एलन), स्किप में वही स्टैक-टॉप बना रहता है।पुश डाउन ऑटोमेटा की स्वीकृति विधियाँ ⏱ 400:24
•पीडीए में स्वीकृति दो तरह से होती है: फाइनल स्टेट द्वारा और एम्टी स्टैक द्वारा। दोनों की शक्ति समान है।•फाइनल स्टेट स्वीकृति में, जब टेप खत्म हो और स्टैक में केवल z0 बचे, तो उसे स्किप करके फाइनल स्टेट में जाते हैं।•एम्टी स्टैक स्वीकृति में, z0 को पॉप करके स्टैक खाली कर देते हैं, जो काम की समाप्ति का संकेत है।पीडीए के विभिन्न उदाहरण और पैटर्न ⏱ 402:27
•उदाहरण: a^n b^n को पीडीए से स्वीकार किया गया, जिसमें a पुश करते हैं और b आने पर पॉप करते हैं।•a^n b^(2n) के लिए, हर a के लिए दो b होते हैं, इसलिए पहले b पर स्किप करते हैं और दूसरे पर पॉप करते हैं। इसी प्रकार a^n b^(3n) के लिए पहले दो b स्किप करके तीसरे पर पॉप करते हैं।•wcw^r पैटर्न (पैलिंड्रोम) के लिए, पहले w को पुश करते हैं, c पर कुछ नहीं करते, और फिर w^r से मिलान करके पॉप करते हैं।•ऐसी भाषा जहाँ a और b की संख्या बराबर हो (किसी भी क्रम में), वहाँ जब टॉप सिंबल इनपुट से मेल खाता है तो पॉप करते हैं, वरना पुश करते हैं।नॉन-डिटरमिनिस्टिक पीडीए की शक्ति ⏱ 415:56
•नॉन-डिटरमिनिस्टिक पीडीए, डिटरमिनिस्टिक पीडीए से अधिक शक्तिशाली है।•ww^r जैसे पैटर्न के लिए, जहाँ बीच में कोई स्पष्ट विभाजक नहीं है, नॉन-डिटरमिनिस्टिक पीडीए में अनुमान लगाकर काम करते हैं।•यह सिद्ध करता है कि कुछ भाषाओं के लिए नॉन-डिटरमिनिस्टिक पीडीए संभव है, लेकिन डिटरमिनिस्टिक पीडीए नहीं, इसलिए नॉन-डिटरमिनिस्टिक की शक्ति अधिक है।पीडीए के गुण और अगले विषय ⏱ 419:58
•रेगुलर भाषाओं में पढ़े गए निर्णायक गुण और क्लोजर प्रॉपर्टीज यहाँ भी लागू होंगे, लेकिन कुछ बदलाव के साथ।•अगले भाग में हम इन गुणों पर विस्तार से चर्चा करेंगे।CFG गुणों का निर्णय ⏱ 420:24
•सीएफजी गुणों को पीडीए मशीन मॉडल के बजाय ग्रामर का उपयोग करके सिद्ध किया जाता है, क्योंकि पीडीए का कार्य अपेक्षाकृत जटिल होता है।•पहली संपत्ति: एमटी/नॉन-एमटी — ग्रामर को सरल बनाएं; यदि कोई उत्पादन बचता है तो नॉन-एमटी, अन्यथा एमटी।•दूसरी संपत्ति: फाइनाइट/इन्फाइनाइट — सीएनएफ नॉर्मलाइजेशन करें, फिर ग्राफ बनाएं; यदि लूप/चक्र मिले तो अनंत अन्यथा परिमित।•तीसरी संपत्ति: सदस्यता — CYK एल्गोरिथ्म से निर्णायक; चौथी संपत्ति: समानता और अस्पष्टता अनिर्णायक हैं।•क्लोजर प्रॉपर्टी: डीसीएफएल और सीएफएल के लिए यूनियन, इंटरसेक्शन, कॉम्प्लीमेंट पर निर्णायकता; डीसीएफएल संघ के अंतर्गत बंद नहीं है, सीएफएल प्रतिच्छेदन के अंतर्गत बंद नहीं है।ट्यूरिंग मशीन परिचय ⏱ 420:24
•चर्च-ट्यूरिंग थीसिस: कोई भी एल्गोरिदमिक प्रक्रिया जो मानव या कंप्यूटर कर सकता है, ट्यूरिंग मशीन कर सकती है; 1936 में प्रस्तावित और आज भी मान्य।•ट्यूरिंग मशीन सबसे शक्तिशाली मॉडल है, टाइप-0 ग्रामर द्वारा उत्पन्न भाषाओं को स्वीकार करती है।•मॉडल: टेप दोनों दिशाओं में अनंत, ब्लैंक सिंबल, रीड-राइट हेड, हर मूव में बाएँ या दाएँ जाना, रुकने का विकल्प नहीं।•परिभाषा: 7-टपल (Q, Σ, Γ, δ, q0, B, F); टेप सिंबल Γ, इनपुट वर्णमाला Σ, संक्रमण फलन δ: Q × Γ → Q × Γ × {L, R}।ट्यूरिंग मशीन का परिचय और उदाहरण ⏱ 440:24
•ट्यूरिंग मशीन a^n b^n (n≥1) जैसी सरल भाषा को संभाल सकती है, हालाँकि यह DCFL है, लेकिन ट्यूरिंग मशीन की कार्यप्रणाली सीखने के लिए इसका उपयोग किया जाता है।•ट्यूरिंग मशीन में a को x से और b को y से प्रतिस्थापित करते हुए एक-से-एक मैपिंग की जाती है, और हेड दाएँ-बाएँ घूमता है।•जब सभी a और b क्रमशः x और y में बदल जाते हैं, तो मशीन अंतिम स्थिति में पहुँचकर स्वीकार करती है।•ट्यूरिंग मशीन का प्रतिनिधित्व तीन तरीकों से होता है: संक्रमण आरेख, संक्रमण तालिका, और संक्रमण आईडी।उन्नत उदाहरण और अवधारणाएँ ⏱ 450:41
•a^n b^n c^n भाषा के लिए ट्यूरिंग मशीन तीन प्रतीकों (a को x, b को y, c को z) को मैप करती है, क्योंकि PDA यह नहीं कर सकता।•w#w पैटर्न मिलान में, ट्यूरिंग मशीन पहले w के प्रतीकों को चिह्नित करती है और फिर सी के बाद के प्रतीकों से मिलान करती है।•ट्यूरिंग मशीन की स्वीकृति शर्त: यह रुकनी चाहिए और अंतिम स्थिति में होनी चाहिए।•ट्यूरिंग मशीन एक काल्पनिक कंप्यूटर मॉडल है; परीक्षा में सामान्यतः बुनियादी डिज़ाइन प्रश्न पूछे जाते हैं।ट्यूरिंग मशीन की कार्यप्रणाली और डिज़ाइन ⏱ 460:24
•ट्यूरिंग मशीन की मदद से a^n b^n c^n पैटर्न की तुलना की जाती है; पहले प्रतीक को x या y से बदलकर, फिर उसी पैटर्न के अन्य प्रतीकों को ढूंढकर मिलान किया जाता है।•इस प्रक्रिया में कई अवस्थाएँ (states) होती हैं, जैसे q0 से q9, और प्रत्येक अवस्था में सिर दाएँ या बाएँ मूव करता है, तथा प्रतीकों को बदलता है।•यदि पहला प्रतीक b है, तो पूरी प्रक्रिया दोबारा शुरू करनी पड़ती है, और b को y से बदला जाता है।•अंत में, जब सभी प्रतीक मिल जाते हैं, तो मशीन स्वीकार करती है और हॉल्ट हो जाती है।•इस मशीन की पावर सीमित है: अगर अल्फाबेट में 26 अक्षर हों, तो 26 लूप बनाने पड़ते हैं, जबकि प्रोग्रामिंग भाषाओं में यह आसान होता है।यूनरी और बाइनरी संख्याओं का योग और रूपांतरण ⏱ 460:24
•ट्यूरिंग मशीन केवल एक्सेप्टर नहीं है, यह संख्याओं का योग भी कर सकती है; उदाहरण के लिए, यूनरी में 3 और 4 को जोड़कर 7 प्राप्त किया जाता है।•यूनरी में योग करने के लिए मशीन पहले नंबर के 1 को स्कैन करती है, ब्लैंक को 1 से बदलती है, और फिर दूसरे नंबर के 1 को भी जोड़ती है, अंत में एक अतिरिक्त 1 हटाकर सही परिणाम देती है।•यूनरी से बाइनरी रूपांतरण में, मशीन हर 1 को एक विशेष प्रतीक (जैसे Z) से बदलती है और साथ ही बाइनरी परिणाम को दूसरी तरफ बनाती है; इस प्रक्रिया में कैरी जनरेट होता है और अंत में सही बाइनरी संख्या प्राप्त होती है।•उदाहरण के तौर पर, 5 (यूनरी: 11111) को बाइनरी में 101 के रूप में प्रस्तुत किया जाता है, जिसे Y और X प्रतीकों से दर्शाया जाता है (Y=1, X=0)।ट्यूरिंग मशीन के विभिन्न संस्करण और उनकी पावर ⏱ 460:24
•डिटरमिनिस्टिक और नॉन-डिटरमिनिस्टिक ट्यूरिंग मशीन की पावर समान होती है; दोनों एक ही भाषा को स्वीकार करती हैं, इसलिए नॉन-डिटरमिनिस्टिक को अलग से पढ़ने की आवश्यकता नहीं है।•मल्टी-टेप ट्यूरिंग मशीन में एक से अधिक टेप होते हैं, लेकिन इससे पावर में कोई वृद्धि नहीं होती है; इसे सिंगल-टेप में परिवर्तित किया जा सकता है और स्वीकृत भाषा समान रहती है।•अन्य संस्करण जैसे मल्टीपल रीड/राइट हेड्स या मल्टी-डाइमेंशनल टेप (जैसे 2D मैट्रिक्स) भी पावर को नहीं बढ़ाते हैं।ट्यूरिंग मशीन का व्यावहारिक उपयोग ⏱ 460:24
•ट्यूरिंग मशीन की अवधारणा ही आधुनिक कंप्यूटर, लैपटॉप और मोबाइल फोन की नींव है; यह एक ही टेप पर सिंबल्स को बदलकर जटिल गणनाएँ करती है।•जटिल समस्याओं को हल करने के लिए ट्यूरिंग मशीन को छोटे-छोटे फ़ंक्शनों में विभाजित किया जा सकता है, जैसे पहले यूनरी में योग करना, फिर उसे बाइनरी में बदलना।ट्यूरिंग मशीन के वेरिएंट, हॉल्टिंग प्रॉब्लम और भाषा वर्गीकरण ⏱ 480:26
•ट्यूरिंग मशीन के विभिन्न वेरिएंट (जैसे स्टे ऑप्शन, वन-वे इन्फिनिट टेप, जंपिंग, नॉन-इरेज़िंग, मल्टीडायमेंशन, मल्टीहेड, थ्री-स्टेट, मल्टीटेप, नॉन-डिटरमिनिस्टिक, पीडीए विद टू स्टैक्स) सभी की शक्ति समान है; कोई भी ट्यूरिंग मशीन की शक्ति को नहीं बढ़ा सकता।•हॉल्टिंग प्रॉब्लम: ट्यूरिंग मशीन में लूप की संभावना होती है, जिससे यह तय करना असंभव है कि मशीन हॉल्ट करेगी या लूप में चली जाएगी।•भाषाओं का वर्गीकरण: रिकर्सिव सेट (हमेशा हॉल्ट करने वाली) और रिकर्सिव एन्यूमरेबल सेट (हॉल्ट या लूप कर सकती है)। रिकर्सिव को ट्यूरिंग डिसाइडेबल और रिकर्सिव एन्यूमरेबल को ट्यूरिंग रिकॉग्नाइज़ेबल कहा जाता है।यूनिवर्सल ट्यूरिंग मशीन, अन्य विषय और समापन ⏱ 490:44
•यूनिवर्सल ट्यूरिंग मशीन (UTM) एक ट्यूरिंग मशीन है जो अन्य ट्यूरिंग मशीनों का सिमुलेशन कर सकती है; इसमें मशीन का विवरण और इनपुट दोनों टेप पर होते हैं, जो स्टोर्ड प्रोग्राम कॉन्सेप्ट को दर्शाता है।•लीनियर बाउंडेड ऑटोमेटा: सीमित मेमोरी वाली ट्यूरिंग मशीन; इसका अध्ययन नहीं किया जाता क्योंकि मेमोरी की सीमा स्पष्ट नहीं होती।•पोस्ट कॉरेस्पॉन्डेंस प्रॉब्लम (PCP): एक अनडिसाइडेड प्रॉब्लम; उदाहरणों में समाधान मौजूद हैं (1,2,3 और 2,1,1,3), लेकिन सामान्य एल्गोरिदम नहीं लिखा जा सकता।•समापन: अगला विषय कंपाइलर होगा, और चैनल को सपोर्ट करने का अनुरोध किया गया।मुख्य बिंदु
•TOC कंप्यूटेशनल शक्ति, समस्या समाधान की सीमाओं और एल्गोरिदम की दक्षता का अध्ययन है।•DFA (नियतात्मक परिमित ऑटोमेटा) पाठ्यक्रम का लगभग 90-95% हिस्सा है, जबकि मूर और मीली मशीनें शेष 5-10%•DFA को 5-टपल (K, Σ, δ, s, F) द्वारा परिभाषित किया जाता है।•NFA में एक स्टेट पर एक सिंबल के लिए कई मूव्स या कोई मूव नहीं हो सकता, जबकि DFA में हर स्टेट पर हर इनपुट के लिए एक ही यूनिक मूव होता है।•मूर मशीन में आउटपुट स्टेट से जुड़ा होता है, जिससे इनपुट की लंबाई n होने पर आउटपुट की लंबाई n+1 होती है, जबकि मीली मशीन में आउटपुट ट्रांज़िशन से जुड़ा होता है और लंबाई n होती है।•ट्यूरिंग मशीन आधुनिक कंप्यूटर, लैपटॉप और मोबाइल फोन की नींव है; यह एक ही टेप पर सिंबल्स को बदलकर जटिल गणनाएँ करती है।निष्कर्ष
इस वीडियो में TOC के सभी प्रमुख विषयों को विस्तार से समझाया गया है, जिसमें ऑटोमेटा, नियमित अभिव्यक्ति, व्याकरण, पुशडाउन ऑटोमेटा, और ट्यूरिंग मशीन शामिल हैं। यह सेमेस्टर परीक्षा की तैयारी के लिए एक संपूर्ण संसाधन है।
