সাধারণীকৃত অনির্ধারণমূলক সসীম অটোমেটন
সাধারণীকৃত অনির্ধারণমূলক সসীম অটোমেটন (generalised non-deterministic finite automaton, সংক্ষেপে GNFA) হলো এমন একটি অনির্ধারণমূলক অটোমেটন, যার ট্রানজিশনে শুধু বর্ণমালার প্রতীক থাকতে হবে এমন নয়, রেগুলার এক্সপ্রেশনও থাকতে পারে।
সংজ্ঞা
সসীম অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তরের অ্যালগরিদমে আমাদের GNFA লাগবে। অর্থাৎ GNFA হলো এমন একটি NFA, যার ট্রানজিশনগুলো রেগুলার এক্সপ্রেশন দিয়ে সংজ্ঞায়িত। এমন GNFA এর একটি উদাহরণ:
দেখতে পাচ্ছি, যেমন স্টেট q2 থেকে স্টেট qf এ একটি ট্রানজিশন যায়, যা রেগুলার এক্সপ্রেশন a∗ b দিয়ে চিহ্নিত। GNFA এর আরও কিছু শর্ত:
- প্রারম্ভিক স্টেট q0 থেকে বাকি সব স্টেটে ট্রানজিশন থাকতে হবে। চিত্রে দেখতে পাচ্ছি, স্টেট q0 থেকে বাকি সব স্টেটে ট্রানজিশন গেছে।
- GNFA তে চূড়ান্ত স্টেট শুধু একটি, আর বাকি সব স্টেট থেকে এই স্টেটে ট্রানজিশন আছে। চিত্রে যেমন দেখা যাচ্ছে, সব স্টেট থেকে একটি করে তীর qf এর দিকে গেছে।
- প্রারম্ভিক স্টেট চূড়ান্ত স্টেটের সঙ্গে অভিন্ন হতে পারবে না। তাই GNFA তে অন্তত দুইটি স্টেট থাকে।
- প্রারম্ভিক ও চূড়ান্ত স্টেট ছাড়া বাকি সব স্টেট থেকে প্রারম্ভিক ও চূড়ান্ত স্টেট ছাড়া বাকি সব স্টেটে ট্রানজিশন থাকতে হবে। লুপও এর অন্তর্ভুক্ত (স্টেট qi থেকে স্টেট qi এ ট্রানজিশন)।
সাধারণ NFA থেকে GNFA তে রূপান্তর
কোনো NFA থাকলে একে GNFA তে রূপান্তর করা সহজ।
- একটি নতুন প্রারম্ভিক স্টেট qs তৈরি করি এবং সেখান থেকে আগের প্রারম্ভিক স্টেটে একটি এপসিলন ট্রানজিশন তৈরি করি।
- একটি নতুন চূড়ান্ত স্টেট qf তৈরি করি এবং আগের সব চূড়ান্ত স্টেট থেকে স্টেট qf এ এপসিলন ট্রানজিশন টানি। আগের চূড়ান্ত স্টেটগুলোকে সাধারণ স্টেট বানাই।
- কোথাও একাধিক ট্রানজিশন থাকলে (অর্থাৎ স্টেট q1 থেকে স্টেট q2 এ প্রতীক 0 দিয়েও যাওয়া যায়, প্রতীক 1 দিয়েও), এই নিয়মগুলোকে একটি রেগুলার এক্সপ্রেশনে মিলিয়ে দিই, আর আগের সব প্রতীককে সংযোগ অপারেটর দিয়ে জুড়ি (অর্থাৎ তীরটিকে রেগুলার এক্সপ্রেশন 0|1 দিয়ে চিহ্নিত করি)।
- সংজ্ঞা অনুযায়ী যে ট্রানজিশন থাকার কথা, তা অটোমেটনে না থাকলে সেটি তৈরি করি এবং রেগুলার এক্সপ্রেশন ∅ দিয়ে চিহ্নিত করি। এতে অটোমেটনের গৃহীত ভাষা বদলায় না, কারণ এমন ট্রানজিশন কখনোই নেওয়া হয় না।
এই অটোমেটন আমরা অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তরের জন্য ব্যবহার করতে পারি।
সূচিপত্র: রেগুলার এক্সপ্রেশন, রেগুলার এক্সপ্রেশন থেকে অটোমেটনে রূপান্তর, সাধারণীকৃত অনির্ধারণমূলক সসীম অটোমেটন, অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তর