এখানে আমরা দেখব কীভাবে ভাষা L = {WWr |W belongs to {0, 1}} এর জন্য একটি টারিং মেশিন তৈরি করা যায়। এটি একটি ধরনের ভাষা উপস্থাপন করে যেখানে শুধু দুটি ক্যারেক্টার ০ এবং ১ ব্যবহার করা হয়। w হলো একটি স্ট্রিং এবং wr হলো তার রিভার্স। তাই যদি w = 10110 হয়, তবে wr হবে 01101। তাই টারিং মেশিনটি স্ট্রিং z = 1011001101 কে একসেপ্ট করবে।
এটি সমাধানের জন্য আমরা এই পদ্ধতি ব্যবহার করব। প্রথমে প্রথম সিম্বল চেক করব, যদি সেটি ০ হয় তবে y দিয়ে রিপ্লেস করব এবং যদি ১ হয় তবে x দিয়ে রিপ্লেস করব। তারপর স্ট্রিংয়ের শেষে যাব। তাই শেষ সিম্বলটি প্রথম সিম্বলের সমান হবে। সেটিও x বা y দিয়ে রিপ্লেস করব। এরপর আবার শুরুয় রিপ্লেস করা সিম্বলের বगलെ আসব এবং উপরে বর্ণিত প্রসেসটি রিপিট করব। আমাদের মনে রাখতে হবে যেহেতু wr, w-এর রিভার্স, তাই উভয়ের সিম্বল সংখ্যা সমান হবে। প্রতিবার স্ট্রিংয়ের শুরু থেকে n-তম সিম্বল রিপ্লেস করলে, শেষ থেকে সংশ্লিষ্ট n-তম সিম্বলটিও রিপ্লেস করতে হবে।
স্টেট ট্রানজিশন ডায়াগ্রাম
