✖

NFA থেকে DFA তে রূপান্তর

অনির্ধারণমূলক অটোমেটনকে কীভাবে নির্ধারণমূলক অটোমেটনে রূপান্তর করা যায়, তা আমরা দেখব। এর মাধ্যমে প্রমাণ হবে যে অনির্ধারণমূলক ও নির্ধারণমূলক অটোমেটনের গণনাশক্তি সমতুল্য।

মূল ভাবনা

ধরি ⟨QN, ΣN, δN, q0, FN⟩ একটি এপসিলন ট্রানজিশনবিহীন অনির্ধারণমূলক অটোমেটন। আমরা নির্ধারণমূলক অটোমেটন ⟨QD, ΣD, δD, p0, FD⟩ এমনভাবে গঠন করব, যেন

  • QD ⊆ 2QN
  • ΣD = ΣN
  • p0 = {q0}
  • FD = {Q ∈ QD | Q ∩ FN ≠ ∅}

ট্রানজিশন ফাংশন δD কে এভাবে সংজ্ঞায়িত করি:

∀Q∈QD,a∈ΣD:δD(Q,a)=⋃q∈QδN(q,a)

এর অর্থ কী? অনির্ধারণমূলক অটোমেটন একসঙ্গে একাধিক স্টেটে থাকতে পারে। তাই এমন পরিস্থিতি আসতে পারে, যখন আমাদের অনির্ধারণমূলক অটোমেটন আছে স্টেট {q0, q1} এ। পরের প্রতীক, ধরা যাক 1, পড়ে আমরা পৌঁছাতে পারি স্টেটের সেট {q0, q2, q3} এ। একই অটোমেটনের নির্ধারণমূলক রূপে এটি প্রকাশ পায় এভাবে: আমরা দুইটি স্টেট তৈরি করি, এদের নাম দিই {q0, q1} ও {q0, q2, q3}, এবং এদের মধ্যে প্রতীক 1 এর একটি ট্রানজিশন বসাই। আনুষ্ঠানিকভাবে আমরা এক স্টেট থেকে অন্য স্টেটে যাই, কিন্তু নামের কারণে জানব যে অনির্ধারণমূলক অটোমেটনে আমরা থাকতাম যথাক্রমে দুইটি ও তিনটি স্টেটে।

উদাহরণ

ধরি অনির্ধারণমূলক অটোমেটনটি এই:

নির্ধারণমূলক অটোমেটন গঠন করতে সবার আগে একটি নতুন ট্রানজিশন ফাংশন গঠন করতে হবে। এতে সাহায্য করবে একটি সারণি, যাতে আমরা সব ট্রানজিশন লিখে রাখব। শুরুতে সারণিটি দেখতে এমন:

স্টেট/প্রতীক01{q0}

অ্যালগরিদমের শেষে বাম কলামে থাকবে নির্ধারণমূলক অটোমেটনের সব স্টেট। পূরণ করা সারণিটি থেকে পাব ট্রানজিশন ফাংশন। এখন সারণিতে লিখি, আমরা স্টেট {q0} এ থাকলে এবং ইনপুটে প্রতীক 0 ও 1 থাকলে কোন স্টেটগুলোতে পৌঁছাই।

স্টেট/প্রতীক01{q0}{q1}{q1,q2}

স্টেট q0 থেকে প্রতীক 0 এর ট্রানজিশন যায় শুধু স্টেট q1 এ, আর প্রতীক 1 এর ট্রানজিশন যায় স্টেট q1 ও q2 এ। এখন সারণিতে দুইটি নতুন স্টেট যোগ করি: {q1} ও {q1, q2}। কেন? সারণিতে স্টেটের এমন কোনো সেট লিখলে, যা বাম কলামে এখনো নেই, সেটটি আমরা বাম কলামে যোগ করি।

স্টেট/প্রতীক01{q0}{q1}{q1,q2}{q1}{q1,q2}

এবং আবার পূরণ করি। স্টেট {q1, q2} এর ক্ষেত্রে দুইটি স্টেটই পরীক্ষা করতে ভুললে চলবে না, অর্থাৎ স্টেট q1 থেকে যেসব স্টেটে পৌঁছাই আর স্টেট q2 থেকে যেসব স্টেটে পৌঁছাই, এদের সংযোগ নিতে হবে।

স্টেট/প্রতীক01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}

আমরা কয়েকটি নতুন স্টেট পেলাম, সেগুলো সারণিতে যোগ করতে হবে:

স্টেট/প্রতীক01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q3}

…এবং আবার ট্রানজিশনগুলো পূরণ করি:

স্টেট/প্রতীক01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}

স্টেট {q0, q1, q3}, {q1} ও {q1,q2} সারণিতে আগেই আছে, তাই শুধু স্টেট {q0,q1,q2,q3} যোগ করি।

স্টেট/প্রতীক01{q0}{q1}{q1,q2}{q1}{q0,q1,q3}{q0,q3}{q1,q2}{q0,q1,q3}{q0,q3}{q0,q1,q3}{q0,q1,q3}{q0,q1,q2,q3}{q0,q3}{q1}{q1,q2}{q0,q1,q2,q3}{q0,q1,q3}{q0,q1,q2,q3}

আর কোনো নতুন স্টেট যোগ হয়নি, তাই সারণি পূরণ হয়ে গেছে। এখন শুধু চিত্রটি গঠন করা বাকি। নির্ধারণমূলক অটোমেটনের স্টেটগুলো আছে প্রথম কলামে, প্রতীক 0 ও 1 এর ট্রানজিশন পরের কলামগুলোতে। যে স্টেটে মূল অটোমেটনের কোনো চূড়ান্ত স্টেট আছে, সেটি এই অটোমেটনেও চূড়ান্ত স্টেট হবে। অর্থাৎ q3 ধারণকারী প্রত্যেক স্টেট হবে চূড়ান্ত স্টেট। অটোমেটনটি দেখতে এমন হবে:

অটোমেটনটি যে সত্যিই ঠিকভাবে কাজ করে, তা দেখানো যায়। স্ট্রিং 11001 গ্রহণ করে দেখি। নির্ধারণমূলক অটোমেটনে আমরা যাব এই পথে

q0→1q1,q2→1q0,q3→0q1→0q0,q1,q3→1q0,q1,q2,q3

এবং অটোমেটন স্ট্রিংটি গ্রহণ করত, কারণ শেষ স্টেট {q0, q1, q2, q3} চূড়ান্ত। অনির্ধারণমূলক অটোমেটনে সিমুলেশনের সময় আমরা একই স্টেটগুলোতে পৌঁছাতাম। অর্থাৎ শুরু করতাম স্টেট q0 থেকে, প্রতীক 1 এর জন্য পৌঁছাতাম স্টেট {q1, q2} এ। পরের প্রতীক 1 আমাদের নিয়ে যেত স্টেট {q0,q3} এ, এভাবে পরের স্টেটগুলোর জন্যও। শেষে আমরা থাকতাম সব স্টেট {q0, q1, q2, q3} এ, আর অটোমেটন স্ট্রিংটি গ্রহণ করত।

তথ্যসূত্র

সূচিপত্র: সসীম অটোমেটন, সম্পূর্ণ অটোমেটন, অনির্ধারণমূলক সসীম অটোমেটন, অনির্ধারণমূলক অটোমেটনের সিমুলেশন, NFA থেকে DFA তে রূপান্তর