युनिट I फॉर्मल लँग्वेज थिअरी आणि फिनाइट ऑटोमॅटा औपचारिक भाषेचा परिचय, भाषेच्या भाषांतर तर्कशास्त्राचा परिचय, भाषांतराची अनिवार्यता, अक्षरे आणि भाषा, भाषेचे मर्यादित प्रतिनिधित्व, फिनाइट ऑटोमेटा (एफए): एफएचे अनौपचारिक चित्र, फिनाइट स्टेट मशीन (एफएसएम) , FA द्वारे स्वीकारलेली भाषा, रेग्युलर भाषेची व्याख्या, Deterministic and Nondeterministic FA(DFA आणि NFA), epsilon- NFA, FA आउटपुटसह: मूर आणि मेली मशीन्स -परिभाषा, मॉडेल्स, आंतर-रूपांतरण. केस स्टडी: व्हेंडिंग मशीनसाठी एफएसएम, स्पेल चेकर युनिट II रेग्युलर एक्सप्रेशन्स (आरई) परिचय, आरईचे ऑपरेटर, बिल्डिंग आरई, ऑपरेटरची प्राधान्ये, आरईसाठी बीजगणितीय कायदे, रूपांतरण: एनएफए ते डीएफए, आरई ते डीएफए रूपांतरण: आरई ते डीएफए, डीएफए ते आरई रूपांतरणे: स्टेट/लूप एलिमिनेशन, आर्डेनचे प्रमेय रेग्युलर भाषांचे गुणधर्म: नियमित भाषांसाठी पंपिंग लेमा, बंद करणे आणि निर्णय गुणधर्म. केस स्टडी: RE मजकूर शोध आणि बदला युनिट III संदर्भ मुक्त व्याकरण (CFG) आणि भाषा परिचय, नियमित व्याकरण, संदर्भ मुक्त व्याकरण- व्याख्या, व्युत्पत्ती, व्याकरणाची भाषा, वाक्यात्मक रूप, पार्स ट्री, अनुमान, व्युत्पत्ती, पार्स ट्री, अस्पष्टता व्याकरण आणि भाषेत- अस्पष्ट व्याकरण, CFG चे सरलीकरण: एकक निर्मिती, निरुपयोगी उत्पादन, निरुपयोगी चिन्हे, आणि -उत्पादने, सामान्य रूपे- चॉम्स्की सामान्य स्वरूप, ग्रीबॅच सामान्य स्वरूप, सीएफएलचे बंद गुणधर्म, सीएफएलचे निर्णय गुणधर्म, चॉम्स्की पदानुक्रम, CFG चे ऍप्लिकेशन: पार्सर, मार्कअप भाषा, XML आणि दस्तऐवज प्रकार व्याख्या. केस स्टडी- पॅलिंड्रोमसाठी सीएफजी, कंस जुळणी, युनिट IV ट्युरिंग मशीन (टीएम) ट्युरिंग मशीन मॉडेल, ट्युरिंग मशीनचे प्रतिनिधित्व, ट्युरिंग मशीनद्वारे भाषा स्वीकार्यता, टीएमचे डिझाइन, टीएमचे वर्णन, टीएम बांधकामाचे तंत्र, ट्युरिंग मशीनचे प्रकार, लीनियर बाउंडेड ऑटोमेटाचे मॉडेल, टीएम आणि टाइप 0 व्याकरण, टीएमची थांबण्याची समस्या. युनिट V पुशडाउन ऑटोमॅटा(पीडीए) मूलभूत व्याख्या, मर्यादित स्थिती आणि रिक्त स्टॅकद्वारे स्वीकृतीची समानता, पीडीए आणि संदर्भ मुक्त भाषा, पीडीए आणि सीएफजीची समतुल्यता, पार्सिंग आणि पीडीए: टॉप-डाउन पार्सिंग, डिटरमिनिस्टिक पीडीए वापरून टॉप-डाउन पार्सिंग, तळ -अप पार्सिंग, क्लोजर गुणधर्म आणि निर्धारक पीडीए. एकक VI अनिश्चितता आणि गुंतागुंतीची समस्या एक भाषा जी पुनरावृत्तीने मोजता येत नाही, एक अनिर्णित समस्या जी RE आहे, पत्रव्यवहारानंतरची समस्या, वर्ग P आणि NP : बहुपदी वेळेत सोडवता येण्याजोग्या समस्या, एक उदाहरण: क्रुस्कलचे अल्गोरिदम, नॉनडिटरमिनिस्टिक, पॉलीनोमियल टाइम NP उदाहरण: ट्रॅव्हलिंग सेल्समन समस्या, बहुपद-वेळ कपात NP पूर्ण समस्या, एक NP पूर्ण समस्या: समाधानकारक समस्या, व्यवहार्य आणि असह्य प्रतिनिधित्व करणारी समाधानकारकता उदाहरणे, SAT समस्येची NP पूर्णता, एक प्रतिबंधित समाधानीता समस्या, Box सामान्य समस्यांसाठी अभिव्यक्ती CNF मध्ये रूपांतरित करणे, स्वतंत्र सेटची समस्या, नोड-कव्हर समस्या.