Omega language
સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં ઔપચારિક ભાષા સિદ્ધાંતમાં, અનંત શબ્દ એ પ્રતીકોનો અનંત-લંબાઈનો ક્રમ (ખાસ કરીને, ω-લંબાઈનો ક્રમ) છે, અને ω-ભાષા એ અનંત શબ્દોનો સમૂહ છે. અહીં, ω એ પ્રથમ ક્રમિક સંખ્યા, કુદરતી સંખ્યાઓના સમૂહનો સંદર્ભ આપે છે. ઔપચારિક વ્યાખ્યા ચાલો σ એ પ્રતીકોનો સમૂહ હોવો જોઈએ (જરૂરી નથી કે તે મર્યાદિત હોય). ઔપચારિક ભાષા સિદ્ધાંતની પ્રમાણભૂત વ્યાખ્યાને અનુસરીને, σ * એ σ પરના તમામ મર્યાદિત શબ્દોનો સમૂહ છે. દરેક મર્યાદિત શબ્દની લંબાઈ હોય છે, જે એક પ્રાકૃતિક સંખ્યા છે. n લંબાઈના શબ્દને આપવામાં આવે તો, w ને {0,1,., n − 1} → σ સમૂહમાંથી એક વિધેય તરીકે જોઈ શકાય છે, જેની કિંમત i પર સ્થિતિ i પર પ્રતીક આપે છે. અનંત શબ્દો, અથવા ω-શબ્દો, એ જ રીતે ફંકશન તરીકે જોઈ શકાય છે. નિષ્પન્ન પરના તમામ અનંત શબ્દોનો સમૂહ  નિષ્પન્ન થાય છે. તમામ મર્યાદિત અને અનંત શબ્દોના સમૂહને કેટલીકવાર  નિષ્પન્ન અથવા  નિષ્પન્ન ω લખવામાં આવે છે. આમ ω-ભાષા L ઓવર σ એ σω નો સબસેટ છે. ω-ભાષાઓ પર વ્યાખ્યાયિત કેટલીક સામાન્ય કામગીરીઓ છેઃ આંતરછેદ અને જોડાણ આપેલ ω-ભાષાઓ L અને M, બંને અને ω-ભાષાઓ છે. ડાબું સંયોજન L એ ω-ભાષા હોવી જોઈએ, અને K એ માત્ર મર્યાદિત શબ્દોની ભાષા હોવી જોઈએ. પછી K ને ડાબી બાજુએ અને માત્ર ડાબી બાજુએ L સાથે જોડી શકાય છે જેથી નવી ω-ભાષા KL મળે. "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" "" ઔપચારિક ભાષા 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. ગણતરીનો સિદ્ધાંત ઔપચારિક ભાષાઓ