রেগুলার ভাষার পূরক
আমাদের আছে একটি রেগুলার ভাষা L। আমরা প্রমাণ করব যে ভাষা L এর পূরক আবার একটি রেগুলার ভাষা।
পূরক কী
ভাষা L এর পূরক বলতে বোঝায় সেইসব স্ট্রিং, যেগুলো ভাষা L এ নেই। পূরককে লিখি L'। অর্থাৎ বর্ণমালা Σ এর জন্য:
যেমন, অন্তত একটি প্রতীক 1 আছে এমন স্ট্রিংয়ের ভাষার পূরক হবে সেই ভাষা, যার স্ট্রিংগুলোতে একটিও প্রতীক 1 নেই।
পদ্ধতি
পদ্ধতিটি খুবই সহজ। আমাদের আছে একটি রেগুলার ভাষা L এবং একটি নির্ধারণমূলক সম্পূর্ণ অটোমেটন A = ⟨Q, Σ, δ, q0, F⟩, যা ভাষাটি গ্রহণ করে (যেকোনো সসীম অটোমেটনকে এমন অটোমেটনে রূপান্তর করা যায়)। L' গ্রহণকারী অটোমেটন A' গঠন করতে চূড়ান্ত ও অচূড়ান্ত স্টেটগুলো অদলবদল করি: A' = ⟨Q, Σ, δ, q0, Q ∖ F⟩। ব্যস, এটুকুই।
উদাহরণ
ধরি অটোমেটনটি এই:
ভাষাটির পূরক গ্রহণকারী অটোমেটন দেখতে এমন হতো:
তথ্যসূত্র
সূচিপত্র: রেগুলার ভাষার আবদ্ধতা ধর্ম, রেগুলার ভাষার সংযোগ, রেগুলার ভাষার ছেদ, রেগুলার ভাষার অন্তর, রেগুলার ভাষার পূরক, রেগুলার ভাষার সংযুক্তি, রেগুলার ভাষার ক্লোজার