Omega-regular language
ω-வழக்கமான மொழிகள் என்பது வழக்கமான மொழிகளின் வரையறையை எல்லையற்ற சொற்களுக்கு பொதுமைப்படுத்தும் ω-மொழிகளின் ஒரு வகுப்பாகும். முறையான வரையறை ஒரு ω-மொழி L என்பது ω-வழக்கமான வடிவத்தைக் கொண்டிருந்தால், அதில் A என்பது வெற்று சரம் AB இல்லாத ஒரு வழக்கமான மொழி, வழக்கமான மொழி A இன் ஒருங்கிணைப்பு மற்றும் ஒரு ω-வழக்கமான மொழி B (BA நன்கு வரையறுக்கப்படவில்லை என்பதைக் கவனியுங்கள்) A மற்றும் B ஆகியவை ω-வழக்கமான மொழிகள் (இந்த விதியை பல முறை மட்டுமே இறுதியாகப் பயன்படுத்த முடியும்) Aω இன் கூறுகள் A இலிருந்து எண்ணற்ற பல முறை சொற்களை இணைப்பதன் மூலம் பெறப்படுகின்றன. A வழக்கமானதாக இருந்தால், Aω என்பது ω-வழக்கமானதாக இருக்க வேண்டிய அவசியமில்லை என்பதை நினைவில் கொள்க, ஏனெனில் A என்பது எடுத்துக்காட்டாக {ε}, வெற்று சரத்தை மட்டுமே கொண்ட தொகுப்பாக இருக்கலாம், இந்த விஷயத்தில் Aω = A, இது ஒரு ω-மொழி அல்ல, எனவே ஒரு ω-வழக்கமான மொழி அல்ல. இது ω-வழக்கமான மொழிகள் துல்லியமாக A1B1ω ≤ வடிவத்தின் ω-மொழிகள் என்ற வரையறையின் நேரடியான விளைவாகும். சில n க்கு ≤ anBnω, இதில் ஐஸ் மற்றும் பிஸ் வழக்கமான மொழிகள் மற்றும் பிஸ் வெற்று சரத்தைக் கொண்டிருக்கவில்லை. புச்சி தானியங்கி தேற்றத்திற்கு இணக்கம்ஃ ஒரு ω-மொழி ஒரு ω-வழக்கமான மொழியாக இருந்தால் மட்டுமே அது ஒரு புச்சி தானியங்கி மூலம் அங்கீகரிக்கப்படுகிறது. சான்றுஃ ஒவ்வொரு ω-வழக்கமான மொழியும் ஒரு நிர்ணயிக்கப்படாத புச்சி தானியங்கி மூலம் அங்கீகரிக்கப்படுகிறது; மொழிபெயர்ப்பு ஆக்கபூர்வமானது. ω-வழக்கமான மொழியின் வரையறைக்கு மேல் புச்சி தானியங்கி மற்றும் கட்டமைப்பு தூண்டலின் மூடல் பண்புகளைப் பயன்படுத்தி, கொடுக்கப்பட்ட ω-வழக்கமான மொழிக்கு ஒரு புச்சி தானியங்கி கட்டமைப்பை உருவாக்க முடியும் என்பதை எளிதாகக் காட்டலாம். மாறாக, கொடுக்கப்பட்ட புச்சி தானியங்கிக்கு, நாம் ஒரு ω-வழக்கமான மொழியை உருவாக்குகிறோம், பின்னர் இந்த மொழி A ஆல் அங்கீகரிக்கப்பட்டுள்ளது என்பதைக் காண்பிப்போம். ஒரு ω-வார்த்தைக்கு w = a1a2. w (i, j) என்பது ai + 1.aj-1aj இன் வரையறுக்கப்பட்ட பிரிவாக இருக்கட்டும். ஒவ்வொன்றிற்கும், ஒரு வழக்கமான மொழி Lq, q 'ஐ வரையறுக்கிறோம், இது வரையறுக்கப்பட்ட தானியங்கிகளால் ஏற்றுக்கொள்ளப்படுகிறது. லெம்மாஃ புச்சி தானியங்கி இயந்திரம் A மொழி ஆதாரத்தை அங்கீகரிக்கிறது என்று நாங்கள் கூறுகிறோம்ஃ சொல் மற்றும் q0, q1, q2,. என்பது W இல் A இன் ஏற்றுக்கொள்ளும் ஓட்டமாகும் என்று வைத்துக்கொள்வோம். எனவே, q0 இல் உள்ளது, மேலும் F இல் ஒரு நிலை இருக்க வேண்டும், இது ஏற்றுக்கொள்ளும் ஓட்டத்தில் எண்ணற்ற அடிக்கடி நிகழ்கிறது. i0, i1, i2 குறியீடுகளின் கண்டிப்பாக அதிகரித்து வரும் எல்லையற்ற வரிசையைத் தேர்ந்தெடுப்போம். அதாவது, அனைத்து k ≤ 0 க்கும். எனவே, மற்றும், அனைவருக்கும், எனவே, இதற்கு நேர்மாறாக, சிலருக்கு என்று வைத்துக்கொள்வோம், எனவே, ஒரு எல்லையற்ற மற்றும் கண்டிப்பாக அதிகரிக்கும் வரிசை i0, i1, i2 உள்ளது. அதாவது, அனைவருக்கும் Lq, q 'இன் வரையறையின்படி, ஒரு வரையறுக்கப்பட்ட ஓட்டம் உள்ளது. அனைத்து k ≤ 0 க்கும், ஒரு வரையறுக்கப்பட்ட ஓட்டம் உள்ளது முதல் வார்த்தை w (ik, ik + 1) வரை. இந்த கட்டுமானத்தின் மூலம், A இன் ஒரு ஓட்டம் உள்ளது, இது தொடங்கி அதில் எல்லையற்ற அடிக்கடி நிகழ்கிறது. எனவே, மோனடிக் இரண்டாவது வரிசை தர்க்கத்திற்கு சமமான புச்சி 1962 ஆம் ஆண்டில் ω-ஒழுங்குமுறை மொழிகள் துல்லியமாக S1S எனப்படும் ஒரு குறிப்பிட்ட மோனடிக் இரண்டாவது வரிசை தர்க்கத்தில் வரையறுக்கக்கூடியவை என்பதைக் காட்டியது. நூலியல் வொல்ப்காங் தாமஸ், "எல்லையற்ற பொருட்களின் மீது தானியங்கி". ஜான் வான் லீயுவென், ஆசிரியர், கோட்பாட்டு கணினி அறிவியலின் கையேடு, தொகுதி B: முறையான மாதிரிகள் மற்றும் சொற்பொருள், பக்கங்கள் 133-192. எல்செவியர் அறிவியல் வெளியீட்டாளர்கள், ஆம்ஸ்டர்டாம், 1990. முறையான மொழிகள்