এখানে আমরা দেখব কিভাবে L ={0n1n2n | ভাষার জন্য একটি টুরিং মেশিন তৈরি করা যায় n ≥ n}। সুতরাং এটি এক ধরনের ভাষাকে উপস্থাপন করে যেখানে আমরা শুধুমাত্র তিনটি অক্ষর 0s, 1s এবং 2s ব্যবহার করব। w একটি স্ট্রিং. সুতরাং w =000111222 হলে, টিউরিং মেশিন এটি গ্রহণ করবে।
এটি সমাধান করার জন্য, আমরা এই পদ্ধতি ব্যবহার করব। প্রথমে একটি 0 কে সামনে থেকে x দ্বারা প্রতিস্থাপন করুন, তারপরে ডানদিকে চলতে থাকুন যতক্ষণ না আমরা একটি 1 পাই এবং এই 1 কে y দ্বারা প্রতিস্থাপন করুন। আবার, ডানদিকে চলতে থাকুন যতক্ষণ না আমরা একটি 2 পাই, এটিকে z দিয়ে প্রতিস্থাপন করুন এবং বামে যান। এখন বাম দিকে সরাতে থাকুন যতক্ষণ না আমরা একটি x খুঁজে পাব। যখন আমরা এটি পাব, একটি ডান সরান, তারপর উপরের মত একই পদ্ধতি অনুসরণ করুন।
একটি শর্ত আসে যখন আমরা একটি x এর সাথে সাথে একটি y এর পরে পাই। এই মুহুর্তে আমরা ডানদিকে চলতে থাকি এবং চেক করতে থাকি যে সমস্ত 1 এবং 2 y এবং z তে রূপান্তরিত হয়েছে কি না। যদি না হয়, তাহলে স্ট্রিং গ্রহণ করা হয় না। যদি আমরা $ এ পৌঁছায় তাহলে স্ট্রিং গৃহীত হয়।
রাষ্ট্রীয় রূপান্তর চিত্র