Parikh's theorem
સૈદ્ધાંતિક કોમ્પ્યુટર વિજ્ઞાનમાં પરીખનો પ્રમેય કહે છે કે જો કોઈ વ્યક્તિ સંદર્ભ-મુક્ત ભાષામાં દરેક અંતિમ પ્રતીકની ઘટનાઓની સંખ્યાને તેમના ક્રમને ધ્યાનમાં લીધા વિના જુએ, તો તે ભાષા નિયમિત ભાષાથી અવિભાજ્ય છે. તે નક્કી કરવા માટે ઉપયોગી છે કે આપેલ સંખ્યાબંધ ટર્મિનલ્સ સાથેના શબ્દમાળાઓ સંદર્ભ-મુક્ત વ્યાકરણ દ્વારા સ્વીકારવામાં આવતા નથી. તે સૌપ્રથમ 1961માં રોહિત પરીખે સાબિત કર્યું હતું અને 1966માં ફરીથી પ્રકાશિત થયું હતું. વ્યાખ્યાઓ અને ઔપચારિક નિવેદન એક મૂળાક્ષર હોવું જોઈએ. શબ્દના પારિખ વેક્ટરને કાર્ય તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જે શબ્દમાં અક્ષરની ઘટનાઓની સંખ્યાને સૂચવે છે. જો તે કેટલાક વેક્ટરના સ્વરૂપમાં હોય તો તેનો સબસેટ રેખીય હોવાનું કહેવાય છે. ના ઉપગણને અર્ધ-રેખીય કહેવામાં આવે છે જો તે મર્યાદિત રીતે ઘણા રેખીય ઉપગણોનું જોડાણ હોય. ટૂંકમાં, સંદર્ભ-મુક્ત ભાષાઓ અને નિયમિત ભાષાઓની છબી સમાન છે, અને તે અર્ધરેખીય સમૂહોના સમૂહની બરાબર છે. બે ભાષાઓ પરિવર્તનીય રીતે સમકક્ષ હોવાનું કહેવાય છે જો તેમની પાસે પારિખ વેક્ટરનો સમાન સમૂહ હોય. આમ, દરેક સંદર્ભ-મુક્ત ભાષા પરિવર્તનીય રીતે અમુક નિયમિત ભાષાની સમકક્ષ હોય છે. પુરાવો બીજો ભાગ સાબિત કરવા માટે સરળ છે. પ્રથમ ભાગ ઓછો સરળ છે. નીચેના પુરાવાનો શ્રેય ગોલ્ડસ્ટીનને આપવામાં આવે છે. પ્રથમ આપણે સંદર્ભ-મુક્ત ભાષાઓ માટે પંપીંગ લેમ્માને થોડું મજબૂત કરવાની જરૂર છેઃ સાબિતી અનિવાર્યપણે પ્રમાણભૂત પંપીંગ લેમ્મા જેવી જ છેઃ ટૂંકી વ્યુત્પત્તિ વૃક્ષમાં સૌથી લાંબા માર્ગમાં કેટલાક બિન-અંતિમ પ્રતીકની નકલો શોધવા માટે કબૂતર છિદ્ર સિદ્ધાંતનો ઉપયોગ કરો. બંધાયેલ ભાષાઓને મજબૂત બનાવવી જો અમુક નિશ્ચિત શબ્દો માટે હોય તો ભાષા બંધાયેલ હોય છે. ગિન્સબર્ગ અને સ્પાનિયરે બંધાયેલ ભાષાઓ માટે પારિખના પ્રમેયની જેમ જ જરૂરી અને પર્યાપ્ત શરત આપી હતી. રેખીય સમૂહને સ્તરીકૃત કહો, જો દરેક વેક્ટર માટે તેની વ્યાખ્યામાં એવો ગુણધર્મ હોય કે તેમાં મહત્તમ બે બિન-શૂન્ય કોઓર્ડિનેટ્સ હોય, અને દરેક માટે જો દરેક વેક્ટરમાં અનુક્રમે બે બિન-શૂન્ય કોઓર્ડિનેટ્સ હોય, અને, તો તેમનો ક્રમ નથી. અર્ધ-રેખીય સમૂહને સ્તરીકૃત કરવામાં આવે છે જો તે મર્યાદિત રીતે ઘણા સ્તરીકૃત રેખીય ઉપગણોનું જોડાણ હોય. મહત્વ આ પ્રમેયમાં બહુવિધ અર્થઘટનો છે. તે દર્શાવે છે કે સિંગલટન મૂળાક્ષર પર સંદર્ભ-મુક્ત ભાષા નિયમિત ભાષા હોવી જોઈએ અને કેટલીક સંદર્ભ-મુક્ત ભાષાઓમાં માત્ર અસ્પષ્ટ વ્યાકરણ હોઈ શકે છે. આવી ભાષાઓને સ્વાભાવિક રીતે અસ્પષ્ટ ભાષાઓ કહેવામાં આવે છે. ઔપચારિક વ્યાકરણના દ્રષ્ટિકોણથી, આનો અર્થ એ છે કે કેટલાક અસ્પષ્ટ સંદર્ભ-મુક્ત વ્યાકરણને સમકક્ષ સ્પષ્ટ સંદર્ભ-મુક્ત વ્યાકરણમાં રૂપાંતરિત કરી શકાતા નથી. સંદર્ભો ઔપચારિક ભાષાઓ