✖

সম্পূর্ণ অটোমেটন

সসীম অটোমেটনের মৌলিক সংজ্ঞায় প্রত্যেক স্টেট থেকে প্রত্যেক প্রতীকের জন্য ট্রানজিশন থাকা জরুরি নয়। সম্পূর্ণ অটোমেটন (complete automaton) হলো এমন অটোমেটন, যার প্রত্যেক স্টেট থেকে ইনপুট বর্ণমালার প্রত্যেক প্রতীকের জন্য ট্রানজিশন সংজ্ঞায়িত।

সম্পূর্ণ অটোমেটন কীভাবে গঠন করতে হয়

ধরি অটোমেটনটি A = ⟨Q, Σ, δ, q0, F⟩:

এখানে স্টেট q0 থেকে বর্ণ “b” এর ট্রানজিশন আঁকা নেই। এমন পরিস্থিতি এলে আমরা বলি, অটোমেটন প্রদত্ত ইনপুট স্ট্রিংটি গ্রহণ করে না। তবে আনুষ্ঠানিকতার দিক থেকে ট্রানজিশন ফাংশন δ কিছু মানের জন্য সংজ্ঞায়িত না থাকা সুবিধাজনক না-ও হতে পারে। এখানে যেমন δ(q0, b) সংজ্ঞায়িত নয়।

এর সহজ সমাধান হলো একটি সমতুল্য অটোমেটন গঠন করা, যাতে একটি স্টেট বেশি থাকবে। “অনুপস্থিত” ট্রানজিশনগুলো যাবে এই স্টেটে, স্টেটটি চূড়ান্ত হবে না, এবং পরের সব ইনপুটে অটোমেটন এই স্টেটেই ঘুরতে থাকবে। এই অটোমেটনকে আমরা বলি সম্পূর্ণ অটোমেটন। পরিবর্তিত সমতুল্য অটোমেটনটি দেখতে এমন হতে পারে:

আমরা স্টেট qfail যোগ করেছি। অন্য স্টেটগুলো থেকে এতে ট্রানজিশন টেনেছি শুধু সেখানে, যেখানে আগে কোনো ট্রানজিশন ছিল না। এই স্টেট চূড়ান্ত নয় এবং পরের সব ইনপুটে নিজের কাছেই ফিরে আসে। তাই আগের অটোমেটনে যেখানে আমরা অনুপস্থিত ট্রানজিশনের মুখোমুখি হতাম, এখানে কোনো ট্রানজিশন অনুপস্থিত নেই, অটোমেটন পৌঁছাত স্টেট qfail এ।

সুতরাং ব্যাপকতার হানি না করে আমরা সবসময় ধরে নিতে পারি যে অটোমেটনে স্টেট ও বর্ণমালার অক্ষরের প্রত্যেক জোড়ের জন্য ট্রানজিশন সংজ্ঞায়িত আছে।

সংজ্ঞা

সম্পূর্ণ অটোমেটন A = ⟨Q, Σ, δ, q0, F⟩ এর জন্য তাই

∀q∈Q∀a∈Σ∃r∈Q:δ(q,a)=r.

তথ্যসূত্র

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