Formal Language & Automata TheoryFinite automata, grammars, Turing machines, decidability & complexity

কোনো একটি সমস্যা আদৌ কম্পিউটারে সমাধানযোগ্য কি না — এবং সমাধানযোগ্য হলে তা কতটা কার্যকরভাবে করা যায় — এই দুটো প্রশ্নের উত্তর খুঁজেই থিওরি অফ কম্পিউটেশনের জন্ম। এই কোর্স ফাইনাইট অটোমাটা (DFA, NFA) ও রেগুলার এক্সপ্রেশনের ফরমাল প্রমাণ থেকে শুরু করে কনটেক্সট-ফ্রি গ্রামার, পুশডাউন অটোমাটা, সম্পূর্ণ চমস্কি হায়ারার্কি, টুরিং মেশিন, ডিসাইডেবিলিটি (হল্টিং প্রবলেম, রাইসের থিওরেম) এবং কমপ্লেক্সিটি থিওরি (P বনাম NP, NP-কমপ্লিটনেস) পর্যন্ত কভার করে — Discrete Mathematicsসেট থিওরি, লজিক ও ইনডাকশন প্রুফ — এই কোর্সের প্রতিটি ফরমাল প্রমাণের ভিত্তি সেই কোর্সেই তৈরি হয়েছে কোর্সের সরাসরি ধারাবাহিকতা, এবং Concepts of Programming Languages & Compiler Designসেই কোর্স অটোমাটা ব্যবহার করে লেক্সার/পার্সার বানানো শেখায় (ব্যবহারিক দিক), এই কোর্স সেই একই অটোমাটার পেছনের গাণিতিক প্রমাণ ও সীমাবদ্ধতা শেখায় (তাত্ত্বিক দিক) কোর্সের তাত্ত্বিক গভীরতা।