এখানে আমরা দেখব কীভাবে ভাষা L = {WW |W belongs to {0, 1}} এর জন্য একটি টারিং মেশিন তৈরি করা যায়। এটি একটি ধরনের ভাষা উপস্থাপন করে যেখানে শুধু দুটি ক্যারেক্টার ০ এবং ১ ব্যবহার করা হয়। w হলো একটি স্ট্রিং। তাই যদি w = 10110 হয়, তবে টারিং মেশিনটি স্ট্রিং z = 1011010110 কে একসেপ্ট করবে।
এটি সমাধানের জন্য আমরা এই পদ্ধতি ব্যবহার করব। প্রথম কাজ হলো স্ট্রিংয়ের মিডপয়েন্ট বের করা, আমরা ০ কে x এবং ১ কে y-তে কনভার্ট করব। সaduraয় এটি করার পর একটি পয়েন্টে পৌঁছাবে যখন সকল ০ এবং ১ x এবং y-তে কনভার্ট হয়ে যাবে। এখন আমরা স্ট্রিংয়ের মিডপয়েন্টে আছি। তাই আমাদের প্রথম উদ্দেশ্য পুরো হয়েছে।
এখন, মিডপয়েন্টের বাম পাশের সব x এবং y কে ০ এবং ১-তে কনভার্ট করুন। এখন স্ট্রিংয়ের প্রথম অর্ধেক ০ এবং ১-র ফর্মে আছে। স্ট্রিংয়ের দ্বিতীয় অর্ধেক x এবং y-র ফর্মে আছে।
এখন, আবার স্ট্রিংয়ের শুরু থেকে 스타ার্ট করুন। যদি ০ পাওয়া যায় তবে সেটিকে x-তে কনভার্ট করুন এবং ডান দিকে যান দ্বিতীয় অর্ধেকে পৌঁছানোর পর্যন্ত, এখানে যদি x পাওয়া যায় তবে সেটিকে ব্ল্যাঙ্ক (B) করে দিন। তারপর বাম দিকে ট্রাভার্স করুন যতক্ষণ না একটি x বা y পাওয়া যায়। আমরা তার ডান পাশের ০ বা ১ কে x বা y-তে কনভার্ট করব এবং সংশ্লিষ্টভাবে দ্বিতীয় অর্ধেকের x বা y কে ব্ল্যাঙ্ক (B) করব।
এটি চলতে থাকুন যতক্ষণ না বাম পাশের সব সিম্বল x এবং y-তে কনভার্ট হয়ে যায় এবং ডান পাশের সব সিম্বল ব্ল্যাঙ্ক হয়ে যায়। যখন এক পাশ পুরোপুরি কনভার্ট হয়ে গেছে কিন্তু অন্য পাশে এখনো কিছু সিম্বল অপরিবর্তিত থাকলে স্ট্রিংটি একসেপ্ট করা হবে না। যদি প্রথম অর্ধেকের ০ বা ১-এর জন্য দ্বিতীয় অর্ধেকে সংশ্লিষ্ট x বা y না পাওয়া যায়। তবেও স্ট্রিং একসেপ্ট করা হবে না।
স্টেট ট্রানজিশন ডায়াগ্রাম
