Equivalence (formal languages)
ઔપચારિક ભાષા સિદ્ધાંતમાં, બે વ્યાકરણની નબળી સમાનતાનો અર્થ એ છે કે તેઓ સમાન શબ્દમાળાઓ ઉત્પન્ન કરે છે, એટલે કે. કે તેઓ જે ઔપચારિક ભાષા ઉત્પન્ન કરે છે તે સમાન છે. સંકલન સિદ્ધાંતમાં કલ્પનાને મજબૂત (અથવા માળખાકીય) સમાનતાથી અલગ પાડવામાં આવે છે, જેનો વધારાનો અર્થ એ છે કે બે પાર્સ વૃક્ષો વ્યાજબી રીતે સમાન છે જેમાં સમાન સિમેન્ટીક અર્થઘટન બંનેને સોંપી શકાય છે. વિજય-શંકર અને વીર (1994) દર્શાવે છે કે રેખીય અનુક્રમિત વ્યાકરણ, સંયુક્ત શ્રેણીબદ્ધ વ્યાકરણ, વૃક્ષ-સંલગ્ન વ્યાકરણ અને મુખ્ય વ્યાકરણ નબળી રીતે સમકક્ષ ઔપચારિકતાઓ છે, જેમાં તેઓ બધા સમાન શબ્દમાળા ભાષાઓને વ્યાખ્યાયિત કરે છે. બીજી બાજુ, જો બે વ્યાકરણ વ્યુત્પત્તિ વૃક્ષોનો સમાન સમૂહ ઉત્પન્ન કરે છે (અથવા વધુ સામાન્ય રીતે, અમૂર્ત વાક્યરચના પદાર્થોનો સમાન સમૂહ), તો પછી બે વ્યાકરણ મજબૂત રીતે સમકક્ષ છે. ચોમ્સ્કી (1963) મજબૂત સમાનતાની કલ્પનાનો પરિચય આપે છે, અને દલીલ કરે છે કે વ્યાકરણની ઔપચારિકતાઓની સરખામણી કરતી વખતે માત્ર મજબૂત સમાનતા જ સુસંગત છે. કોર્નાઈ અને પુલ્લમ (1990) અને મિલર (1994) મજબૂત સમાનતાની શુદ્ધ કલ્પના પ્રસ્તુત કરે છે જે વિવિધ ઔપચારિકતાઓ દ્વારા આપવામાં આવેલા વાક્યરચના વિશ્લેષણ વચ્ચે સમરૂપ સંબંધો માટે પરવાનગી આપે છે. યોશિનાગા, મિયાઓ અને ત્સુજી (2002) એ પુરાવો આપે છે કે કોઈપણ એલટીએજી ઔપચારિકતા માટે, મજબૂત સમકક્ષ એચપીએસજી છે. સંદર્ભ-મુક્ત વ્યાકરણનું ઉદાહરણ એક ઉદાહરણ તરીકે, બેકસ-નૌર સ્વરૂપમાં આપવામાં આવેલા નીચેના બે સંદર્ભ-મુક્ત વ્યાકરણને ધ્યાનમાં લોઃ <અભિવ્યક્તિ>:: = <અભિવ્યક્તિ> + "<અભિવ્યક્તિ> | <અભિવ્યક્તિ>-" <અભિવ્યક્તિ> | <અભિવ્યક્તિ> "*" <અભિવ્યક્તિ> | <અભિવ્યક્તિ> | "x" | "y" | "z" | "1" | "2" | "3" | "(" <અભિવ્યક્તિ> ")" <અભિવ્યક્તિ>:: = <શબ્દ> | <અભિવ્યક્તિ> "+" <શબ્દ> | <અભિવ્યક્તિ> "-" <પદ> <પદ>:: = <પરિબળ> તમામ અંકગણિત અભિવ્યક્તિઓનો સમૂહ જે ચલ "x", "y", "z", અચળાંકો "1", "2", "3", ઓપરેટરો "+", "-", "*", "/", અને કૌંસ "(" અને ")" માંથી બનાવી શકાય છે. જો કે, બીજા વ્યાકરણનું નક્કર વાક્યરચના વૃક્ષ હંમેશા કામગીરીના સામાન્ય ક્રમને પ્રતિબિંબિત કરે છે, જ્યારે પ્રથમ વ્યાકરણના વૃક્ષની જરૂર નથી. ઉદાહરણ તરીકે શબ્દમાળા "1 + 2 * 3", ચિત્રનો જમણો ભાગ બીજા વ્યાકરણ સાથે તેના અનન્ય પાર્સ વૃક્ષને બતાવે છે; આ વૃક્ષનું પોસ્ટફિક્સ ક્રમમાં મૂલ્યાંકન કરવાથી યોગ્ય મૂલ્ય મળશે, 7. તેનાથી વિપરીત, ડાબી બાજુનો ચિત્ર ભાગ પ્રથમ વ્યાકરણ સાથે તે શબ્દમાળા માટે એક પાર્સ ટ્રી બતાવે છે; તેને પોસ્ટફિક્સ ક્રમમાં મૂલ્યાંકન કરવાથી 9 મળશે. કારણ કે બીજું વ્યાકરણ ડાબા ચિત્રના ભાગને અનુરૂપ વૃક્ષ ઉત્પન્ન કરી શકતું નથી, જ્યારે પ્રથમ વ્યાકરણ કરી શકે છે, બંને વ્યાકરણ મજબૂત રીતે સમકક્ષ નથી. ભાષાવિજ્ઞાનમાં, વ્યાકરણની નબળી ઉત્પાદક ક્ષમતાને તેના દ્વારા ઉત્પન્ન થયેલ તમામ તારોના સમૂહ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે, જ્યારે વ્યાકરણની મજબૂત ઉત્પાદક ક્ષમતા તેના દ્વારા ઉત્પન્ન થયેલ "માળખાકીય વર્ણનો" ના સમૂહને સંદર્ભિત કરે છે. પરિણામે, બે વ્યાકરણને નબળા સમકક્ષ ગણવામાં આવે છે જો તેમની નબળી ઉત્પાદક ક્ષમતાઓ એક સાથે હોય; મજબૂત સમાનતા માટે સમાન. ઉત્પાદક ક્ષમતાની કલ્પના નોઆમ ચોમ્સ્કી દ્વારા 1963માં રજૂ કરવામાં આવી હતી. નોંધો સંદર્ભો ઔપચારિક ભાષાઓ