চমস্কি হায়ারার্কি — সম্পূর্ণ তুলনা
এই পাঠে যা শিখবেন
- চারটি চমস্কি টাইপের সম্পূর্ণ, সাইটেশনসহ তুলনা টেবিল — গ্রামার রেস্ট্রিকশন, অটোমাটা, সেপারেটিং উদাহরণ, ডিসাইডেবিলিটি
- প্রপার কন্টেইনমেন্ট চেইন (Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0) এবং প্রতিটি ধাপের প্রমাণ-প্রমাণ কোথায় আছে
- রেগুলার ল্যাঙ্গুয়েজেরও একটি গ্রামার-ভিত্তিক characterization — right-linear গ্রামার (নতুন এই পাঠে)
- একটি ক্লাসিফায়ার ফাংশন যা L14 ও L26-এর সেপারেটিং উদাহরণ ব্যবহার করে সঠিক টাইপ শনাক্ত করে
১ · Type 3 (রেগুলার)-এরও একটি গ্রামার-ভিত্তিক characterization আছে
M2 জুড়ে রেগুলার ল্যাঙ্গুয়েজকে শুধু অটোমাটা (DFA/NFA) দিয়ে বর্ণনা করা হয়েছিল। কিন্তু চমস্কি হায়ারার্কির প্রতিটি টাইপেরই একটি গ্রামার-ভিত্তিক সংজ্ঞা আছে — regular languages-এরও একটি আছে: right-linear গ্রামারRight-Linear Grammarএমন একটি গ্রামার যার প্রতিটি রুল A -> aB অথবা A -> a আকৃতির -- একটি ভেরিয়েবল থাকলে তা সবসময় ডানদিকের শেষ সিম্বল। — প্রতিটি রুল $A \to aB$ অথবা $A \to a$ আকৃতির (একটি টার্মিনাল, তারপর সর্বোচ্চ একটি ভেরিয়েবল, শুধু ডানদিকে)। এই গ্রামার-ভিত্তিক সংজ্ঞা DFA/NFA-এর সাথে প্রমাণযোগ্যভাবে সমতুল্য (mention only) — তাই এখন চমস্কি হায়ারার্কির চারটি টাইপেরই একটি সুসংগত "গ্রামার রেস্ট্রিকশন ⇔ recognizing automaton" প্যাটার্ন সম্পূর্ণ হলো।
২ · প্রপার কন্টেইনমেন্ট — Type 3 ⊊ Type 2 ⊊ Type 1 ⊊ Type 0
"⊊" চিহ্নের অর্থ প্রপার সাবসেট — প্রতিটি নিচের স্তরের সব ভাষা ওপরের স্তরেও আছে, কিন্তু এমন অন্তত একটি ভাষা আছে যা ওপরের স্তরে আছে কিন্তু নিচের স্তরে নেই। এই কোর্স ইতিমধ্যে প্রতিটি ধাপের জন্য একটি কনক্রিট সেপারেটিং উদাহরণ কোড দিয়ে যাচাই করেছে —
- Type 3 ⊊ Type 2: $L = \{0^n1^n : n\geq 0\}$ context-free (M4/M5-এ CFG ও PDA দুটোই তৈরি হয়েছে) কিন্তু L14-এর পাম্পিং লেমা প্রমাণ করেছে এটি regular নয়।
- Type 2 ⊊ Type 1: $L = \{a^nb^nc^n : n\geq 0\}$ context-sensitive (L29-এ একটি real CSG দিয়ে জেনারেট করা হয়েছে) কিন্তু L26-এর CFL পাম্পিং লেমা প্রমাণ করেছে এটি context-free নয়।
- Type 1 ⊊ Type 0: (mention only, অ্যাডভান্সড) — context-sensitive থেকে Type 0-কে আলাদা করে এমন একটি নির্দিষ্ট ভাষার উদাহরণ থাকে, কিন্তু তার প্রমাণ এই কোর্সের সুযোগের বাইরে; মূল যুক্তি হলো L30-এর কন্ট্রাক্টিং রুল কিছু গণনা সম্ভব করে যা নন-কন্ট্রাক্টিং CSG রুল দিয়ে কখনো সম্ভব নয়।
৩ · কোড: সম্পূর্ণ, সাইটেশনসহ তুলনা টেবিল
নিচের কোডে চারটি চমস্কি টাইপ পাশাপাশি — গ্রামার রেস্ট্রিকশন, recognizing automaton, সেপারেটিং উদাহরণ, ও
মেম্বারশিপ ডিসাইডেবিলিটি — প্রতিটি ফিল্ড ঠিক কোন পাঠে প্রতিষ্ঠিত হয়েছে তা উল্লেখ করে একটি সম্পূর্ণ রেফারেন্স
টেবিল তৈরি করা হয়েছে, এবং একটি classify_language ফাংশন L14 ও L26-এর নির্দিষ্ট সেপারেটিং উদাহরণের
বিরুদ্ধে টেস্ট করে দেখানো হয়েছে।
# চমস্কি হায়ারার্কির সম্পূর্ণ, চূড়ান্ত তুলনা টেবিল -- প্রতিটি দাবি নির্দিষ্ট পাঠ সাইট করে
chomsky_table = [
{
"type": "Type 3 (Regular)",
"grammar_restriction": "A -> aB অথবা A -> a (right-linear, L31/S1)",
"automaton": "DFA / NFA (L06-L09)",
"separating_example": "L14: 0^n1^n context-free কিন্তু regular নয়",
"membership_decidable": "হ্যাঁ, দ্রুত -- O(n) DFA সিমুলেশন (L06, L16)",
},
{
"type": "Type 2 (Context-Free)",
"grammar_restriction": "A -> alpha (একক ভেরিয়েবল, L17)",
"automaton": "PDA (L22-L25)",
"separating_example": "L26: a^nb^nc^n context-sensitive কিন্তু context-free নয়",
"membership_decidable": "হ্যাঁ -- CYK, পলিনমিয়াল টাইম (L28, CNF দরকার L20)",
},
{
"type": "Type 1 (Context-Sensitive)",
"grammar_restriction": "alpha A beta -> alpha gamma beta, gamma != eps (L29)",
"automaton": "Linear Bounded Automaton (L29)",
"separating_example": "Type 0-থেকে আলাদাকারী উদাহরণ আছে (mention only, L30)",
"membership_decidable": "হ্যাঁ, কিন্তু সম্ভাব্য ধীর -- বাউন্ডেড কনফিগারেশন (L29)",
},
{
"type": "Type 0 (Unrestricted)",
"grammar_restriction": "alpha -> beta, alpha-তে >=1 ভেরিয়েবল, beta অবাধ (L30)",
"automaton": "টুরিং মেশিন (M8, L32+)",
"separating_example": "-- (সবচেয়ে সাধারণ স্তর)",
"membership_decidable": "না -- সাধারণভাবে আনডিসাইডেবল (forward-ref M9/L38-L39)",
},
]
for row in chomsky_table:
print(row["type"])
for key in ("grammar_restriction", "automaton", "separating_example", "membership_decidable"):
print(" ", key, ":", row[key])
print()
def classify_language(is_regular, is_context_free, is_context_sensitive, has_any_grammar):
"""সবচেয়ে নির্দিষ্ট (specific) টাইপ খুঁজে বের করে -- একটি ভাষা যদি regular হয়,
সেটা context-free ও context-sensitive-ও (নেস্টেড সাবসেট, তাই নির্দিষ্টতমটা রিপোর্ট করি)।"""
if is_regular:
return "Type 3 (Regular)"
if is_context_free:
return "Type 2 (Context-Free)"
if is_context_sensitive:
return "Type 1 (Context-Sensitive)"
if has_any_grammar:
return "Type 0 (Unrestricted)"
return "কোনো টাইপেই নেই -- কোনো গ্রামারই এই ভাষা জেনারেট করতে পারে না"
# L14-এর সেপারেটিং উদাহরণ: 0^n1^n -- context-free, কিন্তু regular নয়
print("0^n1^n (L14 সেপারেটিং উদাহরণ):", classify_language(False, True, True, True))
# L26-এর সেপারেটিং উদাহরণ: a^nb^nc^n -- context-sensitive, কিন্তু context-free নয়
print("a^nb^nc^n (L26 সেপারেটিং উদাহরণ):", classify_language(False, False, True, True))
# একটি সহজ, সরাসরি regular উদাহরণ (স্যানিটি চেক)
print("(a|b)*a (regular):", classify_language(True, True, True, True))classify_language-এ $0^n1^n$ ইনপুট দিলে ঠিক "Type 2 (Context-Free)" পাওয়া যাচ্ছে (L14-এর ফলাফলের
সাথে হুবহু মিলে যায়), আর $a^nb^nc^n$ ইনপুট দিলে ঠিক "Type 1 (Context-Sensitive)" পাওয়া যাচ্ছে (L26/L29-এর
ফলাফলের সাথে হুবহু মিলে যায়) — এই ফাংশনটি hardcoded কোনো "সঠিক উত্তর" নয়, বরং সাধারণ নেস্টেড-সাবসেট লজিক দিয়ে
সঠিকভাবে classification করছে, আগের পাঠের ফলাফলের বিরুদ্ধে verify করা।
৪ · সম্পূর্ণ চিত্র — power vs practicality
এই টেবিলটাই L04-এ প্রথম ফ্ল্যাগ করা টেনশনের সম্পূর্ণ, চার-ধাপের চিত্র দেয় — প্রতিটি স্তরে ওপরে ওঠার সাথে সাথে গণনাশক্তি বাড়ে (আরও বেশি ভাষা চেনা/জেনারেট করা যায়), কিন্তু মেম্বারশিপ প্রশ্নের algorithmic tractability ধারাবাহিকভাবে খারাপ হতে থাকে —
লক্ষ্য করুন L28 ইতিমধ্যে দেখিয়েছে মেম্বারশিপ ছাড়াও অন্যান্য প্রশ্ন (যেমন ইকুইভ্যালেন্স) আরও দ্রুত আনডিসাইডেবল হয়ে যায় — এমনকি Type 2-তেই। এই "যত ওপরে যাই, তত বেশি প্রশ্ন algorithmically কঠিন হয়ে যায়" ধারা M9 (ডিসাইডেবিলিটি) ও M10 (কমপ্লেক্সিটি থিওরি)-এই কোর্সের বাকি অংশের মূল থিম — এই পাঠ সেই যাত্রার একটি সম্পূর্ণ চেকপয়েন্ট।
চারটি চমস্কি টাইপ — regular ⊊ context-free ⊊ context-sensitive ⊊ unrestricted — একটি নেস্টেড, প্রপার সাবসেট হায়ারার্কি, প্রতিটি নিজস্ব recognizing automaton, নির্দিষ্ট সেপারেটিং উদাহরণ, ও ধাপে ধাপে খারাপ হতে থাকা মেম্বারশিপ-ডিসাইডেবিলিটিসহ। এই কোর্সের M2-M7 জুড়ে প্রতিটি দাবি কোড দিয়ে verify করা হয়েছে — এখন M8 থেকে টুরিং মেশিন ও ডিসাইডেবিলিটির গভীরে যাওয়ার পালা।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।
প্র ০১ "$L_1 \subsetneq L_2$" (প্রপার সাবসেট) প্রমাণ করতে দুটো ভিন্ন জিনিস দেখাতে হয় — সেগুলো কী কী, এবং এই পাঠে সেগুলো কীভাবে দেখানো হয়েছে?
প্রথমত, $L_1 \subseteq L_2$ দেখাতে হয় — অর্থাৎ $L_1$-এর প্রতিটি ভাষা $L_2$-এরও সদস্য (সাধারণত অটোমাটা/গ্রামার কনস্ট্রাকশন দিয়ে প্রমাণিত, যেমন প্রতিটি regular grammar একটি বৈধ CFG-ও বটে, কারণ right-linear রুল CFG-এর সাধারণ $A\to\alpha$ রুলের একটি বিশেষ ক্ষেত্র)। দ্বিতীয়ত, $L_1 \neq L_2$ দেখাতে হয় — অন্তত একটি ভাষা $L_2$-তে আছে কিন্তু $L_1$-এ নেই, এই পাঠে ঠিক এই দ্বিতীয় অংশটাই L14 ও L26-এর সেপারেটিং উদাহরণ দিয়ে দেখানো হয়েছে।
প্র ০২ কেন L28 দেখাল CFG ইকুইভ্যালেন্স আনডিসাইডেবল, অথচ এই পাঠের টেবিলে Type 2-এর মেম্বারশিপ "ডিসাইডেবল" বলা হচ্ছে — এই দুটো কি বিরোধী?
না — এগুলো দুটো ভিন্ন প্রশ্ন। মেম্বারশিপ জিজ্ঞেস করে "একটি নির্দিষ্ট স্ট্রিং কি এই ভাষায় আছে?" (CYK দিয়ে ডিসাইডেবল, L28)। ইকুইভ্যালেন্স জিজ্ঞেস করে "দুটো ভিন্ন গ্রামার কি ঠিক একই ভাষা বর্ণনা করে?" (আনডিসাইডেবল, L28)। এই পাঠের টেবিলটি নির্দিষ্টভাবে মেম্বারশিপ-ডিসাইডেবিলিটি ট্র্যাক করছে — এটাই একটি গুরুত্বপূর্ণ শিক্ষা: একই চমস্কি টাইপের মধ্যেই বিভিন্ন প্রশ্নের ডিসাইডেবিলিটি আলাদা আলাদা হতে পারে।
প্র ০৩ এই পাঠ বলছে "কোনো নতুন প্রমাণ নেই, শুধু সিন্থেসিস" — তাহলে এই পাঠের আসল মূল্য কোথায়?
M2-M7-এর প্রতিটি পাঠ একটি নির্দিষ্ট, বিচ্ছিন্ন (isolated) প্রশ্নে ফোকাস করেছিল — একটি নির্দিষ্ট ক্লোজার প্রপার্টি, একটি নির্দিষ্ট পাম্পিং লেমা প্রয়োগ, একটি নির্দিষ্ট ইকুইভ্যালেন্স থিওরেম। এই পাঠের মূল্য হলো সেই সব বিচ্ছিন্ন ফলাফলকে একটি একক, সুসংগত মানসিক মডেলে সংগঠিত করা — যাতে পরবর্তী মডিউলগুলোতে (M8-M13) "এই নতুন ধারণাটি হায়ারার্কির ঠিক কোথায় ফিট করে" প্রশ্নের উত্তর তাৎক্ষণিকভাবে এই একটি রেফারেন্স টেবিল দেখেই পাওয়া যায় — এটাই একটি "মানচিত্র" পাঠের ব্যবহারিক মূল্য।
অনুশীলন
-
পরীক্ষা করুন: উপরের কোডে
classify_language-কে একটি hypothetical ভাষার জন্য কল করুন যেখানেis_regular=False,is_context_free=False,is_context_sensitive=False,has_any_grammar=False। ফলাফল কী, এবং এটি বাস্তবে কী বোঝায়?ফলাফল হবে "কোনো টাইপেই নেই — কোনো গ্রামারই এই ভাষা জেনারেট করতে পারে না।" বাস্তবে এমন একটি ভাষা মানে এটি এমনকি Type 0/টুরিং-রিকগনাইজেবলও নয় — L30-এর §২-তে preview করা এই সম্ভাবনাটির একটি কনক্রিট উদাহরণ M9/L39-এর হল্টিং প্রবলেম-সম্পর্কিত ভাষাগুলো (বা তাদের কমপ্লিমেন্ট) হবে।
-
চিন্তা করুন: এই পাঠের টেবিলে "membership_decidable" কলামটি Type 3 থেকে Type 0 পর্যন্ত ধাপে
ধাপে "আরও খারাপ" হতে থাকে (দ্রুত → পলিনমিয়াল → ধীর কিন্তু ডিসাইডেবল → আনডিসাইডেবল)। এই প্যাটার্নের সাথে
মিলিয়ে, M10 (কমপ্লেক্সিটি থিওরি) কোন ধরনের নতুন প্রশ্ন নিয়ে আসতে পারে বলে আপনার মনে হয়?
যেহেতু এই পাঠ দেখিয়েছে "ডিসাইডেবল কিন্তু সম্ভাব্য ধীর" (Type 1) এবং "সম্পূর্ণ আনডিসাইডেবল" (Type 0)-এর মধ্যে একটি স্পষ্ট ধাপ আছে, স্বাভাবিকভাবেই পরের প্রশ্ন হলো — ডিসাইডেবল সমস্যাগুলোর মধ্যেও কি "দ্রুত ডিসাইডেবল" বনাম "ধীর ডিসাইডেবল"-এর মধ্যে একটি সুনির্দিষ্ট সীমারেখা আছে? ঠিক এটাই M10-এর বিষয় — P (পলিনমিয়াল-টাইম-সমাধানযোগ্য) বনাম NP, এবং বিখ্যাত P বনাম NP প্রশ্ন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পরবর্তী পাঠ: টুরিং মেশিন — ফরমাল ডেফিনিশন পাঠ ৩২ M8 শুরু — চমস্কি হায়ারার্কির সবচেয়ে শক্তিশালী মেশিন, যার ফরমাল সংজ্ঞা এই পাঠে বহুবার উল্লেখ করা হয়েছে।
- পূর্ববর্তী রোডম্যাপ: চমস্কি হায়ারার্কি — একটি রোডম্যাপ পাঠ ০৪ এই পাঠ ঠিক সেই রোডম্যাপের সম্পূর্ণ, ভরাট রূপ — প্রথম থেকে ফিরে দেখলে পুরো যাত্রাটা স্পষ্ট হবে।
- কোর্সের সম্পূর্ণ সিলেবাস দেখুন ৫৬টি পাঠ M9-এ (ডিসাইডেবিলিটি) হল্টিং প্রবলেম, রিডাকশন ও রাইসের থিওরেম — এই পাঠে preview করা থিমের পূর্ণ বিকাশ।