Omega language
তাত্ত্বিক কম্পিউটার বিজ্ঞানের মধ্যে আনুষ্ঠানিক ভাষা তত্ত্বে, একটি অসীম শব্দ হল প্রতীকগুলির একটি অসীম দৈর্ঘ্যের ক্রম (বিশেষত, একটি ω-দৈর্ঘ্যের ক্রম) এবং একটি ω-ভাষা হল অসীম শব্দের একটি সেট। এখানে, ω প্রথম ক্রমিক সংখ্যাকে বোঝায়, প্রাকৃতিক সংখ্যার সেট। আনুষ্ঠানিক সংজ্ঞা ধরা যাক  নিষ্পাপ চিহ্নগুলির একটি সেট (অগত্যা সীমাবদ্ধ নয়)। আনুষ্ঠানিক ভাষা তত্ত্ব থেকে প্রমিত সংজ্ঞা অনুসরণ করে, с * হল с এর উপর সমস্ত সসীম শব্দের সমষ্টি। প্রতিটি সসীম শব্দের একটি দৈর্ঘ্য থাকে, যা একটি স্বাভাবিক সংখ্যা। n দৈর্ঘ্যের একটি শব্দ দেওয়া হলে, w কে সেট {0,1,., n − 1} → σ থেকে একটি ফাংশন হিসাবে দেখা যেতে পারে, যার মান i অবস্থানে প্রতীক দেয়। অসীম শব্দগুলি, বা ω-শব্দগুলি, একইভাবে থেকে σ পর্যন্ত ফাংশন হিসাবে দেখা যেতে পারে। নিষ্পত্তির উপর সমস্ত অসীম শব্দের সেটকে  নিষ্পত্তির দ্বারা চিহ্নিত করা হয়। সমস্ত সসীম এবং অসীম শব্দের সেটকে কখনও কখনও  নিষ্পত্তি বা  নিষ্পত্তি ω লেখা হয়। সুতরাং একটি ω-ভাষা L এর উপর σ হল σω এর একটি উপসেট। ক্রিয়াকলাপ ω-ভাষাগুলিতে সংজ্ঞায়িত কিছু সাধারণ ক্রিয়াকলাপ হ 'লঃ ছেদ এবং মিলন প্রদত্ত ω-ভাষাগুলি L এবং M, উভয়ই ω-ভাষা। বাম সংমিশ্রণ ধরা যাক L একটি ω-ভাষা এবং K শুধুমাত্র সীমাবদ্ধ শব্দের ভাষা। তারপর K কে বাম দিকে এবং শুধুমাত্র বাম দিকে L-এর সাথে যুক্ত করা যেতে পারে যাতে নতুন ω-ভাষা KL পাওয়া যায়। Omega (অসীম পুনরাবৃত্তি) স্বরলিপির ইঙ্গিত হিসাবে, অপারেশনটি সীমাবদ্ধ দৈর্ঘ্যের ভাষাগুলিতে ক্লেইন স্টার অপারেটরের অসীম সংস্করণ। একটি আনুষ্ঠানিক ভাষা L দেওয়া হলে, Lω হল L থেকে শব্দের সমস্ত অসীম ক্রমের ω-ভাষা; কার্যকরী দৃষ্টিতে, সমস্ত ফাংশনের। উপসর্গগুলি ধরা যাক w একটি ω-শব্দ। তারপর আনুষ্ঠানিক ভাষা প্রিফ (ডাব্লু)-এ ডাব্লু-এর প্রতিটি সসীম উপসর্গ থাকে। একটি সসীম দৈর্ঘ্যের ভাষা এল দেওয়া হলে, একটি ω-শব্দ ডাব্লু এল-এর সীমাতে থাকে যদি এবং শুধুমাত্র যদি একটি অসীম সেট হয়। অন্য কথায়, একটি নির্বিচারে বড় স্বাভাবিক সংখ্যা n-এর জন্য, L-এ এমন কিছু শব্দ নির্বাচন করা সর্বদা সম্ভব, যার দৈর্ঘ্য n-এর চেয়ে বেশি এবং যা w-এর উপসর্গ। L-এর সীমা ক্রিয়াকে Lδ বা লেখা যেতে পারে। ω-শব্দের মধ্যে দূরত্ব মেট্রিকের সংজ্ঞা অনুসারে সেটটি মেট্রিক স্পেসে তৈরি করা যেতে পারেঃ যেখানে |x। কে "x-এর দৈর্ঘ্য" (x-এ প্রতীকগুলির সংখ্যা) হিসাবে ব্যাখ্যা করা হয়, এবং inf হল বাস্তব সংখ্যার সেটগুলির উপর অসীম। যদি তা হয় তবে কোনও দীর্ঘতম উপসর্গ x এবং তাই নেই। প্রতিসাম্য স্পষ্ট। ট্রানজিটিভিটি এই সত্য থেকে আসে যে, যদি ডাব্লু এবং ভি-এর দৈর্ঘ্য এম এবং ভি-এর সর্বাধিক ভাগ করা উপসর্গ থাকে এবং ইউ-এর দৈর্ঘ্য এন-এর সর্বাধিক ভাগ করা উপসর্গ থাকে তবে ডাব্লু এবং ইউ-এর প্রথম অক্ষরগুলি অবশ্যই একই হতে হবে। অতএব, d একটি মেট্রিক। গুরুত্বপূর্ণ উপশ্রেণী ω-ভাষাগুলির সর্বাধিক ব্যবহৃত উপশ্রেণী হল ω-নিয়মিত ভাষাগুলির সমষ্টি, যা বুচি অটোমাটা দ্বারা স্বীকৃত হওয়ার দরকারী বৈশিষ্ট্য উপভোগ করে। সুতরাং ω-নিয়মিত ভাষা সদস্যতার সিদ্ধান্তের সমস্যাটি বুচি অটোমেটন ব্যবহার করে নির্ণয়যোগ্য এবং গণনা করা মোটামুটি সহজ। যদি ভাষাটি একটি সেটের পাওয়ার সেট হয় (যাকে "পারমাণবিক প্রস্তাবনা" বলা হয়) তবে ω-ভাষা একটি রৈখিক সময় বৈশিষ্ট্য, যা মডেল চেকিংয়ে অধ্যয়ন করা হয়। গ্রন্থপঞ্জি পেরিন, ডি. এবং পিন, জে. ই. "ইনফাইনাইট ওয়ার্ডসঃ অটোমেটা, সেমিগ্রুপস, লজিক অ্যান্ড গেমস"। বিশুদ্ধ ও ফলিত গণিত খণ্ড 141, এলসেভিয়ার, 2004। স্টাইগার, এল. "ω-ভাষাসমূহ"। জি. রোজেনবার্গ এবং এ. সালোমার সম্পাদক, হ্যান্ডবুক অফ ফরমাল ল্যাঙ্গুয়েজেস, ভলিউম 3, পৃষ্ঠা 339-387। স্প্রিঙ্গার-ভার্লাগ, বার্লিন, 1997। থমাস, ডব্লিউ. "অটোমাটা অন ইনফাইনাইট অবজেক্টস"। হ্যান্ডবুক অফ থিওরিটিক্যাল কম্পিউটার সায়েন্সের সম্পাদক, জ্যান ভ্যান লিউয়েন, ভলিউম বিঃ ফরমাল মডেলস অ্যান্ড সেম্যান্টিক্স, পৃষ্ঠাগুলি 133-192। এলসেভিয়ার সায়েন্স পাবলিশার্স, আমস্টারডাম, 1990। গণনার তত্ত্ব আনুষ্ঠানিক ভাষা