রেগুলার ভাষার সংযুক্তি
ধরি L1, L2 দুইটি রেগুলার ভাষা। আমরা প্রমাণ করব যে এদের সংযুক্তি (concatenation) L = L1 ∘ L2 নিজেও একটি রেগুলার ভাষা।
কনক্যাটেনেশন কী
দুইটি স্ট্রিং “010” ও “1111” জুড়ে পাই স্ট্রিং “0101111”। ভাষার সংযুক্তিতে পাই একটি নতুন ভাষা, যা গঠন করতে একটি ভাষার প্রত্যেক স্ট্রিংকে অন্য ভাষার প্রত্যেক স্ট্রিংয়ের সঙ্গে জুড়ে দিই। দুইটি স্ট্রিং ও দুইটি ভাষার সংযুক্তি আমরা লিখব ছোট বৃত্ত দিয়ে: ∘। তাহলে ভাষা L1 ও L2 এর সংযুক্তির সংজ্ঞা দিতে পারি এভাবে:
প্রমাণের মূল ভাবনা
আমাদের আছে দুইটি রেগুলার ভাষা L1, L2 এবং এই ভাষাগুলো গ্রহণকারী দুইটি অটোমেটন:
আমরা একটি অনির্ধারণমূলক অটোমেটন A = ⟨Q, Σ, δ, q, F⟩ গঠন করব, যার “ভেতরে থাকবে” দুইটি অটোমেটন A1 ও A2 উভয়ই। মূল ভাবনা হলো, স্ট্রিংটি আমরা অটোমেটন A1 দিয়ে গ্রহণ করতে শুরু করি, আর অটোমেটন A1 চূড়ান্ত স্টেটে পৌঁছালে স্ট্রিংয়ের বাকি অংশ অটোমেটন A2 দিয়ে গ্রহণ করার চেষ্টা করি। এই অটোমেটনও স্ট্রিংয়ের অংশটি গ্রহণ করলে অটোমেটন A স্ট্রিংটি গ্রহণ করে।
উদাহরণ
ধরি অটোমেটন A1 গ্রহণ করে শুধু শূন্য দিয়ে গঠিত অশূন্য স্ট্রিং, এবং এমন স্ট্রিং, যেখানে প্রথমে একটি 1 এবং তার পরে শুধু শূন্য আসে (1, 10, 100, …):
এ ছাড়া ধরি অটোমেটন A2 গ্রহণ করে 01 দিয়ে শেষ হওয়া স্ট্রিং:
অটোমেটন দুইটি জুড়তে অটোমেটন A1 এর সব চূড়ান্ত স্টেট থেকে অটোমেটন A2 এর প্রারম্ভিক স্টেটে এপসিলন ট্রানজিশন যোগ করি, তারপর A1 এর চূড়ান্ত স্টেটগুলোকে সাধারণ স্টেট বানাই। পুরো নতুন অটোমেটনের প্রারম্ভিক স্টেট হবে অটোমেটন A1 এর প্রারম্ভিক স্টেট:
অটোমেটনটি কীভাবে কাজ করবে? আমরা অটোমেটন A1 এর কাজ সিমুলেট করতে শুরু করি। আগের চূড়ান্ত স্টেট q1 বা q2 এ গেলে জানি যে অটোমেটন A1 এই স্ট্রিংয়ের একটি অংশ গ্রহণ করে। পুরো স্ট্রিংটি ভাষা L1 ∘ L2 এ থাকতে হলে স্ট্রিংয়ের বাকি অংশ দ্বিতীয় অটোমেটন A2 কে গ্রহণ করতে হবে। এ কারণেই আগের সব চূড়ান্ত স্টেট থেকে অটোমেটন A2 এর নিজস্ব প্রারম্ভিক স্টেটে এপসিলন ট্রানজিশন যায়।
উদাহরণ হিসেবে স্ট্রিং 0001 নিই। এটি দুই ভাষার সংযুক্তিতে আছে, কারণ স্ট্রিংটি 00 ∘ 01 স্ট্রিং জুড়ে তৈরি হতে পারে। আবার এটি 0 ∘ 001 স্ট্রিং জুড়েও তৈরি হতে পারে। আমাদের অটোমেটনে দুইটি পথই সিমুলেট করা যায়। অটোমেটন এই পথে এগোতে পারে:
এই পথে অটোমেটন প্রথমে স্ট্রিংয়ের অংশ 00 “গ্রহণ” করত, তারপর অংশ 01। অথবা এটি এই পথে এগোতে পারে:
এবং তখন অটোমেটন প্রথমে স্ট্রিংয়ের অংশ 0 “গ্রহণ” করত, তারপর অংশ 001। দুই ক্ষেত্রেই আমরা অবশ্যই চূড়ান্ত স্টেট p2 এ পৌঁছাই।
আনুষ্ঠানিক পদ্ধতি
আরেকবার বলি: আমাদের আছে দুইটি রেগুলার ভাষা L1, L2 এবং এই ভাষাগুলো গ্রহণকারী দুইটি অটোমেটন:
আমরা একটি অনির্ধারণমূলক অটোমেটন A = ⟨Q, Σ, δ, q, F⟩ গঠন করি, যার জন্য:
- Q = Q1 ∪ Q2 (সেই সঙ্গে ধরে নিই যে Q1 ∩ Q2 = ∅)
- Σ= Σ1 ∪ Σ2
- q = q0
- F = F2
ট্রানজিশন ফাংশন δ ধাপে ধাপে গঠন করি:
তথ্যসূত্র
সূচিপত্র: রেগুলার ভাষার আবদ্ধতা ধর্ম, রেগুলার ভাষার সংযোগ, রেগুলার ভাষার ছেদ, রেগুলার ভাষার অন্তর, রেগুলার ভাষার পূরক, রেগুলার ভাষার সংযুক্তি, রেগুলার ভাষার ক্লোজার