✖

রেগুলার ভাষার আবদ্ধতা ধর্ম

ভাষা L রেগুলার যদি এবং কেবল যদি এমন একটি অটোমেটন A থাকে, যা এই ভাষা গ্রহণ করে, অর্থাৎ L(A) = L। আমরা প্রমাণ করব যে রেগুলার ভাষা সংযোগ, ছেদ, সংযুক্তি (concatenation) ও ক্লোজার প্রক্রিয়ার সাপেক্ষে আবদ্ধ।

কোনো প্রক্রিয়ার সাপেক্ষে সেটের আবদ্ধতা

আমরা বলি, সেট M প্রক্রিয়া ⊗ এর সাপেক্ষে আবদ্ধ (closed), যদি

∀x,y∈M:x⊗y∈M

উদাহরণ হিসেবে স্বাভাবিক সংখ্যার সেটে যোগ প্রক্রিয়ার কথা বলা যায়। যেকোনো দুইটি স্বাভাবিক সংখ্যার যোগফল আবার একটি স্বাভাবিক সংখ্যা। অন্যদিকে স্বাভাবিক সংখ্যার সেট বিয়োগের সাপেক্ষে আবদ্ধ নয়, কারণ যেমন 7 − 15 = −8, আর সংখ্যা −8 স্বাভাবিক নয়।

রেগুলার ভাষার সেট কোন কোন প্রক্রিয়ার সাপেক্ষে আবদ্ধ, তা আমরা প্রমাণ করব। সব প্রমাণই গঠনমূলক, অর্থাৎ আমরা এমন একটি অটোমেটন গঠন করব, যা প্রাপ্ত ভাষাটি গ্রহণ করে।

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