Parikh's theorem
তাত্ত্বিক কম্পিউটার বিজ্ঞানে পারিখের উপপাদ্য বলে যে, যদি কেউ শুধুমাত্র প্রসঙ্গ-মুক্ত ভাষায় প্রতিটি টার্মিনাল প্রতীকের ঘটনার সংখ্যা দেখে, তাদের ক্রম বিবেচনা না করে, তবে ভাষাটি একটি নিয়মিত ভাষা থেকে আলাদা করা যায় না। এটি সিদ্ধান্ত নেওয়ার জন্য দরকারী যে নির্দিষ্ট সংখ্যক টার্মিনাল সহ স্ট্রিং একটি প্রসঙ্গ-মুক্ত ব্যাকরণ দ্বারা গৃহীত হয় না। এটি প্রথম 1961 সালে রোহিত পারিখ দ্বারা প্রমাণিত হয় এবং 1966 সালে পুনরায় প্রকাশিত হয়। সংজ্ঞা এবং আনুষ্ঠানিক বিবৃতি একটি বর্ণমালা হতে দিন। একটি শব্দের পারিখ ভেক্টরকে ফাংশন হিসাবে সংজ্ঞায়িত করা হয়, যেখানে শব্দের অক্ষরের ঘটনার সংখ্যা বোঝায়। এর একটি উপসেটকে রৈখিক বলা হয় যদি এটি কিছু ভেক্টরের আকারের হয়। এর একটি উপসেটকে আধা-রৈখিক বলা হয় যদি এটি সীমাবদ্ধভাবে অনেক রৈখিক উপসেটগুলির একটি ইউনিয়ন হয়। সংক্ষেপে, প্রসঙ্গ-মুক্ত ভাষা এবং নিয়মিত ভাষার চিত্র একই, এবং এটি অর্ধরেখার সেটের সেটের সমান। দুটি ভাষাকে বিনিময়গতভাবে সমতুল্য বলা হয় যদি তাদের পারিখ ভেক্টরের একই সেট থাকে। সুতরাং, প্রতিটি প্রসঙ্গ-মুক্ত ভাষা বিনিময়গতভাবে কিছু নিয়মিত ভাষার সমতুল্য। প্রমাণ দ্বিতীয় অংশটি প্রমাণ করা সহজ। প্রথম অংশটি কম সহজ। নিম্নলিখিত প্রমাণটি গোল্ডস্টাইনকে দেওয়া হয়েছে। প্রথমে আমাদের প্রসঙ্গ-মুক্ত ভাষাগুলির জন্য পাম্পিং লেম্মার একটি ছোট শক্তিশালীকরণ প্রয়োজনঃ প্রমাণটি মূলত স্ট্যান্ডার্ড পাম্পিং লেম্মার মতোইঃ ক্ষুদ্রতম ব্যুৎপত্তি গাছের দীর্ঘতম পথে কিছু অ-প্রান্তিক প্রতীকের অনুলিপি খুঁজে পেতে পায়রা ছিদ্র নীতি ব্যবহার করুন। সীমাবদ্ধ ভাষার জন্য শক্তিশালীকরণ একটি ভাষা সীমাবদ্ধ যদি কিছু নির্দিষ্ট শব্দের জন্য হয়। গিন্সবার্গ এবং স্প্যানিয়ার সীমাবদ্ধ ভাষার জন্য পারিখের উপপাদ্যের মতো একটি প্রয়োজনীয় এবং পর্যাপ্ত শর্ত দিয়েছিলেন। একটি রৈখিক সেটকে স্তরীভূত বলুন, যদি তার সংজ্ঞায় প্রতিটি ভেক্টরের বৈশিষ্ট্য থাকে যে এটির সর্বাধিক দুটি অ-শূন্য স্থানাঙ্ক রয়েছে, এবং প্রত্যেকের জন্য যদি প্রতিটি ভেক্টরের দুটি অ-শূন্য স্থানাঙ্ক থাকে, এবং, যথাক্রমে, তবে তাদের ক্রম নয়। একটি আধা-রৈখিক সেটকে স্তরায়িত করা হয় যদি এটি সীমাবদ্ধভাবে অনেক স্তরযুক্ত রৈখিক উপসেটগুলির একটি ইউনিয়ন হয়। তাৎপর্য উপপাদ্যটির একাধিক ব্যাখ্যা রয়েছে। এটি দেখায় যে একটি সিঙ্গলটন বর্ণমালার উপর একটি প্রসঙ্গ-মুক্ত ভাষা অবশ্যই একটি নিয়মিত ভাষা হতে হবে এবং কিছু প্রসঙ্গ-মুক্ত ভাষায় শুধুমাত্র দ্ব্যর্থহীন ব্যাকরণ থাকতে পারে। এই ধরনের ভাষাগুলিকে সহজাতভাবে দ্ব্যর্থহীন ভাষা বলা হয়। আনুষ্ঠানিক ব্যাকরণের দৃষ্টিকোণ থেকে, এর অর্থ হল যে কিছু দ্ব্যর্থহীন প্রসঙ্গ-মুক্ত ব্যাকরণকে সমতুল্য দ্ব্যর্থহীন প্রসঙ্গ-মুক্ত ব্যাকরণে রূপান্তরিত করা যায় না। রেফারেন্স আনুষ্ঠানিক ভাষাসমূহ