✖

অনির্ধারণমূলক অটোমেটনের সিমুলেশন

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

অ্যালগরিদমের মূলনীতি

মূলনীতিটি একটি উপযুক্ত উদাহরণে দেখি। ধরি অটোমেটনটি এই:

এটি একটি অনির্ধারণমূলক সসীম অটোমেটন, যা কোনো একটি ভাষা গ্রহণ করে। ভাষাটি কোনটি, তা নিয়ে এখন মাথা ঘামানোর দরকার নেই। ইনপুট স্ট্রিং 11001 এর জন্য এমন অটোমেটনের গণনা কেমন হতে পারে, তা দেখব। ভাবনাটি এরকম: স্ট্রিং থেকে একটি প্রতীক প্রক্রিয়া করি এবং দেখি, একই প্রতীকের একাধিক ট্রানজিশনের কারণে কোথায় কোথায় যাওয়া যায়। এই সব স্টেট মনে রাখি, আর পরের ধাপে ধরে নিই যে আমরা “এই সব স্টেটে একসঙ্গে” আছি, এবং দেখি এই স্টেটগুলো থেকে এরপর কোথায় যাওয়া যায়।

তাই আমরা মনে রাখব যেসব স্টেটে থাকতে পারি তাদের সেট, এবং স্ট্রিংয়ের না পড়া অংশ। শুরুতে আমাদের কাছে জোড় ⟨{q0}, 11001⟩। আমরা শুরু করি স্টেট q0 (প্রারম্ভিক স্টেট) থেকে, ইনপুটে স্ট্রিং 11001। অটোমেটনটি দেখতে এমন, যে স্টেটে আমরা আছি তা লাল ও মোটা করে দেখানো:

প্রথম প্রতীক 1, স্টেট q0 থেকে প্রতীক 1 এর জন্য একটিই ট্রানজিশন আছে, তাই আমরা পৌঁছাই স্টেট q1 এ। মনে রাখি জোড় ⟨{q1}, 1001⟩। অটোমেটনটি দেখতে এমন:

এগিয়ে যাই। স্ট্রিংয়ের না পড়া অংশ 1001, তাই আবার 1 এর ট্রানজিশন খুঁজি। এবার সেগুলো দুইটি: স্টেট q0 এ ফিরে যাওয়া এবং স্টেট q3 এ যাওয়া। এখন আমরা দুইটি স্টেটেই একসঙ্গে যাই। তাই মনে রাখি জোড় ⟨{q0, q3}, 001⟩।

এর যুক্তি কী? আমরা জানি, প্রারম্ভিক স্টেট থেকে স্ট্রিং 11 দিয়ে স্টেট q3 এ যাওয়ার পথও আছে, স্টেট q0 এ যাওয়ার পথও আছে। কোন শাখাটি কাজে লাগবে, তা এখনো জানি না, তাই সহজভাবে দুইটিই মনে রাখি। এগিয়ে যাই। ইনপুটে আছে প্রতীক 0। এখন q0 থেকে বের হওয়া ট্রানজিশন এবং q3 থেকে বের হওয়া ট্রানজিশন দুইটিই দেখতে হবে। স্টেট q0 থেকে ট্রানজিশন যায় স্টেট q1 ও q2 এ, স্টেট q3 থেকে ট্রানজিশন যায় আবার q1 এ। এই সব স্টেট হিসাবে নিলে পাই জোড় ⟨{q1, q2}, 01⟩:

তবে এই ধাপ এখনো শেষ হয়নি। দেখতে পাচ্ছি, স্টেট q2 থেকে একটি এপসিলন ট্রানজিশন যায় স্টেট q4 এ। আমরা জানি, এপসিলন ট্রানজিশন ধরে পরের অক্ষর না পড়েই “যেকোনো সময় যাওয়া যায়”। অন্যভাবে বললে, ইনপুট স্ট্রিং থেকে পরের প্রতীক না পড়েই আমরা স্টেট q4 এও যেতে পারি। তাই যেসব স্টেটে থাকতে পারি, তাদের মধ্যে স্টেট q4 যোগ করি: ⟨{q1, q2, q4}, 01⟩। অটোমেটনটিকে আমরা এভাবে রং করতাম:

এরপর ইনপুটে 0। যে তিনটি স্টেটে আছি, সেখান থেকে কোথায় যাওয়া যায় দেখি। q1 থেকে কোথাও যাওয়া যায় না, কারণ 0 এর ট্রানজিশন নেই। এই শাখায় গণনা শেষ। স্টেট q4 থেকেও কোথাও যাওয়া যায় না। স্টেট q2 থেকে আমরা আবার স্টেট q2 এ পৌঁছাই। কিন্তু যেহেতু স্টেট q2 থেকে আবার একটি এপসিলন ট্রানজিশন যায় স্টেট q4 এ, তাই স্টেট q4 এও পৌঁছানো যায়। সুতরাং স্টেটের সেট {q1, q2, q4} থেকে প্রতীক 0 এর জন্য পৌঁছাতে পারি স্টেটের সেট {q2, q4} এ, পাই জোড় ⟨{q2, q4}, 1⟩:

শেষে ইনপুটে আছে প্রতীক 1। স্টেট q2 থেকে কোথাও যাওয়া যায় না, এই শাখায় গণনা শেষ। কিন্তু স্টেট q4 থেকে পৌঁছাই স্টেট q3 ও q5 এ। পাই জোড় ⟨{q3, q5}, ε⟩:

অটোমেটন এখন পুরো স্ট্রিং পড়ে ফেলেছে এবং দুইটি স্টেটে “আছে”: q3, q5। এদের অন্তত একটি চূড়ান্ত স্টেট বলে অটোমেটন স্ট্রিং 11001 গ্রহণ করে।

অ্যালগরিদম

প্রথমে আমাদের এমন একটি ফাংশন দরকার, যা প্যারামিটার হিসেবে স্টেটের একটি সেট নেবে এবং হিসাব করবে, এপসিলন ট্রানজিশন দিয়ে আর কোন কোন স্টেটে পৌঁছানো যায়। ইনপুট হলো অটোমেটন ⟨Q, Σ, δ, q0, F⟩ এবং স্টেটের সেট States, আর আউটপুট হলো এই স্টেটগুলোর এমন একটি অধিসেট, যার স্টেটগুলোতে এপসিলন ট্রানজিশন দিয়ে পৌঁছানো যায়। এই প্রক্রিয়াকে আমরা বলব সেট States এর এপসিলন ক্লোজার।

FunctionEpsilonClosure(⟨Q,Σ,δ,q0,F⟩,States)NextStates←∅ForEachq∈StatesDoNextStates←NextStates∪{q}∪δ(q,ε)EndForIfNextStates∖States=∅DoReturnStatesElseReturnEpsilonClosure(⟨Q,Σ,δ,q0,F⟩,NextStates)EndIfEndFunction

এই ফাংশনটি আমরা ব্যবহার করব এমন একটি ফাংশনে, যা অনির্ধারণমূলক অটোমেটনের কাজ সিমুলেট করবে। ইনপুট হলো অটোমেটন, ইনপুট স্ট্রিং w = w1w2… wn এবং অটোমেটন এই মুহূর্তে যেসব স্টেটে আছে তাদের সেট। আউটপুট হলো উত্তর হ্যাঁ বা না, অটোমেটন প্রদত্ত স্ট্রিংটি গ্রহণ করে কি না সেই অনুযায়ী।

FunctionComputeNFA(⟨Q,Σ,δ,q0,F⟩,w,States)Ifw=ϵDoIfStates∩F≠∅DoReturnYESElseReturnNOEndIfEndIfNextStates←∅ForEachq∈StatesDoNextStates←NextStates∪δ(q,w1)EndForNextStates←EpsilonClosure(⟨Q,Σ,δ,q0,F⟩,NextStates)ReturnComputeNFA(⟨Q,Σ,δ,q0,F⟩,w2w3…wn,NextStates)EndFunction

অটোমেটন স্ট্রিং w গ্রহণ করে কি না যাচাই করতে চাইলে ফাংশনটি এভাবে কল করি: ComputeNFA(⟨Q, Σ, δ, q0, F⟩, w, EpsilonClosure(⟨Q, Σ, δ, q0, F⟩, {q0}))।

তথ্যসূত্র

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