NFA থেকে DFA তে রূপান্তর
অনির্ধারণমূলক অটোমেটনকে কীভাবে নির্ধারণমূলক অটোমেটনে রূপান্তর করা যায়, তা আমরা দেখব। এর মাধ্যমে প্রমাণ হবে যে অনির্ধারণমূলক ও নির্ধারণমূলক অটোমেটনের গণনাশক্তি সমতুল্য।
মূল ভাবনা
ধরি ⟨QN, ΣN, δN, q0, FN⟩ একটি এপসিলন ট্রানজিশনবিহীন অনির্ধারণমূলক অটোমেটন। আমরা নির্ধারণমূলক অটোমেটন ⟨QD, ΣD, δD, p0, FD⟩ এমনভাবে গঠন করব, যেন
- QD ⊆ 2QN
- ΣD = ΣN
- p0 = {q0}
- FD = {Q ∈ QD | Q ∩ FN ≠ ∅}
ট্রানজিশন ফাংশন δD কে এভাবে সংজ্ঞায়িত করি:
এর অর্থ কী? অনির্ধারণমূলক অটোমেটন একসঙ্গে একাধিক স্টেটে থাকতে পারে। তাই এমন পরিস্থিতি আসতে পারে, যখন আমাদের অনির্ধারণমূলক অটোমেটন আছে স্টেট {q0, q1} এ। পরের প্রতীক, ধরা যাক 1, পড়ে আমরা পৌঁছাতে পারি স্টেটের সেট {q0, q2, q3} এ। একই অটোমেটনের নির্ধারণমূলক রূপে এটি প্রকাশ পায় এভাবে: আমরা দুইটি স্টেট তৈরি করি, এদের নাম দিই {q0, q1} ও {q0, q2, q3}, এবং এদের মধ্যে প্রতীক 1 এর একটি ট্রানজিশন বসাই। আনুষ্ঠানিকভাবে আমরা এক স্টেট থেকে অন্য স্টেটে যাই, কিন্তু নামের কারণে জানব যে অনির্ধারণমূলক অটোমেটনে আমরা থাকতাম যথাক্রমে দুইটি ও তিনটি স্টেটে।
উদাহরণ
ধরি অনির্ধারণমূলক অটোমেটনটি এই:
নির্ধারণমূলক অটোমেটন গঠন করতে সবার আগে একটি নতুন ট্রানজিশন ফাংশন গঠন করতে হবে। এতে সাহায্য করবে একটি সারণি, যাতে আমরা সব ট্রানজিশন লিখে রাখব। শুরুতে সারণিটি দেখতে এমন:
অ্যালগরিদমের শেষে বাম কলামে থাকবে নির্ধারণমূলক অটোমেটনের সব স্টেট। পূরণ করা সারণিটি থেকে পাব ট্রানজিশন ফাংশন। এখন সারণিতে লিখি, আমরা স্টেট {q0} এ থাকলে এবং ইনপুটে প্রতীক 0 ও 1 থাকলে কোন স্টেটগুলোতে পৌঁছাই।
স্টেট q0 থেকে প্রতীক 0 এর ট্রানজিশন যায় শুধু স্টেট q1 এ, আর প্রতীক 1 এর ট্রানজিশন যায় স্টেট q1 ও q2 এ। এখন সারণিতে দুইটি নতুন স্টেট যোগ করি: {q1} ও {q1, q2}। কেন? সারণিতে স্টেটের এমন কোনো সেট লিখলে, যা বাম কলামে এখনো নেই, সেটটি আমরা বাম কলামে যোগ করি।
এবং আবার পূরণ করি। স্টেট {q1, q2} এর ক্ষেত্রে দুইটি স্টেটই পরীক্ষা করতে ভুললে চলবে না, অর্থাৎ স্টেট q1 থেকে যেসব স্টেটে পৌঁছাই আর স্টেট q2 থেকে যেসব স্টেটে পৌঁছাই, এদের সংযোগ নিতে হবে।
আমরা কয়েকটি নতুন স্টেট পেলাম, সেগুলো সারণিতে যোগ করতে হবে:
…এবং আবার ট্রানজিশনগুলো পূরণ করি:
স্টেট {q0, q1, q3}, {q1} ও {q1,q2} সারণিতে আগেই আছে, তাই শুধু স্টেট {q0,q1,q2,q3} যোগ করি।
আর কোনো নতুন স্টেট যোগ হয়নি, তাই সারণি পূরণ হয়ে গেছে। এখন শুধু চিত্রটি গঠন করা বাকি। নির্ধারণমূলক অটোমেটনের স্টেটগুলো আছে প্রথম কলামে, প্রতীক 0 ও 1 এর ট্রানজিশন পরের কলামগুলোতে। যে স্টেটে মূল অটোমেটনের কোনো চূড়ান্ত স্টেট আছে, সেটি এই অটোমেটনেও চূড়ান্ত স্টেট হবে। অর্থাৎ q3 ধারণকারী প্রত্যেক স্টেট হবে চূড়ান্ত স্টেট। অটোমেটনটি দেখতে এমন হবে:
অটোমেটনটি যে সত্যিই ঠিকভাবে কাজ করে, তা দেখানো যায়। স্ট্রিং 11001 গ্রহণ করে দেখি। নির্ধারণমূলক অটোমেটনে আমরা যাব এই পথে
এবং অটোমেটন স্ট্রিংটি গ্রহণ করত, কারণ শেষ স্টেট {q0, q1, q2, q3} চূড়ান্ত। অনির্ধারণমূলক অটোমেটনে সিমুলেশনের সময় আমরা একই স্টেটগুলোতে পৌঁছাতাম। অর্থাৎ শুরু করতাম স্টেট q0 থেকে, প্রতীক 1 এর জন্য পৌঁছাতাম স্টেট {q1, q2} এ। পরের প্রতীক 1 আমাদের নিয়ে যেত স্টেট {q0,q3} এ, এভাবে পরের স্টেটগুলোর জন্যও। শেষে আমরা থাকতাম সব স্টেট {q0, q1, q2, q3} এ, আর অটোমেটন স্ট্রিংটি গ্রহণ করত।
তথ্যসূত্র
সূচিপত্র: সসীম অটোমেটন, সম্পূর্ণ অটোমেটন, অনির্ধারণমূলক সসীম অটোমেটন, অনির্ধারণমূলক অটোমেটনের সিমুলেশন, NFA থেকে DFA তে রূপান্তর