রেগুলার ভাষার সংযোগ
ধরি L1, L2 দুইটি রেগুলার ভাষা। আমরা প্রমাণ করব যে এদের সংযোগ L = L1 ∪ L2 ভাষাটিও রেগুলার।
নির্ধারণমূলক অটোমেটন দিয়ে পদ্ধতি
পদ্ধতির মূল ভাবনা
আমাদের আছে দুইটি রেগুলার ভাষা L1 ও L2, আর প্রমাণ করতে চাই যে এদের সংযোগ L1 ∪ L2 আবার একটি রেগুলার ভাষা। L1 ও L2 রেগুলার ভাষা বলে এমন সসীম অটোমেটন A1 ও A2 আছে, যারা ভাষা L1 ও L2 গ্রহণ করে, অর্থাৎ L(A1) = L1 এবং L(A2) = L2। এরপর আমরা একটি সসীম অটোমেটন A গঠন করব, যা ভাষা L1 ∪ L2 গ্রহণ করবে, আর এতে প্রমাণ হবে যে ভাষা L1 ∪ L2 রেগুলার।
কীভাবে তা করব? আমাদের হাতে আছে সসীম অটোমেটন A1 ও A2, যারা আলাদা আলাদা ভাষা দুইটি গ্রহণ করে। বলা যায়, স্ট্রিং w ভাষা L1 ∪ L2 এ আছে যদি এবং কেবল যদি অটোমেটন A1 বা A2 এর অন্তত একটি তা গ্রহণ করে।
অটোমেটন A এভাবে কাজ করতে পারে: ইনপুট w এর জন্য এটি ইনপুট w এ অটোমেটন A1 এর গণনা সিমুলেট করবে। A1 স্ট্রিং w গ্রহণ করলে A অটোমেটনটিও স্ট্রিং w গ্রহণ করবে। A1 স্ট্রিং w বর্জন করলে A এরপর ইনপুট w এ A2 এর গণনা সিমুলেট করে দেখবে। A2 স্ট্রিং w গ্রহণ করলে A অটোমেটনটিও স্ট্রিং w গ্রহণ করবে। নইলে বর্জন করবে।
বাকি শুধু আনুষ্ঠানিকভাবে বলা, অটোমেটন A অন্য একটি অটোমেটনের গণনা “সিমুলেট করে” বলতে কী বোঝায়।
আনুষ্ঠানিক রূপ
আমাদের আছে দুইটি রেগুলার ভাষা L1 ও L2, যাদের গ্রহণ করে এই সসীম অটোমেটন দুইটি
আমরা একটি সসীম অটোমেটন A = ⟨Q, Σ, δ, q, F⟩ গঠন করব, যা ভাষা L = L1 ∪ L2 গ্রহণ করবে। এখানে কাজে লাগাব দুইটি অটোমেটন A1, A2 সিমুলেট করার ভাবনা। কল্পনা করি, ইনপুটে আছে স্ট্রিং w = w1w2… wn, আর এখন আমরা স্ট্রিং w এর জন্য একই সঙ্গে অটোমেটন A1 ও A2 এর গণনা সিমুলেট করব। অটোমেটন A1 এর প্রারম্ভিক কনফিগারেশন ⟨q1, w1w2… wn⟩, A2 এর প্রারম্ভিক কনফিগারেশন ⟨q2, w1w2… wn⟩। এবার প্রত্যেক অটোমেটনে গণনার একটি ধাপ সম্পন্ন করি, এতে পৌঁছাই কনফিগারেশন ⟨δ1(q1, w1), w2… wn⟩ ও ⟨δ2(q2, w1), w2… wn⟩ এ।
দেখতে পাচ্ছি, এই কনফিগারেশনগুলো শুধু প্রথম উপাংশে আলাদা, দ্বিতীয়টি (স্ট্রিংয়ের না পড়া অংশ) সবসময় একই। তাই সিমুলেশনের সময় দুইটি অটোমেটনের দুইটি কনফিগারেশন রাখার দরকার নেই, ⟨⟨qi, qj⟩, wl… wn⟩ আকারের একটি কনফিগারেশনই যথেষ্ট, যেখানে qi ∈ Q1 এবং qj ∈ Q2। অন্যভাবে বললে, আমরা যে অটোমেটন A গঠন করছি, তার প্রারম্ভিক কনফিগারেশন হবে ⟨⟨q1, q2⟩, w⟩। জোড় ⟨q1, q2⟩ এর প্রথম অংশ হলো অটোমেটন A1 এই মুহূর্তে যে স্টেটে আছে, আর দ্বিতীয় উপাংশ হলো অটোমেটন A2 এর বর্তমান স্টেট।
তাই লিখতে পারি, গঠিত অটোমেটন A এর স্টেটের সেট হবে Q = Q1 × Q2। এটি আগের দুইটি অটোমেটনের স্টেটগুলোর কার্তেসীয় গুণজ। এরপরের ভাবনা হলো, অটোমেটন A এর প্রারম্ভিক স্টেট হবে ⟨q1, q2⟩, এবং অটোমেটন A1 প্রতীক w1 এর জন্য স্টেট qi এ গেলে আর অটোমেটন A2 প্রতীক w1 এর জন্য স্টেট qj এ গেলে অটোমেটন A প্রতীক w1 এর জন্য যাবে স্টেট ⟨qi, qj⟩ এ।
ট্রানজিশন ফাংশন δ লিখি এভাবে (এখানে ধরে নিচ্ছি যে আমরা এই মুহূর্তে আছি স্টেট qi ও qj এ):
বাকি শুধু ছোটখাটো বিষয়। বর্ণমালার জন্য Σ= Σ1 ∪ Σ2। প্রারম্ভিক স্টেট q = ⟨q1, q2⟩। আর চূড়ান্ত স্টেট হলো সেইসব জোড় ⟨qi, qj⟩, যেখানে হয় qi ∈ F1, নয়তো qj ∈ F2।
পদ্ধতির উদাহরণ
ধরি দুইটি অটোমেটন আছে। প্রথমটি অটোমেটন A1, যা সেইসব স্ট্রিং (ফাঁকা স্ট্রিংসহ) গ্রহণ করে, যেখানে শূন্য ও এক পালাক্রমে আসে, অর্থাৎ 01, 0101, 010101, … আকারের স্ট্রিং।
পরের অটোমেটন A2 গ্রহণ করে সেইসব স্ট্রিং, যাতে অন্তত একটি শূন্য আছে:
এই ভাষা দুইটির সংযোগ হলো সেইসব স্ট্রিং, যাতে হয় শূন্য আছে, নয়তো যেগুলো 01, 0101, … আকারের। এখন আমরা একটি সসীম অটোমেটন A = ⟨Q, Σ, δ, q, F⟩ গঠন করব, যা এই সংযোগ ভাষাটিই গ্রহণ করবে। প্রথমে দেখি, এই নতুন অটোমেটন A এর স্টেটগুলো কেমন হবে। এটি হবে প্রথম ও দ্বিতীয় অটোমেটনের স্টেটগুলোর কার্তেসীয় গুণজ:
সংযোগ ভাষা L(A1) ∪ L(A2) গ্রহণকারী অটোমেটন A এর ছয়টি স্টেট এগুলো। চিত্রে এরা দেখতে এমন হতো:
স্টেটগুলো স্টেটের জোড় দিয়ে গঠিত বলে ঘাবড়ানোর কিছু নেই, এটি শুধু অটোমেটনে আসলে কী ঘটছে তা ভালোভাবে বোঝার জন্য। স্টেটগুলোর নাম সাধারণভাবে q0, …, q5 রাখলেও চলত। চূড়ান্ত স্টেট হলো সেইসব স্টেট, যাতে হয় স্টেট q0, নয়তো p1 আছে, কারণ এগুলোই মূল অটোমেটন দুইটির চূড়ান্ত স্টেট। প্রারম্ভিক স্টেট ⟨q0, p0⟩।
এখন সব ট্রানজিশন খুঁজে বের করতে হবে। এমন একটি সারণি লিখি:
আর একে একে সারণিটি পূরণ করব। প্রথমে দেখি, ইনপুট 0 এ স্টেট ⟨q0, p0⟩ থেকে ট্রানজিশন কোথায় যাবে। অটোমেটন A1 এ ইনপুট 0 এ স্টেট q0 থেকে ট্রানজিশন কোথায় যায় দেখি: তা যায় স্টেট q1 এ। অটোমেটন A2 এ শূন্যের জন্য p0 থেকে ট্রানজিশন যায় স্টেট p1 এ। তাই সারণিতে লিখি ⟨q1, p1⟩:
ইনপুট 1 এ পাই: অটোমেটন A1 এর জন্য δ1(q0, 1) = q2 এবং অটোমেটন A2 এর জন্য δ2(p0, 1) = p0। তাই পাই স্টেট ⟨q2, p0⟩।
সারণির বাকি অংশ লিখে ফেলি:
এই সারণি অনুযায়ী চিত্রের বাকি অংশ এঁকে ফেলি।
অটোমেটনটি যেমন কাজ করার কথা তেমন করে কি না, পরীক্ষা করে দেখতে পার। স্ট্রিং 0100 গ্রহণ করে দেখি। অটোমেটন একে একে এই স্টেটগুলো পার হয়
যেহেতু স্টেট ⟨q2, p1⟩ একটি চূড়ান্ত স্টেট, তাই অটোমেটন A স্ট্রিং 0100 গ্রহণ করে। অটোমেটন A1 ও A2 দিয়ে স্ট্রিং 0100 গ্রহণ করার চেষ্টা করলে কী হতো? অটোমেটন A1 একে একে এই স্টেটগুলো পার হতো:
অটোমেটনটি থেমেছে স্টেট q2 এ, যা চূড়ান্ত নয়, তাই অটোমেটন A1 এই স্ট্রিং গ্রহণ করত না। অটোমেটন A2 এর কী হয়?
স্টেট p1 চূড়ান্ত, তাই অটোমেটন A2 স্ট্রিং 0100 গ্রহণ করত। লক্ষ কর, অটোমেটন A1 ও A2 থেমেছে স্টেট q2 ও p1 এ, আর এটি মিলে যায় এই তথ্যের সঙ্গে যে অটোমেটন A থেমেছে স্টেট ⟨q2, p1⟩ এ।
অনির্ধারণমূলক অটোমেটন দিয়ে পদ্ধতি
উদাহরণ
রেগুলার ভাষার সেট সংযোগের সাপেক্ষে আবদ্ধ, তা একটি অনির্ধারণমূলক অটোমেটন গঠন করেও প্রমাণ করা যায়, আর তা অনেক সহজ।
আমাদের আছে দুইটি রেগুলার ভাষা L1, L2, আর প্রমাণ করতে চাই যে এদের সংযোগ L = L1 ∪ L2 ভাষাটিও রেগুলার। L1, L2 রেগুলার ভাষা বলে এমন অটোমেটন A1, A2 থাকতেই হবে, যারা এই ভাষাগুলো গ্রহণ করে। অর্থাৎ L(A1) = L1 এবং L(A2) = L2। এই অটোমেটনগুলোর সাহায্যে আমরা অটোমেটন A গঠন করব, যা ভাষা L গ্রহণ করবে, অর্থাৎ L(A) = L।
ধরে নিই, সসীম অটোমেটন A1 ও A2 দেখতে এমন:
এবং
দুই ভাষার সংযোগ গ্রহণকারী অটোমেটন গঠন করতে আমরা একটি নতুন প্রারম্ভিক স্টেট তৈরি করতাম, আর এই স্টেট থেকে মূল প্রারম্ভিক স্টেট দুইটিতে দুইটি এপসিলন ট্রানজিশন টানতাম। ব্যস, এটুকুই। অটোমেটনটি দেখতে এমন হতো:
আনুষ্ঠানিক রূপ
আমাদের আছে দুইটি অটোমেটন A1 = ⟨Q1, Σ, δ1, q1, F1⟩ ও A2 = ⟨Q2, Σ, δ2, q2, F2⟩। আমরা অটোমেটন A = ⟨Q, Σ, δ, q0, F⟩ গঠন করব, যা আগের অটোমেটন দুইটির গৃহীত ভাষাগুলোর সংযোগ গ্রহণ করবে, অর্থাৎ L(A) = L(A1) ∪ L(A2)। এখানে
- Q = Q1 ∪ Q2 ∪ {q0}
- F = F1 ∪ F2
আর ট্রানজিশন ফাংশন δ এর সংজ্ঞা:
তথ্যসূত্র
সূচিপত্র: রেগুলার ভাষার আবদ্ধতা ধর্ম, রেগুলার ভাষার সংযোগ, রেগুলার ভাষার ছেদ, রেগুলার ভাষার অন্তর, রেগুলার ভাষার পূরক, রেগুলার ভাষার সংযুক্তি, রেগুলার ভাষার ক্লোজার