থিওরি অফ কম্পিউটেশন টিউটোরিয়াল - ফাইনাইট স্টেট মেশিন এবং ডিএফএ

 একটি ফাইনাইট স্টেট মেশিনের একটি সেট অফ স্টেট  এবং দুটি ফাংশন রয়েছে যাকে পরবর্তী-অবস্থা এবং আউটপুট ফাংশন বলা হয়।

সেট অফ স্টেটের অভ্যন্তরীণ স্টোরেজের সমস্ত সম্ভাব্য সংমিশ্রণের সাথে মিলে যায়। যদি n বিট স্টোরেজ থাকে, তাহলে 2n সম্ভাব্য অবস্থা আছে।

পরবর্তী অবস্থা স্টেট হল একটি যৌগিক লজিক ফাংশন যা ইনপুট এবং বর্তমান অবস্থা দেখে সিস্টেমের পরবর্তী অবস্থা নির্ধারণ করে।

দুই ধরনের ফাইনাইট স্টেট মেশিন হলো-

• মুর মেশিন - মুর মেশিনে, আউটপুট শুধুমাত্র বর্তমান অবস্থার উপর নির্ভর করে।
• মিলি মেশিন - মিলি মেশিনে, আউটপুট বর্তমান অবস্থা এবং বর্তমান ইনপুট উভয়ের উপর নির্ভর করে।

আমরা বেশিরভাগ ক্ষেত্রে মুর মেশিন নিয়ে কাজ করি। 

একটি ফাইনাইট অটোমাটা হল ৫টি টুপল (Q, ∑, δ, q0, F) যেখানে:

• Q: ফাইনাইট স্টেটের সেট
• ∑: ইনপুট প্রতীকের ফাইনাইট সেট
• q0: প্রাথমিক অবস্থা
• F: চূড়ান্ত অবস্থা
• δ: ট্রানজিশন ফাংশন