১৯৫৬ সালে নোম চমস্কি গাণিতিক ভাষাতত্ত্বের ভিত্তি স্থাপন করেন ব্যাকরণের রূপান্তর বিধির (Rewriting Rules) ওপর ভিত্তি করে একটি কঠোর স্তরবিন্যাস তৈরির মাধ্যমে—যা চমস্কি হায়ারার্কি (Chomsky Hierarchy) নামে পরিচিত। এই স্তরবিন্যাস ভাষার বিমূর্ত গাণিতিক কাঠামোর সাথে কম্পিউটার বিজ্ঞানের বিভিন্ন অটোমেটার ক্ষমতাকে নিখুঁতভাবে সমন্বয় করে।

১. জেনারেটিভ ব্যাকরণের গাণিতিক সংজ্ঞা

একটি ফরমাল ব্যাকরণ (G) চারটি উপাদানের একটি সেট দ্বারা সংজ্ঞায়িত:

[
G = langle V_N, V_T, P, S
angle
]

যেখানে (V_N) হলো নন-টার্মিনাল চলক, (V_T) হলো টার্মিনাল বর্ণমালা বা শব্দ, (P) হলো রূপান্তর বিধি ((alpha o beta)) এবং (S) হলো শুরুর প্রতীক। এই ব্যাকরণ থেকে উৎপন্ন ভাষার সেট হলো (L(G))।

২. চমস্কি হায়ারার্কির চারটি স্তর

রূপান্তর বিধির ওপর আরোপিত শর্তের কঠোরতার ভিত্তিতে চারটি প্রধান স্তর নির্ধারিত হয়:

টাইপ ৩: রেগুলার ব্যাকরণ (Regular Grammars)

এর নিয়মগুলো রৈখিক আকারের ((A o w B) বা (A o w))। এটি ফাইনাইট অটোমেটন (DFA/NFA) দ্বারা পার্স করা যায়। এর কোনো অভ্যন্তরীণ দীর্ঘমেয়াদী স্মৃতি থাকে না। পাম্পিং লেমার সাহায্যে প্রমাণিত যে (a^n b^n) আকারের ভারসাম্যপূর্ণ ভাষা রেগুলার অটোমেটনে সমাধান করা সম্ভব নয়।

টাইপ ২: কনটেক্সট-ফ্রি ব্যাকরণ (Context-Free Grammars – CFG)

বামপাশে কেবল একটিমাত্র নন-টার্মিনাল থাকে ((A o gamma))। আশেপাশের শব্দের প্রভাব ছাড়াই এটি রূপান্তরিত হতে পারে। এটি একটি LIFO স্ট্যাকবিশিষ্ট পুশডাউন অটোমেটন (PDA) দ্বারা পার্স করা হয়। প্রোগ্রামিং ভাষার সিনট্যাক্স ও প্রাকৃতিক ভাষার সাধারণ বৃক্ষাকার কাঠামো তৈরিতে এটি অপরিহার্য।

টাইপ ১: কনটেক্সট-সেনসিটিভ ব্যাকরণ (Context-Sensitive Grammars)

এখানে রূপান্তর কেবল নির্দিষ্ট প্রতিবেশীর উপস্থিতিতেই অনুমোদিত ((alpha A beta o alpha gamma beta))। এটি লিনিয়ার-বাউন্ডেড অটোমেটন (LBA) দ্বারা পার্স করা যায়, যেখানে মেমোরি টেপের দৈর্ঘ্য ইনপুটের দৈর্ঘ্যের সমানুপাতিক থাকে।

টাইপ ০: অনিয়ন্ত্রিত ব্যাকরণ (Unrestricted Grammars)

রূপান্তরের ওপর কোনো সীমাবদ্ধতা থাকে না। এটি সার্বজনীন টুরিং মেশিন (Turing Machine) দ্বারা পরিচালিত হয় এবং রিকার্সিভলি এনিউমারেবল ভাষার সমস্ত সেট এর অন্তর্ভুক্ত।

৩. প্রাকৃতিক ভাষার গাণিতিক অবস্থান

নোম চমস্কি প্রমাণ করেন যে প্রাকৃতিক ভাষা কখনোই টাইপ ৩ (রেগুলার) হতে পারে না, কারণ এতে অসীম নেস্টেড কাঠামো বিদ্যমান। ১৯৮৫ সালে স্টুয়ার্ট শিবার সুইস-জার্মান ভাষার ক্রসিং ডিপেনডেন্সি বিশ্লেষণ করে প্রমাণ করেন যে প্রাকৃতিক ভাষা বিশুদ্ধ কনটেক্সট-ফ্রিও (টাইপ ২) নয়। বরং প্রাকৃতিক ভাষা হলো মাইল্ডলি কনটেক্সট-সেনসিটিভ (Mildly Context-Sensitive)—যা ট্রি-অ্যাডজয়েনিং ব্যাকরণ (TAG) দ্বারা বহুপদী সময়ে ((mathcal{O}(n^6))) দক্ষতার সাথে পার্স করা যায়।

শাকিল মাহমুদ সজল

শাকিল মাহমুদ সজল

সফটওয়্যার প্রকৌশলী ও লেখক, ঢাকা, বাংলাদেশ। কম্পিউটার বিজ্ঞান, পদার্থবিজ্ঞান, ইতিহাস ও ভাবনার সমন্বয়ে ব্যক্তিগত নোট ও প্রবন্ধ সংকলন।