এখানে আমরা দেখব কিভাবে ভাষা L ={AiBjCk | এর জন্য একটি টুরিং মেশিন তৈরি করা যায় i * j =k; i, j, k ≥ 1}। সুতরাং এটি এক ধরনের ভাষাকে উপস্থাপন করে যেখানে আমরা শুধুমাত্র তিনটি অক্ষর A, B এবং C ব্যবহার করব। w হল একটি স্ট্রিং। সুতরাং w =AABBBBCCCCCCCC হলে, টিউরিং মেশিন এটি গ্রহণ করবে।
এটি সমাধান করার জন্য, আমরা এই পদ্ধতি ব্যবহার করব।
-
প্রথমে একটি A এর পরিবর্তে x দিয়ে ডানদিকে সরান। তারপর সমস্ত A এড়িয়ে যান এবং ডানদিকে যান
-
যখন মাথাটি প্রথম B-এ পৌঁছায় তখন একটি B এর পরিবর্তে y দিয়ে যান, তারপরে সমস্ত মধ্যবর্তী B-এর সাথে বাদ দিয়ে ডানদিকে সরান এবং প্রতিস্থাপিত B-এর সাথে মিল রেখে এখন একটি C-কে z দিয়ে প্রতিস্থাপন করুন এবং বামে যান।
-
এখন সমস্ত z এবং B এড়িয়ে বাম দিকে যান।
-
যখন পয়েন্টার সাম্প্রতিক y-এ পৌঁছায়, তখন ডানদিকে সরে যান।
-
যদি পয়েন্টারটি B এর দিকে নির্দেশ করে তবে 2 থেকে 4 ধাপগুলি পুনরাবৃত্তি করুন, অন্যথায় যখন পয়েন্টার z এ নির্দেশ করে তখন বাম দিকে যান যখন সমস্ত y কে B এর প্রতিস্থাপন করুন এবং সমস্ত A এড়িয়ে যান৷
-
যখন পয়েন্টার সবচেয়ে সাম্প্রতিক x এ আসে তখন ডানে ধাপে যান।
-
যদি পয়েন্টারটি এখনও A এর দিকে নির্দেশ করে তবে উপরের সমস্ত পদক্ষেপগুলি পুনরাবৃত্তি করুন, অন্যথায় যখন মাথা y তে থাকে তখন সমস্ত y এবং z এড়িয়ে ডান দিকে যান৷
-
$ পৌঁছে গেলে বাম দিকে সরান। স্ট্রিং গৃহীত হয়।
রাষ্ট্রীয় রূপান্তর চিত্র
