Foundationপ্রথম নীতি থেকে
LEVEL 13লেসন ১/২৩কঠিন১ ঘণ্টা

Formal Languages ও Chomsky Hierarchy — ভাষার ক্ষমতার সিঁড়ি

Formal Languages and the Chomsky Hierarchy

চারটা স্তরের একটা সিঁড়ি — regular থেকে recursively enumerable পর্যন্ত — যা বলে দেয় একটা ভাষা চিনতে কতটা memory ও কী ধরনের কাঠামো লাগবে; আর কেন lexer আর parser দুইটা আলাদা স্তরে বাস করে।

এই লেসন শেষে আপনি পারবেন

  • Alphabet, string, ও language-কে সেট-তাত্ত্বিক ভাষায় আনুষ্ঠানিকভাবে সংজ্ঞায়িত করতে পারবেন
  • Chomsky hierarchy-র চারটা স্তর (regular, context-free, context-sensitive, recursively enumerable) আলাদা করতে পারবেন production rule-এর আকৃতি দেখে
  • কোন grammar-type কোন automaton class-এর সমতুল্য তা বলতে পারবেন — এই module-এর বাকি লেসনগুলোর মানচিত্র হিসেবে
  • একটা নির্দিষ্ট ভাষা হায়ারার্কির কোন স্তরে পড়ে তা তার গঠন দেখে অনুমান করতে পারবেন
  • কেন এই হায়ারার্কি lexer/parser বিভাজনের মতো বাস্তব compiler design সিদ্ধান্তকে নিয়ন্ত্রণ করে তা ব্যাখ্যা করতে পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

compilers/lexical-analysis লেসনে আমরা একটা lexer লিখেছিলাম যেটা regular expression দিয়ে token চিনত। compilers/grammars-and-ambiguity লেসনে আমরা একটা grammar লিখেছিলাম যেটা arithmetic expression-এর গঠন বর্ণনা করত। দুইটাই “ভাষা বর্ণনা করার নিয়ম” — কিন্তু আমরা কখনো প্রশ্ন করিনি: কেন দুইটা আলাদা টুল? regex দিয়ে পুরো grammar কেন লেখা গেল না?

চেষ্টা করে দেখুন। Balanced parentheses-এর ভাষা — (), (()), ((())), ইত্যাদি — regex দিয়ে লিখুন।

import re
pattern = re.compile(r'^\(*\)*$')     # প্রথম চেষ্টা
pattern.match("(())")                  # match করে... কিন্তু ভুল কারণে!
pattern.match("()(")                   # এটাও match করবে — ভুল

\(*\)* কোনো depth track করে না — এটা শুধু “কতগুলো ( তারপর কতগুলো )” গোনে, তাদের সমান কি না তা নয়, আর নেস্টিং তো একদমই না। আপনি hand-crafted regex দিয়ে যত চেষ্টাই করুন — কয়েক স্তর নেস্টিং পর্যন্ত ঠিক হবে, কিন্তু সাধারণভাবে কখনোই সম্ভব হবে না। এটা কোনো দক্ষতার অভাব না — এটা প্রমাণযোগ্য অসম্ভবতা, যা আমরা এই module-এর তৃতীয় লেসনে (pumping lemma) কঠোরভাবে প্রমাণ করব।

অথচ একটা context-free grammar-এ এটা তুচ্ছ:

S → ( S ) S | ε

এই ব্যর্থতাটাই আজকের লেসনের কেন্দ্রবিন্দু। কিছু ভাষা regex দিয়ে ধরা যায়, কিছু যায় না — আর এই পার্থক্যটা কাকতালীয় নয়, এটা একটা আনুষ্ঠানিক, গাণিতিকভাবে সাজানো সিঁড়ির ফলাফল। Noam Chomsky ১৯৫৬ সালে — মূলত মানুষের ভাষা বোঝার চেষ্টায়, compiler design নয় — এই সিঁড়িটা প্রথম প্রস্তাব করেছিলেন। আজ এটাই compiler-এর lexer আর parser আলাদা কেন, database query language কতটা expressive হতে পারে, আর network protocol validation কোথায় থেমে যায় — সব ব্যাখ্যা করে।

মূল ধারণা

Alphabet, string, language — আনুষ্ঠানিক ভিত্তি

গল্প শুরুর আগে তিনটা শব্দকে নিখুঁতভাবে সংজ্ঞায়িত করা দরকার — বাকি পুরো module এই তিনটার উপর দাঁড়িয়ে থাকবে।

Alphabet (Σ): প্রতীকের একটা সসীম, অ-খালি সেট।

Σ = {0, 1}                    — বাইনারি
Σ = {a, b, ..., z}             — lowercase ইংরেজি
Σ = {if, else, id, (, ), ...}  — একটা lexer-এর token kind সেট

String (w): Σ-এর প্রতীকের একটা সসীম ক্রম। শূন্য দৈর্ঘ্যের string-কে বলা হয় ε (epsilon)। Σ* মানে Σ-এর উপর গঠনযোগ্য সব সসীম string-এর সেট (Kleene star — mathematics/sets লেসনের সেট অপারেশনের সাথে মিলিয়ে দেখুন)।

Σ∗={ε}∪Σ∪Σ2∪Σ3∪⋯\Sigma^* = \{\varepsilon\} \cup \Sigma \cup \Sigma^2 \cup \Sigma^3 \cup \cdots

Σ = {0,1} হলে Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...} — অসীম সেট, যদিও Σ নিজে সসীম।

Language (L): Σ*-এর যেকোনো উপসেট — L ⊆ Σ*।

লক্ষ্য করুন — এই সংজ্ঞায় কোনো “অর্থ” নেই। L শুধুই একটা সেট, হতে পারে সসীম, হতে পারে অসীম। উদাহরণ:

L₁ = {0, 1, 00, 11}                         — সসীম ভাষা
L₂ = {0ⁿ1ⁿ : n ≥ 0}                          — অসীম, প্যাটার্নসহ
L₃ = { প্রতিটা বৈধ Python program }           — অসীম, বাস্তব-প্রাসঙ্গিক
L₄ = ∅                                       — খালি ভাষা (বৈধ!)
L₅ = Σ*                                      — সব string (এটাও বৈধ!)

Language Σ*-এর একটা উপসেট মাত্র — তাই Σ* নিজেই একটা সসীম alphabet-এর উপর একটা অসীম সেট, আর সম্ভাব্য ভাষার সংখ্যা (Σ*-এর power set) uncountably অসীম। এটা এই module-এর শেষ দিকে (decidability লেসনে) একটা মৌলিক প্রমাণের বীজ — countably অনেক program দিয়ে uncountably অনেক ভাষা চেনা অসম্ভব, তাই বেশিরভাগ ভাষাই কোনো প্রোগ্রাম দিয়ে চেনা যায় না — এমনকি নীতিগতভাবেও না। আজ আমরা শুধু সেই “যেগুলো চেনা যায়” -এর ভেতরের সিঁড়িটা দেখছি।

Grammar — ভাষা তৈরির রেসিপি

Σ*-এর একটা অসীম উপসেট লিখে ফেলা অসম্ভব (অসীম তালিকা)। তাই আমরা ভাষাকে generate করার একটা সসীম রেসিপি চাই — এটাই grammar।

compilers/grammars-and-ambiguity-তে আমরা BNF দেখেছি অনানুষ্ঠানিকভাবে। আনুষ্ঠানিক সংজ্ঞা একটা 4-টুপল:

G=(V,Σ,R,S)G = (V, \Sigma, R, S)

উপাদানঅর্থ
VNonterminal symbol-এর সসীম সেট (variable)
ΣTerminal symbol-এর সসীম সেট (alphabet, V-এর থেকে বিচ্ছিন্ন)
RProduction rule-এর সসীম সেট, আকৃতি α → β
SStart symbol, S ∈ V

(V ∪ Σ)* -কে “sentential form” বলা হয় — nonterminal ও terminal মেশানো যেকোনো string। Derivation: S থেকে শুরু করে বারবার কোনো rule প্রয়োগ করে (একটা nonterminal-কে তার production দিয়ে replace করে) যতক্ষণ না শুধু terminal অবশিষ্ট থাকে। Grammar-এর generate করা ভাষা:

L(G)={w∈Σ∗:S⇒∗w}L(G) = \{ w \in \Sigma^* : S \Rightarrow^* w \}

(⇒* মানে শূন্য বা তার বেশি derivation step)।

গুরুত্বপূর্ণ পর্যবেক্ষণ: grammar আর automaton দুইটা সম্পূর্ণ ভিন্ন জিনিস যা একই ভাষার দুই রকম বর্ণনা দিতে পারে — grammar generate করে (তৈরি করে), automaton recognize করে (যাচাই করে, string দিলে হ্যাঁ/না বলে)। এই module-এর কেন্দ্রীয় আবিষ্কার হলো: এই দুই দৃষ্টিভঙ্গি প্রতিটা স্তরে একে অপরের সমতুল্য — যেকোনো grammar-এর জন্য একটা সমতুল্য automaton আছে, আর উল্টোটাও।

Chomsky hierarchy — production rule-এর আকৃতির উপর একটা সিঁড়ি

Noam Chomsky লক্ষ্য করলেন — grammar-এর production rule-এর আকৃতির উপর নিষেধাজ্ঞা বসিয়ে দিলে ভাষার শ্রেণি স্বাভাবিকভাবেই স্তরে স্তরে ভাগ হয়ে যায়। কম নিষেধাজ্ঞা = বেশি ক্ষমতাশালী ভাষা, কিন্তু বেশি জটিল স্বীকৃতি প্রক্রিয়া।

চারটা টাইপ, সবচেয়ে নিষেধাজ্ঞাযুক্ত (সংকীর্ণ) থেকে সবচেয়ে শিথিল (ব্যাপক) পর্যন্ত:

TypeনামProduction rule-এর আকৃতিAutomatonউদাহরণ ভাষা
3RegularA → aB অথবা A → a (আর A → ε)Finite Automaton (DFA/NFA)(ab)*, identifier pattern
2Context-FreeA → γ (A একটা একক nonterminal, γ যেকোনো string)Pushdown Automaton (PDA)0ⁿ1ⁿ, balanced parens, arithmetic expr
1Context-SensitiveαAβ → αγβ (γ ≠ ε, দৈর্ঘ্য অ-হ্রাসমান)Linear-Bounded Automaton (LBA)0ⁿ1ⁿ2ⁿ, বেশিরভাগ programming language-এর পুরো semantic নিয়ম
0Unrestricted / Recursively Enumerableα → β (যেকোনো, α-তে অন্তত একটা nonterminal)Turing Machineযেকোনো algorithm-এর output সেট
Chomsky hierarchy — production rule-এর আকৃতির নিষেধাজ্ঞা যত শিথিল হয়, ভাষার শ্রেণি তত ব্যাপক হয়।

Type সংখ্যা যত কম, নিষেধাজ্ঞা তত কম — এটা একটু উল্টো মনে হতে পারে, তাই মনে রাখার কৌশল: Type 3-এ সবচেয়ে কড়া নিয়ম (তাই সবচেয়ে দুর্বল), Type 0-এ কোনো নিয়ম নেই (তাই সবচেয়ে শক্তিশালী)।

Type 3 — Regular grammar

প্রতিটা rule-এর ডান পাশে সর্বোচ্চ একটা nonterminal, আর সেটা শেষে (right-linear) অথবা শুরুতে (left-linear) — দুটো মিশ্রিত নয়।

A → a B      (right-linear — একটা terminal তারপর একটা nonterminal)
A → a        (একটা terminal, শেষ)
A → ε        (খালি — শুধু start symbol-এ অনুমোদিত সাধারণত)

এই আকৃতিটা লক্ষ্য করুন — প্রতিটা step একটামাত্র নতুন terminal “emit” করে আর একটামাত্র “state”-এর মতো nonterminal বহন করে। এটাই কেন এই grammar একটা সসীম memory (finite automaton-এর state) দিয়ে recognize করা যায় — derivation-এর “অগ্রগতি” ট্র্যাক করতে পুরো sentential form মনে রাখার দরকার নেই, শুধু বর্তমান nonterminal-টা জানলেই চলে। লেসন ২-এ এটাই DFA/NFA-এর state হয়ে উঠবে।

Type 2 — Context-free grammar (CFG)

শর্ত মাত্র একটা: বাম পাশে ঠিক একটা nonterminal, ডান পাশে যেকোনো কিছু (terminal, nonterminal, যেকোনো ক্রমে, যেকোনো দৈর্ঘ্যে)।

E → E + E | E * E | ( E ) | id

নাম “context-free” কেন? কারণ E-কে replace করার নিয়ম E কোথায় বসে আছে তার উপর নির্ভর করে না — বাম-ডানে যা-ই থাকুক, একই production সবসময় প্রযোজ্য। এটাই compilers/grammars-and-ambiguity লেসনের পুরো grammar-এর ভিত্তি — recursive nesting ((, ), নেস্টেড expression) এখন সম্ভব, কারণ ডান পাশে nonterminal একাধিকবার, নিজেকে ঘিরেও থাকতে পারে।

Type 1 — Context-sensitive grammar (CSG)

এবার rule-এ প্রসঙ্গ (context) ঢোকে — A-কে replace করা যাবে শুধু যদি সে α আর β-এর মাঝে বসে থাকে:

αAβ→αγβ(γ≠ε)\alpha A \beta \rightarrow \alpha \gamma \beta \qquad (\gamma \neq \varepsilon)

শর্ত: length-nondecreasing — ডান পাশ বাম পাশের চেয়ে কখনো ছোট না। এই শর্তটাই automaton-কে (LBA) tape-এর একটা সসীম, ইনপুট-সমান অংশে আটকে রাখার অনুমতি দেয় — memory বাড়ে না, শুধু ইনপুটের সমান tape-এই কাজ চলে।

0ⁿ1ⁿ2ⁿ (n টা 0, তারপর n টা 1, তারপর n টা 2) — এটা context-sensitive, কিন্তু context-free না (লেসন ৪-এ আমরা এটা pumping lemma দিয়ে প্রমাণ করব)। ব্যবহারিক জগতে খাঁটি context-sensitive grammar বিরল — বেশিরভাগ “সত্যিকারের” programming language semantics (যেমন “variable ব্যবহারের আগে declare হতে হবে”) technically context-sensitive, কিন্তু compiler-রা এগুলো CFG দিয়ে parse করে, তারপর আলাদা semantic analysis pass-এ (symbol table দিয়ে) চেক করে — কারণ CSG parsing ব্যবহারিকভাবে অনেক ব্যয়বহুল।

Type 0 — Unrestricted grammar

কোনো নিষেধাজ্ঞা নেই — বাম পাশে অন্তত একটা nonterminal থাকলেই হলো, ডান পাশ যা খুশি (এমনকি বাম পাশের চেয়ে ছোটও হতে পারে)।

α→β(α-তে অন্তত ১টা nonterminal)\alpha \rightarrow \beta \qquad (\alpha \text{-তে অন্তত ১টা nonterminal})

এটাই একটা সাধারণ Turing machine-এর সমতুল্য শক্তি — এই ভাষাগুলোকে বলা হয় recursively enumerable (RE)। এই module-এর decidability লেসনগুলোতে আমরা দেখব এমনকি এই সর্বোচ্চ স্তরও সব ভাষা ধরতে পারে না — halting problem-এর মতো ভাষা RE-ও না।

ভেতরে কী ঘটছে

কেন এই সিঁড়িটাই — memory-এর প্রশ্ন

Rule-এর আকৃতি বনাম memory-এর সম্পর্কটা এই লেসনের সবচেয়ে গুরুত্বপূর্ণ অন্তর্দৃষ্টি, তাই একটু ধীরে দেখি।

0ⁿ1ⁿ চিনতে (n যেকোনো) একটা recognizer-কে জানতে হবে কতগুলো 0 দেখেছে, যাতে ঠিক ততগুলো 1 আসছে কি না মিলিয়ে দেখা যায়। এই “গোনা”-টা রাখার জন্য দরকার এমন memory যা ইনপুটের সাথে বাড়ে। সসীম সংখ্যক state (DFA) দিয়ে অসীম বড় n গোনা অসম্ভব — pigeonhole নীতির সরাসরি ফলাফল (mathematics/relations লেসনের pigeonhole মনে করুন): n যত বড় হোক, state সংখ্যা সসীম, তাই দুইটা ভিন্ন n একই state-এ পড়বেই, আর তখন recognizer গুলিয়ে ফেলবে। এটাই লেসন ৩-এ pumping lemma-র আনুষ্ঠানিক রূপ।

কিন্তু একটা stack (LIFO) দিয়ে সহজ — প্রতিটা 0-এ push করুন, প্রতিটা 1-এ pop করুন, শেষে stack খালি হলে accept। Stack-এর depth ইনপুটের সাথে বাড়তে পারে — এটাই unbounded কিন্তু structured memory, আর ঠিক এটাই pushdown automaton (PDA)-এর সংজ্ঞা।

0ⁿ1ⁿ2ⁿ চিনতে stack-ও যথেষ্ট না — push আর pop-এর ক্রম একমুখী (LIFO), কিন্তু এখানে দুইটা ভিন্ন গণনা মেলাতে হবে (0 বনাম 2, 1 বনাম 2) যা একটা stack-এ একসাথে ধরে না। দরকার পুরো ইনপুটের সমান একটা tape যেখানে সামনে-পেছনে চলা যায় — এটাই linear-bounded automaton।

Memory model-এর সিঁড়ি — প্রতিটা স্তর আগেরটার চেয়ে বেশি কাঠামোবদ্ধ স্মৃতি পায়
  1. Regular / DFAসসীম, স্থির সংখ্যক state — কোনো গণনা মনে রাখা যায় না
  2. Context-Free / PDAসসীম state + ১টা unbounded stack (LIFO)
  3. Context-Sensitive / LBAইনপুটের সমান দৈর্ঘ্যের tape, সামনে-পেছনে চলা যায়
  4. Recursively Enumerable / Turing Machineসম্পূর্ণ অসীম tape — কোনো সীমা নেই

Grammar ↔ Automaton — সমতুল্যতার প্রতিশ্রুতি

প্রতিটা স্তরে একটা উপপাদ্য আছে যা বলে grammar-দৃষ্টি আর automaton-দৃষ্টি একই ভাষার সেট বর্ণনা করে:

স্তরGenerator (grammar)Recognizer (automaton)প্রমাণিত হবে
RegularRegular grammar / Regular expressionDFA / NFAলেসন ২, ৩
Context-FreeCFGPDAলেসন ৪
Context-SensitiveCSGLBAএই curriculum-এ বিস্তারিত না (গবেষণা-স্তর)
Recursively EnumerableUnrestricted grammarTuring Machineপরের লেসনগুলো

এই সমতুল্যতাগুলোর প্রতিটাই একটা গঠনমূলক প্রমাণ — মানে শুধু “সমান শক্তিশালী” বলা নয়, বরং একটা থেকে অন্যটা তৈরি করার একটা algorithm দেওয়া। লেসন ৩-এ আমরা ঠিক এই ধরনের একটা algorithm (Thompson’s construction) হাতে-কলমে দেখব — regex থেকে NFA বানানোর পদ্ধতি।

উদাহরণ

চারটা ভাষা, চারটা স্তর — পাশাপাশি

একটাই থিম (সংখ্যা মেলানো) দিয়ে চারটা স্তর তুলনা করা যাক — প্রতিটা আগেরটার চেয়ে সামান্য বেশি demanding।

Regular: (ab)* — শুধু একটা fixed প্যাটার্নের পুনরাবৃত্তি, কোনো matching নেই।

Grammar (right-linear):
  S → a A | ε
  A → b S

Language: ε, ab, abab, ababab, ...

Context-free: {0ⁿ1ⁿ : n ≥ 0} — একটামাত্র জোড়া মেলাতে হচ্ছে, stack-এই যথেষ্ট।

Grammar:
  S → 0 S 1 | ε

Derivation for n=3:
  S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111

Context-sensitive: {0ⁿ1ⁿ2ⁿ : n ≥ 1} — তিনটা গণনা মেলাতে হচ্ছে, stack-এ যথেষ্ট জায়গা নেই।

একটা সম্ভাব্য (সরলীকৃত) CSG স্কেচ — Z কে ডানে "ক্যারি" করে
প্রতিটা 0-এর সাথে একটা 1 আর একটা 2 তৈরি করানো:

  S  → 0 S B C | 0 B C
  C B → B C           (context-sensitive swap — এখানেই "context" শব্দটা সত্যি অর্থ পায়)
  0 B → 0 1
  1 B → 1 1
  1 C → 1 2
  2 C → 2 2

লক্ষ্য করুন CB → BC rule-টা — এটা Type 2-তে অসম্ভব ছিল, কারণ বাম পাশে দুইটা nonterminal (C আর B একসাথে, replace হচ্ছে তাদের প্রসঙ্গ অনুযায়ী)। এটাই “context-sensitive” নামের আক্ষরিক প্রতিফলন।

Recursively enumerable: { p : p একটা Python program যা টার্মিনেট করে } — এর জন্য কোনো fixed-shape grammar rule কল্পনা করা যায় না; এটা চিনতে একটা সম্পূর্ণ general-purpose computation লাগে (আর, দেখা যাবে, এটাও সবসময় সম্ভব না — halting problem)।

ভাষাকী মেলাতে হচ্ছেস্তর
(ab)*কিছুই না — শুধু পুনরাবৃত্তিRegular
0ⁿ1ⁿ১ জোড়া গণনাContext-Free
0ⁿ1ⁿ2ⁿ২ জোড়া গণনা, স্বাধীনভাবেContext-Sensitive
“program টার্মিনেট করে”Arbitrary computationRecursively Enumerable (কখনো কখনো এটাও না)
একই 'সংখ্যা মেলানো' থিম, চার স্তরে — জটিলতা বাড়ছে matching-এর সংখ্যা আর নির্ভরতার সাথে।

নিজে চালিয়ে দেখুন

EXPERIMENT

Regex দিয়ে balanced parentheses ধরার ব্যর্থ চেষ্টা

Python 3· ১৫ মিনিট
import re

# depth-2 পর্যন্ত balanced parens ধরার একটা "hack" regex
depth2 = re.compile(r'^\(([^()]|\([^()]*\))*\)$')

tests = [
    "()",            # depth 1 — ঠিক
    "(())",          # depth 2 — ঠিক
    "((()))",        # depth 3 — এখানেই ভাঙবে
    "(()",           # unbalanced — reject করা উচিত
]

for t in tests:
    ok = bool(depth2.match(t))
    print(f"{t!r:12} → {'MATCH' if ok else 'NO MATCH'}")
'()'         → MATCH
'(())'       → MATCH
'((()))'     → NO MATCH      ← regex-টা depth 2-তেই সীমাবদ্ধ
'(()'        → NO MATCH

depth2 regex-টা আসলে একটা নির্দিষ্ট, সসীম depth পর্যন্ত হাতে লেখা approximation — প্রতিটা নেস্টিং লেভেলের জন্য regex-এ আরেকটা স্তর যোগ করতে হয়। সাধারণ (unbounded) balanced parentheses ধরার কোনো fixed-length regex নেই — কারণ থাকলে সেটা একটা DFA-তে কম্পাইল হতো, আর DFA-র state সংখ্যা সসীম, কিন্তু nesting depth অসীম হতে পারে।

# CFG-ভিত্তিক recognizer — stack দিয়ে, যেকোনো depth-এ কাজ করে
def balanced(s: str) -> bool:
    depth = 0
    for ch in s:
        if ch == '(':
            depth += 1
        elif ch == ')':
            depth -= 1
            if depth < 0:
                return False
    return depth == 0

for t in ["()", "(())", "((()))", "(" * 50 + ")" * 50, "(()"]:
    print(f"{t[:20]!r:22} → {balanced(t)}")

depth variable-টাই stack-এর উচ্চতা — এখানে explicit stack লাগেনি কারণ শুধু গোনাটাই দরকার (কোন bracket খোলা আছে তা মনে রাখার দরকার নেই, শুধু কতগুলো), কিন্তু নীতিগতভাবে এটাই একটা PDA-র simulation। n = 50-এও নিখুঁত কাজ করে — কোনো fixed regex এটা পারবে না।

এটা কী প্রমাণ করে

যেকোনো fixed regex ঠিক একটা সসীম nesting depth পর্যন্তই কাজ করে — এরপর ভেঙে পড়ে। এটাই regex (regular) আর CFG-এর ক্ষমতার পার্থক্যের প্রত্যক্ষ প্রমাণ, তাত্ত্বিক আলোচনার আগে চোখে দেখা।

নিজে বানান

BUILD IT

একটা Grammar Classifier — production rule দেখে Chomsky type বলুন

Python · ●●●○○
  1. প্রতিটা production rule পার্স করুন — বাম পাশ (LHS) আর ডান পাশ (RHS)
  2. Regular শর্ত যাচাই করুন — LHS একটা nonterminal, RHS একটা terminal + (ঐচ্ছিক) একটা trailing nonterminal
  3. Context-free শর্ত যাচাই করুন — শুধু LHS-এর দৈর্ঘ্য ১ এবং সেটা একটা nonterminal
  4. Context-sensitive শর্ত যাচাই করুন — RHS দৈর্ঘ্য ≥ LHS দৈর্ঘ্য
  5. পুরো grammar-এর type হলো তার সবচেয়ে শিথিল (সবচেয়ে কম-restrictive) rule-এর type

লক্ষ্য: একটা grammar-এর production rule-গুলো দেখে স্বয়ংক্রিয়ভাবে বলা এটা কোন Chomsky type-এ পড়ে।

from dataclasses import dataclass

NONTERMINAL = str.isupper   # কনভেনশন: uppercase = nonterminal, lowercase = terminal

@dataclass
class Rule:
    lhs: str   # যেমন "S" বা "AB"  (স্পেস-বিহীন symbol string)
    rhs: str   # যেমন "aSb" বা "epsilon"

    def lhs_symbols(self):
        return list(self.lhs)

    def rhs_symbols(self):
        return [] if self.rhs == "epsilon" else list(self.rhs)


def classify_rule(r: Rule) -> str:
    lhs, rhs = r.lhs_symbols(), r.rhs_symbols()

    # Type 3 — regular: LHS একটা nonterminal, RHS = terminal* (nonterminal)?
    if len(lhs) == 1 and NONTERMINAL(lhs[0]):
        non_terms = [s for s in rhs if NONTERMINAL(s)]
        terms = [s for s in rhs if not NONTERMINAL(s)]
        if len(non_terms) <= 1 and (len(non_terms) == 0 or rhs.index(non_terms[0]) == len(rhs) - 1):
            return "regular (Type 3)"

    # Type 2 — context-free: LHS দৈর্ঘ্য ১, nonterminal
    if len(lhs) == 1 and NONTERMINAL(lhs[0]):
        return "context-free (Type 2)"

    # Type 1 — context-sensitive: |RHS| >= |LHS|, RHS != epsilon
    if len(rhs) >= len(lhs) and r.rhs != "epsilon":
        return "context-sensitive (Type 1)"

    # Type 0 — বাকি সব, যদি LHS-এ অন্তত একটা nonterminal থাকে
    if any(NONTERMINAL(s) for s in lhs):
        return "unrestricted (Type 0)"

    return "invalid rule"


def classify_grammar(rules: list[Rule]) -> str:
    ORDER = ["regular (Type 3)", "context-free (Type 2)",
             "context-sensitive (Type 1)", "unrestricted (Type 0)"]
    types = [classify_rule(r) for r in rules]
    # সবচেয়ে শিথিল rule-ই পুরো grammar-এর type নির্ধারণ করে
    worst = max(types, key=ORDER.index)
    return worst


# ── পরীক্ষা ──────────────────────────────────────────────────────
regular_grammar = [Rule("S", "aA"), Rule("A", "bS"), Rule("S", "epsilon")]
cfg = [Rule("S", "0S1"), Rule("S", "epsilon")]
csg = [Rule("CB", "BC"), Rule("0B", "01"), Rule("1B", "11")]

for name, g in [("regular_grammar", regular_grammar), ("cfg", cfg), ("csg", csg)]:
    print(f"{name:16} → {classify_grammar(g)}")
regular_grammar  → regular (Type 3)
cfg              → context-free (Type 2)
csg              → context-sensitive (Type 1)

নিজে বাড়ান:

  1. mathematics/relations লেসনের বাইনারি relation-এর ধারণা ব্যবহার করে দেখান L(G₁) ⊆ L(G₂) — অর্থাৎ একটা regular grammar থেকে জেনারেট হওয়া প্রতিটা string context-free grammar দিয়েও জেনারেট করা যায় (grammar rewrite করে দেখান)
  2. Left-linear আর right-linear উভয় regular grammar detect করার জন্য classify_rule-কে আরো general করুন
  3. এমন একটা rule set লিখুন যা Type 0 কিন্তু Type 1 না (length-decreasing কোনো rule দিয়ে) — এবং classifier-টা সেটা সঠিকভাবে ধরছে কি না যাচাই করুন
  4. compilers/grammars-and-ambiguity-র arithmetic grammar-টা এই classifier-এ চালান — নিশ্চিত হোন এটা context-free ধরছে

বাস্তব সিস্টেমে

এই হায়ারার্কি কোথায় সিদ্ধান্ত নেয়

Compiler-এর lexer/parser বিভাজন। compilers/lexical-analysis (regular — DFA-ভিত্তিক, দ্রুত, সসীম memory) আর compilers/parsing (context-free — stack-ভিত্তিক, নেস্টিং সামলায়) দুইটা আলাদা pass কেন? কারণ token চেনা (if, 123, +) regular, কিন্তু expression-এর নেস্টিং structure context-free — দুইটা ভিন্ন ক্ষমতার সমস্যা, তাই দুইটা ভিন্ন engine। একটা lexer দিয়ে balanced parens ধরার চেষ্টা করাটাই design ভুল — এই লেসনের প্রথম experiment ঠিক সেটাই দেখাল।

Regex engine ও তাদের সীমা। প্রতিটা প্রোগ্রামিং ভাষার regex library — Python re, JavaScript regex, grep — তাত্ত্বিকভাবে regular ভাষা চেনার জন্য ডিজাইন করা। HTML/XML parse করতে regex ব্যবহার করা একটা ব্যাপকভাবে পরিচিত ভুল (Stack Overflow-র বিখ্যাত “You can’t parse HTML with regex” উত্তর) — কারণ HTML-এর tag নেস্টিং context-free, regex-এর ক্ষমতার বাইরে।

XML/JSON Schema আর DTD। XML DTD context-free-এর কাছাকাছি; কিছু আধুনিক schema language (XML Schema-র key/keyref) আসলে context-sensitive constraint প্রকাশ করে — এই কারণেই তাদের validation সাধারণ CFG parser দিয়ে হয় না, আলাদা constraint-checking pass লাগে।

Network protocol grammar। HTTP, SMTP-এর মতো প্রোটোকলের ABNF (Augmented BNF) স্পেসিফিকেশন মূলত regular বা context-free — header parsing regular, কিন্তু কিছু nested structure (multipart body) context-free।

Natural language processing। Chomsky-র মূল উদ্দেশ্যই ছিল এটা — মানুষের ভাষার গঠন বর্ণনা করা। আধুনিক NLP-তে context-free grammar (বা তার সম্প্রসারণ) এখনো syntax tree বর্ণনার মূল টুল, যদিও modern deep-learning-ভিত্তিক parser (transformer) সরাসরি grammar লেখে না — তবু তাত্ত্বিক ভিত্তি একই।

Configuration language ও DSL design। নতুন কোনো config format (YAML, TOML) ডিজাইন করার সময় প্রশ্ন ওঠে — এটা কি regular রাখব (দ্রুত parse, কিন্তু সীমিত nesting), নাকি context-free করব (নেস্টেড structure, কিন্তু ধীরতর parse)? এই সিদ্ধান্ত সরাসরি এই হায়ারার্কি থেকে আসে।

যে ভুলগুলো সবাই করে

“প্রোগ্রামিং ভাষায় (Python, JavaScript) আপনার regex library-র 'regular expression' মানে Chomsky-র regular ভাষা।”

প্রায়ই না। আধুনিক regex engine (PCRE, Python re, JavaScript regex) backreference (\1), lookahead/lookbehind ((?=...), (?<=...)) সমর্থন করে — এগুলো theoretical regular ভাষার সংজ্ঞার বাইরে।

উদাহরণ: (a+)\1 — এটা {aⁿaⁿ : n ≥ 1} ভাষা চেনে, যেটা এই লেসনে আমরা দেখেছি pumping lemma দিয়ে non-regular প্রমাণিত হবে (0ⁿ1ⁿ-এর সাথে গাণিতিকভাবে সমতুল্য একটা ভাষা)। Backreference-সহ regex তাই strictly বেশি শক্তিশালী — এমনকি কখনো কখনো NP-hard matching তৈরি করে।

নিয়ম: “regex” শব্দটা প্রোগ্রামিং জগতে আর তত্ত্বের জগতে দুইটা ভিন্ন জিনিস বোঝায়। লেসন ৩-এ আমরা এই পার্থক্যটা বিস্তারিত দেখব — কেন এটা শুধু তাত্ত্বিক কৌতূহল না, বাস্তব performance বিপর্যয় (catastrophic backtracking)-এর মূল কারণ।

“'Context-free' মানে ভাষার নিয়মে 'কোনো প্রসঙ্গ/অর্থ' নেই — অর্থাৎ এটা দুর্বল একটা মডেল।”

নামটা বিভ্রান্তিকর, কিন্তু ভুল অর্থে না। “Context-free” মানে grammar rule প্রয়োগের সময় nonterminal-টা কোন string-এর মধ্যে বসে আছে তা বিবেচনা করা লাগে না — A → γ rule যেখানেই A দেখা যাক প্রযোজ্য, তার আগে-পিছে যা-ই থাকুক।

এটা “দুর্বল” নয় — CFG দিয়ে প্রতিটা programming language-এর syntax (semantic নিয়ম বাদে), প্রায় প্রতিটা markup/data format বর্ণনা করা যায়। “Context-sensitive” (Type 1) grammar-এ প্রসঙ্গ সত্যিই লাগে (αAβ → αγβ), কিন্তু সেটা ব্যবহারিকভাবে parse করা অনেক ব্যয়বহুল — তাই বাস্তবে প্রায় সবসময় CFG + আলাদা semantic check ব্যবহার হয়, খাঁটি CSG নয়।

“একটা ভাষা 'জটিল দেখতে' হলেই তা উচ্চ স্তরের।”

Classification নির্ভর করে ভাষার কাঠামোগত প্রয়োজনীয়তার উপর, “জটিলতার অনুভূতি”-র উপর না।

উদাহরণ: {w ∈ {0,1}* : w-তে 0-র সংখ্যা জোড়} — দেখতে হয়তো একটা “গণনা”-নির্ভর শর্ত মনে হয়, কিন্তু এটা regular — মাত্র দুইটা state লাগে (“এখন পর্যন্ত জোড় 0” / “এখন পর্যন্ত বিজোড় 0”), কারণ আপনার শুধু parity মনে রাখতে হয়, প্রকৃত সংখ্যা না।

অন্যদিকে {0ⁿ1ⁿ} দেখতে অনেক সরল, কিন্তু non-regular — কারণ এখানে প্রকৃত (unbounded) সংখ্যা মনে রাখতে হয়, কোনো সসীম parity/modulo কৌশল কাজ করে না।

নিয়ম: classify করার আসল প্রশ্ন — “চিনতে কী ধরনের memory লাগবে”, “কেমন দেখতে” না। লেসন ৩-এ pumping lemma আমাদের এই প্রশ্নের একটা কঠোর, প্রমাণযোগ্য উত্তর দেবে।

বুঝেছেন কি না দেখুন

1

Chomsky hierarchy-র চারটা স্তর তাদের production rule-এর নিষেধাজ্ঞা অনুযায়ী (সবচেয়ে কড়া থেকে সবচেয়ে শিথিল) সাজান, আর প্রতিটার সাথে মিলিত automaton class বলুন।

স্মরণ
স্তর (সবচেয়ে কড়া → শিথিল)Automaton
Type 3 — RegularFinite Automaton (DFA/NFA)
Type 2 — Context-FreePushdown Automaton (PDA)
Type 1 — Context-SensitiveLinear-Bounded Automaton (LBA)
Type 0 — Unrestricted (Recursively Enumerable)Turing Machine

সংখ্যাটা উল্টো মনে হতে পারে — Type সংখ্যা যত কম, grammar-এর নিয়ম তত শিথিল, তাই ভাষার শ্রেণি তত ব্যাপক। Type 3 সবচেয়ে নিষেধাজ্ঞাযুক্ত, তাই সবচেয়ে ছোট ভাষার শ্রেণি ধরে; Type 0-এ কোনো নিষেধাজ্ঞা নেই, তাই সবচেয়ে বড় শ্রেণি (সব computable ভাষা, এবং আরো — recursively enumerable-এ এমন ভাষাও আছে যেগুলোর জন্য কোনো program সবসময় থামে না)।

2

নিচের production rule সেটটা কোন Chomsky type-এ পড়ে, আর কেন?

S → aSb
S → ab
প্রয়োগ

এটা context-free (Type 2), এবং আসলে regular (Type 3) না।

কেন context-free: প্রতিটা rule-এর বাম পাশে ঠিক একটা nonterminal (S), আর ডান পাশ যেকোনো কিছু — এখানে aSb (nonterminal মাঝখানে) এবং ab। CFG-র শর্ত পূরণ হয়।

কেন regular না: Regular grammar-এ nonterminal শুধু ডান পাশের শেষে থাকতে পারে (right-linear) অথবা শুরুতে (left-linear), কখনো মাঝখানে না। S → aSb-তে S মাঝখানে বসে আছে (একটা a আগে, একটা b পরে) — এই “sandwiching” প্যাটার্নটাই 0ⁿ1ⁿ-জাতীয় ভাষার signature, আর ঠিক এই কারণেই regular grammar-এ প্রকাশ করা যায় না (লেসন ৩-এ প্রমাণ)।

এই grammar আসলে জেনারেট করে {aⁿbⁿ : n ≥ 1} — এই লেসনের 0ⁿ1ⁿ উদাহরণেরই একটা রূপ।

3

একজন সহকর্মী বলছেন: “আমাদের নতুন config file format-এর জন্য আমি পুরো grammar regex দিয়ে লিখে ফেলব, তাহলে parsing সহজ হবে।” Format-টাতে নেস্টেড section আছে (section-এর ভেতর section, যেকোনো গভীরতায়)। এই পরিকল্পনা নিয়ে কী বলবেন?

যুক্তি

এটা কাজ করবে না — কারণ নেস্টেড, যেকোনো-গভীরতার structure মূলগতভাবে non-regular। Regex (regular expression, theoretical অর্থে) সসীম state দিয়ে চলে — কোনো “বর্তমান nesting depth” মনে রাখতে পারে না, কারণ depth অসীম সংখ্যক মান নিতে পারে কিন্তু state সসীম।

এটা ঠিক এই লেসনের প্রথম experiment-এর মতো — balanced parentheses-এর একটা fixed-depth regex approximation লেখা যায়, কিন্তু general সমাধান নেই। সহকর্মীর regex “কাজ করবে” শুধু একটা নির্দিষ্ট সর্বোচ্চ nesting depth পর্যন্ত (আর প্রতিটা depth-এর জন্য regex আরো জটিল হবে) — production code-এ এটা একটা লুকানো bug হয়ে থাকবে যতক্ষণ না কেউ deep nesting দিয়ে test করে।

সঠিক পরামর্শ: এই config format-এর ভাষা context-free (nested section = matched bracket-এর মতো)। একটা ছোট CFG লিখুন (compilers/grammars-and-ambiguity-র মতো) আর একটা recursive descent বা existing parser library ব্যবহার করুন (compilers/parsing) — regex শুধু token-level কাজে (section নাম, key-value pattern চেনা) ব্যবহার করুন, পুরো nested structure-এ না। এটাই lexer/parser বিভাজনের ঠিক যুক্তি।

4

নিচের ভাষাগুলোর প্রতিটার জন্য অনুমান করুন (প্রমাণ ছাড়া, শুধু কাঠামো দেখে) এটা কোন Chomsky স্তরে পড়তে পারে, আর সংক্ষেপে যুক্তি দিন:

(ক) {w ∈ {a,b}* : w একটা palindrome} (খ) {aⁿbᵐ : n, m ≥ 0} (কোনো সম্পর্ক নেই n, m-এর মধ্যে) (গ) {aⁿbⁿcᵐdᵐ : n, m ≥ 0}

ডিজাইন

(ক) Palindrome — context-free। একটা string আর তার reverse মেলাতে stack লাগে — প্রথম অর্ধেক push করুন, মাঝ বিন্দুতে pop করতে শুরু করুন, প্রতিটা popped symbol ইনপুটের সাথে মিলছে কি না দেখুন। Grammar: S → aSa | bSb | a | b | ε। এটা regular না — কারণ “প্রথম অর্ধেক কী ছিল” মনে রাখতে unbounded memory লাগে।

(খ) aⁿbᵐ, কোনো সম্পর্ক ছাড়া — regular। এখানে n আর m স্বাধীন — কোনো matching/counting সম্পর্ক নেই যা মেলাতে হবে। Grammar: S → aS | A, A → bA | ε — right-linear, তাই regular। এটা এই লেসনের গুরুত্বপূর্ণ শিক্ষা: শুধু দুই ধরনের symbol একসাথে দেখলেই সেটা context-free ধরে নেওয়া ভুল — সম্পর্কটাই (এখানে n = m-এর অনুপস্থিতি) নির্ধারণ করে।

(গ) aⁿbⁿcᵐdᵐ — context-free, কিন্তু বিশেষভাবে চিন্তা করে। এটা দুইটা স্বাধীন matching সমস্যা — aⁿbⁿ অংশ আর cᵐdᵐ অংশ একে অপরের সাথে সম্পর্কিত না (n, m স্বাধীন)। প্রতিটা অংশ আলাদাভাবে context-free, আর দুইটা context-free ভাষার concatenation-ও context-free (এই বন্ধ-থাকা ধর্ম — closure property — পরের লেসনগুলোতে আরো আসবে)। Grammar: S → S₁ S₂, S₁ → aS₁b | ε, S₂ → cS₂d | ε। এটাকে aⁿbⁿcⁿdⁿ (তিনটা variable একই n)-এর সাথে গুলিয়ে ফেলবেন না — সেটা context-sensitive হয়ে যেত, ঠিক 0ⁿ1ⁿ2ⁿ-এর মতো, কারণ তখন স্বাধীন matching না, একটা একক ভাগ-করা গণনা।

এরপর কী

আজ আমরা পুরো সিঁড়িটা একনজরে দেখলাম — production rule-এর আকৃতি কীভাবে ভাষার ক্ষমতা নির্ধারণ করে, আর কীভাবে প্রতিটা স্তর একটা নির্দিষ্ট ধরনের memory-র সাথে মেলে (সসীম state, stack, tape, অসীম tape)।

পরের লেসনে আমরা সবচেয়ে নিচের, সবচেয়ে ব্যবহারিক স্তরে নামব: finite automata — DFA আর NFA-র আনুষ্ঠানিক সংজ্ঞা, তাদের সমতুল্যতার প্রমাণ (subset construction), আর কীভাবে ঠিক এই মডেলটাই compilers/lexical-analysis-এর lexer আর digital-logic/finite-state-machines-এর হার্ডওয়্যার FSM-এর আনুষ্ঠানিক ভিত্তি।

তারপর লেসন ৩-এ আমরা ফিরব regular expression-এ — এবার শুধু ব্যবহারিক regex না, প্রমাণ করব ঠিক কোন ভাষাগুলো regex দিয়ে ধরা যায় না, আর কেন — pumping lemma দিয়ে।

আরও পড়ুন

  • Introduction to the Theory of Computation (3rd ed.), Chapter 0 ও 2 — Michael Sipser · Formal language ও grammar-এর সবচেয়ে পঠনীয় introduction
  • Introduction to Automata Theory, Languages, and Computation (3rd ed.), Chapter 4, 9 — Hopcroft, Motwani, Ullman · Chomsky hierarchy-র সম্পূর্ণ ও কঠোর treatment
  • Three Models for the Description of Language — Noam Chomsky · IRE Transactions on Information Theory, 1956 — মূল hierarchy যেখানে প্রথম প্রস্তাবিত হয়েছিল, linguistics-এর প্রশ্ন থেকে