Pumping lemma for context-free languages
કોમ્પ્યુટર વિજ્ઞાનમાં, ખાસ કરીને ઔપચારિક ભાષા સિદ્ધાંતમાં, સંદર્ભ-મુક્ત ભાષાઓ માટે પંપીંગ લેમ્મા, જેને બાર-હિલેલ લેમ્મા તરીકે પણ ઓળખવામાં આવે છે, તે એક લેમ્મા છે જે તમામ સંદર્ભ-મુક્ત ભાષાઓ દ્વારા વહેંચાયેલ ગુણધર્મ આપે છે અને નિયમિત ભાષાઓ માટે પંપીંગ લેમ્માને સામાન્ય બનાવે છે. પંપીંગ લેમ્માનો ઉપયોગ વિરોધાભાસ દ્વારા સાબિતી બનાવવા માટે થઈ શકે છે કે કોઈ ચોક્કસ ભાષા સંદર્ભ-મુક્ત નથી. તેનાથી વિપરીત, પંપીંગ લેમ્મા એ ખાતરી આપવા માટે પૂરતું નથી કે ભાષા સંદર્ભ-મુક્ત છે; અન્ય જરૂરી શરતો છે, જેમ કે ઓગ્ડેનની લેમ્મા અથવા ઇન્ટરચેન્જ લેમ્મા. ઔપચારિક નિવેદન જો કોઈ ભાષા સંદર્ભ-મુક્ત હોય, તો ત્યાં અમુક પૂર્ણાંક હોય છે (જેને "પંપીંગ લંબાઈ" કહેવાય છે) જેમ કે તેમાંની દરેક સ્ટ્રિંગની લંબાઈ અથવા વધુ પ્રતીકો હોય છે (એટલે કે. સાથે) સબસ્ટ્રિંગ્સ સાથે લખી શકાય છે અને, જેમ કે બધા માટે 1., 2., અને 3. નીચે પમ્પિંગ લેમ્માની ઔપચારિક અભિવ્યક્તિ છે. અનૌપચારિક નિવેદન અને સમજૂતી સંદર્ભ-મુક્ત ભાષાઓ માટે પંપીંગ લેમ્મા (જેને આ લેખના બાકીના ભાગ માટે માત્ર "પંપીંગ લેમ્મા" કહેવામાં આવે છે) એ એવા ગુણધર્મનું વર્ણન કરે છે જે તમામ સંદર્ભ-મુક્ત ભાષાઓમાં હોવાની ખાતરી આપવામાં આવે છે. મિલકત એ ભાષામાં તમામ શબ્દમાળાની મિલકત છે જે ઓછામાં ઓછી લંબાઈની હોય છે, જ્યાં સતત હોય છે-જેને પંપીંગ લંબાઈ કહેવાય છે-જે સંદર્ભ-મુક્ત ભાષાઓ વચ્ચે બદલાય છે. કહો કે લંબાઈની એક સ્ટ્રિંગ છે જે ઓછામાં ઓછી ભાષામાં છે. પંપીંગ લેમ્મા જણાવે છે કે તેને પાંચ સબસ્ટ્રિંગ્સમાં વિભાજિત કરી શકાય છે, જ્યાં ખાલી નથી અને લંબાઈ વધુમાં વધુ હોય છે, જેમ કે પુનરાવર્તન અને સમાન સંખ્યામાં () in એક સ્ટ્રિંગ ઉત્પન્ન કરે છે જે હજુ પણ ભાષામાં છે. તે ઘણીવાર શૂન્ય વખત પુનરાવર્તન કરવા માટે ઉપયોગી છે, જે સ્ટ્રિંગમાંથી અને દૂર કરે છે. અને ની વધારાની નકલો સાથે "પંપીંગ અપ" કરવાની આ પ્રક્રિયા પંપીંગ લેમ્માને તેનું નામ આપે છે. મર્યાદિત ભાષાઓ (જે નિયમિત હોય છે અને તેથી સંદર્ભ-મુક્ત હોય છે) વત્તા એકમાં મહત્તમ શબ્દમાળા લંબાઈની બરાબર રાખીને પંપીંગ લેમ્માનું તુચ્છ રીતે પાલન કરે છે. આ લંબાઈના કોઈ તાર ન હોવાથી પંપીંગ લેમ્માનું ઉલ્લંઘન થતું નથી. લેમ્માનો ઉપયોગ પંપીંગ લેમ્માનો ઉપયોગ ઘણીવાર એ સાબિત કરવા માટે થાય છે કે આપેલ ભાષા બિન-સંદર્ભ-મુક્ત છે, તે દર્શાવીને કે આપખુદ રીતે લાંબી દોરીઓ તેમાં હોય છે જેને બહારની દોરીઓ ઉત્પન્ન કર્યા વિના "પંપ" કરી શકાતી નથી. ઉદાહરણ તરીકે, જો અનંત હોય પરંતુ તેમાં (અનંત) અંકગણિત પ્રગતિ ન હોય, તો તે સંદર્ભ-મુક્ત નથી. ખાસ કરીને, ન તો મુખ્ય સંખ્યાઓ કે ન તો વર્ગ સંખ્યાઓ સંદર્ભ-મુક્ત હોય છે. ઉદાહરણ તરીકે, વિરોધાભાસ દ્વારા સાબિતીમાં પંપીંગ લેમ્માનો ઉપયોગ કરીને ભાષાને બિન-સંદર્ભ-મુક્ત દર્શાવી શકાય છે. પ્રથમ, ધારો કે તે સંદર્ભ મુક્ત છે. પંપીંગ લેમ્મા દ્વારા, એક પૂર્ણાંક અસ્તિત્વમાં છે જે ભાષાની પંપીંગ લંબાઈ છે. અંદરની દોરીને ધ્યાનમાં લો. પંપીંગ લેમ્મા આપણને કહે છે કે તે સ્વરૂપમાં લખી શકાય છે, ક્યાં, અને સબસ્ટ્રિંગ્સ છે, જેમ કે, અને દરેક પૂર્ણાંક માટે. તેની પસંદગી અને હકીકત દ્વારા, તે સરળતાથી જોવામાં આવે છે કે સબસ્ટ્રિંગમાં બેથી વધુ અલગ પ્રતીકો હોઈ શકતા નથી. એટલે કે, આપણી પાસે પાંચ શક્યતાઓમાંથી એક છેઃ કેટલાક માટે. કેટલાક માટે અને કેટલાક માટે. કેટલાક માટે અને સાથે. કેટલાક માટે. દરેક કેસ માટે, તે સરળતાથી ચકાસવામાં આવે છે કે તેમાં કોઈપણ માટે દરેક અક્ષરની સમાન સંખ્યાઓ નથી. આમ, તેનું કોઈ સ્વરૂપ નથી. આ વ્યાખ્યાથી વિરોધાભાસી છે. તેથી, આપણી પ્રારંભિક ધારણા કે જે સંદર્ભ મુક્ત છે તે ખોટી હોવી જોઈએ. જ્યારે પંપીંગ લેમ્મા ઘણીવાર એ સાબિત કરવા માટે ઉપયોગી સાધન છે કે આપેલ ભાષા સંદર્ભ-મુક્ત નથી, તે સંદર્ભ-મુક્ત ભાષાઓની સંપૂર્ણ લાક્ષણિકતા આપતું નથી. જો કોઈ ભાષા પંપીંગ લેમ્મા દ્વારા આપવામાં આવેલી શરતને સંતોષતી નથી, તો આપણે સ્થાપિત કર્યું છે કે તે સંદર્ભ-મુક્ત નથી. બીજી બાજુ, એવી ભાષાઓ છે જે સંદર્ભ-મુક્ત નથી, પરંતુ તેમ છતાં પંપીંગ લેમ્મા દ્વારા આપવામાં આવેલી શરતને સંતોષે છે, ઉદાહરણ તરીકે ઉદાહરણ તરીકે. જે ≤ 1 એ ફક્ત બી નો સમાવેશ કરવાનું પસંદ કરે છે, કારણ કે તેમાં ફક્ત એ નો સમાવેશ થાય છે; બંને કિસ્સાઓમાં તમામ પમ્પ કરેલા તાર હજુ પણ એલ માં છે. પંપીંગ લેમ્માના પુરોગામીનો ઉપયોગ 1960 માં શાઈનબર્ગ દ્વારા સંદર્ભ-મુક્ત નથી તે સાબિત કરવા માટે કરવામાં આવ્યો હતો. સંદર્ભો-વિભાગ 1.4: અનિયમિત ભાષાઓ, પૃષ્ઠો. 77-83 માં પુનઃમુદ્રિત. વિભાગ 2.3: બિન-સંદર્ભ-મુક્ત ભાષાઓ, પૃષ્ઠ. 115-119. ઔપચારિક ભાષાઓ લેમ્માસ