চমস্কি হায়ারার্কি — এই কোর্সের একটি রোডম্যাপ

The Chomsky hierarchy — a roadmap

৮ মিনিট পড়া শুরু · Beginner Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

চমস্কি হায়ারার্কির চারটি নেস্টেড স্তর — $\text{Type 3 (regular)} \subset \text{Type 2 (context-free)} \subset \text{Type 1 (context-sensitive)} \subset \text{Type 0 (unrestricted)}$ — প্রতিটি স্তর আগেরটির একটি প্রকৃত সাবসেট।
প্রতিটি স্তরের নিজস্ব অটোমাটা আছে — ফাইনাইট অটোমাটা (Type 3) → পুশডাউন অটোমাটা (Type 2) → লিনিয়ার বাউন্ডেড অটোমাটা (Type 1) → টুরিং মেশিন (Type 0)।
পাওয়ার বনাম প্র্যাক্টিক্যালিটি ট্রেড-অফ: বেশি শক্তিশালী অটোমাটা বেশি ভাষা চিনতে পারে, কিন্তু তাদের নিয়ে প্রশ্ন করা (যেমন "খালি কি না") তত বেশি কঠিন — এমনকি কিছু ক্ষেত্রে আনডিসাইডেবল হয়ে যায় (M9)।
এটি এই কোর্সের M2 থেকে M9 পর্যন্ত মডিউলের একটি সম্পূর্ণ মানচিত্র — সামনে কী আসছে তার একটি স্পষ্ট প্রিভিউ।

এই পাঠে যা শিখবেন

চমস্কি হায়ারার্কির চারটি স্তর এবং তাদের নেস্টেড সাবসেট সম্পর্ক
প্রতিটি স্তরের রিকগনাইজিং অটোমাটা
এই কোর্সের মডিউল কীভাবে হায়ারার্কির উপর ম্যাপ হয় — একটি সম্পূর্ণ রেফারেন্স টেবিল
পাওয়ার-বনাম-ডিসাইডেবিলিটি ট্রেড-অফ — কেন বেশি শক্তিশালী মেশিন মানে কম ডিসাইডেবল প্রশ্ন
Python দিয়ে একটি রেফারেন্স টেবিল ও একটি ফিচার-ভিত্তিক ক্লাসিফায়ার

১ · চারটি নেস্টেড স্তর

L01-এর ফ্লো-ডায়াগ্রামে আমরা DFA থেকে PDA থেকে টুরিং মেশিন পর্যন্ত একটি "গণনাশক্তির সিঁড়ি" দেখেছিলাম। এই পাঠে সেটিকে ফরমালি সম্প্রসারণ করছি — চমস্কি হায়ারার্কিChomsky Hierarchyগ্রামারের/ভাষার চারটি নেস্টেড স্তরের একটি শ্রেণীবিভাগ, প্রতিটি স্তরের প্রোডাকশন রুলের উপর ভিন্ন মাত্রার বিধিনিষেধ অনুযায়ী। হলো ভাষার চারটি নেস্টেড শ্রেণীর একটি শ্রেণীবিভাগ, প্রতিটি স্তর প্রোডাকশন রুলের উপর ভিন্ন মাত্রার বিধিনিষেধ দিয়ে সংজ্ঞায়িত ( programming-languages-compilers L15-এ পড়ে থাকলে পরিচিত হবে — এখানে গভীরতর তাত্ত্বিক ফোকাস, পরবর্তী প্রতিটি মডিউল এই একই কাঠামো অনুসরণ করবে)।

$$\text{Type 3 (regular)} \subset \text{Type 2 (context-free)} \subset \text{Type 1 (context-sensitive)} \subset \text{Type 0 (unrestricted)}$$

প্রতিটি $\subset$ চিহ্ন একটি প্রকৃত সাবসেট সম্পর্ক বোঝায় — অর্থাৎ প্রতিটি regular ভাষা context-free-ও (কিন্তু বিপরীতটা সবসময় সত্য নয় — এমন context-free ভাষা আছে যা regular নয়, M3/L14-এ প্রমাণসহ দেখানো হবে)।

প্রতিটি ভেতরের স্তর বাইরের স্তরের একটি প্রকৃত সাবসেট — Type 3-এর প্রতিটি ভাষা Type 0-এরও একটি ভাষা, কিন্তু বিপরীতটা সত্য নয়।

২ · এই কোর্সের মডিউল ম্যাপিং

Type 3 · Regular
ফাইনাইট অটোমাটা (DFA/NFA) — M2 (L06-L11), প্রপার্টি M3 (L12-L16)। উদাহরণ: জোড়-সংখ্যক 1 থাকা স্ট্রিং।

Type 2 · Context-Free
পুশডাউন অটোমাটা (PDA) — গ্রামার M4 (L17-L21), PDA M5 (L22-L25), প্রপার্টি M6 (L26-L28)। উদাহরণ: ব্যালেন্সড বন্ধনী।

Type 1 · Context-Sensitive
লিনিয়ার বাউন্ডেড অটোমাটা (LBA) — M7 (L29-L31)। উদাহরণ: $\{a^nb^nc^n : n\geq0\}$।

Type 0 · Unrestricted
টুরিং মেশিন — M8 (L32-L37), ডিসাইডেবিলিটি M9 (L38-L42)। উদাহরণ: হল্টিং প্রবলেমের ভাষা।

৩ · পাওয়ার বনাম প্র্যাক্টিক্যালিটি — একটি গুরুত্বপূর্ণ ট্রেড-অফ

হায়ারার্কিতে যত ডানে/নিচে যাওয়া যায় (Type 3 → Type 0), অটোমাটা তত বেশি ভাষা চিনতে পারে — কিন্তু সেই অটোমাটা সম্পর্কে প্রশ্ন করা তত বেশি কঠিন হয়ে যায়। উদাহরণস্বরূপ, "এই ভাষা কি খালি (empty)?" প্রশ্নটি —

regular ও context-free ভাষার জন্য সবসময় algorithmically decidable (M3/L16, M6/L28) — একটি নিশ্চিত অ্যালগরিদম আছে যা সবসময় সঠিক উত্তর দেয়।
কিন্তু টুরিং মেশিন/Type 0-এর জন্য সাধারণভাবে undecidable (M9) — এমন কোনো অ্যালগরিদমই থাকতে পারে না যা সব টুরিং মেশিনের জন্য সঠিকভাবে এই প্রশ্নের উত্তর দেয়।

এই ট্রেড-অফ কেন গুরুত্বপূর্ণ

এটি একটি বারবার-ফিরে-আসা থিম — যত বেশি শক্তি (expressiveness), তত কম নিয়ন্ত্রণ (analyzability)। এই কোর্স জুড়ে প্রতিটি নতুন মডিউল এই একই প্রশ্ন নতুন করে জিজ্ঞাসা করবে — এই স্তরের অটোমাটা দিয়ে কোন প্রশ্নগুলো এখনও decidable, আর কোনগুলো নয়।

৪ · Python-এ হায়ারার্কি রেফারেন্স টেবিল ও ক্লাসিফায়ার

নিচের কোড সেলে চমস্কি হায়ারার্কির একটি সম্পূর্ণ রেফারেন্স টেবিল তৈরি করা হচ্ছে (এই পুরো কোর্সের রোডম্যাপ হিসেবে), এবং একটি ছোট্ট classify_by_features ফাংশন — যা একটি গ্রামারের সরলীকৃত প্রোডাকশন-বিধিনিষেধ দেখে সঠিক Type চিহ্নিত করে।

Python

chomsky_table = {
    "Type 3 (Regular)": {
        "automaton": "Finite Automaton (DFA/NFA)",
        "modules": "M2-M3 (L06-L16)",
        "example_language": "জোড়-সংখ্যক 1 থাকা বাইনারি স্ট্রিং",
        "membership_decidable": True,
    },
    "Type 2 (Context-Free)": {
        "automaton": "Pushdown Automaton (PDA)",
        "modules": "M4-M6 (L17-L28)",
        "example_language": "ব্যালেন্সড বন্ধনী",
        "membership_decidable": True,
    },
    "Type 1 (Context-Sensitive)": {
        "automaton": "Linear Bounded Automaton (LBA)",
        "modules": "M7 (L29-L31)",
        "example_language": "{ a^n b^n c^n : n >= 0 }",
        "membership_decidable": True,
    },
    "Type 0 (Unrestricted / Recursively Enumerable)": {
        "automaton": "Turing Machine",
        "modules": "M8-M9 (L32-L42)",
        "example_language": "হল্টিং প্রবলেমের ভাষা",
        "membership_decidable": False,
    },
}

print(f"{'Chomsky Type':46s} | {'অটোমাটা':28s} | {'মডিউল':16s} | Decidable?")
print("-" * 110)
for chomsky_type, info in chomsky_table.items():
    print(f"{chomsky_type:46s} | {info['automaton']:28s} | {info['modules']:16s} | {info['membership_decidable']}")

def classify_by_features(features):
    """features: gramar-er production-rule bidhinishedh borno kore emon ekti dict"""
    if features.get("right_linear"):
        return "Type 3 (Regular)"
    if features.get("single_nonterminal_lhs"):
        return "Type 2 (Context-Free)"
    if features.get("non_contracting"):
        return "Type 1 (Context-Sensitive)"
    return "Type 0 (Unrestricted)"

examples = [
    ("রেগুলার-স্টাইল গ্রামার (A -> aB | a)",
     {"right_linear": True, "single_nonterminal_lhs": True, "non_contracting": True}),
    ("CFG-স্টাইল গ্রামার (S -> (S)S | ε)",
     {"right_linear": False, "single_nonterminal_lhs": True, "non_contracting": True}),
    ("কনটেক্সট-সেনসিটিভ গ্রামার (aAb -> aBb, non-contracting, multi-symbol LHS)",
     {"right_linear": False, "single_nonterminal_lhs": False, "non_contracting": True}),
    ("আনরেস্ট্রিক্টেড গ্রামার (aAb -> ε, contracting)",
     {"right_linear": False, "single_nonterminal_lhs": False, "non_contracting": False}),
]

print()
for description, features in examples:
    result = classify_by_features(features)
    print(f"{description}\n  -> classify হলো: {result}\n")

লক্ষ্য করুন classify_by_features-এর চেক-অর্ডার গুরুত্বপূর্ণ — right-linear হলে সবচেয়ে কড়া বিধিনিষেধ (Type 3), তারপর single-nonterminal-LHS (Type 2), তারপর non-contracting (Type 1), সবশেষে কোনো বিধিনিষেধ না থাকলে Type 0 — ঠিক হায়ারার্কির নেস্টিং অনুযায়ী, সবচেয়ে সংকীর্ণ শর্ত আগে যাচাই হচ্ছে।

মূল কথা · Key takeaway

চমস্কি হায়ারার্কি এই পুরো কোর্সের কাঠামো — M2 থেকে M9 পর্যন্ত প্রতিটি মডিউল এই চারটি স্তরের একটির উপর ফোকাস করবে, একই প্যাটার্নে (ফরমাল ডেফিনিশন → রিকগনাইজিং অটোমাটা → প্রপার্টি → ডিসিশন প্রবলেম)। পরের পাঠ (L05) দেখাবে কীভাবে যেকোনো সিদ্ধান্তমূলক সমস্যাকেই একটি ভাষা হিসেবে দেখা যায় — এই পুরো কাঠামোর গভীরতম প্রেরণা।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ "Type 3 ⊂ Type 2" মানে ঠিক কী — এর মানে কি সব context-free ভাষাও regular?

না, উল্টো — $\text{Type 3} \subset \text{Type 2}$ মানে সব regular ভাষা context-free-ও (কারণ regular একটি বিশেষ, আরও সীমাবদ্ধ ধরনের context-free গ্রামার দিয়েই লেখা যায়), কিন্তু বিপরীতটা সত্য নয়। এমন context-free ভাষা আছে (যেমন ব্যালেন্সড বন্ধনী, বা $\{0^n1^n\}$) যা regular নয় — M3/L14-এ pumping lemma দিয়ে এই "regular নয়" দাবিটি ফরমালি প্রমাণ করা হবে।

প্র ০২ যদি একটি টুরিং মেশিন (Type 0) সবচেয়ে শক্তিশালী মেশিন হয়, তাহলে DFA/PDA ব্যবহার করার কোনো লাভ আছে কি — কেন সবসময় টুরিং মেশিন ব্যবহার করা হয় না?

দুটি বড় কারণে। প্রথমত, প্র্যাক্টিক্যাল কারণ — DFA/PDA-এর মতো সীমিত মেশিন অনেক বেশি efficient (দ্রুত, কম মেমরি) এমন ভাষার জন্য যেগুলো আসলেই regular/context-free (যেমন compiler-এর লেক্সার/পার্সার — ../programming-languages-compilers/ দ্রষ্টব্য)। দ্বিতীয়ত, তাত্ত্বিক কারণ — সীমিত মেশিন সম্পর্কে অনেক বেশি প্রশ্নের নিশ্চিত (decidable) উত্তর পাওয়া যায় (L04-এর "পাওয়ার বনাম প্র্যাক্টিক্যালিটি" বিভাগ দ্রষ্টব্য) — টুরিং মেশিনের ক্ষেত্রে এই একই প্রশ্নগুলোর অনেকগুলোই আনডিসাইডেবল হয়ে যায় (M9)। তাই "সবচেয়ে শক্তিশালী" সবসময় "সবচেয়ে ভালো পছন্দ" নয়।

প্র ০৩ উপরের কোড সেলের classify_by_features-এ যদি চেক-অর্ডার উল্টো করা হয় (Type 0 আগে চেক করে, Type 3 শেষে), তাহলে কী সমস্যা হবে?

যেহেতু একটি right-linear গ্রামার (Type 3) স্বয়ংক্রিয়ভাবে single-nonterminal-LHS-ও (Type 2-এর শর্ত) এবং non-contracting-ও (Type 1-এর শর্ত) — সব শর্তই একসাথে সত্য থাকতে পারে একটি নির্দিষ্ট গ্রামারের জন্য। যদি চেক-অর্ডার উল্টো করা হয় (সবচেয়ে সাধারণ/আলগা শর্ত আগে চেক করা), তাহলে একটি প্রকৃত Type 3 গ্রামারও ভুলভাবে "Type 0" হিসেবে classify হয়ে যেত, কারণ Type 0-এর শর্ত (কোনো বিধিনিষেধ নেই) সবসময় সত্য। তাই সঠিকভাবে classify করতে সবচেয়ে সংকীর্ণ/কড়া শর্ত থেকে শুরু করে ধীরে ধীরে আলগা শর্তের দিকে যাচাই করা জরুরি — ঠিক নেস্টেড হায়ারার্কির গঠন অনুযায়ী।

অনুশীলন

চিন্তা করুন: $\{a^nb^nc^n : n \geq 0\}$ ভাষাটি (উদাহরণস্বরূপ "abc", "aabbcc") — এটি কোন Chomsky Type-এর প্রতিনিধিত্ব করে উপরের টেবিল অনুযায়ী, এবং কেন এটি context-free (Type 2) নয় বলে মনে করা হয় (একটি পূর্ণ প্রমাণ M6/L26-এ আসবে, কিন্তু স্বজ্ঞা এখনই ভাবুন)?

এটি Type 1 (context-sensitive)-এর উদাহরণ। স্বজ্ঞাগতভাবে — একটি PDA-এর একটিমাত্র স্ট্যাক আছে, যা একসাথে দুটি স্বাধীন "গণনা" (একইসাথে $a$-এর সংখ্যা $b$-এর সাথে, আবার $b$-এর সংখ্যা $c$-এর সাথে মেলানো) ট্র্যাক করতে যথেষ্ট নয় — একটি স্ট্যাক দিয়ে সহজে দুটি সংখ্যা (n এবং n) মেলানো যায় ($a^nb^n$-এর মতো, M5/L22-এ PDA দিয়ে দেখানো হবে), কিন্তু তিনটি একসাথে মেলাতে অতিরিক্ত মেমরি লাগে যা LBA-এর ফাইনাইট কিন্তু ইনপুট-সমানুপাতিক টেপ দিতে পারে।
পরীক্ষা করুন: উপরের কোড সেলে classify_by_features-এ একটি নতুন feature-set যোগ করুন যেখানে right_linear=False, single_nonterminal_lhs=True, non_contracting=False — এটি কোন Type হিসেবে classify হবে হাতে অনুমান করে তারপর কোড চালিয়ে যাচাই করুন।

right_linear=False হওয়ায় প্রথম শর্ত ব্যর্থ; কিন্তু single_nonterminal_lhs=True হওয়ায় দ্বিতীয় শর্ত সত্য হয়ে যাবে — ফলাফল "Type 2 (Context-Free)"। লক্ষ্য করুন non_contracting=False এখানে কোনো প্রভাব ফেলে না, কারণ ফাংশনটি দ্বিতীয় শর্তেই থেমে যায় — এটি দেখায় CFG-শর্ত (single-nonterminal LHS) নিজেই non-contracting-এর চেয়ে কড়া, তাই CFG-এর জন্য non-contracting আলাদা করে যাচাই করার দরকার নেই।