Pumping lemma for context-free languages
কম্পিউটার বিজ্ঞানে, বিশেষত আনুষ্ঠানিক ভাষা তত্ত্বে, প্রসঙ্গ-মুক্ত ভাষাগুলির জন্য পাম্পিং লেম্মা, যা বার-হিলেল লেম্মা নামেও পরিচিত, একটি লেম্মা যা সমস্ত প্রসঙ্গ-মুক্ত ভাষাগুলির দ্বারা ভাগ করা একটি বৈশিষ্ট্য দেয় এবং নিয়মিত ভাষার জন্য পাম্পিং লেম্মাকে সাধারণীকরণ করে। পাম্পিং লেম্মা একটি নির্দিষ্ট ভাষা প্রসঙ্গ-মুক্ত নয় এমন দ্বন্দ্ব দ্বারা প্রমাণ তৈরি করতে ব্যবহার করা যেতে পারে। বিপরীতভাবে, পাম্পিং লেম্মা কোনও ভাষা প্রসঙ্গ-মুক্ত হওয়ার নিশ্চয়তা দেওয়ার জন্য যথেষ্ট নয়; অন্যান্য প্রয়োজনীয় শর্ত রয়েছে, যেমন ওগডেনের লেম্মা বা ইন্টারচেঞ্জ লেম্মা। আনুষ্ঠানিক বিবৃতি যদি কোনও ভাষা প্রসঙ্গ-মুক্ত হয়, তবে কিছু পূর্ণসংখ্যা (যাকে "পাম্পিং দৈর্ঘ্য" বলা হয়) এমন থাকে যাতে প্রতিটি স্ট্রিংয়ের দৈর্ঘ্য বা তার বেশি চিহ্ন থাকে (অর্থাৎ। সহ) সাবস্ট্রিং সহ লেখা যেতে পারে এবং, যেমন 1., 2., এবং 3. সকলের জন্য। নীচে পাম্পিং লেমার একটি আনুষ্ঠানিক অভিব্যক্তি রয়েছে। অনানুষ্ঠানিক বিবৃতি এবং ব্যাখ্যা প্রসঙ্গ-মুক্ত ভাষাগুলির জন্য পাম্পিং লেম্মা (এই নিবন্ধের বাকি অংশের জন্য কেবল "পাম্পিং লেম্মা" বলা হয়) এমন একটি বৈশিষ্ট্য বর্ণনা করে যা সমস্ত প্রসঙ্গ-মুক্ত ভাষাগুলির থাকার নিশ্চয়তা দেওয়া হয়। বৈশিষ্ট্যটি ভাষার সমস্ত স্ট্রিংয়ের একটি বৈশিষ্ট্য যা কমপক্ষে দৈর্ঘ্যের, যেখানে একটি ধ্রুবক-যাকে পাম্পিং দৈর্ঘ্য বলা হয়-যা প্রসঙ্গ-মুক্ত ভাষার মধ্যে পরিবর্তিত হয়। বলুন দৈর্ঘ্যের একটি স্ট্রিং যা অন্তত ভাষায় রয়েছে। পাম্পিং লেমা বলে যে পাঁচটি সাবস্ট্রিংয়ে বিভক্ত করা যেতে পারে, যেখানে খালি নয় এবং দৈর্ঘ্য সর্বাধিক, যাতে পুনরাবৃত্তি এবং একই সংখ্যক বার () ইন একটি স্ট্রিং তৈরি করে যা এখনও ভাষায় রয়েছে। এটি প্রায়শই শূন্য বার পুনরাবৃত্তি করতে কার্যকর, যা স্ট্রিং থেকে সরিয়ে দেয়। এবং এর অতিরিক্ত অনুলিপি সহ "পাম্প আপ" করার এই প্রক্রিয়াটিই পাম্পিং লেম্মাকে এর নাম দেয়। সীমাবদ্ধ ভাষাগুলি (যা নিয়মিত এবং তাই প্রসঙ্গ-মুক্ত) প্লাস ওয়ান-এ সর্বাধিক স্ট্রিং দৈর্ঘ্যের সমান রেখে পাম্পিং লেম্মাকে তুচ্ছভাবে মেনে চলে। যেহেতু এই দৈর্ঘ্যের কোনও স্ট্রিং নেই তাই পাম্পিং লেমা লঙ্ঘন করা হয় না। লেম্মার ব্যবহার পাম্পিং লেম্মা প্রায়শই একটি প্রদত্ত ভাষা অ-প্রসঙ্গ-মুক্ত প্রমাণ করতে ব্যবহৃত হয়, এটি দেখিয়ে যে নির্বিচারে দীর্ঘ স্ট্রিং রয়েছে যা বাইরে স্ট্রিং তৈরি না করে "পাম্প" করা যায় না। উদাহরণস্বরূপ, যদি অসীম হয় কিন্তু একটি (অসীম) গাণিতিক অগ্রগতি না থাকে, তাহলে প্রসঙ্গ-মুক্ত নয়। বিশেষ করে, মৌলিক সংখ্যা বা বর্গ সংখ্যা কোনওটাই প্রসঙ্গ-মুক্ত নয়। উদাহরণস্বরূপ, বিপরীতভাবে প্রমাণ হিসাবে পাম্পিং লেম্মা ব্যবহার করে ভাষাটিকে অপ্রাসঙ্গিক হিসাবে দেখানো যেতে পারে। প্রথমত, ধরে নিন যে এটি প্রসঙ্গ মুক্ত। পাম্পিং লেমা দ্বারা, একটি পূর্ণসংখ্যা বিদ্যমান যা ভাষার পাম্পিং দৈর্ঘ্য। স্ট্রিংটি বিবেচনা করুন। পাম্পিং লেম্মা আমাদের বলে যে এটি এই আকারে লেখা যেতে পারে, কোথায়, এবং সাবস্ট্রিং, যেমন, এবং প্রতিটি পূর্ণসংখ্যার জন্য। এর পছন্দ এবং সত্য দ্বারা, এটি সহজেই দেখা যায় যে সাবস্ট্রিংয়ে দুটি স্বতন্ত্র প্রতীক থাকতে পারে না। অর্থাৎ, আমাদের কাছে পাঁচটি সম্ভাবনার মধ্যে একটি রয়েছেঃ কারো কারো জন্য। কারো জন্য, কারো জন্য। কারো জন্য এবং কারো সঙ্গে। কারো কারো জন্য। প্রতিটি ক্ষেত্রে, এটি সহজেই যাচাই করা যায় যে কোনওটির জন্য প্রতিটি অক্ষরের সমান সংখ্যা নেই। সুতরাং, ফর্ম নেই। এটি এর সংজ্ঞার বিরোধিতা করে। অতএব, আমাদের প্রাথমিক অনুমান যে প্রসঙ্গ মুক্ত তা অবশ্যই মিথ্যা হতে হবে। যদিও পাম্পিং লেম্মা প্রায়শই একটি দরকারী হাতিয়ার প্রমাণ করার জন্য যে একটি প্রদত্ত ভাষা প্রসঙ্গ-মুক্ত নয়, এটি প্রসঙ্গ-মুক্ত ভাষাগুলির সম্পূর্ণ বৈশিষ্ট্য প্রদান করে না। যদি কোনও ভাষা পাম্পিং লেমা দ্বারা প্রদত্ত শর্ত পূরণ না করে, তবে আমরা প্রতিষ্ঠিত করেছি যে এটি প্রসঙ্গ-মুক্ত নয়। অন্যদিকে, এমন কিছু ভাষা রয়েছে যা প্রসঙ্গ-মুক্ত নয়, তবে এখনও পাম্পিং লেমা দ্বারা প্রদত্ত শর্তটি পূরণ করে, উদাহরণস্বরূপ যেমন। শুধুমাত্র a-এর সমন্বয়ে নির্বাচন করার জন্য, শুধুমাত্র b-এর সমন্বয়ে নির্বাচন করুন; উভয় ক্ষেত্রেই সমস্ত পাম্প করা স্ট্রিং এখনও L-এ রয়েছে। পাম্পিং লেম্মার একটি অগ্রদূত 1960 সালে শাইনবার্গ দ্বারা ব্যবহার করা হয়েছিল এটি প্রমাণ করার জন্য যে এটি প্রসঙ্গ-মুক্ত নয়। তথ্যসূত্র-ধারা 1.4-এ পুনঃমুদ্রিত হয়েছেঃ অনিয়মিত ভাষা, পৃ. 77-83। ধারা 2ঃ অপ্রাসঙ্গিক-মুক্ত ভাষাসমূহ, পৃ. 115-119। আনুষ্ঠানিক ভাষাগুলি লেম্মাস