✖

রেগুলার ভাষার অন্তর

ধরি L1, L2 দুইটি রেগুলার ভাষা। আমরা প্রমাণ করব যে এদের অন্তর L = L1 ∖ L2 ভাষাটিও রেগুলার।

মূল ভাবনা

আসলে প্রমাণ করার তেমন কিছু নেই। কারণ দুইটি সেটের অন্তরের জন্য এই সম্পর্কটি সত্য:

L1∖L2=L1∩L2′,

যেখানে L2′ হলো L2 এর পূরক ভাষা। রেগুলার ভাষার ছেদ ও রেগুলার ভাষার পূরক অধ্যায় থেকে আমরা জানি, রেগুলার ভাষা এই দুই প্রক্রিয়ার সাপেক্ষেই আবদ্ধ। তার মানে আমরা এমন অটোমেটন গঠন করতে পারি, যা ভাষাগুলোর ছেদ গ্রহণ করে, এবং এমন অটোমেটনও, যা ভাষার পূরক গ্রহণ করে। তাই এই অটোমেটনগুলো দিয়ে আমরা এমন একটি অটোমেটন গঠন করতে পারি, যা ভাষা L1 ∩ L2′ গ্রহণ করবে, আর এটিই আবার ভাষা L1 ∖ L2।

উদাহরণ

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

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

আমরা এমন একটি অটোমেটন গঠন করব, যা এই ভাষা দুইটির অন্তর গ্রহণ করবে। এর জন্য দরকার অটোমেটন A2′, যা অটোমেটন A2 এর পূরক। শুধু চূড়ান্ত ও অচূড়ান্ত স্টেটগুলো অদলবদল করি:

এখন বাকি শুধু অটোমেটন A গঠন করা, যা L(A1) ও L(A2′) ভাষার ছেদ গ্রহণ করবে:

তথ্যসূত্র

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