ট্যুরিং মেশিন - একটি টিউরিং মেশিন হল একটি যন্ত্র যা টাইপ 0 ব্যাকরণ দ্বারা উত্পন্ন একটি ভাষার শব্দ গ্রহণ করতে ব্যবহৃত হয়। একটি টিউরিং মেশিন (TM) হল একটি গাণিতিক মডেল যা একটি অসীম দৈর্ঘ্যের টেপ নিয়ে কোষে বিভক্ত যা ইনপুট দেওয়া হয়। এতে একটি মাথা থাকে যা ইনপুট টেপ পড়ে। একটি রাষ্ট্রীয় রেজিস্টার টুরিং মেশিনের অবস্থা সংরক্ষণ করে। একটি ইনপুট প্রতীক পড়ার পরে, এটি অন্য চিহ্ন দিয়ে প্রতিস্থাপিত হয়, এর অভ্যন্তরীণ অবস্থা পরিবর্তিত হয় এবং এটি একটি ঘর থেকে ডান বা বাম দিকে চলে যায়। যদি TM চূড়ান্ত অবস্থায় পৌঁছায়, ইনপুট স্ট্রিং গ্রহণ করা হয়, অন্যথায় প্রত্যাখ্যান করা হয়।
একটি টিএমকে আনুষ্ঠানিকভাবে 7-টুপল (Q, X, Σ, δ, q0, B, F) হিসাবে বর্ণনা করা যেতে পারে যেখানে −
- Q হল রাজ্যের একটি সীমিত সেট
- X হল টেপ বর্ণমালা
- Σ হল ইনপুট বর্ণমালা
- δ একটি ট্রানজিশন ফাংশন; δ :Q × X → Q × X × {Left_shift, Right_shift}।
- q0 হল প্রাথমিক অবস্থা
- B হল ফাঁকা প্রতীক
- F হল চূড়ান্ত অবস্থার সেট
আমাদের লক্ষ্য হল একটি টিউরিং মেশিন টিএম তৈরি করা যা ভাষা গ্রহণ করে
L=anbma(n+m) যেখানে n,m>=1
TM গ্রহণ করতে পারে এমন শব্দের উদাহরণ নেওয়া যাক,
- abaa, n=1,m=1
- aabaaa, n=2,m=1
- আব্বা, n=1,m=2
- aaabaaaa, n=3,m=1
সেটা হল n বার a তারপর m গুন b তারপর n+m বার a আবার। n,m>=1
সর্বনিম্ন না. a's সর্বদা 3 এবং b হবে 1। যখন উভয় n=m=1।
পদ্ধতিটি নীচে সংক্ষিপ্ত করা হয়েছে -
মেশিন প্রথমে সব n নং গ্রহণ করে। a এর পরে সব m no। খ এর। তারপর যত বেশি a এর সম্মুখীন হয়, এটি আগের ইনপুট b's এবং a's মুছে ফেলা শুরু করে। শেষ পর্যন্ত যখন কোন নতুন a আসছে না এবং মাথাটি প্রথম ইনপুট অক্ষরে পৌঁছেছে, এর অর্থ হল সমস্ত অক্ষর সঠিকভাবে প্রক্রিয়া করা হয়েছে। ইনপুট স্ট্রিং-
-এর জন্য ধাপে ধাপে অনুসরণ করা যাকstate q0 থেকে ট্রানজিশন
-
δ (q0, a) → ( q1, x, R)। স্টেট q0 এ যদি ক্যারেক্টার রিড হয় তাহলে q1 স্টেটে ট্রানজিট করুন, এটিকে x এবং ডানদিকে সরান যাতে স্ট্রিং এর পরবর্তী ক্যারেক্টারটি নির্দেশ করে।
Ex − aabaaa → xabaaa (প্রথম অক্ষরটি x হেড হয়ে গেছে ডান পাশের a-তে সরানো হয়েছে)
-
δ ( q0, b ) → ( q3, x, R)। স্টেট q0 এ যদি ক্যারেক্টার রিড হয় তাহলে q3 স্টেটে ট্রানজিট করুন, স্ট্রিং-এ পরবর্তী ক্যারেক্টারটিকে নির্দেশ করতে এটিকে x এবং ডানদিকে সরান।
প্রাক্তন - বাবা…. → xabaaa…. (প্রথম অক্ষরটি x হেড হয়ে গেছে ডান পাশের a-তে সরানো হয়েছে)
এখানে x প্রথম অক্ষরকে উপস্থাপন করতে ব্যবহৃত হয়।
স্টেট q1 থেকে ট্রানজিশন
-
δ ( q1, a ) → ( q1, a, R)। স্টেট q1 এ যদি ক্যারেক্টার রিড হয় তাহলে q1 স্টেটে থাকুন এবং স্ট্রিং এর পরবর্তী ক্যারেক্টারটিকে নির্দেশ করতে ডানদিকে সরান।
যেমন:xaabaaa… → xaabaaa… (বিশ্রামের জন্য কিছু করবেন না এবং ডানদিকে সরান)
-
δ ( q1, b ) → ( q2, b, R)। q1 অবস্থায় অক্ষর রিড b হলে q1 অবস্থায় থাকুন এবং স্ট্রিং-এ পরবর্তী অক্ষরটি নির্দেশ করতে ডানদিকে সরান।
Ex − xaabaaa… → xaabaaa… (বিশ্রামের জন্য কিছু করবেন না এবং ডানদিকে সরে যাবেন)
স্টেট q2 থেকে ট্রানজিশন
-
δ ( q2, b ) → ( q2, b, R)। q2 অবস্থায় অক্ষর রিড b হলে q2 অবস্থায় থাকুন এবং স্ট্রিং-এর পরবর্তী অক্ষরটিকে নির্দেশ করতে ডানদিকে সরান।
Ex − xaabbbaaa… → xaabbbaaa… (বিশ্রামের জন্য b's কিছুই করবেন না এবং ডানদিকে সরান)
-
δ ( q2, z ) → ( q2, z, R)। q2 স্টেটে যদি ক্যারেক্টার রিড z হয় তাহলে q2 স্টেটে থাকুন এবং স্ট্রিং এর পরবর্তী ক্যারেক্টারটিকে নির্দেশ করতে ডানদিকে সরে যান।
Ex − xaabaazz… → xaabaazz… ( বাকি z এর জন্য কিছুই করবেন না এবং ডানদিকে সরান)
-
δ ( q2, a ) → ( q3, z, L)। স্টেট q2 এ যদি ক্যারেক্টার রিড a হয়, এটিকে z করুন তারপর q3 স্টেটে ট্রানজিট করুন এবং স্ট্রিং-এ আগের অক্ষরটিকে নির্দেশ করতে বাম দিকে সরান।
Ex − xaabaazz… → xaabazzz… ( a এর z দিয়ে প্রতিস্থাপনের জন্য এবং বামে সরান)
স্টেট q3 থেকে ট্রানজিশন
-
δ ( q3, z ) → ( q3, z, L)। q3 স্টেটে যদি ক্যারেক্টার রিড z হয় তাহলে q3 স্টেটে থাকুন এবং স্ট্রিং এর আগের ক্যারেক্টারটিকে নির্দেশ করতে বাম দিকে সরান।
Ex − xaabzzzz… → xaabzzzzz… ( z-এর জন্য কিছুই করবেন না এবং বামে যান)
-
δ ( q3, b ) → ( q2, z, R)। স্টেট q2 এ যদি ক্যারেক্টার রিড b হয় তাহলে এটাকে z করুন এবং stateq2 এ ট্রানজিট করুন এবং স্ট্রিং এর পরবর্তী ক্যারেক্টারটিকে নির্দেশ করতে ডানদিকে সরান। সমস্ত b এর প্রতিস্থাপন করুন
Ex − xaabzzzz… → xaazzzzz… ( b এর জন্য z দিয়ে প্রতিস্থাপন করুন এবং ডানদিকে সরান)
-
δ ( q3, a ) → ( q2, z, R)। স্টেট q2 এ যদি ক্যারেক্টার রিড a হয় তাহলে এটিকে z করুন এবং stateq3 এ ট্রানজিট করুন এবং স্ট্রিং এর পরবর্তী ক্যারেক্টারটিকে নির্দেশ করতে ডানদিকে সরান। সমস্ত a এর প্রতিস্থাপন করুন
Ex − xaazzzz… → xaazzzzz… ( a এর বদলে z দিয়ে ডানে সরান)
-
δ ( q3, x ) → ( q4, z, R)। স্টেট q2 এ যদি ক্যারেক্টার রিড হয় x মেক ইট z তারপর স্টেট q3 এ ট্রানজিট করুন এবং স্ট্রিং এর পরবর্তী ক্যারেক্টারটিকে নির্দেশ করতে ডানদিকে সরান। প্রথম প্রতীকে পৌঁছে গেছে।
Ex − xzzzzzzzz… → zzzzzzzz… ( x এর জন্য z দিয়ে প্রতিস্থাপন করুন এবং ডানদিকে সরান)
স্টেট q4 থেকে ট্রানজিশন
-
δ ( q4, z ) → ( q4 z, R)। স্টেট q4 এ যদি ক্যারেক্টার রিড z হয় তাহলে q4 স্টেটে থাকুন এবং স্ট্রিং এর পরবর্তী ক্যারেক্টারটি নির্দেশ করতে ডানদিকে সরান। সমস্ত অক্ষর এখন z৷
৷Ex − zzzzzzzz… → zzzzzzzz… (সকল z-এর জন্য কিছুই করবেন না এবং ডানদিকে সরান)
-
δ ( q4, $ ) → ( qf, $ , R)। q4 অবস্থায় কোনো অক্ষর না থাকলে, শেষ হয়ে গেছে। চূড়ান্ত রাজ্যে ট্রানজিট qf. যার অর্থ স্ট্রিং গৃহীত হয়৷
Ex − zzzzzzzz$ → zzzzzzzz ( স্ট্রিং শেষের জন্য, $ কিছুই করবেন না এবং চূড়ান্ত অবস্থায় যান)
ডায়াগ্রাম টিউরিং মেশিন দেখায় -
ইনপুট
aabaaaq0:aabaaa → q1:xabaaa → q1:xabaaa → q2:xabaaa → q3:xabzaa → q2:xazzaaq2:xazzaa → q3:xazzza → q3:xazzza → q3:xazzza:xzzz2 → xzzz2:xzzz2 → q2:xzzzzza → q2:xzzzzza → q2:xzzzzzz → q3:xzzzzzz……..q3:xzzzzzz → q3:xzzzzzz → q4:zzzzzzzz → q4:zzzzzz…….q4:xzzzzzz$ → xzzzz$>qf পৌঁছেছে মানে aabaaa গৃহীত হয়েছে
