Omega-regular language
ω-નિયમિત ભાષાઓ એ ω-ભાષાઓનો એક વર્ગ છે જે નિયમિત ભાષાઓની વ્યાખ્યાને અનંત શબ્દોમાં સામાન્ય બનાવે છે. ઔપચારિક વ્યાખ્યા એક ω-ભાષા L એ ω-નિયમિત છે જો તેમાં Aω સ્વરૂપ હોય જ્યાં A એક નિયમિત ભાષા છે જેમાં ખાલી શબ્દમાળા AB નથી, નિયમિત ભાષા A નું સંયોજન અને ω-નિયમિત ભાષા B (નોંધ કરો કે BA સારી રીતે વ્યાખ્યાયિત નથી) A ≤ B જ્યાં A અને B એ ω-નિયમિત ભાષાઓ છે (આ નિયમ ફક્ત મર્યાદિત રીતે ઘણી વખત લાગુ કરી શકાય છે) Aω ના ઘટકો A માંથી શબ્દોને અનંત ઘણી વખત સંયોજિત કરીને મેળવવામાં આવે છે. નોંધ લો કે જો A નિયમિત હોય, તો Aω એ ω-નિયમિત હોવું જરૂરી નથી, કારણ કે A ઉદાહરણ તરીકે {ε} હોઈ શકે છે, જે ફક્ત ખાલી શબ્દમાળા ધરાવતો સમૂહ છે, આ કિસ્સામાં Aω = A, જે ω-ભાષા નથી અને તેથી ω-નિયમિત ભાષા નથી. તે વ્યાખ્યાનું સીધું પરિણામ છે કે ω-નિયમિત ભાષાઓ ચોક્કસપણે A1B1ω ≤ સ્વરૂપની ω-ભાષાઓ છે. ≤ anBnω અમુક n માટે, જ્યાં એઇસ અને બિસ નિયમિત ભાષાઓ છે અને બિસમાં ખાલી શબ્દમાળા નથી. બુચી ઓટોમેટન પ્રમેયની સમકક્ષતાઃ ω-ભાષાને બુચી ઓટોમેટન દ્વારા ત્યારે જ ઓળખવામાં આવે છે જ્યારે તે ω-નિયમિત ભાષા હોય. પુરાવોઃ દરેક ω-નિયમિત ભાષાને બિનનિર્ધારણીય બુચી ઓટોમેટન દ્વારા ઓળખવામાં આવે છે; અનુવાદ રચનાત્મક છે. ω-નિયમિત ભાષાની વ્યાખ્યા પર બુચી ઓટોમેટા અને માળખાકીય પ્રેરણાના બંધ ગુણધર્મોનો ઉપયોગ કરીને, તે સરળતાથી બતાવી શકાય છે કે કોઈપણ ω-નિયમિત ભાષા માટે બુચી ઓટોમેટનનું નિર્માણ કરી શકાય છે. તેનાથી વિપરીત, આપેલ બુચી ઓટોમેટન માટે, આપણે ω-નિયમિત ભાષા બનાવીએ છીએ અને પછી આપણે બતાવીશું કે આ ભાષા A દ્વારા ઓળખાય છે. ω-શબ્દ માટે ડબલ્યુ = એ1એ2. ચાલો ડબલ્યુ (આઇ, જે) એ ડબલ્યુ નો મર્યાદિત ભાગ એઆઇ + <આઇડી1> છે. દરેક માટે, આપણે નિયમિત ભાષા એલક્યૂ, ક્યૂ 'વ્યાખ્યાયિત કરીએ છીએ જે મર્યાદિત ઓટોમેટન દ્વારા સ્વીકારવામાં આવે છે. લેમ્માઃ અમે દાવો કરીએ છીએ કે બુચી ઓટોમેટન એ ભાષાના પુરાવાને ઓળખે છેઃ ધારો કે શબ્દ અને q0, q1, q2,. એ ડબલ્યુ પર A નો સ્વીકાર્ય રન છે. તેથી, q0 અંદર છે અને F માં એવી સ્થિતિ હોવી જોઈએ કે જે સ્વીકાર્ય રનમાં અનંત વાર થાય છે. ચાલો અનુક્રમણિકાઓ i0, i1, i2 નો સખત રીતે વધતો અનંત ક્રમ પસંદ કરીએ. જેમ કે, બધા k ≤ 0 માટે, છે. તેથી, અને, બધા માટે તેથી, તેનાથી વિપરીત, ધારો કે કેટલાક માટે અને તેથી, એક અનંત અને સખત રીતે વધતો ક્રમ i0, i1, i2 છે. જેમ કે અને, બધા માટે Lq, q 'ની વ્યાખ્યા અનુસાર, શબ્દ w (0, i0) પર થી એક મર્યાદિત રન છે. બધા k ≤ 0 માટે, શબ્દ w (ik, ik + 1) થી એક મર્યાદિત રન છે. આ રચના દ્વારા, A નો એક રન છે, જે શરૂ થાય છે અને જેમાં અનંત વાર થાય છે. એટલે, તા. મોનાડિક બીજા ક્રમના તર્ક સાથે સમાનતા બુચીએ 1962માં દર્શાવ્યું હતું કે ω-નિયમિત ભાષાઓ ચોક્કસપણે S1S તરીકે ઓળખાતા ચોક્કસ મોનાડિક બીજા ક્રમના તર્કમાં વ્યાખ્યાયિત કરી શકાય તેવી ભાષાઓ છે. ગ્રંથસૂચિ વોલ્ફગેંગ થોમસ, "અનંત પદાર્થો પર ઓટોમેટા". હેન્ડબુક ઓફ થિયોરેટિકલ કોમ્પ્યુટર સાયન્સના સંપાદક, જાન વાન લીઉવેનમાં, ખંડ બીઃ ઔપચારિક નમૂનાઓ અને સિમેન્ટિક્સ, પૃષ્ઠો 133-192. એલ્સેવિયર સાયન્સ પબ્લિશર્સ, એમ્સ્ટરડેમ, 1990. ઔપચારિક ભાષાઓ