Conjunctive grammar
સંયુગ્મ વ્યાકરણ એ ઔપચારિક ભાષાના સિદ્ધાંતમાં અભ્યાસ કરાયેલ ઔપચારિક વ્યાકરણનો એક વર્ગ છે. તેઓ વ્યાકરણના મૂળભૂત પ્રકાર, સંદર્ભ-મુક્ત વ્યાકરણને સંયોજન કામગીરી સાથે વિસ્તરે છે. સ્પષ્ટ સંયોજન ઉપરાંત, સંયુગ્મ વ્યાકરણ એક બિન-અંતિમ પ્રતીક માટે બહુવિધ નિયમો દ્વારા રજૂ કરાયેલ ગર્ભિત વિચ્છેદને મંજૂરી આપે છે, જે સંદર્ભ-મુક્ત વ્યાકરણમાં વ્યક્ત કરી શકાય તેવું એકમાત્ર તાર્કિક સંયોજક છે. સંયોજનનો ઉપયોગ, ખાસ કરીને, ભાષાઓના આંતરછેદને સ્પષ્ટ કરવા માટે થઈ શકે છે. બુલિયન વ્યાકરણ તરીકે ઓળખાતા સંયુગ્મ વ્યાકરણનું વધુ વિસ્તરણ વધુમાં સ્પષ્ટ નકારાત્મકતાને મંજૂરી આપે છે. સંયુગ્મ વ્યાકરણના નિયમો એવા સ્વરૂપના હોય છે જ્યાં બિન-અંતિમ હોય છે અને.., અને (અનુક્રમે અંતિમ અને બિન-અંતિમ પ્રતીકોના મર્યાદિત સમૂહો) માં પ્રતીકોથી બનેલા શબ્દમાળાઓ હોય છે. અનૌપચારિક રીતે, આવા નિયમ ભારપૂર્વક જણાવે છે કે દરેક શબ્દમાળા કે જે દ્વારા રજૂ કરાયેલ દરેક વાક્યરચના શરતોને સંતોષે છે, તેથી દ્વારા વ્યાખ્યાયિત શરતને સંતોષે છે. ઔપચારિક વ્યાખ્યા સંયુગ્મ વ્યાકરણને 4-ટુપલ દ્વારા વ્યાખ્યાયિત કરવામાં આવે છે જ્યાં એક મર્યાદિત સમૂહ હોય છે; દરેક તત્વને બિન-અંતિમ પ્રતીક અથવા ચલ કહેવામાં આવે છે. દરેક ચલ વાક્યમાં એક અલગ પ્રકારના શબ્દસમૂહ અથવા કલમનું પ્રતિનિધિત્વ કરે છે. ચલને કેટલીકવાર વાક્યરચના શ્રેણીઓ પણ કહેવામાં આવે છે. તે ટર્મિનલ્સનો એક મર્યાદિત સમૂહ છે, જે વાક્યની વાસ્તવિક સામગ્રી બનાવે છે. ટર્મિનલ્સનો સમૂહ એ વ્યાકરણ દ્વારા વ્યાખ્યાયિત ભાષાની મૂળાક્ષર છે. તે પ્રોડક્શન્સનો મર્યાદિત સમૂહ છે, અને કેટલાક માટે દરેક સ્વરૂપ છે. ના સભ્યોને વ્યાકરણના નિયમો અથવા રચનાઓ કહેવામાં આવે છે. તે પ્રારંભ ચલ (અથવા પ્રારંભ પ્રતીક) છે, જેનો ઉપયોગ સમગ્ર વાક્ય (અથવા કાર્યક્રમ) નું પ્રતિનિધિત્વ કરવા માટે થાય છે. તે એક તત્વ હોવું જોઈએ. એક જ લીટી પર એક જ ડાબી બાજુ માટે જમણી બાજુની તમામ બાજુઓને અલગ કરવા માટે | (પાઇપ પ્રતીક) નો ઉપયોગ કરીને સૂચિબદ્ધ કરવી સામાન્ય બાબત છે. નિયમો અને તેથી તરીકે લખી શકાય છે. સંયોજી વ્યાકરણ દ્વારા નિર્દિષ્ટ ભાષાની બે સમકક્ષ ઔપચારિક વ્યાખ્યાઓ અસ્તિત્વમાં છે. એક વ્યાખ્યા વ્યાકરણને જોડાણ, આંતરછેદ અને સંયોજન સાથે ભાષાના સમીકરણોની પ્રણાલી તરીકે રજૂ કરવા અને તેના ઓછામાં ઓછા ઉકેલને ધ્યાનમાં લેવા પર આધારિત છે. બીજી વ્યાખ્યા ચોમ્સ્કીની સંદર્ભ-મુક્ત વ્યાકરણની ઉત્પાદક વ્યાખ્યાને સામાન્ય બનાવે છે, જેમાં જોડાણ અને સંયોજન પર શબ્દોના પુનર્લેખનનો ઉપયોગ કરવામાં આવે છે. વ્યુત્પત્તિ દ્વારા વ્યાખ્યા કોઈપણ શબ્દમાળા માટે, આપણે કહીએ છીએ કે સીધી ઉપજ આપે છે, જેમ કે, જો ત્યાં કોઈ નિયમ હોય કે અને, અથવા ત્યાં એક શબ્દમાળા અસ્તિત્વમાં હોય જેમ કે અને. કોઈપણ શબ્દમાળા માટે આપણે કહીએ છીએ કે તે જનરેટ કરે છે, આ રીતે લખાય છે, જો એવું હોય તો. વ્યાકરણની ભાષા એ તે પેદા કરે છે તે તમામ શબ્દમાળાઓનો સમૂહ છે. ઉદાહરણ વ્યાકરણ, રચનાઓ સાથે,,,,, સંયોજનશીલ છે. એક લાક્ષણિક વ્યુત્પત્તિ એ છે કે તે બતાવી શકાય છે. ભાષા સંદર્ભ-મુક્ત નથી, જે સંદર્ભ-મુક્ત ભાષાઓ માટે પંપીંગ લેમ્મા દ્વારા સાબિત થાય છે. પાર્સિંગ એલ્ગોરિધમ્સ જો કે સંયુગ્મ વ્યાકરણની અભિવ્યક્ત શક્તિ સંદર્ભ-મુક્ત વ્યાકરણ કરતાં વધારે છે, તેમ છતાં સંયુગ્મ વ્યાકરણ કેટલાકને જાળવી રાખે છે. સૌથી અગત્યનું, મુખ્ય સંદર્ભ-મુક્ત પદચ્છેદન અલ્ગોરિધમ્સના સામાન્યીકરણ છે, જેમાં લીનિયર-ટાઇમ રિકર્સિવ ડિસેન્ટ, ક્યુબિક-ટાઇમ જનરલાઈઝ્ડ એલઆર, ક્યુબિક-ટાઇમ કોક-કસામી-યંગર, તેમજ વેલિયન્ટનું અલ્ગોરિધમ મેટ્રિક્સ ગુણાકાર જેટલું ઝડપી ચાલે છે. સૈદ્ધાંતિક ગુણધર્મો એ ગુણધર્મ કે જે સંદર્ભ-મુક્ત ભાષાઓ અથવા તેમના મર્યાદિત આંતરછેદો માટે પહેલેથી જ અનિર્ણાયક છે, તે સંયુક્ત વ્યાકરણ માટે પણ અનિર્ણાયક હોવો જોઈએ; તેમાં નીચેનાનો સમાવેશ થાય છેઃ ખાલીપણું, મર્યાદિતતા, નિયમિતતા, સંદર્ભ-સ્વતંત્રતા, સમાવેશ અને સમાનતા. સંયુગ્મ ભાષાઓનો પરિવાર જોડાણ, આંતરછેદ, સંયોજન અને ક્લેન સ્ટાર હેઠળ બંધ છે, પરંતુ સ્ટ્રિંગ હોમોમોર્ફિઝમ, ઉપસર્ગ, પ્રત્યય અને સબસ્ટ્રિંગ હેઠળ નહીં. પૂરક હેઠળ અને ε-મુક્ત સ્ટ્રિંગ હોમોમોર્ફિઝમ હેઠળ બંધ થવું એ હજુ પણ ખુલ્લી સમસ્યાઓ છે (2001 મુજબ). એક અક્ષરના મૂળાક્ષર પર વ્યાકરણની અભિવ્યક્તિની શક્તિ પર સંશોધન કરવામાં આવ્યું છે. આ કાર્યએ વધુ સામાન્ય સ્વરૂપના ભાષા સમીકરણોના અભ્યાસ માટે આધાર પૂરો પાડ્યો હતો. સિંક્રનાઇઝ્ડ અલ્ટરનેટિંગ પુશડાઉન ઓટોમેટા આઈઝિકોવિટ્ઝ અને કમિન્સ્કીએ સિંક્રનાઇઝ્ડ અલ્ટરનેટિંગ પુશડાઉન ઓટોમેટા (SAPDA) તરીકે ઓળખાતા પુશડાઉન ઓટોમેટા (PDA) નો એક નવો વર્ગ રજૂ કર્યો. જેમ બિનનિર્ધારણીય પી. ડી. એ. સંદર્ભ-મુક્ત વ્યાકરણની સમકક્ષ હોય છે તેવી જ રીતે તેમણે તેને સંયુગ્મ વ્યાકરણની સમકક્ષ સાબિત કર્યું. નોંધો સંદર્ભો બાહ્ય કડીઓ ટેકનિકલ અહેવાલ સંસ્કરણ (પી. ડી. એફ.) ઔપચારિક ભાષાઓ