অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তর
যেকোনো সসীম অটোমেটনকে কীভাবে রেগুলার এক্সপ্রেশনে রূপান্তর করা যায়, তা আমরা দেখব।
অ্যালগরিদমের বর্ণনা
ইনপুটে আছে কোনো একটি NFA A। প্রথমে একে GNFA বানাই। দ্বিতীয় পর্যায়ে প্রতি ধাপে একটি করে স্টেট বাদ দিই, ট্রানজিশন ফাংশন ঠিকমতো বদলে নিই, আর এভাবে চালিয়ে যাই, যতক্ষণ না শুধু দুইটি স্টেট বাকি থাকে: প্রারম্ভিক ও চূড়ান্ত। এদের মধ্যে থাকবে একটি প্রান্ত, যার লেবেল হবে একটি রেগুলার এক্সপ্রেশন, আর এটিই পুরো অ্যালগরিদমের ফল। তাই পুরো পদ্ধতির মূল কাজ হলো একটি স্টেট বাদ দেওয়া এবং তারপর অটোমেটনটি এমনভাবে ঠিক করা, যেন একটি সমতুল্য অটোমেটন পাই।
একটি স্টেট বাদ দেওয়া
একটি স্টেট কীভাবে বাদ দিতে হয়, তা একটি সরল উদাহরণে দেখানো যায়। ধরি আমাদের অটোমেটনের একটি অংশ দেখতে এমন:
যেখানে Ri কোনো রেগুলার এক্সপ্রেশন। স্টেট qr বাদ দিলে অটোমেটন দেখতে কেমন হতো? কল্পনা করি, আমরা আছি স্টেট qi এ এবং জানতে চাই, এই অংশে কোন কোন স্ট্রিং তৈরি করা যায়। স্টেট qi থেকে সরাসরি স্টেট qj এ গেলে তা হবে রেগুলার এক্সপ্রেশন R4 এর সঙ্গে মেলে এমন সব স্ট্রিং।
কিন্তু স্টেট qr এ গেলে আমরা R1 আকারের স্ট্রিং তৈরি করতে পারি। স্টেট qr এ আবার রেগুলার এক্সপ্রেশন R2 এর জন্য বারবার ঘুরতে পারি, তাই আসলে
এখন জানি, অটোমেটনের এই অংশ থেকে তৈরি হতে পারে R4 আকারের, অথবা
এবার সহজেই স্টেট qr বাদ দিতে পারি, শুধু দুইটি স্টেট qi ও qj রেখে R4 এর জায়গায় লিখি এইমাত্র নির্ণয় করা রেগুলার এক্সপ্রেশন:
এই পদ্ধতি আমরা প্রত্যেক স্টেট qi থেকে কোনো স্টেট qj এ যাওয়া প্রত্যেক প্রান্তের জন্য প্রয়োগ করি, লুপসহ, অর্থাৎ qi = qj এর ক্ষেত্রেও।
একটি স্টেট বাদ দেওয়ার পর পাই একটি সমতুল্য অটোমেটন, অর্থাৎ এমন অটোমেটন, যা একই ভাষা শনাক্ত করে।
পুরো অ্যালগরিদম
ইনপুটে আছে NFA A = ⟨Q, Σ, δ, q0, F⟩।
- NFA A কে GNFA Z = ⟨Q′, Σ, δ′, q0′, qf′⟩ এ রূপান্তর করি। এরপর বর্ণ k দিয়ে বোঝাব Z এর স্টেটের সংখ্যা।
- k = 2 হলে অ্যালগরিদম শেষ, আর প্রারম্ভিক ও চূড়ান্ত স্টেটের মধ্যের প্রান্তে আছে প্রাপ্ত রেগুলার এক্সপ্রেশন।
- k>2 হলে এমন যেকোনো একটি স্টেট qr বেছে নিই, যা প্রারম্ভিক বা চূড়ান্ত স্টেটের সমান নয়, অর্থাৎ qr ≠ q0′ এবং qr ≠ qf′। এরপর একটি নতুন GNFA Z′ = ⟨Q′′, Σ, δ′′,q0′,qf′⟩ তৈরি করি, যার জন্য:
এবং সব qi ∈ Q′′ ∖ {qf′} ও সব qj ∈ Q′′ ∖ {q0′} এর জন্য যেখানে R1 = δ′(qi,qr), R2 = δ′(qr,qr), R3 = δ′(qr, qj), R4 = δ′(qi, qj)। এরপর ধাপ 2 এ ফিরে যাই।
উদাহরণ
ধরি ইনপুটে আছে এই সসীম অটোমেটন:
প্রথমে একে GNFA তে রূপান্তর করি (অদরকারি ∅-ট্রানজিশনগুলো আঁকব না):
এবার অ্যালগরিদমের দ্বিতীয় অংশ প্রয়োগ করে একটি নোড বাদ দিই। শুরু করি নোড q2 দিয়ে। নোড q2 বাদ দিই এবং স্টেট q1 থেকে স্টেট qf এ একটি ট্রানজিশন যোগ করি। এই ট্রানজিশনকে চিহ্নিত করি b(a|b)∗ দিয়ে, কারণ নোড q1 থেকে স্টেট q2 এ পৌঁছাই b আকারের স্ট্রিং দিয়ে, তারপর a|b এর জন্য বারবার ঘুরতে পারি, এতে পাই (a|b)∗, আর শেষে এপসিলন নিয়মে চলে যাই qf এ। এখানে b(a|b)∗ϵ = b(a|b)∗। পাই এই অটোমেটন:
বাকি শুধু শেষ স্টেট q1 বাদ দেওয়া। স্টেট qs থেকে স্টেট qf এ একটি প্রান্ত যোগ করি। একে কী দিয়ে চিহ্নিত করব? স্টেট q1 এ পৌঁছাই এপসিলন নিয়মে, তা সরাসরি বাদ দেওয়া যায়। তারপর a এর জন্য বারবার ঘুরতে পারি, তাই পাই রেগুলার এক্সপ্রেশন a∗। আর শেষে প্রান্ত ধরে পৌঁছাই qf এ, তাই এক্সপ্রেশনটির সঙ্গে আরও জুড়ে দিই b(a|b)∗। তাই প্রান্তটির লেবেল দিই রেগুলার এক্সপ্রেশন a∗ b(a|b)∗।
অটোমেটনে এখন শুধু দুইটি স্টেট, তাই অ্যালগরিদম শেষ। প্রান্তে আছে প্রাপ্ত রেগুলার এক্সপ্রেশন।
তথ্যসূত্র
- উদাহরণ ও অ্যালগরিদমের বর্ণনা নেওয়া হয়েছে M. Sipser: Introduction to the Theory of Computation থেকে
সূচিপত্র: রেগুলার এক্সপ্রেশন, রেগুলার এক্সপ্রেশন থেকে অটোমেটনে রূপান্তর, সাধারণীকৃত অনির্ধারণমূলক সসীম অটোমেটন, অটোমেটন থেকে রেগুলার এক্সপ্রেশনে রূপান্তর