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 সালে নোম চমস্কি উৎপাদক ক্ষমতার ধারণাটি প্রবর্তন করেন। নোটস রেফারেন্স আনুষ্ঠানিক ভাষাগুলি