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