Chomsky Hierarchy

Noam Chomsky (১৯৫৬) — production rule α → β-এর আকৃতির উপর নিষেধাজ্ঞা যত শিথিল, ভাষার শ্রেণি তত ব্যাপক:

Type	নাম	Rule আকৃতি	Automaton
3	Regular	A → aB বা A → a	Finite Automaton (DFA/NFA)
2	Context-Free	A → γ (একক nonterminal বাম পাশে)	Pushdown Automaton
1	Context-Sensitive	αAβ → αγβ, `	γ
0	Unrestricted (RE)	যেকোনো α → β	Turing Machine

নীড়েড সেট (strict subset): প্রতিটা স্তরের ভাষা পরের স্তরেরও সদস্য — 0ⁿ1ⁿ regular না কিন্তু context-free; 0ⁿ1ⁿ2ⁿ context-free না কিন্তু context-sensitive — pumping lemma দিয়ে প্রমাণযোগ্য।

যেখানে সর্বত্র ফিরে আসে: compiler-এর lexer (regular) বনাম parser (context-free) বিভাজন, regex engine-এর তাত্ত্বিক সীমা, XML/JSON schema validation, natural language parsing — সব জায়গায় এই একই প্রশ্ন: “এই ভাষা চিনতে কী ধরনের memory লাগবে?”