✖

রেগুলার ভাষার ছেদ

ধরি 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 রেগুলার।

কোনো স্ট্রিং ভাষাগুলোর ছেদে থাকে, যদি তা ভাষা L1 এ এবং একই সঙ্গে L2 এ থাকে। অর্থাৎ অটোমেটন A1 ও অটোমেটন A2 দুইটিকেই স্ট্রিংটি গ্রহণ করতে হবে। আমরা রেগুলার ভাষার সংযোগের ক্ষেত্রে ব্যবহৃত ভাবনাটিই হুবহু কাজে লাগাব, শুধু চূড়ান্ত স্টেটের সেটটি বদলে দেব।

পদ্ধতির আনুষ্ঠানিক রূপ

আমাদের আছে দুইটি অটোমেটন,

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

আমরা অটোমেটন A = ⟨Q, Σ, δ, q, F⟩ গঠন করব, যা ভাষা L(A1) ∩ L(A2) গ্রহণ করে। এখানে

  • Q = Q1 × Q2
  • Σ= Σ1 ∩ Σ2
  • q = ⟨q0, p0⟩
  • F = F1 × F2

ট্রানজিশন ফাংশন δ এর জন্য এই সম্পর্কটি সত্য হবে:

∀q∈Q1,p∈Q2:δ(⟨q,p⟩,a)=⟨δ1(q,a),δ2(p,a)⟩

উদাহরণ

ধরি অটোমেটন A1 গ্রহণ করে সেইসব স্ট্রিং, যাতে জোড় সংখ্যক 1 আছে:

আর অটোমেটন A2 গ্রহণ করে সেইসব স্ট্রিং, যাতে বিজোড় সংখ্যক 0 আছে:

আমরা এমন একটি অটোমেটন গঠন করব, যা এই ভাষা দুইটির ছেদ গ্রহণ করবে। এই অটোমেটনের স্টেটের সেট Q = Q1 × Q2 আকারের, প্রারম্ভিক স্টেট ⟨q0, p0⟩, আর চূড়ান্ত স্টেট F1 × F2:

এরপর δ(⟨q,p⟩, a) = ⟨δ1(q, a), δ2(p, a)⟩ নিয়মে ট্রানজিশনগুলো যোগ করি:

যেমন, এই অটোমেটনে স্টেট ⟨q0, p0⟩ থেকে প্রতীক 0 এর ট্রানজিশন যায় স্টেট ⟨q0,p1⟩ এ। এর অর্থ, অটোমেটন A1 এ স্টেট q0 থেকে প্রতীক 0 এর ট্রানজিশন ফিরে আসে স্টেট q0 এ। আর অটোমেটন A2 এ প্রতীক 0 এর ট্রানজিশন যায় স্টেট p0 থেকে স্টেট p1 এ।

অটোমেটনটি পরীক্ষা করে দেখতে পার। এটি 110 বা 00000 এর মতো স্ট্রিং গ্রহণ করবে (এগুলোতে জোড় সংখ্যক 1 এবং একই সঙ্গে বিজোড় সংখ্যক 0 আছে), কিন্তু 11, 111, 1010 এর মতো স্ট্রিং গ্রহণ করবে না।

তথ্যসূত্র

সূচিপত্র: রেগুলার ভাষার আবদ্ধতা ধর্ম, রেগুলার ভাষার সংযোগ, রেগুলার ভাষার ছেদ, রেগুলার ভাষার অন্তর, রেগুলার ভাষার পূরক, রেগুলার ভাষার সংযুক্তি, রেগুলার ভাষার ক্লোজার