রেগুলার এক্সপ্রেশন থেকে অটোমেটনে রূপান্তর
যেকোনো রেগুলার এক্সপ্রেশনকে কীভাবে অনির্ধারণমূলক সসীম অটোমেটনে রূপান্তর করা যায়, তা আমরা দেখব।
উদাহরণ
অ্যালগরিদমটি বর্ণনা করার আগে একটি উদাহরণে দেখি, আসলে আমরা কী করতে চাই। ধরি রেগুলার এক্সপ্রেশনটি a(b|c)x∗। এই রেগুলার এক্সপ্রেশন যে ভাষা তৈরি করে, তা কথায় বললে: যেসব স্ট্রিং বর্ণ “a” দিয়ে শুরু হয়, এরপর আসে বর্ণ “b” বা “c”, আর তারপর যেকোনো সংখ্যক বর্ণ “x”। এই ভাষা গ্রহণ করে এমন অটোমেটন কি আমরা গঠন করতে পারতাম? অবশ্যই, দেখ:
স্পষ্টতই এই অটোমেটন একই ভাষা গ্রহণ করে। তাই প্রশ্ন জাগে, প্রত্যেক রেগুলার এক্সপ্রেশনের জন্যই কি এমন অটোমেটন আছে, যা প্রদত্ত ভাষাটি গ্রহণ করে? হ্যাঁ, আছে।
রেগুলার এক্সপ্রেশন থেকে অটোমেটনে রূপান্তরের অ্যালগরিদম
ধরে নিই, ইনপুটে আছে রেগুলার এক্সপ্রেশন R। রেগুলার এক্সপ্রেশন নিয়ে আগের অংশ থেকে আমরা জানি, রেগুলার এক্সপ্রেশনের মোট ছয়টি ভিন্ন আকার হতে পারে। তাই ছয়টি ভিন্ন ক্ষেত্র আলাদা করি:
-
কোনো প্রতীক a ∈ Σ এর জন্য R = a। অর্থাৎ রেগুলার এক্সপ্রেশনটি হলো আমরা যে বর্ণমালা Σ এর উপর কাজ করছি, তার শুধু একটি প্রতীক। একটি প্রতীক a গ্রহণকারী অটোমেটন দেখতে এমন হতো:
-
R = ϵ, ফাঁকা স্ট্রিং। ফাঁকা স্ট্রিং গ্রহণকারী অটোমেটন দেখতে এমন হতো:
-
R = ∅, ফাঁকা ভাষা তৈরি করে এমন রেগুলার এক্সপ্রেশন। এমন ভাষা শনাক্ত করে এই অটোমেটন:
-
R = R1 ∪ R2, যেখানে R1, R2 রেগুলার এক্সপ্রেশন। আমরা আগেই জানি, রেগুলার ভাষার সংযোগ আবার রেগুলার ভাষা, এবং এমন ভাষা গ্রহণকারী অটোমেটন আমরা গঠন করতে পারি। অন্যভাবে বললে, ধরে নিই আমাদের কাছে এক্সপ্রেশন R1 ও R2 এর তৈরি ভাষা শনাক্তকারী অটোমেটন আছে, আর এগুলো দিয়ে আমরা এক্সপ্রেশন R1 ∪ R2 এর তৈরি ভাষা গ্রহণকারী অটোমেটন গঠন করি। উদাহরণ: R1 = a ও R2 = ϵ হলে পদ্ধতি অনুযায়ী পাই এই অটোমেটন:
-
R = R1 ∘ R2, যেখানে R1, R2 রেগুলার এক্সপ্রেশন। আগের ক্ষেত্রের মতোই। রেগুলার ভাষার সংযুক্তি একটি রেগুলার ভাষা, তাই এমন ভাষা গ্রহণকারী অটোমেটনও আমরা গঠন করতে পারি। তাই R1 = a, R2 = b হলে সংযুক্তিটি দেখতে এমন হতো:
-
, যেখানে R1 রেগুলার এক্সপ্রেশন। আবারও জানি, রেগুলার ভাষার ক্লোজার একটি রেগুলার ভাষা। তাই R = a∗ হলে অটোমেটনটি দেখতে এমন হতো:
এই ক্ষেত্রগুলো ধাপে ধাপে প্রয়োগ করে আমরা পুরো রেগুলার এক্সপ্রেশনকে সসীম অটোমেটনে রূপান্তর করি।
পূর্ণাঙ্গ উদাহরণ
রেগুলার এক্সপ্রেশন (a|bc)∗ রূপান্তর করে দেখি। একে একে পাই এই অটোমেটনগুলো:
এই প্রাপ্ত অটোমেটন সেই ভাষা গ্রহণ করে, যা রেগুলার এক্সপ্রেশন (a|bc)∗ তৈরি করে। অবশ্যই অটোমেটনটি ভয়ানক জটিল, আর নিশ্চয়ই অনেক সরল কোনো অটোমেটন আছে, যা একই ভাষা গ্রহণ করে। এর জন্য আমরা NFA থেকে DFA তে রূপান্তরের অ্যালগরিদম ব্যবহার করতে পারি, তারপর অটোমেটনের ন্যূনতমকরণ করতে পারি।
তথ্যসূত্র
সূচিপত্র: রেগুলার এক্সপ্রেশন, রেগুলার এক্সপ্রেশন থেকে অটোমেটনে রূপান্তর, সাধারণীকৃত অনির্ধারণমূলক সসীম অটোমেটন, অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তর