Omega-regular language
ω-নিয়মিত ভাষাগুলি হল ω-ভাষাগুলির একটি শ্রেণী যা নিয়মিত ভাষার সংজ্ঞাকে অসীম শব্দের মধ্যে সাধারণীকরণ করে। আনুষ্ঠানিক সংজ্ঞা একটি ω-ভাষা L হল ω-নিয়মিত যদি এর Aω রূপ থাকে যেখানে A একটি নিয়মিত ভাষা যেখানে খালি স্ট্রিং AB নেই, একটি নিয়মিত ভাষা A এবং একটি ω-নিয়মিত ভাষা B-এর সংমিশ্রণ (লক্ষ্য করুন যে BA ভালভাবে সংজ্ঞায়িত নয়) A ≤ B যেখানে A এবং B হল ω-নিয়মিত ভাষা (এই নিয়মটি কেবলমাত্র সীমিতভাবে অনেকবার প্রয়োগ করা যেতে পারে) Aω-এর উপাদানগুলি A থেকে শব্দগুলিকে অসীমভাবে বহুবার সংহত করে প্রাপ্ত হয়। লক্ষ্য করুন যে যদি A নিয়মিত হয়, তবে Aω অপরিহার্যভাবে ω-নিয়মিত নয়, কারণ A উদাহরণস্বরূপ {ε} হতে পারে, শুধুমাত্র খালি স্ট্রিং ধারণকারী সেট, এই ক্ষেত্রে Aω = A, যা একটি ω-ভাষা নয় এবং তাই একটি ω-নিয়মিত ভাষা নয়। এটি এই সংজ্ঞার একটি সোজাসুজি পরিণতি যে ω-নিয়মিত ভাষাগুলি সঠিকভাবে A1B1ω ≤. ≤ anBnω ফর্মের ω-ভাষাগুলি কিছু n-এর জন্য, যেখানে আইস এবং বিস নিয়মিত ভাষা এবং বিস খালি স্ট্রিং ধারণ করে না। বুচি অটোমেটন উপপাদ্যের সমতুল্যঃ একটি ω-ভাষা বুচি অটোমেটন দ্বারা স্বীকৃত হয় যদি এবং শুধুমাত্র যদি এটি একটি ω-নিয়মিত ভাষা হয়। প্রমাণঃ প্রতিটি ω-নিয়মিত ভাষা একটি অনির্ধারিত বুচি অটোমেটন দ্বারা স্বীকৃত; অনুবাদটি গঠনমূলক। ω-নিয়মিত ভাষার সংজ্ঞার উপর বুচি অটোমাটার ক্লোজার বৈশিষ্ট্য এবং কাঠামোগত আনয়ন ব্যবহার করে, এটি সহজেই দেখানো যেতে পারে যে কোনও প্রদত্ত ω-নিয়মিত ভাষার জন্য একটি বুচি অটোমেটন তৈরি করা যেতে পারে। বিপরীতভাবে, একটি প্রদত্ত বুচি অটোমেটনের জন্য, আমরা একটি ω-নিয়মিত ভাষা তৈরি করি এবং তারপর আমরা দেখাব যে এই ভাষাটি এ দ্বারা স্বীকৃত। একটি ω-শব্দের জন্য ডাব্লু = এ1এ2. ধরা যাক ডাব্লু (আই, জে) ডাব্লু-এর সীমাবদ্ধ বিভাগ এআই + 1.aj-1aj। প্রতিটির জন্য, আমরা একটি নিয়মিত ভাষা এলকিউ, কিউ 'সংজ্ঞায়িত করি যা সীমাবদ্ধ অটোমেটন দ্বারা গৃহীত হয়। লেম্মাঃ আমরা দাবি করি যে বুচি অটোমেটন এ ভাষার প্রমাণকে স্বীকৃতি দেয়ঃ ধরা যাক শব্দ এবং q0, q1, q2,. ডাব্লু-এর উপর A-এর একটি গ্রহণযোগ্য রান। অতএব, q0 রয়েছে এবং অবশ্যই F-এ এমন একটি অবস্থা থাকতে হবে যা গ্রহণযোগ্য রানের মধ্যে অসীমভাবে প্রায়শই ঘটে। আসুন i0, i1, i2 সূচকগুলির কঠোরভাবে ক্রমবর্ধমান অসীম ক্রমটি বেছে নেওয়া যাক. যাতে, সমস্ত k ≤ 0-এর জন্য, হয়। অতএব, এবং, সকলের জন্য, অতএব, বিপরীতভাবে, ধরুন কারো কারো জন্য এবং অতএব, একটি অসীম এবং কঠোরভাবে ক্রমবর্ধমান ক্রম i0, i1, i2 রয়েছে. যেমন এবং, সকলের জন্য। সমস্ত k ≤ 0-এর জন্য, শব্দ w (ik, ik + 1) থেকে একটি সীমাবদ্ধ রান রয়েছে। এই গঠন দ্বারা, এ-এর একটি রান রয়েছে, যা থেকে শুরু হয় এবং যা অসীমভাবে প্রায়শই ঘটে। তাই,। মনাডিক দ্বিতীয়-ক্রম যুক্তির সমতুল্য বুচি 1962 সালে দেখিয়েছিলেন যে ω-নিয়মিত ভাষাগুলি এস1এস নামক একটি নির্দিষ্ট মনাডিক দ্বিতীয়-ক্রম যুক্তিতে সুনির্দিষ্টভাবে সংজ্ঞায়িত করা যায়। গ্রন্থপঞ্জি ওল্ফগ্যাং থমাস, "অসীম বস্তুর উপর অটোমেটা"। হ্যান্ডবুক অফ থিওরিটিক্যাল কম্পিউটার সায়েন্সের সম্পাদক জ্যান ভ্যান লিউয়েন খণ্ড বিঃ ফরমাল মডেলস অ্যান্ড সেম্যান্টিক্স, পৃষ্ঠাগুলি 133-192-এ লিখেছেন। এলসেভিয়ার সায়েন্স পাবলিশার্স, আমস্টারডাম, 1990। আনুষ্ঠানিক ভাষাসমূহ