এই পর্বে যা শিখবেন
- CFG-এর membership problem কেন কঠিন দেখায়, আর dynamic programming কীভাবে একে polynomial করে
- যেকোনো CNF grammar আর string-এর CYK টেবিল হাতে ভরা, ঘর ধরে ধরে, প্রতিটি split দেখে
- CYK-এর সঠিকতার প্রমাণ (দৈর্ঘ্যের ওপর induction) আর O(n3) সময়ের হিসাব
- Back-pointer থেকে parse tree পুনর্গঠন, parse tree গোনা, আর টেবিল দেখে ambiguity ধরা
- বাস্তবের parser-এর সঙ্গে CYK-এর তুলনা: lark-এর Earley, Valiant-এর দ্রুত পদ্ধতি, আর LL/LR
১ · Membership problem — “এই string কি grammar-এর language-এ আছে?”
বাজারঘরের admin panel-এ কেউ একটি order-query লিখলেন: FIND order WHERE amount >= 1000 AND district = "Dhaka". পর্ব ২২-এর lexer এটিকে token-এ ভাঙে, আর পর্ব ২৫-এ লেখা grammar ঠিক করে কোন token-ক্রম বৈধ query. সিস্টেমের প্রথম প্রশ্ন খুব সরল: এই token-ক্রমটি কি grammar-এর language-এ আছে, হ্যাঁ বা না? এই প্রশ্নের নাম membership problem. Formal রূপে, Sipser-এর রীতিতে:
এখানে ⟨G, w⟩ মানে grammar আর string দুটিকে একসঙ্গে একটি string-এ লেখা (পর্ব ০৫-এর encoding). প্রশ্ন হলো, এমন কোনো algorithm আছে কি, যা প্রতিটি ⟨G, w⟩-তে থেমে সঠিক উত্তর দেয়? আর থাকলে, কত দ্রুত?
Regular language-এর জন্য উত্তরটি সহজ ছিল। পর্ব ২০-এ দেখেছেন, DFA-কে w-এর ওপর একবার চালালেই |w|টি ধাপে উত্তর মেলে। CFG-তে কোনো “চালানোর যন্ত্র” সরাসরি হাতে নেই; আছে শুধু নিয়ম। প্রথম যে চিন্তা মাথায় আসে: start symbol থেকে সব derivation চেষ্টা করে দেখা, w আসে কি না। কিন্তু grammar-এ E → T বা T → F-এর মতো নিয়ম থাকলে derivation string না বাড়িয়েই ঘুরতে পারে, আর ε-নিয়ম থাকলে string ছোটও হতে পারে। তাহলে কখন থামবেন?
এখানে পর্ব ২৬-এর একটি ফল আর পর্ব ২৯-এর normal form কাজে লাগে। Chomsky normal form-এ প্রতিটি নিয়ম A → BC বা A → a, আর দৈর্ঘ্য n ≥ 1-এর string-এর প্রতিটি derivation ঠিক 2n − 1 ধাপের। কারণ গাছে n-টি পাতা, তাদের ঠিক ওপরে n-টি A → a node, আর বাকি ভেতরের node-গুলো দুই সন্তানের, যারা সংখ্যায় n − 1. তাই একটি সীমাবদ্ধ খোঁজ সম্ভব: 2n − 1 ধাপের সব leftmost derivation চেষ্টা করুন। এটি থামে, তাই ACFG decidable. কিন্তু প্রতিটি ধাপে |R|টি পর্যন্ত নিয়মের বিকল্প, মোট প্রায় |R|2n−1টি পথ। ২০টি token-এর একটি ছোট query-তেও এই সংখ্যা জ্যোতির্বিজ্ঞানের মাপে পৌঁছায়।
বাজারঘরের গুদামে একটি লম্বা তাকে সারি করে পণ্য রাখা। ম্যানেজার জানতে চান, পুরো সারিটি কি একটি বৈধ “বড় প্যাকেজ”? নিয়ম হলো: দুটি বৈধ ছোট প্যাকেজ পাশাপাশি জুড়লে একটি বড় প্যাকেজ হয়, আর প্রতিটি একক পণ্য নিজে একটি প্যাকেজ। একজন নতুন কর্মী প্রতিবার পুরো সারি নতুন করে ভাঙতে শুরু করেন, একই ছোট অংশ বারবার পরীক্ষা করেন। একজন অভিজ্ঞ কর্মী একটি খাতা রাখেন: আগে প্রতিটি পণ্য, তারপর পাশাপাশি দুটি, তারপর তিনটি, এভাবে প্রতিটি একটানা অংশের পাশে লিখে রাখেন “এটি কোন ধরনের প্যাকেজ হতে পারে”. বড় অংশের প্রশ্ন এলে তিনি শুধু খাতা দেখেন: অংশটিকে কোথাও দুই ভাগ করলে দুই ভাগই কি খাতায় বৈধ? এই খাতাই CYK টেবিল।
অভিজ্ঞ কর্মীর কৌশলটির নাম dynamic programming: বড় সমস্যাকে একে অপরের ওপর নির্ভরশীল ছোট উপসমস্যায় ভাঙা, আর প্রতিটি উপসমস্যার উত্তর একবার হিসাব করে রেখে দেওয়া। DSA কোর্সের পর্ব ৫২-এ এর ভিত্তি (memoization আর tabulation) বিস্তারিত আছে; এখানে আমরা শুধু grammar-এর জন্য এর একটি বিশেষ রূপ দেখব।
২ · CNF কেন, আর CYK-এর মূল ভাবনা
পর্ব ২৯-এ দেখেছেন, ε ছাড়া প্রতিটি context-free language-এর একটি CNF grammar আছে, আর রূপান্তরটি যান্ত্রিক। এখানে শুধু সংজ্ঞাটি মনে করিয়ে দেওয়া হলো, কারণ CYK পুরোপুরি এর ওপর দাঁড়িয়ে।
CFG G = (V, Σ, R, S) Chomsky normal form-এ থাকে, যদি প্রতিটি নিয়ম এই দুই আকারের একটি হয়: A → BC (B, C ∈ V, আর দুটির কোনোটিই start symbol নয়) অথবা A → a (a ∈ Σ). শুধু start symbol-এর জন্য একটি ছাড়: S → ε থাকতে পারে, যদি ε ∈ L(G) হয়।
CNF দুটি জিনিস নিশ্চিত করে, আর দুটিই CYK-এর দরকার। প্রথমত, প্রতিটি ভেতরের node-এর ঠিক দুটি সন্তান, তাই parse tree একটি binary tree, আর গাছের root-এর নিচে string-টি ঠিক দুই ভাগে ভাগ হয়। দ্বিতীয়ত, S ছাড়া কোনো variable ε তৈরি করে না, তাই প্রতিটি ভাগ অন্তত একটি অক্ষরের। এই দুই কথা মিলিয়ে একটি পুনরাবৃত্তি পাওয়া যায়। ধরুন w = w0w1⋯wn−1 (অবস্থান ০ থেকে গোনা, Python-এর মতো)। শুরুর অবস্থান i আর দৈর্ঘ্য l-এর টুকরো w[i : i+l]-এর জন্য একটি ঘর:
অর্থাৎ ঘরে থাকে সেই সব variable, যারা এই টুকরোটি derive করতে পারে। দৈর্ঘ্য ১-এর ঘর ভরা সহজ: T[i, 1] = { A : A → wi ∈ R }. দৈর্ঘ্য l ≥ 2-এর জন্য টুকরোটিকে k ও l − k দৈর্ঘ্যের দুই ভাগে ভাঙুন, k = 1, 2, …, l − 1:
ডান দিকের দুটি ঘরই ছোট দৈর্ঘ্যের, তাই সারি ধরে l = 1, 2, …, n ক্রমে ভরলে প্রতিটি ঘর ভরার সময় তার দরকারি ঘরগুলো আগেই তৈরি। শেষে প্রশ্নের উত্তর একটি ঘরে: w ∈ L(G) ⇔ S ∈ T[0, n]. এই পদ্ধতির নাম Cocke, Younger আর Kasami-র নামে CYK (কেউ কেউ CKY লেখেন)। ১৯৬০-এর দশকে তিনজন প্রায় স্বাধীনভাবে এই ভাবনায় পৌঁছান বলে সাধারণত বলা হয়: Tadao Kasami-র ১৯৬৫ সালের একটি প্রতিবেদন, Daniel Younger-এর ১৯৬৭ সালের প্রবন্ধ “Recognition and parsing of context-free languages in time n3”, আর John Cocke-এর ভাবনা, যা ১৯৭০ সালে Jacob Schwartz-এর সঙ্গে লেখা compiler-বিষয়ক নোটে প্রকাশিত হয় বলে পরিচিত।
এই পর্ব জুড়ে একটি পাঠ্যবই-ধাঁচের ছোট CNF grammar ব্যবহার হবে (Hopcroft–Motwani–Ullman-এর বইয়ে একই grammar দেখা যায়):
নিচের ছবিতে “baaba”-র পুরো CYK টেবিল, পিরামিড আকারে সাজানো। নিচের সারিতে প্রতিটি অক্ষরের ঘর (l = 1), তার ওপরে পাশাপাশি দুই অক্ষরের ঘর, এভাবে চূড়ায় পুরো string-এর ঘর। প্রতিটি ঘর ঠিক তার নিচের “ত্রিভুজ”-এর অক্ষরগুলো ঢাকে। ঘরের মানগুলো পরের অংশের Python ব্লক থেকে নেওয়া।
“baaba”-র CYK টেবিল, পিরামিড আকারে
প্রতিটি ঘর: যে variable-গুলো ঘরের নিচের টুকরোটি derive করে (“A,C,S” মানে set {A, C, S})। হলুদ ঘরগুলো একটি parse tree-র node (অংশ ৫); ধূসর ∅ মানে কোনো variable নেই।
দুটি পর্যবেক্ষণ। প্রথমত, টেবিলে মোট ঘর n(n + 1)/2টি, n = 5-এ ১৫টি; প্রতিটি ঘর w-এর একটি একটানা টুকরো। দ্বিতীয়ত, একটি ঘর ফাঁকা হলেও ওপরের ঘর ভরতে পারে, কারণ ওপরের ঘর অন্য split দিয়েও আসতে পারে। “baab”-এর ঘর ফাঁকা, অথচ চূড়ার ঘর {A, C, S}: চূড়া ভরেছে b∣aaba আর ba∣aba split দিয়ে, baab∣a দিয়ে নয়।
৩ · ধাপে ধাপে টেবিল ভরা — সারি ধরে, split ধরে
এবার ঘরগুলো কীভাবে এল, ধাপে ধাপে। নিচের stepper-এ টেবিলটি সাধারণ সারণির আকারে: কলাম মানে শুরুর অবস্থান i (০ থেকে ৪), সারি মানে দৈর্ঘ্য l. দৈর্ঘ্য l-এর সারিতে ঘর 5 − l + 1টি, তাই সারণিটি সিঁড়ির মতো। জায়গা বাঁচাতে ঘরে set-এর বন্ধনী বাদ: “A,C” মানে {A, C}, “·” মানে ঘরটি এখনো ভরা হয়নি। প্রতিটি ধাপে একটি পুরো সারি ভরে।
| l ∖ i | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 5 | |||||
| 4 | |||||
| 3 | |||||
| 2 | |||||
| 1 | |||||
| w | b | a | a | b | a |
- দৈর্ঘ্য ১। প্রতিটি অক্ষরের জন্য A → a আকারের নিয়ম খুঁজুন। b শুধু B → b থেকে আসে, তাই {B}; a আসে A → a আর C → a থেকে, তাই {A, C}. এই সারিতে কোনো split নেই।
- দৈর্ঘ্য ২। প্রতিটি দুই-অক্ষরের টুকরোর একটিই split (১ + ১)। “ba”: বাঁয়ে {B}, ডানে {A, C}; জোড় BA আর BC. A → BA আর S → BC আছে, তাই {A, S}. “aa”: জোড় AA, AC, CA, CC; শুধু B → CC মেলে, তাই {B}. “ab”: AB আর CB; S → AB আর C → AB, তাই {C, S}.
- দৈর্ঘ্য ৩। এখন দুটি split. “baa”: b∣aa দেয় B·B, ba∣a দেয় {A, S}·{A, C}; কোনো জোড় কোনো নিয়মের ডান দিক নয়, তাই ∅. “aab”: a∣ab দেয় {A, C}·{C, S}, যার CC থেকে B. “aba”: ab∣a দেয় {C, S}·{A, C}, যার CC থেকে B.
- দৈর্ঘ্য ৪। তিনটি split. “baab”: তিনটিই ব্যর্থ, তাই ∅. “aaba”: a∣aba দেয় {A, C}·{B}, যার AB থেকে S আর C; aa∣ba দেয় {B}·{A, S}, যার BA থেকে A; aab∣a দেয় B·{A, C}, যা আবার A আর S দেয়। মোট {A, C, S}.
- দৈর্ঘ্য ৫, চূড়া। চারটি split. b∣aaba: B·{A, C, S}, জোড় BA আর BC, তাই A আর S. ba∣aba: {A, S}·{B}, জোড় AB, তাই S আর C. baa∣ba আর baab∣a-র বাঁ ঘর ফাঁকা, কিছু দেয় না। মোট {A, C, S}.
- সিদ্ধান্ত। S ∈ T[0, 5], তাই baaba ∈ L(G). লক্ষ করুন, S দুটি আলাদা split থেকে এসেছে: এর মানে এই string-এর parse tree দুটি (অংশ ৫)। পুরো টেবিল ভরতে মোট ২০টি (i, l, k) জোড়া পরীক্ষা হয়েছে, যা অংশ ৪-এর সূত্রের (53 − 5)/6.
হাতে করা হিসাব যন্ত্রে যাচাই করা দরকার। নিচের Python ব্লকে grammar একটি dict, আর cyk function টেবিলটি একটি list-of-list-এ ভরে: T[i][l] হলো ওপরের T[i, l]. তিনটি nested loop ঠিক পুনরাবৃত্তি সূত্রটি: দৈর্ঘ্য l, শুরু i, split k. show টেবিলটি ওপর থেকে নিচে ছাপে, পিরামিডের মতো, আর একটি প্রত্যাখ্যাত string “abb”-ও চালায়।
# CYK on a CNF grammar: T[i][l] = variables that derive w[i:i+l]
G = {"S": ["AB", "BC"], "A": ["BA", "a"], "B": ["CC", "b"], "C": ["AB", "a"]}
UNARY = [(A, r) for A, rs in G.items() for r in rs if len(r) == 1]
BINARY = [(A, r[0], r[1]) for A, rs in G.items() for r in rs if len(r) == 2]
def cyk(w):
n = len(w)
T = [[set() for _ in range(n + 1)] for _ in range(n)]
for i, a in enumerate(w): # length 1: A -> a
T[i][1] = {A for A, b in UNARY if b == a}
for l in range(2, n + 1): # longer pieces
for i in range(n - l + 1):
for k in range(1, l): # split: w[i:i+k] + rest
for A, B, C in BINARY:
if B in T[i][k] and C in T[i + k][l - k]:
T[i][l].add(A)
return T
def show(w):
T, n = cyk(w), len(w)
print("w =", w)
for l in range(n, 0, -1): # top row = whole string
cells = ["{" + ",".join(sorted(T[i][l])) + "}" for i in range(n - l + 1)]
print(f"l={l}: " + " ".join(f"{c:8}" for c in cells))
print(" " + " ".join(f"{a:8}" for a in w))
print("S in top cell?", "S" in T[0][n], "\n")
show("baaba")
show("abb")আসল আউটপুট (ব্রাউজারের Python):
w = baaba
l=5: {A,C,S}
l=4: {} {A,C,S}
l=3: {} {B} {B}
l=2: {A,S} {B} {C,S} {A,S}
l=1: {B} {A,C} {A,C} {B} {A,C}
b a a b a
S in top cell? True
w = abb
l=3: {}
l=2: {C,S} {}
l=1: {A,C} {B} {B}
a b b
S in top cell? False
প্রথম টেবিলটি stepper আর ছবি ৩১.১-এর সঙ্গে ঘরে ঘরে মেলে; Python ফাঁকা set-কে {} লেখে, ছবিতে যা ∅. দ্বিতীয় string “abb”-এর চূড়া ফাঁকা: “bb” কোনো variable থেকে আসে না (BB কোনো নিয়মের ডান দিক নয়), আর a∣bb বা ab∣b-র কোনো জোড়ও মেলে না। লক্ষ করুন, কোডে কোথাও derivation খোঁজা হয়নি; শুধু ঘর আর নিয়ম মেলানো। show("bab") বা নিজের string দিয়ে চালিয়ে দেখুন, আর অংশ ২-এর grammar-এ একটি নিয়ম বদলে টেবিল কীভাবে বদলায় লক্ষ করুন।
ঘরের ভেতরের কাজটি আরও কাছ থেকে দেখতে নিচের JavaScript ব্লকটি চালান। এটি একই টেবিল ভরে, কিন্তু প্রতিটি ঘরের পাশে লেখে কোন নিয়ম কোন split-এ প্রথম মিলেছে। এই “প্রথম মিল”-এর তথ্যটুকুই অংশ ৫-এর back-pointer.
// CYK, cell by cell: for each cell, try every split and print what it found.
const G = { S: ["AB", "BC"], A: ["BA", "a"], B: ["CC", "b"], C: ["AB", "a"] };
const w = "baaba", n = w.length, T = {};
const set = (vs) => "{" + [...vs].sort().join(",") + "}";
for (let i = 0; i < n; i++) { // length 1: A -> a
T[i + ",1"] = new Set(Object.keys(G).filter(A => G[A].includes(w[i])));
}
console.log("length 1:", [...Array(n).keys()].map(i => set(T[i + ",1"])).join(" "));
for (let l = 2; l <= n; l++) {
for (let i = 0; i + l <= n; i++) {
const cell = new Set(), why = [];
for (let k = 1; k < l; k++) { // left part has length k
const L = T[i + "," + k], R = T[(i + k) + "," + (l - k)];
for (const A in G) for (const r of G[A]) {
if (r.length === 2 && L.has(r[0]) && R.has(r[1]) && !cell.has(A)) {
cell.add(A);
why.push(`${A}->${r} at ${w.slice(i, i + k)}|${w.slice(i + k, i + l)}`);
}
}
}
T[i + "," + l] = cell;
console.log(`T[${i},${l}] ${w.slice(i, i + l).padEnd(5)} = ${set(cell).padEnd(7)}`,
why.join("; "));
}
}
console.log(T["0," + n].has("S") ? "S in top cell: accept" : "reject");আসল আউটপুট (ব্রাউজারের JavaScript):
length 1: {B} {A,C} {A,C} {B} {A,C}
T[0,2] ba = {A,S} S->BC at b|a; A->BA at b|a
T[1,2] aa = {B} B->CC at a|a
T[2,2] ab = {C,S} S->AB at a|b; C->AB at a|b
T[3,2] ba = {A,S} S->BC at b|a; A->BA at b|a
T[0,3] baa = {}
T[1,3] aab = {B} B->CC at a|ab
T[2,3] aba = {B} B->CC at ab|a
T[0,4] baab = {}
T[1,4] aaba = {A,C,S} S->AB at a|aba; C->AB at a|aba; A->BA at aa|ba
T[0,5] baaba = {A,C,S} S->BC at b|aaba; A->BA at b|aaba; C->AB at ba|aba
S in top cell: accept
প্রতিটি লাইন একটি ঘর, আর “at” এর পরে সেই split, যেখানে variable-টি প্রথম পাওয়া গেছে (k ছোট থেকে বড় ক্রমে)। চূড়ার লাইনে S এসেছে b|aaba split-এ, নিয়ম S → BC দিয়ে। কিন্তু stepper-এর ধাপ ৫-এ দেখেছেন, ba|aba split-ও S দেয়; কোডের !cell.has(A) শর্তটি দ্বিতীয় মিল লেখে না, কারণ গ্রহণ-বর্জনের প্রশ্নে একটি মিলই যথেষ্ট। সব মিল রাখলে কী পাওয়া যায়, তা অংশ ৫-এ। লাইনের ক্রম খেয়াল করুন: আগে সব l = 2, তারপর সব l = 3; কোনো ঘর তার আগে-ভরা ঘর ছাড়া অন্য কিছুর ওপর নির্ভর করে না।
৪ · সঠিকতার প্রমাণ আর সময়ের হিসাব
টেবিল ঠিক ফল দিল, কিন্তু প্রতিটি grammar আর প্রতিটি string-এ দেবে, তার নিশ্চয়তা কী? এর উত্তর একটি উপপাদ্য, যার প্রমাণ দৈর্ঘ্যের ওপর induction.
G = (V, Σ, R, S) Chomsky normal form-এ একটি CFG, আর w = w0⋯wn−1, n ≥ 1. CYK algorithm শেষ হলে প্রতিটি 0 ≤ i, 1 ≤ l, i + l ≤ n আর প্রতিটি A ∈ V-এর জন্য
A ∈ T[i, l] ⇔ A ⇒∗ wi⋯wi+l−1.
ফলে, w ∈ L(G) ⇔ S ∈ T[0, n]. আর w = ε-এর ক্ষেত্রে, ε ∈ L(G) ⇔ S → ε ∈ R.
প্রমাণে একটি তথ্য বারবার লাগে: CNF-এ S → ε ছাড়া কোনো ε-নিয়ম নেই, আর S কোনো নিয়মের ডান দিকে নেই। তাই কোনো ধাপে কোনো variable খালি string হয় না, আর একটি variable থেকে আসা প্রতিটি terminal string-এর দৈর্ঘ্য অন্তত ১। (S → ε নিয়মটি শুধু ε derive করে, তাই দৈর্ঘ্য ≥ ১-এর টুকরোয় এর কোনো ভূমিকা নেই।)
প্রমাণ (l-এর ওপর strong induction; x = wi⋯wi+l−1 লিখি):
- ভিত্তি, l = 1: algorithm T[i, 1]-এ ঠিক সেই A রাখে, যার জন্য A → wi ∈ R. এমন নিয়ম থাকলে স্পষ্টতই A ⇒ wi. উল্টো দিকে, A ⇒∗ wi হলে প্রথম ধাপটি A → a বা A → BC. A → BC হলে B আর C প্রতিটি অন্তত এক অক্ষর তৈরি করে, ফলে দৈর্ঘ্য ≥ ২, অসম্ভব। তাই প্রথম ধাপ A → a, আর তখনই derivation শেষ, a = wi. — CNF-এর দুই আকার + ε-নিয়ম নেই
- Induction hypothesis: ধরুন l ≥ 2, আর l-এর চেয়ে ছোট প্রতিটি দৈর্ঘ্যের প্রতিটি ঘরে কথাটি সত্য। Algorithm l দৈর্ঘ্যের ঘর ভরার আগে সব ছোট ঘর ভরে ফেলে, তাই ধাপ ৩ আর ৪-এ ব্যবহৃত ঘরগুলোর মান চূড়ান্ত। — loop-এর ক্রম
- (⇐) A ⇒∗ x হলে A ∈ T[i, l]: |x| = l ≥ 2, তাই ধাপ ১-এর যুক্তিতে প্রথম নিয়মটি A → BC. পর্ব ২৬-এর ভাগ করার lemma অনুযায়ী x = yz, যেখানে B ⇒∗ y আর C ⇒∗ z. ε-নিয়ম নেই বলে |y| ≥ 1 আর |z| ≥ 1; k = |y| নিলে 1 ≤ k ≤ l − 1. Induction hypothesis-এ B ∈ T[i, k] আর C ∈ T[i+k, l−k]. Algorithm এই k আর এই নিয়মটি পরীক্ষা করে, তাই A-কে T[i, l]-এ যোগ করে। — ভাগ করার lemma + IH
- (⇒) A ∈ T[i, l] হলে A ⇒∗ x: Algorithm A-কে যোগ করে শুধু তখন, যখন কোনো k আর কোনো A → BC-তে B ∈ T[i, k], C ∈ T[i+k, l−k]. IH-এ B ⇒∗ wi⋯wi+k−1 আর C ⇒∗ wi+k⋯wi+l−1. তাই A ⇒ BC ⇒∗ x. — IH + নিয়ম A → BC
- উপসংহার: l = n, i = 0, A = S বসালে w ∈ L(G) ⇔ S ∈ T[0, n]. খালি string-এর জন্য টেবিল নেই; CNF-এ ε শুধু S → ε থেকে আসতে পারে, তাই সেটি আলাদা করে দেখা হয়। ∎
এবার সময়। ধাপ ৩-এর loop গোনা যাক। দৈর্ঘ্য l-এ শুরুর অবস্থান n − l + 1টি, আর প্রতিটির জন্য split l − 1টি। প্রতিটি (i, l, k)-তে সব binary নিয়ম একবার দেখা হয়।
দৈর্ঘ্য n-এর string-এ CYK মোট ∑l=2n (n − l + 1)(l − 1) = (n3 − n)/6টি (i, l, k) জোড়া পরীক্ষা করে। প্রতিটিতে খরচ O(|R|), তাই মোট সময় O(n3 · |R|), আর টেবিলের জায়গা O(n2 · |V|). Grammar-কে স্থির ধরলে সময় O(n3).
প্রমাণের রূপরেখা: একটি সুন্দর গণনা আছে। w-এর অক্ষরগুলোর মাঝে, শুরুতে আর শেষে মোট n + 1টি “সীমানা” (০ থেকে n). প্রতিটি (i, l, k) ঠিক তিনটি সীমানা বাছে: i < i + k < i + l, অর্থাৎ টুকরোর শুরু, ভাগের জায়গা আর শেষ। উল্টো দিকে, যেকোনো তিনটি আলাদা সীমানা p < q < r একটি জোড়া দেয় (i = p, k = q − p, l = r − p). তাই সংখ্যাটি C(n + 1, 3) = (n + 1)n(n − 1)/6 = (n3 − n)/6. n = 5-এ ২০, ঠিক stepper-এর গোনা। ∎ (বিস্তারিত প্রমাণ অনুশীলন ২-এ।)
এই উপপাদ্যের দুটি বড় ফল আছে। প্রথমত, ACFG শুধু decidable নয়, polynomial সময়ে decidable: input ⟨G, w⟩ পেলে G-কে CNF-এ নিন (পর্ব ২৯), তারপর CYK চালান। CNF রূপান্তরে grammar-এর আকার বাড়তে পারে; সাবধানী ক্রমে বৃদ্ধি polynomial থাকে বলে জানা, আর অসাবধানী ক্রমে exponential হতে পারে (পর্ব ২৯-এ বিস্তারিত)। দ্বিতীয়ত, grammar স্থির রাখলে প্রতিটি context-free language-এর জন্য একটি O(n3) decider আছে। Complexity-র ভাষায়: প্রতিটি CFL class P-তে আছে। এই কথাটি পর্ব ৫৭-এ class P-র সংজ্ঞার পর আবার আসবে, আর decidability-র পূর্ণ আলোচনা পর্ব ৩৭ আর ৫০-এ।
সাধারণ ভুল: “টেবিলে n2/2টি ঘর, তাই CYK O(n2).” ঘরের সংখ্যা n2-এর মাপের, কিন্তু প্রতিটি ঘরে l − 1টি split দেখতে হয়; দীর্ঘ ঘরগুলোর split প্রায় n-টি। আরেকটি ভুল: CNF ছাড়াই, A → B বা A → ε-এর মতো নিয়ম রেখে CYK চালানো। তখন প্রমাণের ধাপ ১ আর ৩ ভেঙে পড়ে: A → B থাকলে দৈর্ঘ্য ১-এর ঘরে B আসে কিন্তু A আসে না, আর ε-নিয়ম থাকলে k = 0 বা k = l-এর “ভাগ”-ও বৈধ হয়ে যায়। অনুশীলন ৪-এ এর একটি ছোট প্রতি-উদাহরণ আছে।
৫ · Back-pointer থেকে parse tree, আর parse গোনা
CYK শুধু “হ্যাঁ/না” বলে না। ঘরে A রাখার সময় যদি সঙ্গে লিখে রাখেন “কোন split k আর কোন নিয়ম A → BC দিয়ে এলাম”, তাহলে চূড়ার S থেকে নিচে নেমে পুরো parse tree পাওয়া যায়। এই নোটের নাম back-pointer. প্রতিটি back-pointer একটি ঘর-variable জোড়াকে দুটি ছোট ঘর-variable জোড়ার দিকে দেখায়, যা গাছের একটি node আর তার দুই সন্তান। নিচের stepper “baaba”-র গাছটি এভাবে পড়ে; ছবি ৩১.১-এর হলুদ ঘরগুলোই এই পথ।
| এখন খোলা | |
| back-pointer | |
| দুই ভাগ |
- চূড়া থেকে শুরু। S ∈ T[0, 5], তাই গাছের root S, আর তার yield হবে পুরো baaba. এবার S-এর back-pointer দেখতে হবে: কোন split আর কোন নিয়মে S এই ঘরে এসেছিল।
- প্রথম ভাগ। Back-pointer: k = 1, নিয়ম S → BC. অর্থাৎ বাঁ ভাগ “b” (ঘর T[0, 1], যেখানে B আছে) আর ডান ভাগ “aaba” (ঘর T[1, 4], যেখানে C আছে)। গাছে S-এর দুই সন্তান B আর C.
- B পাতায় থামে, C নিচে নামে। T[0, 1]-এ B এসেছে B → b থেকে, তাই B-এর সন্তান পাতা b. C ∈ T[1, 4]-এর back-pointer: k = 1, C → AB; ভাগ a ∣ aba.
- আরও এক স্তর। A ∈ T[1, 1] এসেছে A → a থেকে। B ∈ T[2, 3]-এর back-pointer: k = 2, B → CC; ভাগ ab ∣ a, অর্থাৎ বাঁয়ের C ঘর T[2, 2]-এ, ডানের C ঘর T[4, 1]-এ।
- শেষ binary node. C ∈ T[2, 2]: k = 1, C → AB, ভাগ a ∣ b. ডানের C ∈ T[4, 1] এসেছে C → a থেকে, তাই সেটি সরাসরি পাতা a.
- গাছ সম্পূর্ণ। সব শাখা A → a বা B → b-এর মতো নিয়মে শেষ। পাতাগুলো বাঁ থেকে ডানে b, a, a, b, a: yield ঠিক baaba. Variable-node ৯টি = 2 · 5 − 1, যেমন CNF-এ হওয়ার কথা; এর ৪টি binary আর ৫টি পাতার ঠিক ওপরে।
- দ্বিতীয় গাছ। T[0, 5]-এ S-এর আরেকটি back-pointer আছে: k = 2, S → AB, ভাগ ba ∣ aba. এটি ধরে নামলে আরেকটি গাছ। একই string-এর দুটি আলাদা parse tree, তাই এই grammar ambiguous (পর্ব ২৭-এর সংজ্ঞা)। CYK টেবিল থেকেই ambiguity চোখে পড়ল।
একটি back-pointer রাখলে একটি গাছ মেলে; সব রাখলে সব গাছ। কিন্তু গাছ exponential সংখ্যক হতে পারে, তাই প্রায়ই শুধু তাদের সংখ্যা জানতে চাওয়া হয়। কৌশলটি সরল: ঘরে variable-এর set-এর বদলে রাখুন N[i, l, A] = “A-root আর yield w[i : i+l]-এর গাছের সংখ্যা”. পুনরাবৃত্তি সূত্রে “কোনো k আর কোনো নিয়ম আছে কি” (OR) হয়ে যায় “সব k আর সব নিয়মের যোগফল”, আর “B আছে এবং C আছে” (AND) হয়ে যায় “B-গাছের সংখ্যা × C-গাছের সংখ্যা”:
CNF-এর গাছের সঙ্গে মূল grammar-এর গাছের হুবহু মিল সবসময় থাকে না (unit নিয়ম মুছলে E → T → F-এর শিকল এক node-এ গুটিয়ে যায়), তবে এই পর্বের দুই expression grammar-এ গাছের সংখ্যা ঠিক থাকে। নিচের ব্লকে পর্ব ২৫-এর স্তরভাগ করা expression grammar-এর একটি CNF রূপ (layered) আর এক-স্তরের E → E+E ∣ E∗E ∣ (E) ∣ id-এর CNF রূপ (flat). CNF রূপ দুটি scratch-এ দৈর্ঘ্য ৭ পর্যন্ত সব token-ক্রমে মূল grammar-এর সঙ্গে brute force-এ মিলিয়ে নেওয়া হয়েছে (৯৭,৬৫৫টি string, একটিও অমিল নেই)। Layered রূপের অর্থ: A মানে “+T”, B মানে “∗F”, C মানে “E)”, আর P, M, L, R চারটি চিহ্ন + ∗ ( ).
# CYK that counts parse trees and keeps one back-pointer per (cell, variable)
LAYERED = ("E->E A|T B|L C|id; T->T B|L C|id; F->L C|id; A->P T; B->M F;"
" C->E R; P->+; M->*; L->(; R->)")
FLAT = "E->E A|E B|L C|id; A->P E; B->M E; C->E R; P->+; M->*; L->(; R->)"
def parse_grammar(text):
return [(A.strip(), tuple(alt.split())) for part in text.split(";")
for A, rhs in [part.split("->")] for alt in rhs.split("|")]
def cyk_count(rules, w):
n, N, bp = len(w), {}, {} # N[i,l,A] = number of trees
for i, a in enumerate(w):
for A, r in rules:
if r == (a,): N[i, 1, A] = 1; bp[i, 1, A] = a
for l in range(2, n + 1):
for i in range(n - l + 1):
for k in range(1, l):
for A, r in rules:
if len(r) == 2:
c = N.get((i, k, r[0]), 0) * N.get((i + k, l - k, r[1]), 0)
if c:
N[i, l, A] = N.get((i, l, A), 0) + c
bp.setdefault((i, l, A), (k, r[0], r[1]))
return N, bp
def tree(bp, i, l, A): # rebuild one tree from back-pointers
b = bp[i, l, A]
if isinstance(b, str): return f"{A}:{b}"
k, B, C = b
return f"{A}({tree(bp, i, k, B)} {tree(bp, i + k, l - k, C)})"
w = "id + id * id".split()
for name, g in [("layered", LAYERED), ("flat", FLAT)]:
N, bp = cyk_count(parse_grammar(g), w)
print(name, "trees:", N.get((0, len(w), "E"), 0))
print(" one tree:", tree(bp, 0, len(w), "E"))
N, _ = cyk_count(parse_grammar(FLAT), "id + id + id + id + id + id".split())
print("flat, 5 plus signs:", N[0, 11, "E"], "trees")আসল আউটপুট (ব্রাউজারের Python):
layered trees: 1
one tree: E(E:id A(P:+ T(T:id B(M:* F:id))))
flat trees: 2
one tree: E(E:id A(P:+ E(E:id B(M:* E:id))))
flat, 5 plus signs: 42 trees
Layered grammar-এ id+id∗id-এর গাছ একটি: গুণ (B, অর্থাৎ ∗F) যোগের ডান অংশ T-এর ভেতরে, অর্থ id + (id ∗ id). Flat grammar-এ গাছ দুটি, যা পর্ব ২৬-এ brute force-এ পাওয়া “দুটি leftmost derivation”-এর সঙ্গে মেলে; back-pointer প্রথম পাওয়া গাছটি দেখাচ্ছে, যেখানেও যোগ ওপরে। শেষ লাইন: ৫টি “+” থাকলে flat grammar-এ গাছ ৪২টি, যা পঞ্চম Catalan সংখ্যা C5. সব গাছ আলাদা করে না বানিয়ে, শুধু গুণ আর যোগ করে সংখ্যাটি এল, O(n3) সময়েই। w বদলে (id+id)∗id দিয়ে দেখুন: বন্ধনী থাকলে flat grammar-এও গাছ একটি।
ওপরের দুটি ব্লকের তুলনাটি গভীর। একই loop-কাঠামো, শুধু “OR আর AND”-এর জায়গায় “যোগ আর গুণ”. সংখ্যার বদলে সম্ভাবনা রাখলে, আর যোগের জায়গায় সর্বোচ্চ (max) নিলে, পাওয়া যায় সবচেয়ে সম্ভাব্য parse tree; ভাষাতত্ত্বের probabilistic parser ঠিক এটি করে (ভাবনার প্রশ্ন ৪)। গণিতের ভাষায় এই সব রূপ একটি “semiring”-এর ওপর একই DP.
৬ · যখন উত্তর “না” — প্রত্যাখ্যাত string পড়া
প্রত্যাখ্যানও টেবিল থেকে পড়া যায়, আর সেখানে একটি সূক্ষ্ম ফাঁদ আছে: চূড়ার ঘর ফাঁকা না হলেও string প্রত্যাখ্যাত হতে পারে। একই grammar-এ “abab” দেখুন। Scratch-এ দৈর্ঘ্য ৮ পর্যন্ত সব ৫১০টি string-এ এই grammar-এর জন্য CYK আর brute-force derivation-এর ফল মিলিয়ে দেখা হয়েছে, আর abab সত্যিই L(G)-এর বাইরে।
| l=4 | |
| l=3 (aba, bab) | |
| l=2 (ab, ba, ab) | |
| l=1 (a, b, a, b) |
- দৈর্ঘ্য ১। a-র ঘর {A, C}, b-র ঘর {B}, আগের মতোই।
- দৈর্ঘ্য ২। “ab”: AB আর CB জোড়, S → AB আর C → AB মেলে, তাই {C, S}. “ba”: BA আর BC, তাই {A, S}. তৃতীয় টুকরো আবার “ab”, {C, S}.
- দৈর্ঘ্য ৩। “aba”: a∣ba দেয় {A, C}·{A, S}, কিছু মেলে না; ab∣a দেয় {C, S}·{A, C}, যার CC থেকে B. “bab”: b∣ab দেয় B·{C, S}, যার BC থেকে S; ba∣b দেয় {A, S}·B, যার AB থেকে S আর C. তাই {C, S}.
- চূড়া। a∣bab: {A, C}·{C, S}, CC থেকে B. ab∣ab: {C, S}·{C, S}, আবার CC থেকে B. aba∣b: B·B, কোনো নিয়ম নেই। চূড়ার ঘর {B}.
- সিদ্ধান্ত। চূড়ায় B আছে, তাই B ⇒∗ abab সত্য; কিন্তু প্রশ্ন ছিল S ⇒∗ abab কি না, আর S ঘরে নেই। তাই abab ∉ L(G). শুধু “ঘর ফাঁকা কি না” দেখলে এখানে ভুল উত্তর আসত; দেখতে হবে ঠিক start symbol আছে কি না।
প্রত্যাখ্যানের পরও টেবিল কাজের। এটি জানে w-এর প্রতিটি টুকরো কোন variable থেকে আসে। বাজারঘরের query box-এ কেউ ভুল query লিখলে, টেবিল দেখে বলা যায় “এই অংশটি একটি বৈধ শর্ত (C), কিন্তু পুরোটা query নয়”. Left-to-right parser-এর মতো ভুলের সবচেয়ে বাঁয়ের জায়গা CYK নিজে থেকে দেখায় না, তবে সবচেয়ে লম্বা বৈধ টুকরোগুলো খুঁজে দিতে পারে। প্রাকৃতিক ভাষার parser-এ এর একটি ব্যবহার আছে: পুরো বাক্য না মিললে বড় বড় বৈধ খণ্ড ফেরত দেওয়া।
৭ · বাস্তবে CYK — lark-এর Earley-র সঙ্গে তুলনা আর ঘন বৃদ্ধি (সত্যিকারের run)
নিজের লেখা algorithm-কে বিশ্বাস করার আগে একটি স্বাধীন, পরীক্ষিত parser-এর সঙ্গে মেলানো ভালো অভ্যাস। পর্ব ২৬-এ ব্যবহৃত lark (Python parser library, MIT licence) মূল grammar সরাসরি নেয়, CNF ছাড়াই, আর তার Earley parser যেকোনো CFG মেনে নেয়। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টি তিনটি কাজ করে: (১) মূল grammar থেকে একটি সরল converter দিয়ে CNF বানায় (ε-নিয়ম নেই, তাই unit নিয়ম মোছা, terminal-এর জন্য নতুন variable আর লম্বা ডান দিক ভাঙা যথেষ্ট); (২) দুটি grammar-এ ২০০০টি করে string-এ CYK আর lark-এর উত্তর মেলায়; (৩) লম্বা হতে থাকা input-এ দুটির সময় মাপে। String-গুলোর এক-তৃতীয়াংশের কিছু বেশি grammar থেকে random derivation-এ বানানো (তাই বৈধ), সমান সংখ্যক তাদের একটি token মুছে, যোগ করে বা বদলে বানানো “প্রায়-বৈধ”, আর বাকিগুলো সম্পূর্ণ random token-ক্রম। নিচে script-এর মূল অংশ (CNF converter আলাদা ফাইলে, পুরো script প্রায় ৯০ লাইন):
QUERY = {"Q": [("FIND", "order", "WHERE", "C")],
"C": [("C", "OR", "T"), ("T",)], "T": [("T", "AND", "F"), ("F",)],
"F": [("(", "C", ")"), ("amount", "R", "NUM"),
("district", "=", "STR"), ("status", "=", "STR")],
"R": [("=",), (">=",), ("<",)]}
...
for name, G, start in [("arith", ARITH, "E"), ("order-query", QUERY, "Q")]:
unary, binary = to_cnf(G, start)
earley = Lark(lark_grammar(G, start), start=start.lower(), parser="earley")
...
for w in tests:
c = cyk(unary, binary, w, start)
try: earley.parse(" ".join(w)); e = True
except LarkError: e = False
agree += c == e; acc += c
...
for n in (51, 101, 201, 401): # id+id+...+id, n tokens
w = ("id + " * (n // 2) + "id").split()
t0 = time.perf_counter(); ok = cyk(unary, binary, w, "E")
t1 = time.perf_counter(); earley.parse(" ".join(w)); t2 = time.perf_counter()সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13, uv 0.11.28; random seed স্থির):
~/bazarghar-toc$ uv run python cyk_vs_earley.py
lark 1.3.1 | Python 3.12.13
== arith: CNF has 13 variables, 19 rules
strings tested: 2000 accepted: 778 rejected: 1222
CYK and Earley agree on 2000/2000
== order-query: CNF has 35 variables, 49 rules
strings tested: 2000 accepted: 727 rejected: 1273
CYK and Earley agree on 2000/2000
== timing on id+id+...+id (n tokens)
n= 51 CYK 2.5 ms Earley 2.2 ms True
n=101 CYK 15.5 ms x6.1 Earley 4.1 ms True
n=201 CYK 148.1 ms x9.6 Earley 11.8 ms True
n=401 CYK 1404.3 ms x9.5 Earley 23.3 ms True
মিল: দুই grammar-এ মোট ৪০০০টি string, প্রায় ৩৮% গৃহীত, আর একটিতেও CYK আর Earley-র অমিল নেই। দুটি সম্পূর্ণ আলাদা algorithm (একটি CNF-এর ওপর নিচ থেকে ওপরে টেবিল, অন্যটি মূল grammar-এর ওপর বাঁ থেকে ডানে) একই উত্তর দিচ্ছে, যা দুটিরই ভুলের সম্ভাবনা কমায়। এটি প্রমাণ নয়, প্রমাণ অংশ ৪-এ; এটি প্রমাণ আর কোড যে একই জিনিস, তার পরীক্ষা।
CNF-এর আকার: order-query grammar-এর মূল নিয়ম ১২টি, CNF-এ ৪৯টি নিয়ম আর ৩৫টি variable. কারণ ১৫টি terminal-এর প্রতিটির জন্য একটি নতুন variable (যেমন T_FIND → FIND), unit নিয়ম মোছায় C আর T-কে F-এর সব নিয়মের কপি নিতে হয়, আর এই সরল converter একই ডান দিকের (যেমন “= STR”) জন্যও প্রতিবার আলাদা নতুন variable বানায়। অভিন্ন অংশ ভাগাভাগি করলে সংখ্যা কমে; arith-এর ১৩টি variable-এর বদলে অংশ ৫-এর হাতে লেখা রূপে ১০টি।
সময়: n প্রায় দ্বিগুণ হলে CYK-এর সময় প্রায় ৬ থেকে ১০ গুণ, আর বড় n-এ অনুপাত ৮-এর কাছাকাছি স্থির হচ্ছে, যা n3 বৃদ্ধির চিহ্ন (23 = 8); ছোট n-এ নির্দিষ্ট খরচ আর মাপার অনিশ্চয়তা অনুপাতকে কিছুটা বিকৃত করে। Earley এই unambiguous grammar আর input-এ প্রতি দ্বিগুণে মোটামুটি দ্বিগুণ সময় নিচ্ছে। সময়ের সংখ্যা যন্ত্র ভেদে বদলাবে; অনুপাতগুলোই আসল তথ্য।
শেষ পর্যবেক্ষণটি গুরুত্বপূর্ণ। CYK-এর n3 হলো সবচেয়ে খারাপ ক্ষেত্রের এবং প্রায় সব ক্ষেত্রের খরচ: টেবিলের প্রতিটি ঘর আর প্রতিটি split সবসময় দেখতে হয়, grammar সহজ হোক বা কঠিন। Earley parser-এর সবচেয়ে খারাপ খরচও n3, কিন্তু unambiguous grammar-এ এর খরচ বড়জোর n2, আর অনেক বাস্তব grammar-এ প্রায় linear বলে জানা (Jay Earley, ১৯৭০)। Programming language-এর compiler সাধারণত আরও সীমিত শ্রেণির grammar নেয় (LL বা LR, পর্ব ৩৮ আর ৩৯), যাদের parsing linear সময়ে। সাধারণ CFG-এর জন্য Earley আর GLR পর্ব ৪১-এ।
| পদ্ধতি | কোন grammar | সময় (n = input-এর দৈর্ঘ্য) | কোথায় |
|---|---|---|---|
| সব 2n − 1 ধাপের derivation | CNF | exponential | decidability-র প্রমাণে |
| CYK | CNF (বা binary রূপ) | সবসময় Θ(n3), grammar স্থির ধরলে | তত্ত্ব, ভাষাতত্ত্ব, শিক্ষা |
| Valiant-এর পদ্ধতি | CNF | O(nω), ω = matrix গুণের ঘাত | মূলত তত্ত্বে |
| Earley | যেকোনো CFG | সবচেয়ে খারাপ O(n3), unambiguous-এ O(n2) | lark, ভাষাতত্ত্ব (পর্ব ৪১) |
| LL(1), LR(1) | বিশেষ শ্রেণি | O(n) | compiler (পর্ব ৩৮–৩৯) |
সারণির তৃতীয় সারিটি নিয়ে একটু বলা দরকার। Leslie Valiant ১৯৭৫ সালে দেখান, CYK টেবিল ভরার কাজটিকে Boolean matrix গুণের মাধ্যমে করা যায়, ফলে n3-এর চেয়ে কম সময়ে, matrix গুণের ঘাত ω-এর সমান মাপে। ω-এর বর্তমান জানা ওপরের সীমা ২.৩৭-এর সামান্য নিচে, তবে সেই algorithm-গুলোর ধ্রুবক এত বড় যে বাস্তবে কেউ Valiant-এর পদ্ধতি দিয়ে parse করে না। ২০০২ সালে Lillian Lee উল্টো দিকটি দেখান: CFG parsing-এর কোনো যথেষ্ট দ্রুত algorithm পেলে তা থেকে দ্রুত Boolean matrix গুণও পাওয়া যায়। অর্থাৎ দুটি সমস্যা গভীরভাবে জড়িত, আর “CFG parsing কত দ্রুত সম্ভব” প্রশ্নটি এখনো খোলা (ভাবনার প্রশ্ন ২)।
আরও গভীরে: Abboud, Backurs আর Vassilevska Williams ২০১৫ সালের একটি প্রবন্ধে দেখান, একটি নির্দিষ্ট CFG-এর জন্যও যদি “combinatorial” পদ্ধতিতে n3-এর চেয়ে উল্লেখযোগ্যভাবে দ্রুত parsing সম্ভব হতো, তবে graph-এর k-clique সমস্যার জন্য একটি বহুদিনের প্রত্যাশিত সীমা ভেঙে যেত; শিরোনামেই তাঁরা বলেন, বর্তমান clique algorithm সর্বোত্তম হলে Valiant-এর parser-ও সর্বোত্তম। এটি fine-grained complexity-র একটি শর্তসাপেক্ষ ফল, কোনো নিঃশর্ত lower bound নয় (পর্ব ৭২)। অন্যদিকে, LR(k) grammar-এর deterministic language-গুলোর জন্য linear সময় যে যথেষ্ট, তা Knuth ১৯৬৫ সালেই দেখান।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- একটি CNF grammar আর একটি ৪–৫ অক্ষরের string দিয়ে CYK টেবিল ভরুন, string-টি গ্রহণযোগ্য কি না বলুন। অংশ ৩-এর stepper-এর পদ্ধতি; প্রতিটি ঘরে সব split দেখান।
- CYK-এর time complexity কত, আর কেন? O(n3 · |G|): (n3 − n)/6টি (i, l, k) জোড়া, প্রতিটিতে সব binary নিয়ম।
- CYK কেন CNF চায়? Binary নিয়ম দুই অ-ফাঁকা ভাগ দেয়; ε বা unit নিয়ম থাকলে সঠিকতার induction ভাঙে।
- টেবিল থেকে ambiguity কীভাবে বোঝা যায়? কোনো ঘরে একই variable দুটি আলাদা (split, নিয়ম) থেকে এলে আর সেটি চূড়ার গাছে কাজে লাগলে, অথবা গাছ-গোনা DP-তে সংখ্যা ১-এর বেশি হলে।
- ACFG কি decidable? হ্যাঁ; CNF-এ রূপান্তর আর CYK, polynomial সময়ে।
৮ · AI-এর যুগে CYK
“CYK algorithm-এর Python কোড দাও” বললে AI assistant কয়েক সেকেন্ডে পরিচ্ছন্ন কোড দেয়। সমস্যা হলো, তিনটি nested loop-এর সীমায় একটি off-by-one ভুল খুব সহজে ঢোকে, আর ছোট এক-দুটি উদাহরণে তা ধরা পড়ে না। সবচেয়ে কার্যকর যাচাই হলো একটি brute force reference: grammar থেকে নির্দিষ্ট দৈর্ঘ্য পর্যন্ত সব string তৈরি করুন, তারপর সেই দৈর্ঘ্যের সব string-এ CYK-এর উত্তর মেলান। নিচের ব্লকে “AI draft” একটি নমুনা ভুল কোড, যাতে split-এর loop range(1, l - 1), অর্থাৎ শেষ split k = l − 1 বাদ পড়ে।
# Test a CYK implementation against brute force on ALL strings up to length 7
from itertools import product
G = {"S": ["AB", "BC"], "A": ["BA", "a"], "B": ["CC", "b"], "C": ["AB", "a"]}
def brute(maxlen): # leftmost expansion; CNF never shrinks
out, todo, seen = set(), ["S"], set()
while todo:
f = todo.pop()
if f in seen or len(f) > maxlen: continue
seen.add(f)
i = next((j for j, x in enumerate(f) if x.isupper()), None)
if i is None: out.add(f); continue
todo += [f[:i] + r + f[i + 1:] for r in G[f[i]]]
return out
def make_cyk(last_split): # last_split = l (correct) or l - 1 (bug)
def cyk(w):
n, T = len(w), {}
for i, a in enumerate(w):
T[i, 1] = {A for A in G if a in G[A]}
for l in range(2, n + 1):
for i in range(n - l + 1):
T[i, l] = {A for A in G for r in G[A] if len(r) == 2
for k in range(1, last_split(l))
if r[0] in T[i, k] and r[1] in T[i + k, l - k]}
return "S" in T[0, n]
return cyk
L = brute(7)
for name, cyk in [("correct", make_cyk(lambda l: l)),
("AI draft", make_cyk(lambda l: l - 1))]:
wrong = [w for n in range(1, 8) for w in map("".join, product("ab", repeat=n))
if cyk(w) != (w in L)]
print(f"{name:9} wrong on {len(wrong):3} of 254 strings; first: {wrong[:3]}")আসল আউটপুট (ব্রাউজারের Python):
correct wrong on 0 of 254 strings; first: []
AI draft wrong on 69 of 254 strings; first: ['ab', 'ba', 'aaa']
brute শুধু grammar-এর সংজ্ঞা ব্যবহার করে: start symbol থেকে সবচেয়ে বাঁয়ের variable বদলাতে থাকে, আর CNF-এ sentential form কখনো ছোট হয় না বলে দৈর্ঘ্য ৭-এর বেশি হলে থামা নিরাপদ। এটি ধীর, কিন্তু সহজ, তাই বিশ্বাসযোগ্য reference. দৈর্ঘ্য ১ থেকে ৭-এর সব ২৫৪টি string-এ সঠিক CYK একটিতেও ভুল করেনি; ভুল draft ৬৯টিতে ভুল করেছে, আর প্রথম প্রতি-উদাহরণ মাত্র দুই অক্ষরের “ab”: l = 2-এ range(1, 1) ফাঁকা, তাই কোনো split-ই দেখা হয় না। ভুলটি এত স্পষ্ট হলেও baaba-র মতো একটি উদাহরণে হাতে মিলিয়ে ধরা কঠিন হতে পারে; সব ছোট string-এ পরীক্ষা এক মুহূর্তে ধরে। নিজের বা AI-এর লেখা কোড make_cyk-এর জায়গায় বসিয়ে পরীক্ষা করুন।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| Split বা দৈর্ঘ্যের loop-এ off-by-one (শেষ split বাদ, বা ঘরের index ভুল) | ওপরের মতো সব ছোট string-এ brute force-এর সঙ্গে মেলান; দৈর্ঘ্য ২-এর string-ই প্রায়ই প্রথম প্রতি-উদাহরণ |
| CNF-এ না এনে, unit বা ε-নিয়মসহ grammar-এ সরাসরি CYK | প্রতিটি নিয়ম A → BC বা A → a কি না দেখুন; না হলে আগে রূপান্তর (পর্ব ২৯), বা unit closure যোগ (অনুশীলন ৪) |
| ঘর ফাঁকা নয় দেখে “গ্রহণ” বলা | শুধু start symbol চূড়ায় আছে কি না দেখুন; abab-এর চূড়ায় B আছে, তবু প্রত্যাখ্যান |
| খালি string ε ভুলে যাওয়া (n = 0-এ টেবিলই নেই, কোড crash বা ভুল উত্তর) | ε আলাদা করে পরীক্ষা করুন: S → ε নিয়ম আছে কি না |
| “CYK O(n2)” বা “Valiant-এর পদ্ধতি বাস্তবে দ্রুততম” জাতীয় দাবি | (i, l, k) জোড়া গুনুন; n দ্বিগুণ করে সময় মাপুন। Valiant-এর তাত্ত্বিক সীমা আর বাস্তব গতি আলাদা জিনিস |
| বানানো ইতিহাস বা রেফারেন্স (ভুল সাল, ভুল লেখক) | Sipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে নিন; Younger ১৯৬৭ আর Valiant ১৯৭৫-এর মূল প্রবন্ধের শিরোনাম খুঁজুন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: টেবিলের সঙ্গে প্রতিটি ঘরের split-ভিত্তিক ব্যাখ্যা আর একটি স্বাধীন যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: সঠিক উত্তরে bbab-এর চূড়ার ঘর {C, S}, তাই string-টি গ্রহণযোগ্য, আর জোড়া (43 − 4)/6 = 10টি। একটি parse tree: S → BC, যেখানে বাঁয়ের B → b, আর C → AB, যার A → BA থেকে “ba” আর B → b. এই string-এরও parse tree দুটি, গাছ-গোনার DP তা দেখায়। ওপরের cyk_table.py-তে show("bbab") চালিয়ে টেবিলটি মিলিয়ে নিন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১CYK-এর নামে তিনজন কেন? ১৯৬০-এর দশকে একই ভাবনা প্রায় একসঙ্গে কয়েক জায়গায় কেন এল?
১৯৫০-এর দশকের শেষে Noam Chomsky-র grammar-এর শ্রেণিবিভাগ আর ALGOL 60-এর BNF প্রায় একসঙ্গে দুটি জগতে আলো ফেলে: ভাষাতত্ত্ব আর programming language. দুই জগতেই একটি ব্যবহারিক প্রশ্ন জরুরি হয়ে ওঠে: grammar হাতে আছে, এখন একটি বাক্য বা একটি program এই grammar মানে কি না, যন্ত্রে কীভাবে বের করব? সে সময়ের কম্পিউটারের memory আর গতি এত সীমিত ছিল যে exponential খোঁজ কোনো সমাধান নয়; দরকার ছিল এমন পদ্ধতি, যার খরচ input-এর দৈর্ঘ্যের একটি polynomial.
সাধারণত যে বিবরণ দেওয়া হয়: John Cocke, যিনি পরে IBM-এ compiler optimization আর RISC ধারণার জন্য বিখ্যাত হন, ১৯৬০-এর দশকে এই ভাবনা ব্যবহার করেন, কিন্তু তা প্রকাশিত হয় অনেক পরে, ১৯৭০ সালে Jacob Schwartz-এর সঙ্গে লেখা compiler-বিষয়ক নোটে। জাপানের Tadao Kasami ১৯৬৫ সালে মার্কিন বিমানবাহিনীর একটি গবেষণাগারের প্রতিবেদনে একটি দক্ষ recognition আর syntax-analysis algorithm বর্ণনা করেন। Daniel Younger ১৯৬৭ সালে Information and Control পত্রিকায় প্রবন্ধ প্রকাশ করেন, যার শিরোনামেই “time n3”. কে আগে, তা নিয়ে উৎসভেদে বর্ণনা আলাদা, আর তাই নামের অক্ষরের ক্রমও বইভেদে বদলায় (CYK, CKY).
একই ভাবনা কয়েক জায়গায় আসার কারণ, সমস্যাটির গঠনই ভাবনাটি “চেয়ে নেয়”. Grammar-এর নিয়ম বলে একটি বড় অংশ ছোট অংশ জুড়ে তৈরি; তাই প্রশ্নটি স্বাভাবিকভাবে টুকরো ধরে ভাবা যায়, আর একটানা টুকরো মাত্র n(n + 1)/2টি। সেই সময়েই Richard Bellman-এর dynamic programming (১৯৫০-এর দশক) অপারেশন রিসার্চে পরিচিত হয়ে উঠছিল। CNF-ও (Chomsky, ১৯৫৯) হাতে ছিল, যা প্রতিটি নিয়মকে দুই ভাগে বাঁধে। সব উপকরণ তৈরি থাকলে আবিষ্কার প্রায়ই কয়েক জায়গায় ঘটে।
মূল উপলব্ধি: CYK কোনো একক প্রতিভার চমক নয়, বরং সমস্যার গঠন, CNF আর dynamic programming-এর মিলনের স্বাভাবিক ফল। ইতিহাস হিসেবে নাম তিনটি, কিন্তু ভাবনা একটিই: সব একটানা টুকরোর উত্তর ছোট থেকে বড় ক্রমে।
প্র ০২CFG parsing কি n3-এর চেয়ে দ্রুত সম্ভব? Matrix গুণের সঙ্গে এর সম্পর্ক কী, আর কোন অংশ এখনো অজানা?
CYK-এর ভেতরের কাজটি দেখুন: ঘর T[i, l]-এর জন্য সব k-তে “বাঁ ঘরে B আর ডান ঘরে C” খোঁজা। এটি দেখতে অনেকটা matrix গুণের মতো, যেখানে (i, j) ঘর পেতে সব k-তে প্রথম matrix-এর (i, k) আর দ্বিতীয়টির (k, j) মেলানো হয়, শুধু যোগ-গুণের জায়গায় OR-AND. Leslie Valiant ১৯৭৫ সালের “General context-free recognition in less than cubic time” প্রবন্ধে এই মিলকে নিখুঁত করেন: টেবিল ভরার কাজকে একটি বিশেষ “transitive closure” হিসেবে লিখে, ভাগ করে জয় করার কৌশলে, Boolean matrix গুণের সময়ে কমিয়ে আনেন। ফলে CFG recognition-এর সময় O(nω), যেখানে ω হলো n × n matrix গুণের সেরা ঘাত।
Strassen ১৯৬৯ সালে দেখান ω ≤ log27 ≈ ২.৮১; তারপর কয়েক দশকের কাজে সীমা নেমে এসেছে ২.৩৭-এর সামান্য নিচে। কিন্তু এই সব দ্রুত matrix algorithm-এর ধ্রুবক বিশাল, আর বাস্তব আকারের input-এ তারা সাধারণ পদ্ধতিকে হারায় না। তাই Valiant-এর ফল মূলত তাত্ত্বিক: এটি বলে CFG parsing মৌলিকভাবে “ঘন” নয়।
উল্টো দিকটিও আছে। Lillian Lee ২০০২ সালে দেখান, একটি দ্রুত CFG parser (যা শুধু হ্যাঁ/না নয়, টুকরো-ভিত্তিক তথ্যও দেয়) পেলে তা দিয়ে দ্রুত Boolean matrix গুণ করা যায়। অর্থাৎ দুটি সমস্যা প্রায় সমান কঠিন। ২০১৫ সালে Abboud, Backurs আর Vassilevska Williams আরও এক ধাপ এগিয়ে দেখান, একটি নির্দিষ্ট স্থির CFG-এর parsing-ও k-clique সমস্যার মতো কঠিন, একটি প্রচলিত অনুমানের অধীনে। কিন্তু কোনো নিঃশর্ত lower bound জানা নেই: ω = 2 কি না, সেটিই একটি বড় খোলা প্রশ্ন। আজ পর্যন্ত কেউ প্রমাণ করেননি যে CFG membership-এর জন্য n2-এর মাপের সময় যথেষ্ট নয়; আবার কেউ এমন algorithm-ও দেননি।
মূল উপলব্ধি: CYK-এর n3 একটি সহজ ওপরের সীমা, শেষ কথা নয়। CFG parsing আর matrix গুণ একে অপরের প্রতিচ্ছবি, আর দুটিরই প্রকৃত জটিলতা এখনো অজানা; প্রমাণিত আর অনুমিত অংশকে আলাদা রাখা এখানে জরুরি।
প্র ০৩CYK এত সাধারণ আর সুন্দর হলে programming language-এর compiler কেন এটি ব্যবহার করে না?
প্রথম কারণ সময়। একটি বড় source file-এ লাখ লাখ token থাকতে পারে। n3 মানে দশ হাজার token-এ প্রায় এক লক্ষ কোটি মৌলিক ধাপ, যা প্রতিবার save করার সময় অসম্ভব। অংশ ৭-এর run-এ মাত্র ৪০১টি token-এ CYK এক সেকেন্ডের বেশি নিয়েছে, আর Earley নিয়েছে কয়েক মিলিসেকেন্ড। LL আর LR parser linear সময়ে চলে, তাই ভাষার নকশাকারীরা জেনেশুনে grammar-কে এমন শ্রেণিতে রাখেন, যেখানে এই parser কাজ করে।
দ্বিতীয় কারণ গাছের আকার। CNF-এ রূপান্তরে grammar-এর গঠন বদলে যায়: E → E+T-এর মতো নিয়ম ভেঙে নতুন সহায়ক variable আসে, আর unit নিয়ম মুছে যায়। ফলে CYK যে গাছ দেয়, তা মূল grammar-এর গাছ নয়; সেটি ফেরত আনতে আলাদা কাজ লাগে। Compiler-এর পরের ধাপ (AST, type checking) মূল grammar-এর কাঠামো চায়। তৃতীয় কারণ ভুলের বার্তা। CYK পুরো input পড়ে টেবিল শেষ করার পরই বলে “না”, আর ভুল কোথায় তা সরাসরি বলে না। LL বা LR parser বাঁ থেকে পড়তে পড়তে প্রথম অসম্ভব token-এ থামে (valid prefix property), যা প্রোগ্রামারের জন্য অনেক বেশি উপকারী।
তবু CYK অকেজো নয়। Grammar ambiguous হলে, বা grammar ঘন ঘন বদলায় আর parser-generator-এর শর্ত মানে না, তখন সাধারণ parser লাগে; বাস্তবে সেখানে Earley বা GLR বেশি ব্যবহৃত হয়, কারণ তারা সহজ grammar-এ দ্রুত চলে। CYK বেশি দেখা যায় ভাষাতত্ত্বে (যেখানে grammar প্রায়ই binary আকারে লেখা হয়), শিক্ষায়, আর তাত্ত্বিক প্রমাণে, যেমন “প্রতিটি CFL P-তে আছে”. অনেক parsing তত্ত্বের নতুন ধারণা প্রথমে CYK-এর সরল কাঠামোয় পরীক্ষা করা হয়, তারপর জটিল parser-এ নেওয়া হয়।
মূল উপলব্ধি: একটি algorithm-এর মূল্য শুধু সাধারণতায় নয়, তার ব্যবহারের প্রেক্ষাপটে। Compiler গতি, মূল গাছ আর দ্রুত ভুল ধরা চায়, তাই সীমিত grammar আর linear parser বেছে নেয়; CYK থেকে যায় তত্ত্ব আর সাধারণ grammar-এর নির্ভরযোগ্য মানদণ্ড হিসেবে।
প্র ০৪প্রাকৃতিক ভাষার বাক্য-বিশ্লেষণে CKY কীভাবে ব্যবহার হয়? “সবচেয়ে সম্ভাব্য গাছ” বলতে কী বোঝায়?
মানুষের ভাষা ভীষণ ambiguous. “আমি দূরবিন দিয়ে লোকটিকে দেখলাম” বাক্যে দূরবিন কার হাতে, দেখার উপায় নাকি লোকটির পরিচয়, grammar একা ঠিক করতে পারে না; দুটি গাছই বৈধ। বড় বাক্যে বৈধ গাছের সংখ্যা Catalan সংখ্যার মতো exponential হারে বাড়ে। তাই ভাষাতত্ত্বের parser-কে শুধু “বৈধ কি না” নয়, বলতে হয় “কোন গাছটি সবচেয়ে বিশ্বাসযোগ্য”.
এর একটি প্রচলিত উত্তর probabilistic CFG (PCFG): প্রতিটি নিয়মের সঙ্গে একটি সম্ভাবনা, যা সাধারণত একটি বড় বিশ্লেষিত বাক্য-সংগ্রহ (treebank) থেকে গুনে বের করা হয়। একটি গাছের সম্ভাবনা তার সব নিয়মের সম্ভাবনার গুণফল। এবার অংশ ৫-এর গোনার DP-টি মনে করুন। যোগের জায়গায় সর্বোচ্চ (max) নিলে প্রতিটি ঘর রাখে “এই টুকরোর জন্য A-root-এর সবচেয়ে সম্ভাব্য গাছের সম্ভাবনা”, আর back-pointer সেই গাছটি দেয়; একে Viterbi parsing বলা হয়। যোগ রাখলে পাওয়া যায় বাক্যটির মোট সম্ভাবনা, যার নাম inside probability; এর ওপর ভিত্তি করে James Baker ১৯৭৯ সালে inside-outside algorithm দেন বলে পরিচিত, যা treebank ছাড়াই নিয়মের সম্ভাবনা শিখতে পারে।
Joshua Goodman ১৯৯৯ সালের “Semiring parsing” প্রবন্ধে এই সব রূপকে এক ছাতার নিচে আনেন: Boolean (OR, AND) দিলে recognition, (যোগ, গুণ) দিলে গোনা বা মোট সম্ভাবনা, (max, গুণ) দিলে সেরা গাছ। Algorithm একটিই, শুধু অঙ্কের “নিয়ম” বদলায়। ১৯৯০ আর ২০০০-এর দশকে statistical parser-এর মূল কাঠামো ছিল এই ধরনের CKY chart; পরে neural parser এলেও অনেক constituency parser-এ গাছ খোঁজার শেষ ধাপে CKY-ধাঁচের DP আজও দেখা যায়।
মূল উপলব্ধি: CYK-এর আসল শক্তি তার কাঠামোয়: টুকরো ধরে ছোট থেকে বড় হিসাব। কী হিসাব করছেন (হ্যাঁ/না, সংখ্যা, সম্ভাবনা, সেরা গাছ) তা বদলালেও কাঠামো একই থাকে; একটি প্রমাণ সব রূপের সঠিকতা দেয়।
প্র ০৫“টুকরো ধরে DP” কৌশলটি grammar-এর বাইরে আর কোথায় দেখা যায়? এই পরিবারের মিল কোথায়?
CYK একটি বড় পরিবারের সদস্য, যার নাম interval dynamic programming: উপসমস্যা হলো একটি ক্রমের একটানা অংশ [i, j], আর বড় অংশের উত্তর আসে অংশটিকে সব সম্ভাব্য জায়গায় দুই ভাগ করে দুই ভাগের উত্তর জুড়ে। এদের প্রায় সবার সময় n3-এর মাপের, ঠিক একই কারণে: n2-এর মাপের অংশ, প্রতিটিতে n-এর মাপের ভাগ।
সবচেয়ে পরিচিত উদাহরণ matrix-chain গুণ: A1A2⋯An গুণ করতে বন্ধনী কীভাবে বসালে মোট গুণের সংখ্যা সবচেয়ে কম? প্রতিটি বন্ধনী-বিন্যাস একটি binary গাছ, ঠিক CNF-এর parse tree-র মতো, আর বিন্যাসের সংখ্যা আবার Catalan সংখ্যা। DSA কোর্সের dynamic programming মডিউলে এমন সমস্যা আছে। আরেকটি উদাহরণ optimal binary search tree, যেখানে কোন key root হবে তা প্রতিটি অংশে বাছতে হয়।
জীববিজ্ঞানেও এই কাঠামো এসেছে। RNA অণু একটি অক্ষর-ক্রম (A, C, G, U), যা নিজের ওপর ভাঁজ হয়ে জোড়া তৈরি করে, আর জোড়াগুলো সাধারণত সুষম বন্ধনীর মতো একে অপরের ভেতরে বসে। Ruth Nussinov ও সহকর্মীরা ১৯৭৮ সালে সর্বোচ্চ জোড়ার ভাঁজ খোঁজার একটি interval DP দেন বলে পরিচিত, যা n3 সময়ে চলে। ১৯৯০-এর দশকে RNA পরিবার খোঁজার জন্য stochastic CFG ব্যবহার শুরু হয় (যেমন Sean Eddy ও Richard Durbin-এর covariance model), আর তার কেন্দ্রেও CYK-ধাঁচের হিসাব। বাজারঘরের দিক থেকেও একটি উদাহরণ ভাবতে পারেন: একটি লম্বা ডেলিভারি রুটকে কোথায় কোথায় ভাগ করলে প্রতিটি অংশের খরচের যোগফল সবচেয়ে কম।
মূল উপলব্ধি: যেখানেই কাঠামোটি “একটানা অংশকে দুই ভাগে ভাঙা, আর প্রতিটি ভাগ একই ধরনের”, সেখানে CYK-এর ভাবনা খাটে। Parse tree, বন্ধনী-বিন্যাস আর RNA-র ভাঁজ একই গাণিতিক বস্তু: binary গাছ, যার পাতা একটি ক্রম।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। cyk_table.py আর test_cyk.py ব্লকে নিজের grammar বা string বসিয়ে উত্তর যাচাই করতে পারেন।
-
Grammar নকশা আর টেবিল: L = { anbn : n ≥ 1 }-এর জন্য একটি CNF grammar নকশা করুন। তারপর “aabb” আর “abab”-এর CYK টেবিল ভরে দেখান কোনটি গৃহীত।
নকশা: S → aSb ∣ ab থেকে শুরু করুন (n ≥ 1, তাই ε নেই)। Terminal-এর জন্য A → a, B → b. S → aSb তিন চিহ্নের, তাই ভাঙুন: S → AX, X → SB. আর S → ab হয় S → AB. চূড়ান্ত grammar: S → AX ∣ AB, X → SB, A → a, B → b. Scratch-এ দৈর্ঘ্য ১০ পর্যন্ত সব string-এ brute force-এ এর language ঠিক {ab, aabb, aaabbb, …} এসেছে।
aabb: l = 1: {A}, {A}, {B}, {B}. l = 2: “aa” ∅, “ab” {S} (S → AB), “bb” ∅. l = 3: “aab”: a∣ab দেয় A·S, কোনো নিয়ম নেই; aa∣b-র বাঁ ঘর ফাঁকা; তাই ∅. “abb”: a∣bb-র ডান ঘর ফাঁকা; ab∣b দেয় S·B, X → SB, তাই {X}. l = 4: a∣abb দেয় A·X, S → AX, তাই {S}. চূড়ায় S: গৃহীত।
abab: l = 2: “ab” {S}, “ba” ∅, “ab” {S}. l = 3: “aba”: a∣ba (A·∅), ab∣a (S·A): ∅. “bab”: b∣ab (B·S), ba∣b (∅): ∅. l = 4: a∣bab (A·∅), ab∣ab (S·S), aba∣b (∅·B): কোনো নিয়ম নেই, ∅. প্রত্যাখ্যাত, যেমন হওয়ার কথা।
-
প্রমাণ: প্রমাণ করুন, দৈর্ঘ্য n-এর string-এ CYK ঠিক ∑l=2n (n − l + 1)(l − 1) = C(n + 1, 3)টি (i, l, k) জোড়া পরীক্ষা করে। তারপর একজন শিক্ষার্থীর এই যুক্তির ভুল দেখান: “টেবিলে n(n + 1)/2টি ঘর, প্রতিটি ঘর ভরতে স্থির সময় লাগে, তাই CYK O(n2).”
- w-এর অবস্থানগুলোর মাঝের সীমানাগুলোকে 0, 1, …, n নাম দিন (মোট n + 1টি); টুকরো w[i : i+l] মানে সীমানা i থেকে সীমানা i + l. — সংজ্ঞা
- একটি বৈধ জোড়া (i, l, k)-তে 0 ≤ i, 1 ≤ k ≤ l − 1 আর i + l ≤ n. তাই p = i, q = i + k, r = i + l তিনটি সীমানা, আর 0 ≤ p < q < r ≤ n. — শর্তগুলো থেকে সরাসরি
- উল্টো দিকে, যেকোনো p < q < r থেকে i = p, k = q − p, l = r − p একটি বৈধ জোড়া, আর দুটি মানচিত্র একে অপরের উল্টো। তাই জোড়াগুলো আর তিন-সীমানার উপসেটগুলোর মধ্যে bijection. — bijection
- n + 1টি সীমানা থেকে তিনটি বাছার উপায় C(n + 1, 3) = (n + 1)n(n − 1)/6 = (n3 − n)/6. বাঁ দিকের যোগফল একই জোড়াগুলো l ধরে গোনে, তাই দুটি সমান। ∎ — গণনা
যুক্তির ভুল: “প্রতিটি ঘর ভরতে স্থির সময়” মিথ্যা। দৈর্ঘ্য l-এর ঘরে l − 1টি split দেখতে হয়; চূড়ার কাছের ঘরগুলোয় প্রায় n-টি। মোট কাজ ঘরের সংখ্যা নয়, জোড়ার সংখ্যা, যা Θ(n3). পরীক্ষা: n = 5-এ ১৫টি ঘর কিন্তু ২০টি জোড়া; n = 100-এ ৫০৫০টি ঘর কিন্তু ১,৬৬,৬৫০টি জোড়া।
-
Output অনুমান: cyk_count.py ব্লকের শেষ দুই লাইনে string-টি বদলে “id * id * id * id” করা হলো, আর layered ও flat দুটি grammar-এই গাছ গোনা হলো। দুটিতে কত গাছ আসবে? আর flat grammar-এ “( id + id ) * id” দিলে?
“id ∗ id ∗ id ∗ id”-এ তিনটি operator. Flat grammar-এ গাছের সংখ্যা তৃতীয় Catalan সংখ্যা C3 = 5: চারটি operand-কে binary গাছে বসানোর পাঁচটি উপায় ((ab)c)d, (a(bc))d, (ab)(cd), a((bc)d), a(b(cd)). Layered grammar-এ T → T∗F বাঁ দিকে recursive, তাই শুধু ((id ∗ id) ∗ id) ∗ id, গাছ ১টি।
“( id + id ) ∗ id”-এ বন্ধনী গঠন বেঁধে দেয়: যোগটি অবশ্যই বন্ধনীর ভেতরে, গুণ বাইরে। Flat grammar-এও গাছ ১টি। Scratch-এ ব্লকটি এই তিন ক্ষেত্রে চালিয়ে ঠিক 5, 1 আর 1 এসেছে। শিক্ষা: গাছের সংখ্যা নির্ভর করে grammar আর string দুটির ওপর; একই grammar কোনো string-এ ambiguous, কোনোটিতে নয়।
-
নকশা ও সংশোধন: G: S → AB, A → a, B → C, C → b. এটি CNF নয় (B → C একটি unit production). কেউ এটির ওপরেই অংশ ৩-এর CYK চালালেন, B → C নিয়মটি উপেক্ষা করে। “ab”-এর জন্য কী উত্তর আসবে, আর সঠিক উত্তর কী? CNF-এ না এনেও CYK-কে কীভাবে বদলালে সঠিক উত্তর আসে, এমন একটি পরিবর্তন নকশা করুন।
ভুল উত্তর: T[0, 1] = {A} (A → a), T[1, 1] = {C} (C → b). B ঘরে নেই, কারণ B → b নিয়ম নেই। তাই T[0, 2]-এ জোড় A·C, কিন্তু কোনো নিয়ম → AC নেই; ঘর ফাঁকা, উত্তর “প্রত্যাখ্যান”. অথচ S ⇒ AB ⇒ aB ⇒ aC ⇒ ab, তাই ab ∈ L(G). এটি অংশ ৪-এর প্রমাণের ধাপ ১-এর ঠিক সেই জায়গা, যা unit নিয়মে ভাঙে।
সংশোধন (unit closure): প্রতিটি ঘর ভরার পর, ঘরে C থাকলে আর B → C নিয়ম থাকলে B-ও যোগ করুন; নতুন কিছু যোগ না হওয়া পর্যন্ত এটি বারবার করুন। (আগে থেকে সব “unit pair” (B, C), অর্থাৎ B ⇒∗ C, হিসাব করে রাখলে প্রতিটি ঘরে একবারেই হয়; পর্ব ২৮-এর unit pair-এর ধারণা।) এখানে T[1, 1] = {C, B}, তারপর T[0, 2]-এ A·B থেকে S: গৃহীত। Lange ও Leiß ২০০৯ সালের একটি প্রবন্ধে এমন একটি রূপ (CNF-এর বদলে শুধু binary নিয়ম আর unit closure) প্রস্তাব করেন বলে পরিচিত, যাতে CNF রূপান্তরের আকার-বৃদ্ধি এড়ানো যায়। ε-নিয়মের জন্যও আলাদা যত্ন লাগে (nullable variable), তাই সাধারণভাবে CNF-ই সবচেয়ে নিরাপদ পথ।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি সাধারণ CFG আর string w-এর membership CYK দিয়ে ঠিক করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Grammar-টিকে Chomsky normal form-এ রূপান্তর করা
- w = ε হলে শুধু S → ε নিয়ম আছে কি না দেখে উত্তর দেওয়া
- প্রতিটি অক্ষরের ঘর A → a নিয়ম দিয়ে ভরা
- দৈর্ঘ্য ২ থেকে n পর্যন্ত, প্রতিটি ঘরে সব split আর সব A → BC নিয়ম পরীক্ষা করা
- চূড়ার ঘরে start symbol আছে কি না দেখে গ্রহণ বা প্রত্যাখ্যান করা
- গৃহীত হলে back-pointer ধরে চূড়া থেকে নিচে নেমে parse tree লেখা
CNF grammar S → AB ∣ BC, A → BA ∣ a, B → CC ∣ b, C → AB ∣ a. String “ab”-এর CYK টেবিলে পুরো string-এর ঘরে কী থাকবে?
- {A, S}
- {B}
- {C, S}
- ∅
দৈর্ঘ্য n-এর string-এ, একটি স্থির CNF grammar নিয়ে, CYK algorithm-এর সময় কত?
- O(n2), কারণ টেবিলে প্রায় n2/2টি ঘর
- O(n3)
- O(2n)
- O(n)
একটি CNF grammar-এ (start symbol S) একটি string-এর CYK টেবিলের চূড়ার ঘর {B}. কোন সিদ্ধান্তটি সঠিক?
- ঘর ফাঁকা নয়, তাই string গৃহীত
- আরও তথ্য ছাড়া বলা যায় না
- Grammar-টি অবশ্যই ambiguous
- String প্রত্যাখ্যাত, যদিও B থেকে string-টি derive হয়
CYK চালানোর আগে grammar-কে Chomsky normal form-এ আনার মূল কারণ কোনটি?
- প্রতিটি ভেতরের node-এর ঠিক দুই সন্তান আর কোনো ভাগ ফাঁকা নয়, তাই ঘর ছোট দুই ঘর থেকে ভরা যায়
- CNF-এ grammar কখনো ambiguous হয় না
- CNF-এ নিয়মের সংখ্যা সবসময় কম হয়
- CNF-এ CYK linear সময়ে চলে
CYK-এর ঘরে variable-এর set-এর বদলে “কতগুলো parse tree” সংখ্যা রাখা হলো। পুনরাবৃত্তি সূত্রে কোন বদলটি ঠিক?
- OR আর AND দুটির জায়গায় সর্বোচ্চ (max)
- OR-এর জায়গায় গুণ, AND-এর জায়গায় যোগ
- OR-এর জায়গায় যোগ, AND-এর জায়গায় গুণ
- কিছুই বদলাতে হয় না, set-এর আকারই গাছের সংখ্যা
Valiant (১৯৭৫) আর Lee (২০০২)-এর কাজ মিলিয়ে CFG parsing-এর গতি নিয়ে কোন কথাটি সঠিক?
- প্রমাণিত হয়েছে যে n3-এর চেয়ে দ্রুত CFG parsing অসম্ভব
- CFG parsing আর Boolean matrix গুণ প্রায় সমান কঠিন, আর সেরা সম্ভাব্য সময় এখনো অজানা
- Valiant সব CFG-এর জন্য linear সময়ের parser দিয়েছেন
- বাস্তবের সব parser আজ Valiant-এর পদ্ধতি ব্যবহার করে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Membership problem: w ∈ L(G)? CNF-এ derivation ঠিক 2n − 1 ধাপের বলে ACFG decidable, কিন্তু সব derivation খোঁজা exponential.
- CYK-এর ঘর T[i, l] = { A : A ⇒∗ w[i : i+l] }; A ∈ T[i, l] ⇔ কোনো k আর A → BC-তে B ∈ T[i, k], C ∈ T[i+k, l−k]. গ্রহণ ⇔ S ∈ T[0, n].
- সঠিকতা: দৈর্ঘ্যের ওপর induction, যা CNF-এর দুই শর্তের (binary নিয়ম, ε নেই) ওপর দাঁড়িয়ে; ε আলাদা করে।
- খরচ: (n3 − n)/6টি (i, l, k) জোড়া, সময় O(n3 · |G|), জায়গা O(n2 · |V|); তাই প্রতিটি CFL P-তে।
- Back-pointer থেকে parse tree; set-এর বদলে সংখ্যা রাখলে গাছ গোনা (Catalan), সম্ভাবনা রাখলে সেরা গাছ। চূড়ায় অন্য variable থাকলেও S না থাকলে প্রত্যাখ্যান।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২৯ · Chomsky normal form — রূপান্তর ধাপে ধাপেপূর্বশর্তযেকোনো CFG থেকে CYK-এর উপযোগী CNF grammar বানানোর ধাপ।
- পর্ব ২৬ · Derivation আর parse tree — leftmost, rightmost আর yieldফিরে দেখুনভাগ করার lemma আর গাছ-derivation সংযোগ, যা CYK-এর প্রমাণে লেগেছে।
- পর্ব ২৫ · Context-free grammar — formal definition আর উদাহরণফিরে দেখুনG = (V, Σ, R, S), expression grammar আর বাজারঘরের order-query grammar.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৩২ pushdown automaton, আর পর্ব ৪১-এ Earley ও GLR.
- DSA · পর্ব ৫২ — Dynamic programming-এর ভিত্তিপাশের ট্র্যাকMemoization আর tabulation, CYK-এর পেছনের সাধারণ কৌশল।