✖

অটোমেটনের ন্যূনতমকরণ

অটোমেটনের ন্যূনতমকরণ (minimization) বলতে বোঝায় এমন একটি সমতুল্য অটোমেটন খুঁজে বের করা, যাতে স্টেটের সংখ্যা যথাসম্ভব কম। যে অটোমেটনে কোনো অপ্রয়োজনীয় স্টেট নেই, তাকেও আরও সরল করা যেতে পারে।

উদাহরণ

এই অটোমেটনটি নিই:

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

স্পষ্টতই এই অটোমেটন আগেরটির মতোই একই ভাষা গ্রহণ করে, অথচ এর স্টেট কম।

স্টেটের সমতুল্যতা

ধরি A = ⟨Q, Σ, δ, q0, F⟩ একটি অটোমেটন। স্টেট q ∈ Q এর ভাষা, যাকে লিখি L(q), এভাবে সংজ্ঞায়িত করি:

L(q)=L(⟨Q,Σ,δ,q,F⟩)

অর্থাৎ অটোমেটন A এর প্রারম্ভিক স্টেট q0 বদলে q করি এবং এই অটোমেটন যে ভাষা গ্রহণ করে, তা নির্ণয় করি। অন্যভাবে বললে, ভাষা L(q) এ আছে সেইসব স্ট্রিং w, যেগুলোর জন্য অটোমেটন A এ স্টেট q থেকে স্ট্রিং w পড়ে অটোমেটনের কোনো চূড়ান্ত স্টেটে পৌঁছানো যায়। আগের অটোমেটনে ফিরে গেলে L(q1) = {1}।

আমরা বলি, দুইটি ভিন্ন স্টেট q1 ও q2 সমতুল্য, যদি

L(q1)=L(q2)

এর অর্থ কী? স্টেট q1, q2 সমতুল্য হলে এদের অটোমেটনের প্রারম্ভিক স্টেট বানালে এরা একই ভাষা তৈরি করবে। অন্যভাবে বললে, অটোমেটন কনফিগারেশন ⟨q1, w⟩ ও ⟨q2, w⟩ এ পৌঁছালে দুই ক্ষেত্রেই হয় গ্রহণ করবে, নয়তো দুই ক্ষেত্রেই বর্জন করবে।

আগের অটোমেটনে ফিরে যাই: স্টেট q1 ও q2 সমতুল্য, কারণ স্টেট q1 এ থাকলে ইনপুট স্ট্রিংটি আমরা গ্রহণ করতে পারি কেবল তখনই, যখন স্ট্রিংয়ের না পড়া অংশ 1 এর সমান। স্টেট q2 এ থাকলেও একই কথা।

সুতরাং অটোমেটনের ন্যূনতমকরণে মূল কাজ হলো সমতুল্য স্টেটগুলো খুঁজে বের করা এবং এগুলোকে একটি নতুন স্টেটে জুড়ে দিয়ে বাদ দেওয়া, যেমন উপরের উদাহরণে করেছি।

সমতুল্য স্টেট কীভাবে খুঁজতে হয়

কোন স্টেটগুলো নিশ্চয়ই সমতুল্য হবে না? একটি চূড়ান্ত ও একটি অচূড়ান্ত স্টেট নিলে এরা নিশ্চয়ই সমতুল্য নয়, কারণ চূড়ান্ত স্টেটের ভাষা অচূড়ান্ত স্টেটের ভাষার সমান নয়: চূড়ান্ত স্টেট নিশ্চয়ই স্ট্রিং ε গ্রহণ করে, অচূড়ান্ত স্টেট করে না। পদ্ধতিটি সরাসরি একটি উদাহরণে দেখি। ধরি অটোমেটনটি এই:

শুরুতে স্টেটের দুইটি সেট তৈরি করি

S1=F={q3,q6},S2=Q∖F={q0,q1,q2,q4,q5}.

এখন ট্রানজিশন সারণি তৈরি করি এবং গুচ্ছ S1 ও S2 এর তথ্যও রাখি:

গুচ্ছস্টেট01S1q3q5q4q6——S2q0q1q2q1—q3q2—q3q4q6—q5q6—

এবার সারণিটি বদলে নিই: প্রদত্ত প্রতীকের জন্য কোন স্টেটে যাওয়া হয়, তা সরাসরি না লিখে শুধু লিখি কোন গুচ্ছে যাওয়া হয়। যেমন, স্টেট q3 থেকে 0 এর জন্য পৌঁছাই স্টেট q5 এ, যা গুচ্ছ S2 এ আছে। তাই সারণিতে q5 এর জায়গায় লিখি S2:

গুচ্ছস্টেট01S1q3S2S2q6——S2q0S2S2q1—S1q2—S1q4S1—q5S1—

এখন দুইটি গুচ্ছকে আরও ভাগ করি। একই গুচ্ছে সবসময় রাখি সেইসব স্টেট, যেগুলো সব প্রতীকের জন্য একই গুচ্ছে যায়। যেমন, স্টেট q3 ও q6 একই গুচ্ছে থাকবে না, কারণ 0 বা 1 কোনোটির জন্যই এরা একই গুচ্ছে যায় না। অন্যদিকে স্টেট q1 ও q2 একই গুচ্ছে থাকবে, কারণ দুইটিরই 0 এর ট্রানজিশন নেই এবং দুইটিই 1 এর জন্য যায় গুচ্ছ S1 এ। এভাবে নতুন গুচ্ছ তৈরি করি:

গুচ্ছস্টেট01q3S2S2q6——q0S2S2q1—S1q2—S1q4S1—q5S1—

প্রত্যেক গুচ্ছে ট্রানজিশনগুলো একই। নতুন তৈরি হওয়া গুচ্ছগুলোর নাম দিই এবং আবার দেখি, স্টেটগুলো এই নতুন গুচ্ছগুলোর কোনটিতে যায়:

গুচ্ছস্টেট01S1q3S5S5S2q6——S3q0S4S4S4q1—S1q2—S1S5q4S2—q5S2—

এই পর্যায়ে গুচ্ছগুলোকে আবার ভাগ করার কথা। কিন্তু দেখতে পাচ্ছি, আর কোনো ভাগ করা যায় না, একই গুচ্ছ পেতাম। কারণ স্টেট q1 ও q2 এর ট্রানজিশন গুচ্ছের হিসাবে একই বটে, কিন্তু এরা আগেই একই গুচ্ছে আছে, আর গুচ্ছ S4 এ অন্য কোনো স্টেট নেই। সমতুল্য স্টেট খোঁজার অ্যালগরিদম শেষ। প্রত্যেক গুচ্ছ থেকে একটি স্টেট বেছে নিলেই চলবে, বাকিগুলো মুছে ফেলি। যে ট্রানজিশনগুলো মুছে ফেলা স্টেটে যেত, সেগুলো যাবে বেছে নেওয়া সেই একটি স্টেটে।

তাই আমরা ঠিক করতে পারি, নতুন অটোমেটনে থাকবে স্টেট q3, q6, q0, q1, q4, আর স্টেট q2 ও q5 বাদ দেব। যে ট্রানজিশনগুলো q2 এ যেত, এখন সেগুলো যাবে q1 এ, আর যেগুলো q5 এ যেত, সেগুলো যাবে q4 এ:

অটোমেটন ন্যূনতমকরণের ধাপ

  1. অগম্য স্টেটগুলো বাদ দিই,
  2. অপ্রয়োজনীয় স্টেটগুলো বাদ দিই,
  3. সমতুল্য স্টেটগুলো বাদ দিই।

তথ্যসূত্র

সূচিপত্র: অগম্য স্টেট, অপ্রয়োজনীয় স্টেট, অটোমেটনের ন্যূনতমকরণ