অপ্রয়োজনীয় স্টেট
সসীম অটোমেটনে এমন স্টেট থাকতে পারে, যেখান থেকে কোনো চূড়ান্ত স্টেটে পৌঁছানো সম্ভব নয়, ফলে এগুলো অদরকারি। এমন স্টেটকে আমরা বলি অপ্রয়োজনীয় স্টেট (redundant state)। সাধারণত আমরা এগুলো বাদ দিতে চাই, কারণ এরা শুধু অকারণে পুরো অটোমেটনকে জটিল করে তোলে।
অপ্রয়োজনীয় স্টেটের উদাহরণ
ধরি সসীম অটোমেটনটি এই:
দেখতে পাচ্ছি, একবার স্টেট q4 বা q5 এ পৌঁছালে আমরা আর কখনো চূড়ান্ত স্টেট q1 বা q2 এর কোনোটিতে পৌঁছাতে পারব না। তাই এমন স্টেট অপ্রয়োজনীয়, এদের আমরা সরাসরি বাদ দিতে পারি। এতে একটি নতুন অটোমেটন পেতাম, যা কিন্তু সমতুল্য, অর্থাৎ একই ভাষা গ্রহণ করত। অপ্রয়োজনীয় স্টেটগুলো মুছে ফেলার পর অটোমেটনটি দেখতে এমন হতো:
তবু এটি একই ভাষা গ্রহণ করত। অবশ্য কিছু ক্ষেত্রে কয়েকটি অপ্রয়োজনীয় স্টেট রাখাই সুবিধাজনক, যেমন যখন আমরা সম্পূর্ণ অটোমেটন গঠন করি।
অপ্রয়োজনীয় স্টেটের সংজ্ঞা
ধরি A = ⟨Q, Σ, δ, q0, F⟩ একটি সসীম অটোমেটন। আমরা বলি, স্টেট q ∈ Q অপ্রয়োজনীয়, যদি এমন কোনো স্ট্রিং w ∈ Σ∗ ও কোনো স্টেট qf ∈ F না থাকে, যেন
অপ্রয়োজনীয় স্টেট কীভাবে বাদ দিতে হয়
ধরে নিই, ইনপুটে আছে এমন অটোমেটন A = ⟨Q, Σ, δ, q0, F⟩, যাতে আর কোনো অগম্য স্টেট নেই। আমরা একে একে খুঁজে বের করব সেইসব স্টেট, যেগুলো থেকে চূড়ান্ত স্টেটে যাওয়া যায়, তারপর সেইসব স্টেট, যেগুলো থেকে এমন স্টেটে যাওয়া যায় যেখান থেকে চূড়ান্ত স্টেটে যাওয়া যায়, এবং এভাবে বারবার। এতে পাব সেইসব স্টেটের সেট, যেগুলো অপ্রয়োজনীয় নয়। শুরুতে বসাই S0 = F। i ∈ ℕ এর জন্য পরের সেট Si গুলো গঠন করব এই নিয়মে:
অপ্রয়োজনীয় নয় এমন সব স্টেটের প্রাপ্ত সেটটি এভাবে প্রকাশ করা যায়:
আর অপ্রয়োজনীয় স্টেটের সেট
অন্যভাবে বললে: Si = Si + 1 হলে সেট Q ∖ Si এ থাকে অপ্রয়োজনীয় স্টেটগুলো। পদ্ধতিটি দেখাব এই অটোমেটনে:
প্রথমে বসাই S0 = {q1, q2}। এরপর সেট S1 গঠন করি: সেট S0 এর সঙ্গে যোগ করি সেইসব স্টেট, যেগুলো থেকে S0 সেটের কোনো একটি স্টেটে যাওয়া যায়। তাই যোগ করি স্টেট q0 ও q3, কারণ q0 থেকে ট্রানজিশন যায় q1 এ এবং q3 থেকে ট্রানজিশন যায় q2 এ। পাই S1 = {q0, q1, q2, q3}। যেহেতু S0 ≠ S1, তাই এগিয়ে যাই।
সেট S2 গঠন করি। খুঁজি সেইসব স্টেট, যেগুলো থেকে S1 এ পৌঁছানো যায় এবং যেগুলো এখনো S1 এ নেই। এমন স্টেট একটিই, q6, যেখান থেকে স্টেট q3 এ পৌঁছানো যায়। পাই S2 = {q0, q1, q2, q3, q6}। যেহেতু S1 ≠ S2, তাই এগিয়ে যাই।
সেট S3 গঠন করি। এমন কোনো নতুন স্টেট কি আছে, যেখান থেকে S2 এর কোনো স্টেটে পৌঁছানো যায়? নেই। স্টেট q4 ও q5 থেকে S2 এর কোনো স্টেটে পৌঁছানো যায় না, আর বাকি স্টেটগুলো আগেই S2 এ আছে। তাই S3 = {q0, q1, q2, q3, q6}। যেহেতু S2 = S3, অ্যালগরিদম শেষ, আর সেট S2 হলো অপ্রয়োজনীয় নয় এমন স্টেটের সেট। সেট {q4, q5} হলো অপ্রয়োজনীয় স্টেটের সেট।
আনুষ্ঠানিকভাবে অপ্রয়োজনীয় স্টেটবিহীন নতুন সমতুল্য অটোমেটনটি এভাবে গঠন করি। আমাদের আছে অটোমেটন A = ⟨Q, Σ, δ, q0, F⟩, এর সমতুল্য অপ্রয়োজনীয় স্টেটবিহীন অটোমেটন A′ = ⟨Q′, Σ, δ′, q0, F⟩ গঠন করি।
- ∀q ∈ Q′, a ∈ Σ: δ′(q, a) = δ(q, a), যদি δ(q, a) ∈ Q′ হয়, নইলে δ′(q, a) সংজ্ঞায়িত নয়
তথ্যসূত্র
সূচিপত্র: অগম্য স্টেট, অপ্রয়োজনীয় স্টেট, অটোমেটনের ন্যূনতমকরণ