টিউরিং মেশিন (TM) - টাইপ ০ গ্রামার দ্বারা জেনারেটেড ল্যাঙ্গুয়েজের শব্দ গ্রহণ করার একটি ডিভাইস। TM একটি গাণিতিক মডেল যাতে অসীম দৈর্ঘ্যের টেপ রয়েছে সেলে ভাগ করে ইনপুট দেওয়া হয়। একটি হেড টেপ পড়ে। স্টেট রেজিস্টার TM-এর স্টেট স্টোর করে। ইনপুট সিম্বল পড়ার পর সেটি অন্য সিম্বল দিয়ে রিপ্লেস হয়, ইন্টারনল স্টেট চেঞ্জ হয়, এবং হেড বাম বা ডানে সরায়। ফাইনাল স্টেটে পৌঁছালে স্ট্রিং একসেপ্ট, অন্যথায় রিজেক্ট।
TM ৭-টাপল (Q, X, Σ, δ, q₀, B, F) দিয়ে ফরমালি বর্ণনা করা হয়।
লক্ষ্য: L = aⁿbᵐa⁽ⁿ⁺ᵐ⁾ (n,m ≥ 1) একসেপ্ট করা TM তৈরি।
স্বীকৃত শব্দ উদাহরণ: abaa (n=1,m=1), aabaaa (n=2,m=1), abbaaa (n=1,m=2), aaabaaaa (n=3,m=1)।
অ্যালগরিদম সারসংক্ষেপ: মেশিন প্রথমে n সংখ্যক 'a' এবং m সংখ্যক 'b' একসেপ্ট করে। তারপর আরও 'a' আসলে আগের ইনপুট 'b' এবং 'a' ডিলিট করা শুরু করে। শেষে কোনো নতুন 'a' না আসা এবং হেড প্রথম ইনপুট ক্যারেক্টরে পৌঁছালে সব ক্যারেক্টর সঠিকভাবে প্রসেস হয়েছে বলে বোঝায়।
স্টেট ট্রানজিশন (আংশিক)
- q₀: 'a' পেলে -> q১, 'x' লিখে, R। 'b' পেলে -> q৩, 'x' লিখে, R।
- q১: 'a' পেলে -> q১, 'a', R। 'b' পেলে -> q২, 'b', R।
- q২: 'b' পেলে -> q২, 'b', R। 'z' পেলে -> q২, 'z', R। 'a' পেলে -> q৩, 'z', L।
- q৩: 'z' পেলে -> q৩, 'z', L। 'b' পেলে -> q২, 'z', R। 'a' পেলে -> q২, 'z', R। 'x' পেলে -> q৪, 'z', R।
- q৪: 'z' পেলে -> q৪, 'z', R। '$' (এন্ড) পেলে -> q_f (ফাইনাল), $, R।
ডায়াগ্রাম টিউরিং মেশিনের ভিজ্যুয়াল রিপ্রেজেন্টেশন দেখাচ্ছে।
ইনপুট উদাহরণ
aabaaa -> q0 -> q1 -> q1 -> q2 -> q3 -> q2 -> q2 -> q3 -> q3 -> q3 -> q2 -> q2 -> q3 -> q4 -> q4 -> qf (Accepted)
