এই পর্বে যা শিখবেন
- GNF-এর সংজ্ঞা, আর প্রমাণ যে GNF-এ দৈর্ঘ্য n-এর string-এর derivation ঠিক n ধাপের
- Immediate আর indirect left recursion চেনা, আর কেন সরল top-down parser এতে আটকে যায়
- Immediate left recursion দূর করার সূত্র আর তার শুদ্ধতার প্রমাণ
- Variable সাজিয়ে substitution-এর সাধারণ algorithm দিয়ে যেকোনো ε-মুক্ত grammar-কে GNF-এ নেওয়া
- GNF থেকে ε-move ছাড়া PDA বানানো, আর রূপান্তরে grammar-এর আকার কত বাড়ে তা মাপা
১ · প্রতিটি ধাপে একটি terminal — Greibach normal form কী
পর্ব ২৯-এ একটি context-free grammar-এর Chomsky normal form (CNF) দেখেছেন: প্রতিটি নিয়ম A → BC বা A → a. CNF গাছের আকার বাঁধে: প্রতিটি ভেতরের node-এর দুটি সন্তান। এই পর্বের normal form বাঁধে derivation-এর গতি: প্রতিটি ধাপে ঠিক একটি নতুন terminal, আর সেটি সবসময় বাকি variable-গুলোর ঠিক আগে বসে।
বাজারঘরের গুদামে একটি order মেলানো হচ্ছে। কর্মী তালিকার প্রথম জিনিসটি তাক থেকে তুলে ঝুড়িতে রাখেন, আর তালিকায় লিখে রাখেন “এরপর কী কী বাকি”. প্রতিটি পদক্ষেপে ঠিক একটি জিনিস ঝুড়িতে যায়, আর বাকি কাজ তালিকার শেষে জমা থাকে। ১২টি জিনিসের order মানে ঠিক ১২টি পদক্ষেপ, এক বেশিও না, এক কমও না। কোনো পদক্ষেপে “কিছু না তুলে শুধু তালিকা নতুন করে লেখা” চলবে না। GNF ঠিক এই নিয়ম: প্রতিটি derivation-ধাপ একটি terminal “তোলে” আর বাকি variable-গুলো তালিকার মতো পেছনে রাখে।
একটি CFG G = (V, Σ, R, S) Greibach normal form-এ আছে, যদি প্রতিটি নিয়ম এই আকারের হয়:
অর্থাৎ ডান দিক একটি terminal দিয়ে শুরু, আর তারপর শুধু variable (শূন্য বা বেশি)। ε ∈ L(G) চাইলে একটিমাত্র ব্যতিক্রম: S → ε নিয়মটি রাখা যায়, তবে তখন S কোনো নিয়মের ডান দিকে আসবে না।
প্রতিটি চিহ্নের মানে আবার বলি: V হলো variable বা nonterminal-এর set, Σ হলো terminal-এর alphabet, আর V∗ মানে variable দিয়ে গড়া যেকোনো ক্রম, ফাঁকা ক্রমসহ। তাই A → a (α = ε) চলে, A → aBC চলে, কিন্তু A → BC (terminal দিয়ে শুরু নয়), A → aBb (পরে একটি terminal) বা A → ε (S ছাড়া অন্য variable-এর) চলে না। কিছু বই শর্তটি শিথিল করে α ∈ (V ∪ Σ)∗ লেখে; সেই রূপ থেকে কঠোর রূপে যাওয়া সহজ, প্রতিটি পরের terminal a-কে একটি নতুন variable Xa → a দিয়ে বদলালেই হয়। এই কোর্সে কঠোর রূপটিই GNF.
একটি ছোট উদাহরণ। পর্ব ২৫-এর anbn grammar S → aSb ∣ ε GNF-এ নেই: aSb-তে শেষে একটি terminal, আর ε-নিয়ম আছে। n ≥ 1 অংশের জন্য একটি GNF grammar:
aabb-এর derivation: S ⇒ aSB ⇒ aaBB ⇒ aabB ⇒ aabb. চারটি অক্ষর, চারটি ধাপ। লক্ষ করুন, প্রতিটি sentential form-এর আকার “কিছু terminal, তারপর শুধু variable”: a·SB, aa·BB, aab·B. ε-সহ পুরো language চাইলে নতুন start S0 → ε ∣ aSB ∣ aB যোগ করুন, যেখানে S0 কোথাও ডান দিকে আসে না।
G যদি GNF-এ থাকে আর A ⇒∗ w হয়, যেখানে A ∈ V আর w ∈ Σ+ (অর্থাৎ |w| ≥ ১), তবে এই derivation-এর ধাপ-সংখ্যা ঠিক |w|. তার ওপর, প্রতিটি leftmost derivation-এর প্রতিটি sentential form xβ আকারের, যেখানে x ∈ Σ∗ আর β ∈ V∗.
প্রমাণ:
- একটি sentential form-এ terminal-এর সংখ্যা t ধরুন। শুরুতে form-টি শুধু A, তাই t = 0. — derivation-এর শুরু
- প্রতিটি ধাপ একটি variable B-কে একটি নিয়ম B → bγ-এর ডান দিক দিয়ে বদলায়, যেখানে b ∈ Σ আর γ ∈ V∗. ডান দিকে terminal ঠিক একটি, তাই প্রতি ধাপে t ঠিক ১ বাড়ে। S → ε নিয়মটি এখানে খাটে না: S কোনো ডান দিকে নেই, তাই এটি শুধু প্রথম ধাপে S ⇒ ε হিসেবে আসতে পারত, আর তাতে w = ε হতো, যা |w| ≥ ১ শর্তে বাদ। — সংজ্ঞা ১.১
- k ধাপ পরে t = k. শেষ form w-তে t = |w|, তাই k = |w|. — ধাপ ১ আর ২ থেকে induction
- Leftmost derivation-এর জন্য |w|-এর ওপর induction: শুরুতে x = ε, β = A. যদি form xβ হয় আর β = Bβ′, তবে সবচেয়ে বাঁয়ের variable B, আর B → bγ খাটালে নতুন form (xb)(γβ′), আবার “terminal তারপর variable” আকারের। ∎ — leftmost-এর সংজ্ঞা আর ধাপ ২
শর্ত |w| ≥ ১ কেন: S → ε থাকলে w = ε-র derivation S ⇒ ε এক ধাপের, ০ ধাপের নয়; এই একটি ক্ষেত্রই ব্যতিক্রম। এর দুটি গুরুত্বপূর্ণ ফল আছে, অংশ ৬-এ বিস্তারিত: (ক) membership-এর জন্য derivation খোঁজা সবসময় |w| গভীরতায় থামে, আর (খ) form-এর variable-অংশ β ঠিক একটি stack-এর মতো আচরণ করে, যার ওপরের চিহ্ন প্রতিবার একটি input অক্ষর পড়ে বদলায়।
| বৈশিষ্ট্য | CNF (পর্ব ২৯) | GNF (এই পর্ব) |
|---|---|---|
| নিয়মের আকার | A → BC, A → a | A → aα, α ∈ V∗ |
| দৈর্ঘ্য n ≥ ১-এর string-এর derivation | ঠিক 2n − 1 ধাপ | ঠিক n ধাপ |
| Parse tree-র আকার | binary tree | প্রতিটি node-এর প্রথম সন্তান একটি পাতা |
| Left recursion | থাকতে পারে (A → AB) | অসম্ভব |
| প্রধান ব্যবহার | CYK (পর্ব ৩১), pumping lemma (পর্ব ৩৬) | ε-move ছাড়া PDA, তত্ত্বের প্রমাণ |
| রূপান্তরে আকার | সতর্ক ক্রমে polynomial | ক্লাসিক পদ্ধতিতে খুব দ্রুত বাড়তে পারে (অংশ ৫) |
“Left recursion অসম্ভব” সারিটি এই পর্বের কেন্দ্র। GNF-এ প্রতিটি নিয়ম terminal দিয়ে শুরু, তাই কোনো variable A থেকে এক বা বেশি ধাপে আবার A দিয়ে শুরু হওয়া form পাওয়া যায় না। উল্টো দিকে, যেকোনো grammar-কে GNF-এ নিতে হলে প্রথমে তার left recursion ভাঙতে হবে। তাই আগে দেখি left recursion কী, আর কেন এটি parser-এর শত্রু।
২ · Left recursion — top-down parser কেন আটকে যায়
G = (V, Σ, R, S) একটি CFG আর A ∈ V. A left-recursive, যদি কোনো α ∈ (V ∪ Σ)∗-এর জন্য A ⇒+ Aα হয়, অর্থাৎ এক বা বেশি ধাপে A থেকে এমন form পাওয়া যায় যা আবার A দিয়ে শুরু। নিয়মটি নিজেই A → Aα আকারের হলে একে বলে immediate (সরাসরি) left recursion; একাধিক ধাপ লাগলে indirect (পরোক্ষ) left recursion. কোনো variable left-recursive হলে grammar-টিকে left-recursive বলা হয়।
তিনটি উদাহরণ:
- Immediate: পর্ব ২৫-এর expression grammar E → E+T ∣ T. নিয়ম E → E+T নিজেই E দিয়ে শুরু।
- Indirect: S → Aa ∣ b, A → Sc ∣ d. কোনো নিয়ম নিজের variable দিয়ে শুরু নয়, তবু S ⇒ Aa ⇒ Sca: দুই ধাপে S আবার সামনে।
- লুকানো (ε-এর আড়ালে): A → BAc ∣ d, B → b ∣ ε. দেখতে A-এর নিয়ম B দিয়ে শুরু, কিন্তু B ফাঁকা হতে পারে, তাই A ⇒ BAc ⇒ Ac. শুধু নিয়মের প্রথম চিহ্ন দেখে এটি ধরা যায় না; এজন্যই সাধারণ algorithm আগে ε-নিয়ম সরাতে বলে (পর্ব ২৮)।
Left recursion গণিতে কোনো দোষ নয়: E → E+T একটি সম্পূর্ণ বৈধ CFG, আর যোগের বাঁ-সংযোগ (associativity) ঠিকঠাক প্রকাশ করে (পর্ব ২৭)। সমস্যা বাধে parser-এ। সবচেয়ে সরল top-down parser হলো recursive descent parser: প্রতিটি variable-এর জন্য একটি function, আর function-টি তার নিয়মের ডান দিক বাঁ থেকে ডানে “চালায়”: terminal হলে input-এর পরের token মেলায়, variable হলে সেই variable-এর function ডাকে। E → E+T চালাতে গিয়ে E-এর function প্রথমেই E-এর function ডাকে, কোনো token না পড়েই। দ্বিতীয় ডাকও একই অবস্থায়, একই কাজ করে। Input-এর অবস্থান এক চুলও সরে না, অথচ ডাকের stack বাড়তেই থাকে।
নিচের JavaScript ব্লক এটি নিজের চোখে দেখায়। প্রথম parser E → E+T ∣ T, T → id-এর সরল রূপ; নিরাপত্তার জন্য ১০০০ ডাকের একটি সীমা (cap) বসানো আছে, যাতে আপনার ব্রাউজার আটকে না যায়। দ্বিতীয় parser একই language-এর left recursion-মুক্ত grammar E → TE′, E′ → +TE′ ∣ ε (অংশ ৩-এ এর নির্মাণ) চালায়।
// Naive recursive descent: one function per variable, rules tried in order.
const toks = ["id", "+", "id", "+", "id"];
const CAP = 1000; // safety cap: never freeze the page
let calls = 0;
// Grammar 1 (left-recursive): E -> E + T | T, T -> id
function E_left(pos, depth) {
calls++;
if (depth < 3) console.log(`depth ${depth}: E at pos ${pos}, try E -> E + T`);
if (depth === CAP) throw new Error(`cap ${CAP} reached, pos still ${pos}`);
return E_left(pos, depth + 1); // first symbol is E again: same pos!
}
try { E_left(0, 0); } catch (e) { console.log("...\nstopped:", e.message, `(${calls} calls)`); }
// Grammar 2 (left recursion removed): E -> T E', E' -> + T E' | ε, T -> id
calls = 0;
function T(pos) {
calls++;
if (toks[pos] !== "id") throw new Error(`id expected at pos ${pos}`);
console.log(`T reads id at pos ${pos}`);
return pos + 1;
}
function Ep(pos) { // E'
calls++;
if (toks[pos] === "+") {
console.log(`E' reads + at pos ${pos}`);
return Ep(T(pos + 1));
}
console.log(`E' -> ε at pos ${pos}`);
return pos;
}
const end = Ep(T(0));
console.log(end === toks.length ? "accepted" : "rejected", `(${calls} calls)`);আসল আউটপুট (ব্রাউজারের JavaScript):
depth 0: E at pos 0, try E -> E + T
depth 1: E at pos 0, try E -> E + T
depth 2: E at pos 0, try E -> E + T
...
stopped: cap 1000 reached, pos still 0 (1001 calls)
T reads id at pos 0
E' reads + at pos 1
T reads id at pos 2
E' reads + at pos 3
T reads id at pos 4
E' -> ε at pos 5
accepted (6 calls)
প্রথম parser ১০০১ বার নিজেকে ডেকেছে, আর প্রতিবার pos 0: একটি token-ও পড়েনি। Cap না থাকলে ব্রাউজার শেষে stack ফুরিয়ে একটি error দিত (যেমন “Maximum call stack size exceeded”). কম ডাকের সীমা থাকলেও ফল একই: সমস্যাটি ডাকের সংখ্যা নয়, “অগ্রগতি নেই”. দ্বিতীয় parser মাত্র ৬টি ডাকে পুরো input পড়েছে: প্রতিটি T ডাক একটি id পড়ে, প্রতিটি E′ ডাক একটি + পড়ে বা ε নিয়ে থামে। মূল পার্থক্য: দ্বিতীয় grammar-এ কোনো function নিজেকে ডাকার আগে অন্তত একটি token পড়ে। toks বদলে ["id", "+"] দিয়ে দেখুন: দ্বিতীয় parser তখন “id expected at pos 2” error দেবে, অর্থাৎ ভুল input-এও সে থামে।
নিচের stepper ডাকের stack ধরে ঘটনাটি ধীরে দেখায়। Input: id + id + id, অবস্থান ০ থেকে ৪, আর অবস্থান ৫ মানে input শেষ।
1E → E + T2E → T3E → T E′4E′ → + T E′ ∣ ε5T → id
| ডাকের stack | |
| input-এর অবস্থান | |
| পড়া token |
- প্রথম ডাক। Parser E দিয়ে শুরু করে, প্রথম নিয়ম E → E + T নেয়। ডান দিকের প্রথম চিহ্ন E, তাই কোনো token মেলানোর আগেই E-এর function আবার ডাকতে হয়।
- দ্বিতীয় ডাক, একই অবস্থা। নতুন ডাকটিও অবস্থান 0-তে, একই input দেখছে, একই প্রথম নিয়ম নেয়। Function-এর কাছে আগের ডাকের থেকে আলাদা কোনো তথ্য নেই, তাই আচরণও হুবহু এক।
- অগ্রগতি শূন্য। Stack বাড়ছে, অবস্থান 0-তেই আটকে। ক্রম বদলে আগে E → T চেষ্টা করলেও লাভ নেই: T একটি id পড়ে সফল হয়, কিন্তু তারপর “+ id + id” বাকি থাকে, আর parser ফিরে এসে E → E + T চেষ্টা করলে আবার একই ফাঁদ।
- নতুন grammar: T আগে। E → T E′-এ প্রথম চিহ্ন T, আর T → id একটি token পড়ে। অবস্থান 0 থেকে 1. এখন যেকোনো পরের ডাক নতুন অবস্থান থেকে শুরু হবে।
- E′ + পড়ে। অবস্থান 1-এ “+”, তাই E′ → + T E′: + পড়ে, T একটি id পড়ে, অবস্থান 3. তারপর E′ নিজেকে ডাকে, কিন্তু ততক্ষণে দুটি token পড়া হয়ে গেছে।
- আবার + id. অবস্থান 3-এ আরেকটি “+”, একই নিয়ম, অবস্থান 5. প্রতিটি পুনরাবৃত্ত ডাক input-কে ছোট করছে, তাই ডাকের গভীরতা input-এর দৈর্ঘ্য দিয়ে বাঁধা।
- শেষ। অবস্থান 5-এ input শেষ, কোনো “+” নেই, তাই E′ → ε. সব ডাক ফেরে, পুরো input পড়া হয়েছে: গৃহীত। মোট ৬টি ডাক, যা JavaScript ব্লকের আউটপুটের সঙ্গে মেলে।
সাধারণ ভুল: “নিয়মের ক্রম বদলে দিলে, অর্থাৎ আগে E → T আর পরে E → E + T চেষ্টা করলে, loop থাকবে না” ভাবা। Backtracking parser প্রথম বিকল্প ব্যর্থ হলে বা পুরো input না মিললে দ্বিতীয় বিকল্পে যায়, আর তখনই আবার অসীম ডাক। Left recursion সরাতে হয় grammar বদলে, ক্রম বদলে নয়। উল্টো দিকে, bottom-up (LR) parser left recursion-এ কোনো সমস্যায় পড়ে না, বরং পছন্দ করে (পর্ব ৩৯)।
৩ · Immediate left recursion দূর করা
E → E+T ∣ T কী বানায়, তা খুলে দেখুন: E ⇒ E+T ⇒ E+T+T ⇒ T+T+T. বাঁ দিকে E যতবার নিজেকে খোলে, ডানে একটি করে “+T” জমা হয়; শেষে একবার E → T. তাই E থেকে আসে “একটি T, তারপর শূন্য বা বেশি +T”, অর্থাৎ T(+T)∗. একই set ডান দিক থেকেও বানানো যায়: আগে T বসান, তারপর একটি নতুন variable E′ যা (+T)∗ বানায়, ডান-recursion দিয়ে। এটিই সাধারণ সূত্র।
ধরুন A-এর সব নিয়ম
যেখানে m ≥ ১, প্রতিটি αj ≠ ε, আর কোনো βi A দিয়ে শুরু নয়। একটি নতুন variable A′ নিন, আর A-এর নিয়মগুলো বদলে লিখুন:
ε-মুক্ত রূপ (GNF-এর পথে এটিই লাগে): A → βi ∣ βiA′ আর A′ → αj ∣ αjA′, সব i আর j-এর জন্য।
শর্ত αj ≠ ε কেন? A → A নিয়মটি (α = ε) কিছুই বানায় না, শুধু একটি চক্র; এটি আগেই মুছে ফেলা যায়, আর না মুছলে গঠনটি A′ → A′ দেয়, নতুন একটি চক্র। আর k ≥ ১ না হলে, অর্থাৎ A-এর সব নিয়মই A দিয়ে শুরু হলে, A থেকে কোনো terminal string আসেই না: A একটি useless symbol (পর্ব ২৮), মুছে দিন।
G থেকে গঠন ৩.১ দিয়ে পাওয়া grammar G′ হলে L(G′) = L(G). দুই রূপেই (ε-সহ আর ε-মুক্ত) কথাটি সত্য।
প্রমাণ (গাছ বদলের যুক্তি):
- G-তে A-root-এর যেকোনো parse tree নিন। Root থেকে বাঁ দিকের সন্তান ধরে নামতে থাকুন, যতক্ষণ node-টি A আর তার নিয়ম A → Aαj. এই শিকল সসীম (গাছ সসীম), আর শিকলের নিচের A-তে একটি β-নিয়ম খাটে। তাই শিকলটি পড়লে yield হয় βi αjr ⋯ αj1-এর প্রতিটি অংশের উপগাছের yield জুড়ে। — গাছ সসীম; k ≥ ১
- G′-এ একই অংশগুলো দিয়ে একটি ডান-ঝোঁকা শিকল বানান: A → βiA′, তারপর A′ → αjrA′, …, A′ → αj1A′, শেষে A′ → ε. βi আর প্রতিটি α-র নিচের উপগাছগুলো হুবহু বসান (তাদের ভেতরের A-গুলোর ওপর একই বদল আগে করে নিয়ে)। Yield একই ক্রমে একই অংশ, তাই একই। — উপগাছের উচ্চতার ওপর induction
- উল্টো দিকে, G′-এর একটি গাছে A → βiA′ থেকে শুরু হওয়া A′-শিকলকে একইভাবে G-এর বাঁ-ঝোঁকা শিকলে বদলানো যায়। A′ শুধু এই শিকলেই আসে, কারণ A′ নতুন variable আর শুধু A আর A′-এর নিয়মে আছে। — A′-এর নিয়ম শুধু গঠন ৩.১-এর
- ধাপ ১–৩ মিলিয়ে, A থেকে কোনো terminal string w-এর গাছ G-তে থাকা আর G′-এ থাকা সমতুল্য; বিশেষ করে S-এর জন্য, L(G′) = L(G). ε-মুক্ত রূপে শুধু শেষ A′ → ε-র বদলে শেষ α-টি A′ → αj দিয়ে লেখা হয়, আর শিকলে কোনো α না থাকলে A → βi; যুক্তি একই। ∎ — পর্ব ২৬-এর গাছ ⇔ derivation উপপাদ্য
প্রমাণের মূল ছবিটি নিচে। Grammar A → Aa ∣ b (language ba∗) আর string “baa”. বাঁয়ে মূল grammar-এর গাছ: A-এর শিকল বাঁ দিকে নামে, আর a-গুলো ডান দিকে ঝোলে। ডানে নতুন grammar A → bA′, A′ → aA′ ∣ ε-এর গাছ: b আগে, তারপর A′-এর শিকল ডান দিকে নামে। পাতা দুটিতেই বাঁ থেকে ডানে b, a, a.
একই string “baa”, দুই grammar, দুই গাছ
বাঁয়ে A → Aa ∣ b (বাঁ-ঝোঁকা), ডানে A → bA′, A′ → aA′ ∣ ε (ডান-ঝোঁকা)। নীল বৃত্ত variable, সবুজ terminal.
এবার stepper-এ পুরো expression grammar-এ গঠনটি খাটানো হলো, প্রথমে E-তে, তারপর T-তে।
1E → E+T ∣ T2A → Aα ∣ β3E → T E′4E′ → +T E′ ∣ ε5T → T∗F ∣ F6T → F T′, T′ → ∗F T′ ∣ ε
| α (পুনরাবৃত্ত অংশ) | |
| β (শুরুর অংশ) | |
| যা বানায় |
- সমস্যা চেনা। E → E+T নিজের variable দিয়ে শুরু: immediate left recursion. E থেকে আসে T, T+T, T+T+T, …: সব শেষে একটি T দিয়ে শুরু, তারপর কিছু “+T”.
- ছাঁচে মেলানো। গঠন ৩.১-এর ছাঁচ A → Aα ∣ β. এখানে A = E, α = +T (E-এর পরের অংশ), β = T (যে নিয়ম E দিয়ে শুরু নয়)। E যা বানায় তা β-র পরে কিছু α: β α α ⋯ α.
- β আগে। নতুন নিয়ম E → TE′: আগে β = T, তারপর একটি নতুন variable E′, যার কাজ বাকি α-গুলো বানানো। E আর নিজেকে দিয়ে শুরু হয় না।
- ডান দিকে recursion. E′ → +TE′ ∣ ε: E′ একটি α বসিয়ে আবার E′, বা ε দিয়ে থামে। তাই E′ বানায় (+T)∗, আর E বানায় T(+T)∗, মূলের সমান। Recursion এখন ডান দিকে, যা top-down parser-এর জন্য নিরাপদ।
- একই কাজ T-তে। T → T∗F ∣ F-এ α = ∗F, β = F. নতুন নিয়ম T → FT′, T′ → ∗FT′ ∣ ε. T বানায় F(∗F)∗.
- ফল। E → TE′, E′ → +TE′ ∣ ε, T → FT′, T′ → ∗FT′ ∣ ε, F → (E) ∣ id. ছয়টি নিয়ম থেকে আটটি বিকল্প (দুটি নতুন ε-বিকল্পসহ)। F-এর নিয়মে left recursion ছিল না, তাই বদলায়নি। এটিই top-down parsing-এর পাঠ্যবই-grammar, পর্ব ৩৮-এর LL(1) table এর ওপরেই বানানো হবে।
দাবিটি এবার কোডে যাচাই করুন। নিচের ব্লকের lang(G, n) প্রতিটি variable থেকে আসা দৈর্ঘ্য n পর্যন্ত সব terminal string বের করে, একটি fixpoint iteration-এ: প্রতিটি নিয়মের ডান দিকের অংশগুলোর এখন পর্যন্ত জানা string জুড়ে নতুন string পায়, আর নতুন কিছু না আসা পর্যন্ত চলে। এটি left recursion আর ε-নিয়ম দুটিই নিরাপদে সামলায়, কারণ কোনো derivation “চালায়” না, শুধু set বড় করে। দৈর্ঘ্য গোনা হয় token-এ, তাই id একটি token. এই পর্বের তিনটি Python ব্লক একই namespace ভাগ করে (data-shared); পরের ব্লক আগে চালালে এটি নিজে থেকে আগে চলবে।
# A grammar is {variable: [right-hand sides as tuples]}; () means ε.
def lang(G, n): # all terminal strings of length <= n, per variable
L, changed = {A: set() for A in G}, True
while changed: # fixpoint: repeat until nothing new
changed = False
for A, rhss in G.items():
for rhs in rhss:
cur = {()}
for X in rhs:
part = L[X] if X in G else {(X,)}
cur = {u + v for u in cur for v in part if len(u + v) <= n}
if cur - L[A]: L[A] |= cur; changed = True
return L
def remove_immediate(G, A, eps=True): # A -> A a | b ==> A -> b A', ...
rec = [r[1:] for r in G[A] if r[:1] == (A,)]
base = [r for r in G[A] if r[:1] != (A,)]
if not rec: return None
B = A + "'"
if eps: G[A], G[B] = [b + (B,) for b in base], [a + (B,) for a in rec] + [()]
else: G[A], G[B] = base + [b + (B,) for b in base], rec + [a + (B,) for a in rec]
return B
def show(G):
for A, rhss in G.items():
print(f" {A:2} ->", " | ".join(" ".join(r) or "ε" for r in rhss))
AR = {"E": [("E", "+", "T"), ("T",)], "T": [("T", "*", "F"), ("F",)],
"F": [("(", "E", ")"), ("id",)]}
for eps in (True, False):
G = {A: list(rs) for A, rs in AR.items()}
remove_immediate(G, "E", eps); remove_immediate(G, "T", eps)
print("with ε-rules:" if eps else "ε-free version:"); show(G)
ok = all(lang(G, n)["E"] == lang(AR, n)["E"] for n in range(10))
print(" same strings as the original, all lengths <= 9:", ok)
print("expressions with <= 9 tokens:", len(lang(AR, 9)["E"]))আসল আউটপুট (ব্রাউজারের Python):
with ε-rules:
E -> T E'
T -> F T'
F -> ( E ) | id
E' -> + T E' | ε
T' -> * F T' | ε
same strings as the original, all lengths <= 9: True
ε-free version:
E -> T | T E'
T -> F | F T'
F -> ( E ) | id
E' -> + T | + T E'
T' -> * F | * F T'
same strings as the original, all lengths <= 9: True
expressions with <= 9 tokens: 257
প্রথম grammar stepper-এর ফলের সঙ্গে হুবহু মেলে। দ্বিতীয়টি ε-মুক্ত রূপ: প্রতিটি β একা আর β-র পরে A′ দুইভাবে আসে, আর A′-এর ε-বিকল্পের বদলে প্রতিটি α একা থাকে। দুই রূপেই ৯ token পর্যন্ত মূল grammar-এর ঠিক ২৫৭টি expression আসে, একটি বেশিও না, কমও না। এটি প্রমাণ নয়, উপপাদ্য ৩.২ প্রমাণ; কিন্তু গঠনে একটি টাইপের ভুল থাকলে (যেমন A′-এর ε ভুলে যাওয়া) এই পরীক্ষা সঙ্গে সঙ্গে False দেখাত। অংশ ৭-এ ঠিক এমন একটি ভুল ধরা হবে।
Associativity হারানোর ফাঁদ: নতুন grammar-এর গাছ ডান-ঝোঁকা (ছবি ৩০.১)। কেউ যদি id − id − id-এর মান এই গাছ ধরে সরাসরি নিচ থেকে ওপরে হিসাব করে, পাবে id − (id − id), যা ভুল। Language একই থাকে, কিন্তু গাছের অর্থ বদলায়। তাই বাস্তব parser E′-এর ভেতরে একটি চলমান যোগফল বাঁ থেকে ডানে বহন করে, বা E → T {+ T}-এর মতো EBNF loop লেখে (পর্ব ৩৮ আর ৪২)।
৪ · সাধারণ algorithm — variable সাজানো আর substitution
Indirect left recursion-এ গঠন ৩.১ সরাসরি খাটে না: S → Aa ∣ b, A → Sc ∣ d-এ কোনো নিয়মই নিজের variable দিয়ে শুরু নয়। কৌশলটি হলো recursion-কে আগে “সরাসরি” বানানো। দুটি ছোট হাতিয়ার লাগে: একটি substitution-এর নিয়ম, আর variable-এর একটি ক্রম।
ধরুন A → Bγ একটি নিয়ম আর B-এর সব নিয়ম B → δ1 ∣ ⋯ ∣ δk. A → Bγ মুছে A → δ1γ ∣ ⋯ ∣ δkγ যোগ করলে language বদলায় না।
প্রমাণ: (১) প্রতিটি নতুন নিয়ম A → δiγ পুরোনো grammar-এ দুই ধাপে পাওয়া যায়: A ⇒ Bγ ⇒ δiγ; তাই নতুন grammar-এর প্রতিটি derivation পুরোনোতে অনুকরণ করা যায়। (২) উল্টো দিকে, পুরোনো grammar-এর কোনো গাছে A → Bγ নিয়মের node থাকলে, তার B-সন্তান কোনো একটি B → δi খাটায় (গাছ সম্পূর্ণ, তাই B-এর নিচে কিছু আছে)। দুটি node জুড়ে একটি A → δiγ node বানান; yield বদলায় না। প্রতিবার A → Bγ-এর ব্যবহার এক কমে, তাই সসীম বার পরে গাছটি নতুন grammar-এর। ∎
এবার ক্রম। Variable-গুলোকে A1, A2, …, An নামে সাজান। লক্ষ্য: প্রতিটি নিয়ম Ai → Ajγ-তে j > i. এমন হলে left recursion অসম্ভব, কারণ প্রতিটি “প্রথম চিহ্ন বদল” কঠোরভাবে বড় সূচকে যায়, আর সূচক n-এর বেশি হতে পারে না। নিচের algorithm বইগুলোতে প্রায়ই Paull-এর algorithm নামে পরিচিত।
পূর্বশর্ত: G-তে কোনো ε-নিয়ম নেই (S → ε ছাড়া, যা আলাদা রাখা হয়) আর কোনো চক্র A ⇒+ A নেই। CNF-এর grammar (পর্ব ২৯) দুটি শর্তই মানে।
ধাপ: i = 1, 2, …, n ক্রমে:
১. j = 1, 2, …, i − 1 ক্রমে: Ai → Ajγ আকারের প্রতিটি নিয়মে lemma ৪.১ দিয়ে Aj-এর বর্তমান সব নিয়ম বসান।
২. এখন Ai-এর কোনো নিয়ম j < i-এর Aj দিয়ে শুরু নয়। Ai → Aiα থাকলে গঠন ৩.১-এর ε-মুক্ত রূপ দিয়ে তা সরান, নতুন variable Ai′ নিয়ে।
প্রমাণের রূপরেখা (কেন কাজ করে): i-এর ওপর induction দিয়ে দেখানো যায়, ধাপ i শেষে প্রতিটি k ≤ i-এর জন্য Ak → Alγ মানে l > k. ধাপ i-এর ভেতরের loop-এ j বাড়ার ক্রমে substitution হয়; Aj-এর নিয়মগুলো induction অনুযায়ী terminal বা j-এর চেয়ে বড় সূচক দিয়ে শুরু, তাই বসানোর পর Ai-এর নিয়মের প্রথম সূচক কঠোরভাবে বাড়ে, আর j = i − 1 শেষে সব প্রথম সূচক ≥ i. সমান i মানে immediate left recursion, যা ধাপ ২ সরায়। নতুন Ai′-এর নিয়ম α দিয়ে শুরু, আর α ≠ ε কারণ চক্র নেই; ε-নিয়মও তৈরি হয় না কারণ ε-মুক্ত রূপ ব্যবহার করা হয়েছে। Language বদলায় না, কারণ প্রতিটি ধাপ lemma ৪.১ বা উপপাদ্য ৩.২. বিস্তারিত প্রমাণ Hopcroft–Motwani–Ullman-এর বইয়ের Greibach normal form অংশে পাবেন। ∎
পূর্বশর্ত দুটি কেন? ε-নিয়ম থাকলে অংশ ২-এর লুকানো উদাহরণের মতো recursion প্রথম চিহ্নে দেখা যায় না, ফলে algorithm তা ধরতেই পারে না। চক্র থাকলে (যেমন A → B, B → A) substitution-এর পর A → A নিয়ম আসে, যার α = ε, আর গঠন ৩.১ খাটে না।
Left recursion সরানোর পর GNF মাত্র দুই ধাপ দূরে। এখন An-এর প্রতিটি নিয়ম terminal দিয়ে শুরু (তার চেয়ে বড় সূচক নেই)। An−1-এর নিয়ম terminal বা An দিয়ে শুরু; An বসালে সবই terminal দিয়ে শুরু। এভাবে পেছন থেকে A1 পর্যন্ত (back-substitution). তারপর নতুন Ai′-গুলোর নিয়মে একবার substitution. শেষে প্রথম ছাড়া অন্য জায়গার প্রতিটি terminal a-কে Xa দিয়ে বদলান, আর Xa → a যোগ করুন। নিচের stepper ছোট indirect উদাহরণে তিনটি ধাপ চালায়।
1S → Aa ∣ b2A → Sc ∣ d3A → Aac ∣ bc ∣ d4A → bc ∣ d ∣ bcA′ ∣ dA′5A′ → ac ∣ acA′6S → bca ∣ da ∣ bcA′a ∣ dA′a ∣ b7Xa → a, Xc → c
| পর্যায় | |
| মূল ঘটনা | |
| মোট নিয়ম |
- শুরু। ক্রম S = A1, A = A2. কোনো নিয়ম নিজের variable দিয়ে শুরু নয়, তবু S ⇒ Aa ⇒ Sca: indirect left recursion. নিয়ম ৪টি; ε-নিয়ম বা চক্র নেই, তাই algorithm ৪.২ চলবে।
- i = 1 (S). ছোট সূচকের কোনো variable নেই, তাই substitution নেই। S → Aa শুরু হয় A2 দিয়ে, যার সূচক ১-এর বড়: লক্ষ্যের সঙ্গে মানানসই। S-এ immediate left recursion নেই।
- i = 2 (A), j = 1. A → Sc শুরু হয় S = A1 দিয়ে, সূচক ছোট। Lemma ৪.১: S-এর দুটি নিয়ম বসিয়ে A → Aac ∣ bc. সঙ্গে আগের A → d. লুকানো recursion এখন সরাসরি: A → Aac.
- Immediate সরানো। গঠন ৩.১-এর ε-মুক্ত রূপ: α = ac, β = bc আর d. ফল A → bc ∣ d ∣ bcA′ ∣ dA′ আর A′ → ac ∣ acA′. মোট ২ + ৪ + ২ = ৮টি নিয়ম। পর্যায় ১ শেষ: কোথাও left recursion নেই।
- Back-substitution, শেষ থেকে। A হলো শেষ সূচক, তার সব নিয়ম আগেই terminal (b বা d) দিয়ে শুরু। A′-এর নিয়মও a দিয়ে শুরু। কিছু বদলায় না।
- S-এ A বসানো। S → Aa শুরু হয় A দিয়ে; A-এর চারটি নিয়ম বসিয়ে S → bca ∣ da ∣ bcA′a ∣ dA′a, সঙ্গে আগের S → b. সব নিয়ম এখন terminal দিয়ে শুরু। মোট ৫ + ৪ + ২ = ১১.
- পরের terminal বদলানো। প্রথমের পরে থাকা a আর c-কে Xa, Xc দিয়ে বদলে: S → bXcXa ∣ dXa ∣ bXcA′Xa ∣ dA′Xa ∣ b, A → bXc ∣ d ∣ bXcA′ ∣ dA′, A′ → aXc ∣ aXcA′. ১১ + ২ = ১৩টি নিয়ম, সবই A → aα আকারের: GNF.
একটি মজার পর্যবেক্ষণ: শেষ grammar-এ S-এর কোনো নিয়মে A আর নেই, তাই A এখন S থেকে পৌঁছানো যায় না, একটি useless symbol. পর্ব ২৮-এর reachable-পরীক্ষা চালালে A-এর চারটি নিয়ম মুছে যায়, বাকি থাকে ৯টি। মূল language-টি কী? S = b ∣ Sca ∣ da থেকে S = (b ∣ da)(ca)∗, অর্থাৎ b, da, bca, daca, bcaca, …; পরের ব্লক এটি brute force-এ মেলাবে।
৫ · Greibach-এর উপপাদ্য আর পূর্ণ রূপান্তর
প্রতিটি context-free language L-এর জন্য L − {ε}-এর একটি GNF grammar আছে। ফলে ε ∉ L হলে L নিজেই কোনো GNF grammar-এর language, আর ε ∈ L হলে একটি নতুন start S0 → ε যোগ করে (S0 ডান দিকে আসে না) L-এর grammar পাওয়া যায়।
প্রমাণের রূপরেখা:
- L-এর যেকোনো CFG নিয়ে পর্ব ২৯-এর রূপান্তরে L − {ε}-এর একটি CNF grammar বানান। CNF-এ ε-নিয়ম নেই, unit নিয়ম নেই, তাই চক্রও নেই। — পর্ব ২৯-এর CNF উপপাদ্য
- Variable-গুলো যেকোনো ক্রমে সাজিয়ে algorithm ৪.২ চালান। ফল: কোনো left recursion নেই, প্রতিটি Ai → Ajγ-তে j > i, আর নতুন Ai′-এর নিয়ম কোনো Aj বা terminal দিয়ে শুরু। — algorithm ৪.২-এর invariant
- An থেকে A1 পর্যন্ত back-substitution, তারপর Ai′-গুলোতে একবার। প্রতিটি নিয়ম এখন terminal দিয়ে শুরু, আর বাকি অংশে CNF থেকে আসা variable বা terminal. — lemma ৪.১, সূচকের ওপর নিচ থেকে induction
- প্রথমের পরের প্রতিটি terminal a-কে Xa → a দিয়ে বদলান। এটিও lemma ৪.১-এর উল্টো প্রয়োগ, language একই। এখন প্রতিটি নিয়ম A → aα, α ∈ V∗. ∎ — সংজ্ঞা ১.১
CNF থেকে শুরু করা সুবিধার, কিন্তু বাধ্যতামূলক নয়: যেকোনো ε-মুক্ত, চক্রহীন grammar-এ algorithm চলে। নিচের ব্লক আগের ব্লকের lang, remove_immediate আর show ব্যবহার করে তিনটি grammar-এ পুরো রূপান্তর চালায়: অংশ ৪-এর S/A উদাহরণ, পর্ব ২৫-এর expression grammar (এতে T → F-এর মতো unit নিয়ম আছে, কিন্তু চক্র নেই), আর বহু বইয়ে দেখা একটি ক্লাসিক CNF উদাহরণ A1 → A2A3, A2 → A3A1 ∣ b, A3 → A1A2 ∣ a, যেখানে A3 ⇒ A1A2 ⇒ A2A3A2 ⇒ A3A1A3A2: তিন ধাপের indirect recursion. প্রতিটির জন্য ব্লকটি নিয়ম-সংখ্যা, GNF-এর শর্ত আর ১০ দৈর্ঘ্য পর্যন্ত language-এর সমতা ছাপে, তারপর একটি GNF derivation দেখায়।
def to_gnf(G, order): # needs: no ε-rules, no A =>+ A
G, new = {A: list(rs) for A, rs in G.items()}, []
def subst_first(A, allowed): # expand a leading variable in allowed
G[A] = [s + r[1:] for r in G[A]
for s in (G[r[0]] if r[0] in allowed else [r[:1]])]
for i, Ai in enumerate(order): # phase 1: Ai -> Aj... only if j > i
for Aj in order[:i]: subst_first(Ai, {Aj})
B = remove_immediate(G, Ai, eps=False)
if B: new.append(B)
for A in order[::-1] + new: subst_first(A, set(G)) # phase 2: back-substitute
terms = {X for rs in G.values() for r in rs for X in r[1:] if X not in G}
for A in G: # phase 3: a later terminal a -> X_a
G[A] = [r[:1] + tuple(X if X in G else "X_" + X for X in r[1:]) for r in G[A]]
G.update({"X_" + a: [(a,)] for a in sorted(terms)})
return G
def is_gnf(G):
return all(r and r[0] not in G and all(X in G for X in r[1:])
for rs in G.values() for r in rs)
def derive(G, form, w, i=0): # leftmost; every step eats w[i]
if not form or i == len(w) or len(form) > len(w) - i:
return [] if not form and i == len(w) else None
for r in G[form[0]]:
if r[0] == w[i]:
rest = derive(G, r[1:] + form[1:], w, i + 1)
if rest is not None: return [w[:i + 1] + r[1:] + form[1:]] + rest
SA = {"S": [("A", "a"), ("b",)], "A": [("S", "c"), ("d",)]}
HU = {"A1": [("A2", "A3")], "A2": [("A3", "A1"), ("b",)], "A3": [("A1", "A2"), ("a",)]}
for G, order in [(SA, ["S", "A"]), (AR, ["E", "T", "F"]), (HU, ["A1", "A2", "A3"])]:
H, S, size = to_gnf(G, order), order[0], lambda g: sum(map(len, g.values()))
ok = all(lang(G, n)[S] == lang(H, n)[S] for n in range(11))
print(f"{S}: {size(G)} -> {size(H)} rules | GNF: {is_gnf(H)} | same <= 10: {ok}")
H = to_gnf(SA, ["S", "A"]); show(H)
steps = derive(H, ("S",), tuple("bcaca"))
print(f"bcaca, {len(steps)} steps: S =>", " => ".join(" ".join(f) for f in steps))আসল আউটপুট (ব্রাউজারের Python):
S: 4 -> 13 rules | GNF: True | same <= 10: True
E: 6 -> 19 rules | GNF: True | same <= 10: True
A1: 5 -> 24 rules | GNF: True | same <= 10: True
S -> b X_c X_a | d X_a | b X_c A' X_a | d A' X_a | b
A -> b X_c | d | b X_c A' | d A'
A' -> a X_c | a X_c A'
X_a -> a
X_c -> c
bcaca, 5 steps: S => b X_c A' X_a => b c A' X_a => b c a X_c X_a => b c a c X_a => b c a c a
S/A উদাহরণে ৪টি নিয়ম থেকে ১৩টি, stepper-এর শেষ ধাপের সঙ্গে হুবহু একই grammar. Expression grammar ৬ থেকে ১৯: E-এর নিয়মই ৮টি, যেমন E → (EXT′E′ বা E → idT′E′ (এখানে X → ); কোডে এর নাম X_))। ক্লাসিক উদাহরণে ৫ থেকে ২৪, যার ১০টি শুধু নতুন A3′-এর; হাতে করলে এখানেই সবচেয়ে বেশি ভুল হয়। তিনটিতেই is_gnf True আর ১০ দৈর্ঘ্য পর্যন্ত language হুবহু এক। শেষ লাইন উপপাদ্য ১.২ চোখে দেখায়: bcaca-র ৫টি অক্ষর, ৫টি ধাপ, আর প্রতিটি ধাপে বাঁয়ের terminal-অংশ ঠিক একটি অক্ষর বাড়ে, পেছনে শুধু variable. লক্ষ করুন derive কখনো আটকায় না: প্রতিটি ডাক একটি অক্ষর খায়, তাই গভীরতা বড়জোর |w|; অংশ ২-এর অসীম loop এখানে অসম্ভব।
আকারের দাম
৪ থেকে ১৩, ৫ থেকে ২৪: বৃদ্ধি চোখে পড়ার মতো। কারণ back-substitution গুণ করে: Ai-এর একটি নিয়ম Aj দিয়ে শুরু হলে সেটি Aj-এর যত নিয়ম, তত কপি হয়, আর Aj-এর নিয়মগুলো নিজেরাই আগের substitution-এ বেড়েছে। একটি সহজ পরিবার দিয়ে scratch-এ মাপা হয়েছে: Ai → Ai+1X ∣ Ai+1Y ∣ c (i < m), Am → a ∣ b, X → x, Y → y. এতে কোনো left recursion-ই নেই, তবু একই to_gnf চালিয়ে পাওয়া গেছে:
| m | ২ | ৩ | ৪ | ৫ | ৬ | ৭ | ৮ |
|---|---|---|---|---|---|---|---|
| মূল নিয়ম | ৭ | ১০ | ১৩ | ১৬ | ১৯ | ২২ | ২৫ |
| GNF-এর নিয়ম | ৯ | ২০ | ৪৩ | ৯০ | ১৮৫ | ৩৭৬ | ৭৫৯ |
মূল grammar রৈখিকভাবে বাড়ছে (প্রতি ধাপে ৩টি নিয়ম), অথচ GNF প্রায় দ্বিগুণ হচ্ছে প্রতিবার: exponential বৃদ্ধি। এটি algorithm-এর দোষ, language-এর নয়: এই পরিবারের m = 8-এর জন্য হাতে ৪৪ নিয়মের একটি GNF grammar লেখা গেছে, আর brute force-এ ৯ দৈর্ঘ্য পর্যন্ত মূলের সঙ্গে মিলেছে। সাহিত্যে জানা আছে যে সতর্ক পদ্ধতিতে (যেমন Rosenkrantz-এর ১৯৬৭ সালের matrix পদ্ধতি, আর পরবর্তী উন্নত algorithm) GNF-এ যাওয়া যায় মূল আকারের polynomial আকারে; সঠিক সীমা পদ্ধতিভেদে আলাদা, তাই এখানে নির্দিষ্ট ঘাত বলা হলো না। পরীক্ষার খাতায় অবশ্য ক্লাসিক algorithm-ই প্রত্যাশিত।
৬ · GNF কেন কাজের — ε-move ছাড়া PDA আর সসীম খোঁজ
উপপাদ্য ১.২ বলেছিল, GNF-এর leftmost derivation-এর প্রতিটি form হলো “পড়া অংশ x, তারপর variable-এর ক্রম β”. এখন β-কে একটি stack ভাবুন, সবচেয়ে বাঁয়ের variable ওপরে। Input-এর পরের অক্ষর a আর stack-এর ওপরে A হলে, A → aα নিয়ম মানে: a পড়ুন, A তুলে ফেলুন, α রাখুন। এটি ঠিক একটি pushdown automaton-এর move, যা পর্ব ৩২-এ formal ভাবে আসবে।
GNF grammar G = (V, Σ, R, S) থেকে একটি PDA বানান, যার একটিমাত্র state q, stack alphabet V, শুরুতে stack-এ S. প্রতিটি নিয়ম A → aα-এর জন্য একটি move: state q-তে input a পড়ে, stack-এর ওপরের A-কে α দিয়ে বদলানো (α-র প্রথম চিহ্ন ওপরে)। Input শেষে stack খালি হলে গ্রহণ (empty stack দিয়ে গ্রহণ, পর্ব ৩৩)। এই PDA-র কোনো move ε পড়ে না: প্রতিটি move ঠিক একটি input অক্ষর পড়ে।
শুদ্ধতা সরাসরি উপপাদ্য ১.২ থেকে: PDA-র k move পরে অবস্থা (পড়া অংশ x, stack β) ঠিক তখনই সম্ভব, যখন S ⇒lmk xβ. তাই w পড়ে stack খালি ⇔ S ⇒∗ w. S → aSB ∣ aB, B → b-এর PDA:
| move | পড়া অক্ষর | নিয়ম | stack (ওপর বাঁয়ে) | বাকি input |
|---|---|---|---|---|
| শুরু | — | — | S | aabb |
| ১ | a | S → aSB | SB | abb |
| ২ | a | S → aB | BB | bb |
| ৩ | b | B → b | B | b |
| ৪ | b | B → b | ফাঁকা | ফাঁকা: গৃহীত |
প্রতিটি move একটি অক্ষর, মোট ৪টি move. এখান থেকে একটি গুরুত্বপূর্ণ তাত্ত্বিক ফল: প্রতিটি ε-মুক্ত CFL এমন একটি PDA দিয়ে গ্রহণ করা যায়, যার কোনো ε-move নেই। এমন PDA-কে প্রায়ই real-time PDA বলা হয়। তবে সাবধান: PDA-টি সাধারণত nondeterministic; move ২-এ S-এর দুটি নিয়মই a দিয়ে শুরু, তাই PDA-কে “অনুমান” করতে হয় কোন নিয়ম নেবে। তাই GNF সরাসরি দ্রুত parsing দেয় না। “Real-time parsing” কথাটি এই অর্থেই সীমিত: প্রতিটি অক্ষরে সসীম কাজ, কিন্তু অনেকগুলো বিকল্প পথ একসঙ্গে।
দ্বিতীয় ফল: membership সমস্যার একটি সরল, সবসময় থামে এমন সমাধান। w ∈ L(G)? GNF-এ সব leftmost derivation-এর দৈর্ঘ্য ঠিক |w|, প্রতিটি ধাপে প্রথম অক্ষর মিলতেই হবে, আর stack-এ input-এর বাকি অংশের চেয়ে বেশি variable রাখা অর্থহীন (প্রতিটি variable অন্তত একটি অক্ষর বানায়)। তাই derive-এর মতো backtracking খোঁজ সবসময় থামে। দাম: সবচেয়ে খারাপ ক্ষেত্রে নিয়মের সংখ্যার |w|-তম ঘাত, অর্থাৎ exponential. পরের পর্বের CYK CNF ব্যবহার করে একই প্রশ্নের উত্তর দেয় n3-এর অনুপাতের সময়ে।
তৃতীয় ফল, ব্যবহারিক: left recursion দূর করা নিজেই top-down parsing-এর প্রথম শর্ত। পর্ব ৩৮-এর LL(1) parser left-recursive grammar নিতে পারে না: E → E+T ∣ T-এ id দেখে দুটি নিয়মই প্রার্থী। তাই বাস্তবে GNF-এ পুরো রূপান্তর প্রায় কেউ করে না (আকার বাড়ে, গাছ অচেনা হয়), কিন্তু অংশ ৩-এর গঠন প্রায় প্রতিটি হাতে লেখা parser-এর পেছনে আছে। এর সঙ্গে আরেকটি কৌশল লাগে, “left factoring”: A → αβ1 ∣ αβ2-এর মতো একই শুরুর নিয়মকে A → αA″, A″ → β1 ∣ β2 করা; এর আলোচনা পর্ব ৩৮-এ। Compiler নির্মাণের পূর্ণ প্রকৌশল একটি পরের “Programming Languages & Compilers” কোর্সে আসবে।
আরও গভীরে: GNF-এর আরও কঠোর রূপও আছে। Quadratic GNF-এ প্রতিটি নিয়ম A → aα-তে |α| ≤ 2, আর প্রতিটি ε-মুক্ত CFL-এর এমন grammar আছে বলে জানা। Daniel Rosenkrantz ১৯৬৭ সালের প্রবন্ধে “double Greibach normal form” দেখান, যেখানে প্রতিটি নিয়মের ডান দিক terminal দিয়ে শুরু এবং শেষ হয় (বা একটিমাত্র terminal). এই রূপগুলো CFL-এর বীজগাণিতিক তত্ত্বে (grammar-কে language-এর সমীকরণ-ব্যবস্থা হিসেবে দেখা, পর্ব ১৫-এর Arden-এর সূত্রের CFL-রূপ) আর ε-মুক্ত, এক-state PDA-র প্রমাণে কাজে লাগে।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- GNF-এর সংজ্ঞা দিন; CNF-এর সঙ্গে পার্থক্য কী? A → aα, α ∈ V∗; GNF-এ n ধাপে derivation, CNF-এ 2n − 1.
- A → Aα ∣ β থেকে left recursion দূর করুন। A → βA′, A′ → αA′ ∣ ε (বা ε-মুক্ত রূপ A → β ∣ βA′, A′ → α ∣ αA′)।
- Recursive descent parser কেন left recursion-এ আটকায়? Function কোনো token না পড়েই নিজেকে ডাকে, অবস্থান বদলায় না।
- Indirect left recursion কীভাবে দূর করবেন? Variable সাজিয়ে ছোট সূচকের variable substitute করুন, তারপর immediate রূপ সরান; আগে ε-নিয়ম আর চক্র সরাতে হয়।
- GNF থেকে PDA কেন সহজ? প্রতিটি নিয়ম একটি input অক্ষর পড়ে stack-এর ওপরের variable বদলানোর একটি move.
৭ · AI-এর যুগে GNF আর left recursion
“এই grammar-কে GNF-এ নাও” বললে AI assistant সাধারণত দেখতে নিখুঁত একটি উত্তর দেয়। ভুলগুলো সূক্ষ্ম: কখনো ε-সহ সূত্র (A′ → αA′ ∣ ε) সরাসরি GNF-এ রেখে দেয়, কখনো ε-মুক্ত রূপে “একা β” বা “একা α” কপিগুলো ভুলে যায়, কখনো indirect recursion দেখেই না। নিচের ব্লক অংশ ৪-এর grammar-এর দুটি নমুনা ভুল উত্তর (AI যেমন প্রায়ই দেয়) আর আমাদের to_gnf-এর উত্তর পরীক্ষা করে: কোন নিয়ম GNF ভাঙে, আর ৮ দৈর্ঘ্য পর্যন্ত কোন string বাদ পড়েছে বা বাড়তি এসেছে।
# Check claimed GNF answers for S -> A a | b, A -> S c | d (shared block).
G = {"S": [("A", "a"), ("b",)], "A": [("S", "c"), ("d",)]}
XT = {"X_a": [("a",)], "X_c": [("c",)]}
claims = {
"ai_1": {"S": [("b", "X_c", "A'", "X_a"), ("d", "A'", "X_a"), ("b",)],
"A'": [("a", "X_c", "A'"), ()], **XT},
"ai_2": {"S": [("b", "X_c", "A'", "X_a"), ("d", "A'", "X_a"), ("b",)],
"A'": [("a", "X_c"), ("a", "X_c", "A'")], **XT},
"ours": to_gnf(G, ["S", "A"]),
}
def words(s): return sorted(("".join(w) for w in s), key=lambda w: (len(w), w))
for name, H in claims.items():
bad = [f"{A} -> {' '.join(r) or 'ε'}" for A, rs in H.items() for r in rs
if not (r and r[0] not in H and all(X in H for X in r[1:]))]
want, got = lang(G, 8)["S"], lang(H, 8)["S"]
print(f"{name}: rules breaking GNF: {bad or 'none'}")
print(f" missing: {words(want - got)[:3]} extra: {words(got - want)[:3]}")আসল আউটপুট (ব্রাউজারের Python):
ai_1: rules breaking GNF: ["A' -> ε"]
missing: [] extra: []
ai_2: rules breaking GNF: none
missing: ['da', 'bca'] extra: []
ours: rules breaking GNF: none
missing: [] extra: []
প্রথম উত্তরের language ঠিক, কিন্তু A′ → ε নিয়মটি GNF-এ নিষিদ্ধ: এটি ε-সহ সূত্রের অবশেষ। “Language মিলেছে” দেখে নিশ্চিন্ত হলে এই ভুল চোখ এড়িয়ে যায়; তাই আকারের পরীক্ষা আলাদা লাগে। দ্বিতীয় উত্তর দেখতে সম্পূর্ণ GNF, কিন্তু S-এর “bXcXa” আর “dXa” নিয়ম দুটি নেই, অর্থাৎ A′ ছাড়া β-কপিগুলো বাদ। ফলে da আর bca-র মতো ছোট string হারিয়েছে: language-এর পরীক্ষা ছাড়া এটি ধরা কঠিন। আমাদের উত্তর দুই পরীক্ষাতেই উত্তীর্ণ। নিয়ম বদলে নিজের হাতে করা রূপান্তরও এভাবে পরীক্ষা করুন।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| GNF-এ A′ → ε রেখে দেওয়া, বা A → aBb-এর মতো পরের terminal | প্রতিটি নিয়মে “প্রথমে একটি terminal, তারপর শুধু variable” শর্তটি কোডে বা হাতে মেলান |
| ε-মুক্ত রূপে A → β বা A′ → α-এর একা কপি বাদ দেওয়া | ছোট দৈর্ঘ্যের সব string brute force-এ মূলের সঙ্গে মেলান; সবচেয়ে ছোট string-গুলোই আগে হারায় |
| Indirect recursion (S → Aa, A → Sc) না দেখে “left recursion নেই” বলা | প্রথম চিহ্ন ধরে একটি graph আঁকুন (A → B… মানে A থেকে B-তে তীর); কোনো চক্র থাকলে left recursion আছে |
| ε-নিয়ম বা চক্র থাকতেই algorithm ৪.২ চালানো | আগে পর্ব ২৮-এর ধাপ (nullable, unit pair) চালানো হয়েছে কি না দেখুন |
| “GNF থেকে deterministic, দ্রুত parser পাওয়া যায়” দাবি | একই terminal দিয়ে শুরু দুটি নিয়ম আছে কি না দেখুন; থাকলে PDA nondeterministic |
| বানানো ইতিহাস (Greibach-এর সাল, প্রবন্ধের নাম) | Hopcroft–Motwani–Ullman বা মূল প্রবন্ধে (Journal of the ACM, ১৯৬৫) নিজে মিলিয়ে নিন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু শেষ grammar নয়, প্রতিটি পর্যায়ের grammar আর একটি যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: S ⇒ AB ⇒ SaB, তাই indirect left recursion আছে; language-টি (b ∣ cb)(ab)∗. AI-এর grammar এই ব্লকের check-ধাঁচের পরীক্ষায় বসিয়ে দেখুন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Sheila Greibach কেন এমন একটি normal form খুঁজছিলেন, যেখানে প্রতিটি নিয়ম একটি terminal দিয়ে শুরু? যন্ত্রে ভাষা বিশ্লেষণের প্রথম যুগের সঙ্গে এর সম্পর্ক কী?
১৯৫০-এর দশকের শেষ আর ১৯৬০-এর দশকের শুরুতে context-free grammar শুধু গণিতের বিষয় ছিল না; যন্ত্রে অনুবাদ (machine translation) প্রকল্পগুলো বাস্তব বাক্য parse করার উপায় খুঁজছিল। Harvard-এ Anthony Oettinger-এর দলের কাজে “predictive analysis” নামের একটি পদ্ধতি ব্যবহৃত হতো বলে পরিচিত: বাক্য বাঁ থেকে ডানে পড়তে পড়তে একটি stack-এ “এরপর কী কী আসবে বলে অনুমান” জমা রাখা, আর প্রতিটি শব্দ পড়ে সেই অনুমান একধাপ এগোনো। Susumu Kuno ও Oettinger-এর ১৯৬২-৬৩ সালের দিকের “multiple-path” বিশ্লেষক এর একটি পরিচিত রূপ, যা একসঙ্গে অনেক অনুমান-পথ রাখত।
এই পদ্ধতি কাজ করে তখনই, যখন grammar-এর প্রতিটি নিয়ম একটি “শব্দ” দিয়ে শুরু: প্রতিটি শব্দ পড়লে একটি নিয়ম বাছা যায়, আর stack-এ বাকি অনুমান বসে। এটি ঠিক অংশ ৬-এর এক-state PDA. প্রশ্ন দাঁড়াল: সব context-free language কি এভাবে বিশ্লেষণ করা যায়, নাকি কিছু language-এর জন্য এমন grammar আদৌ নেই? Sheila Greibach Harvard-এ এই পরিবেশে কাজ করতেন, আর ১৯৬৫ সালে Journal of the ACM-এ প্রকাশিত প্রবন্ধে প্রমাণ করেন যে প্রতিটি ε-মুক্ত CFL-এর এমন grammar আছে। অর্থাৎ predictive পদ্ধতির ধারণাগত সীমা grammar-এর আকার নয়; প্রতিটি CFL-ই এই ছাঁচে আনা যায়।
তবে উপপাদ্যটি দক্ষতার প্রতিশ্রুতি দেয় না। এক শব্দে একাধিক নিয়ম মিললে বিকল্প পথের সংখ্যা বাড়তে থাকে, আর multiple-path বিশ্লেষক দীর্ঘ বাক্যে খুব ধীর হয়ে পড়ত বলে পরিচিত। পরে Earley (১৯৬৮-৭০) আর CYK-ধাঁচের dynamic programming বিকল্প পথগুলো ভাগাভাগি করে polynomial সময়ে আনে। Greibach নিজে পরবর্তী দশকগুলোতে formal language তত্ত্বের অনেক মৌলিক কাজ করেন, যেমন ১৯৭৩ সালের “hardest context-free language” নামে পরিচিত ফলাফল।
মূল উপলব্ধি: GNF একটি বাস্তব প্রশ্নের উত্তর হিসেবে এসেছিল: “প্রতি শব্দে এক ধাপ” পদ্ধতি কি সব CFL-এ খাটে? উত্তর হ্যাঁ, কিন্তু nondeterminism-এর দাম নিয়ে। ধারণাগত সম্ভাব্যতা আর দক্ষ algorithm দুটি আলাদা প্রশ্ন, এই কোর্সে বারবার এটি দেখবেন।
প্র ০২বাস্তবের parser generator আর হাতে লেখা parser left recursion-কে কীভাবে সামলায়? সবাই কি grammar বদলে ফেলে?
তিনটি আলাদা পথ আছে, আর কোনটি নেওয়া হবে তা parsing কৌশলের ওপর নির্ভর করে। প্রথম পথ bottom-up: yacc, Bison বা অন্য LR/LALR parser generator left recursion-এ কোনো সমস্যায় পড়ে না। বরং এদের জন্য E → E + T লেখাই ভালো, কারণ এতে parser-এর stack ছোট থাকে: প্রতিটি “+ T” পড়ার পরই reduce হয়। ডান-recursion E → T + E লিখলে পুরো expression শেষ না হওয়া পর্যন্ত stack-এ সব জমে থাকে। তাই bottom-up জগতে left recursion বন্ধু (পর্ব ৩৯)।
দ্বিতীয় পথ top-down, grammar বদলে। LL(1) parser আর বেশিরভাগ হাতে লেখা recursive descent parser অংশ ৩-এর গঠন ব্যবহার করে, তবে প্রায়ই সরাসরি E′ না লিখে একটি loop লেখে: “একটি T পড়ুন; যতক্ষণ পরের token +, ততক্ষণ + আর আরেকটি T পড়ুন, আর ফলাফল বাঁ দিক থেকে জুড়ুন”. এতে associativity-র ফাঁদও এড়ানো যায় (অংশ ৩-এর সতর্কতা)। অনেক production compiler-এর হাতে লেখা parser এই ধাঁচের; precedence climbing বা Pratt parsing (Vaughan Pratt-এর ১৯৭৩ সালের প্রবন্ধ থেকে) একই সমস্যার আরও সাজানো সমাধান।
তৃতীয় পথ: tool নিজেই রূপান্তর করে। ANTLR 4 (Terence Parr-এর দল, ২০১৩ সালের দিকে প্রকাশ) সরাসরি left-recursive নিয়ম (যেমন e : e '*' e | e '+' e | INT) মেনে নেয় আর ভেতরে precedence-সহ একটি loop-এ রূপান্তর করে; তবে indirect left recursion সাধারণত সমর্থন করে না বলে এর documentation-এ বলা আছে। PEG বা packrat parser-এর জগতেও left recursion একসময় নিষিদ্ধ ছিল; ২০০৮ সালে Alessandro Warth ও সহকর্মীরা memoization বাড়িয়ে left recursion সামলানোর একটি কৌশল প্রকাশ করেন, আর CPython-এর নতুন PEG parser (PEP 617, Python 3.9) এই ধরনের কৌশল ব্যবহার করে left-recursive নিয়ম মেনে নেয় বলে পরিচিত।
মূল উপলব্ধি: Left recursion নিজে কোনো দোষ নয়; এটি নির্দিষ্ট একটি parsing কৌশলের সমস্যা। তত্ত্ব (গঠন ৩.১, উপপাদ্য ৩.২) নিশ্চয়তা দেয় যে language না বদলে সমস্যাটি সরানো যায়; প্রকৌশল ঠিক করে কে, কখন, কোথায় সেটি সরাবে।
প্র ০৩GNF-এ derivation-এর দৈর্ঘ্য ঠিক |w|. তাহলে কি membership-এর জন্য CYK-এর চেয়ে GNF ভালো? “প্রতি অক্ষরে এক ধাপ” কেন দ্রুত parsing-এর নিশ্চয়তা নয়?
দৈর্ঘ্যের সীমা খোঁজকে সসীম করে, দ্রুত করে না। GNF-এ w-এর leftmost derivation খুঁজতে প্রতিটি ধাপে input-এর পরের অক্ষর দিয়ে শুরু হওয়া নিয়মগুলো চেষ্টা করতে হয়। ধরুন stack-এর ওপরের variable-এর এমন দুটি নিয়ম প্রায় প্রতিবারই থাকে; তাহলে |w| ধাপে সম্ভাব্য পথ 2|w| পর্যন্ত। অংশ ৫-এর derive এই backtracking খোঁজ, আর এটি ছোট string-এ তৎক্ষণাৎ শেষ হলেও খারাপ grammar-এ দীর্ঘ input-এ exponential সময় নিতে পারে।
CYK (পর্ব ৩১) অন্য কৌশল নেয়: “variable A কি input-এর i থেকে j অংশ বানাতে পারে?” প্রশ্নটি প্রতিটি (A, i, j)-এর জন্য একবারই উত্তর দেয় আর table-এ রাখে। বিকল্প পথগুলো একই উপ-প্রশ্নে মিলিত হলে আবার হিসাব হয় না, তাই সময় n3-এর অনুপাতে। এটি dynamic programming-এর মূল কৌশল। একই ভাগাভাগি GNF-এর PDA-র ওপরেও করা যায়: “এই অবস্থানে, stack-এর ওপরে এই variable” অবস্থাগুলো মিলিয়ে রাখলে exponential খোঁজ polynomial হয়; Earley-র algorithm (পর্ব ৪১) মোটামুটি এই ধারণার একটি পরিশীলিত রূপ।
তত্ত্বের দিক থেকে আরও একটি কথা: “ε-move নেই” মানে প্রতিটি অক্ষরে PDA-র কাজ সসীম, কিন্তু PDA nondeterministic. প্রতিটি nondeterministic PDA-কে deterministic PDA-তে আনা যায় না (পর্ব ৩৫), তাই সাধারণ CFL-এর জন্য “এক পাসে, এক পথে, প্রতি অক্ষরে সসীম কাজ” অসম্ভব। পাঠ্যবইয়ে GNF-এর ব্যবহার মূলত প্রমাণে: যেমন PDA আর CFG-এর সমতার একটি সরল দিক, বা কোনো CFL-এর ধর্ম প্রমাণে নিয়মের আকার বেঁধে রাখা।
মূল উপলব্ধি: Normal form-গুলো ভিন্ন ভিন্ন প্রশ্নের হাতিয়ার: CNF দেয় গাছের বাঁধা আকার, যা dynamic programming-এ লাগে; GNF দেয় প্রতি অক্ষরে এক ধাপ, যা automaton-এর সঙ্গে সরাসরি মেলে। দ্রুততা আসে ভাগাভাগি থেকে, normal form থেকে নয়।
প্র ০৪Algorithm ৪.২-এ variable-এর ক্রম যেকোনো হতে পারে। কিন্তু ক্রমভেদে ফলের আকার কি বদলায়? বড় বাস্তব grammar-এ এটি কতটা গুরুত্বপূর্ণ?
ক্রম শুদ্ধতা বদলায় না: যেকোনো ক্রমেই ফলের language একই, আর left recursion থাকে না। কিন্তু আকার অনেক বদলাতে পারে। অংশ ৪-এর উদাহরণে ক্রম উল্টে (A আগে, S পরে) চালালে recursion ধরা পড়ে S-এর নিয়মে, নতুন variable হয় S′, আর নিয়মের বিন্যাস আলাদা হয়। ছোট উদাহরণে পার্থক্য সামান্য, কিন্তু অংশ ৫-এর পরিবারে দেখেছেন, back-substitution প্রতিটি স্তরে নিয়ম গুণ করে; কোন variable কোন স্তরে বসছে, তার ওপর গুণফল নির্ভর করে।
মানুষের ভাষার বড় grammar-এ এটি বাস্তব সমস্যা হিসেবে দেখা দিয়েছিল। Robert C. Moore ২০০০ সালে NAACL সম্মেলনে “Removing left recursion from context-free grammars” প্রবন্ধে কয়েকটি বড় ইংরেজি grammar-এ ক্লাসিক algorithm চালিয়ে দেখান যে ফল অত্যন্ত বড় হয়ে যেতে পারে, আর কিছু উন্নতি প্রস্তাব করেন: যেমন শুধু আসলেই left-recursive variable-গুলোর ওপর কাজ করা, ক্রম বুদ্ধিমানভাবে বাছা, আর left-corner transform নামের একটি বিকল্প রূপান্তর ব্যবহার করা। তাঁর ফলাফলে উন্নত পদ্ধতিগুলো আকার বহুগুণ কমিয়েছিল বলে প্রবন্ধে রিপোর্ট করা আছে; সঠিক সংখ্যার জন্য মূল প্রবন্ধ দেখুন।
তত্ত্বের দিক থেকে ১৯৬৭ সালে Rosenkrantz grammar-কে একটি matrix সমীকরণ হিসেবে লিখে GNF-এ যাওয়ার এমন একটি পথ দেন, যার আকার polynomial বলে জানা; পরে আরও কিছু গবেষক এ নিয়ে উন্নত সীমা দেন। ব্যবহারিক শিক্ষা হলো: পরীক্ষার খাতায় ক্লাসিক algorithm ঠিক আছে, কিন্তু কোডে বড় grammar-এ চালানোর আগে আকার মাপুন, যেমন অংশ ৫-এর ব্লক নিয়ম গুনে দেখায়।
মূল উপলব্ধি: “Algorithm সঠিক” আর “algorithm ব্যবহারযোগ্য” এক কথা নয়। একই রূপান্তরের ভিন্ন ক্রম বা ভিন্ন পদ্ধতি exponential আর polynomial আকারের পার্থক্য করতে পারে, আর সেটি মাপার একমাত্র নির্ভরযোগ্য উপায় হলো চালিয়ে গুনে দেখা।
প্র ০৫বাজারঘরের order-query language-এর grammar যদি একটি top-down parser দিয়ে চালাতে হয়, তবে কী কী বদলাতে হবে, আর কোন বদল অর্থ নষ্ট করতে পারে?
পর্ব ২৫-২৬-এর token-grammar-এ শর্তের অংশ C → C OR T ∣ T, T → T AND F ∣ F, F → (C) ∣ amount R NUM ∣ district = STR ∣ status = STR. C আর T দুটিই immediate left-recursive, ঠিক expression grammar-এর মতো, কারণ এই নকশা OR আর AND-কে বাঁ-সংযোগ দেয় আর AND-কে OR-এর চেয়ে শক্ত বাঁধে। Top-down parser-এর জন্য গঠন ৩.১ দুবার: C → TC′, C′ → OR T C′ ∣ ε, T → FT′, T′ → AND F T′ ∣ ε. Precedence অক্ষত থাকে, কারণ স্তরগুলো (C, T, F) একই আছে; AND এখনো OR-এর নিচে।
কোন বদল অর্থ নষ্ট করতে পারে? AND আর OR দুটিই সংযোগ-নিরপেক্ষ (associative): (a AND b) AND c আর a AND (b AND c)-এর ফল একই। তাই ডান-ঝোঁকা গাছ এখানে কোনো ভুল ফল দেয় না। কিন্তু বাজারঘর যদি পরে একটি “EXCEPT” operator যোগ করে, যেমন “district = "Dhaka" EXCEPT status = "cancelled" EXCEPT …”, তবে বাঁ-সংযোগ আর ডান-সংযোগের ফল আলাদা হতে পারে, ঠিক বিয়োগের মতো। তখন ডান-ঝোঁকা গাছ থেকে সরাসরি হিসাব করলে ভুল order ফেরত আসবে, অথচ parser কোনো error দেবে না। এটিই অংশ ৩-এর সতর্কতার বাস্তব রূপ।
দ্বিতীয় সূক্ষ্ম বিষয় হলো F-এর তিনটি নিয়ম amount, district, status দিয়ে শুরু, আলাদা token, তাই top-down parser পরের token দেখেই নিয়ম বাছতে পারে। কিন্তু বাজারঘর যদি “amount >= NUM” আর “amount BETWEEN NUM AND NUM” দুটিই চায়, তবে দুটি নিয়ম একই token amount দিয়ে শুরু হবে, আর left factoring লাগবে (পর্ব ৩৮)। লক্ষ করুন, এখানে AND শব্দটি দুই ভূমিকায় আসছে, যা grammar-কে আরও জটিল করে; এ ধরনের নকশার প্রশ্ন পর্ব ৪২-এর বিষয়।
মূল উপলব্ধি: Grammar রূপান্তর language রক্ষা করে, অর্থ নয়। Left recursion সরানোর পর গাছের আকার বদলায়, তাই কোন operator-এর ক্ষেত্রে সংযোগের দিক অর্থ বদলায়, তা জেনে হিসাবের কোড লিখতে হয়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। left_recursion.py আর to_gnf.py ব্লকে নিজের grammar বসিয়ে উত্তর যাচাই করতে পারেন।
-
GNF নকশা: L = {anb2n : n ≥ 1}-এর জন্য একটি GNF grammar নকশা করুন। তারপর aabbbb-এর leftmost derivation লিখে দেখান যে ধাপ-সংখ্যা string-এর দৈর্ঘ্যের সমান।
নকশা: S → aSBB ∣ aBB, B → b. ভাবনা: প্রতিটি a পড়ার সময় “পরে দুটি b আসবে” এই প্রতিশ্রুতি হিসেবে দুটি B stack-এ রাখা। সব নিয়ম terminal দিয়ে শুরু আর পরে শুধু variable, তাই GNF.
শুদ্ধতা: S-এর k বার প্রয়োগ (k − 1 বার aSBB, শেষে aBB) দেয় akB2k, আর প্রতিটি B একটি b. উল্টো দিকে S থেকে যেকোনো derivation এই আকারেরই, কারণ S শুধু এই দুই নিয়মে খোলে। তাই L(G) = {akb2k : k ≥ 1}.
Derivation: S ⇒ aSBB ⇒ aaBBBB ⇒ aabBBB ⇒ aabbBB ⇒ aabbbB ⇒ aabbbb. ছয়টি অক্ষর, ছয়টি ধাপ। Scratch-এ brute force-এ ১২ দৈর্ঘ্য পর্যন্ত এই grammar-এর string ঠিক abb, aabbbb, aaabbbbbb, aaaabbbbbbbb পাওয়া গেছে।
-
প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “দাবি: যে CFG-তে A → Aα আকারের কোনো নিয়ম নেই, তাতে কোনো variable left-recursive নয়; তাই তার recursive descent parser সবসময় থামে। প্রমাণ: left recursion মানে variable নিজে দিয়ে শুরু হওয়া। কোনো নিয়ম নিজের variable দিয়ে শুরু নয়, তাই কোনো derivation-এ A থেকে A দিয়ে শুরু হওয়া form আসে না। ∎” প্রমাণের ভুলটি কোথায়? দুটি আলাদা ধরনের পাল্টা উদাহরণ দিন।
ভুল: “কোনো নিয়ম নিজের variable দিয়ে শুরু নয়” থেকে “কোনো derivation-এ A থেকে A-শুরু form আসে না” সিদ্ধান্তটি এক ধাপের কথাকে বহু ধাপে টেনে নেওয়া। সংজ্ঞা ২.১ A ⇒+ Aα চায়, এক বা বেশি ধাপে। প্রমাণ শুধু এক ধাপ পরীক্ষা করেছে।
পাল্টা উদাহরণ ১ (indirect): S → Aa ∣ b, A → Sc ∣ d. কোনো নিয়ম নিজের variable দিয়ে শুরু নয়, অথচ S ⇒ Aa ⇒ Sca. S-এর function A ডাকে, A-এর function S ডাকে, কোনো token না পড়েই।
পাল্টা উদাহরণ ২ (ε-এর আড়ালে): A → BAc ∣ d, B → b ∣ ε. A-এর নিয়ম B দিয়ে শুরু, কিন্তু B ⇒ ε, তাই A ⇒ BAc ⇒ Ac: এক ধাপের পরেই A আবার সামনে। Parser B-কে ε হিসেবে নিলে A আবার ডাকে।
সঠিক পরীক্ষা: একটি directed graph বানান, যেখানে A থেকে B-তে তীর থাকবে যদি A-এর কোনো নিয়মে B-এর আগে শুধু nullable চিহ্ন (যারা ε বানাতে পারে) থাকে, বা কিছুই না থাকে। এই graph-এ চক্র থাকলে, আর কেবল তখনই, grammar left-recursive. দুটি উদাহরণই scratch-এ
langদিয়ে পরীক্ষা করা হয়েছে: প্রথমটির language (b ∣ da)(ca)∗. -
Output অনুমান: to_gnf.py ব্লকের শেষ লাইনে
"bcaca"-এর বদলে"daca"দিলে কী ছাপা হবে? আর"dac"দিলে কী হবে, কেন?"daca":
daca, 4 steps: S => d A' X_a => d a X_c X_a => d a c X_a => d a c a. প্রথম অক্ষর d, তাই S-এর d দিয়ে শুরু নিয়ম দুটি: dXa আর dA′Xa. খোঁজ প্রথমে dXa নেয়, কিন্তু তখন stack-এ ১টি variable আর বাকি input “aca” — Xa একটি a বানিয়ে শেষ, “ca” বাকি থাকে, তাই ব্যর্থ, তারপর dA′Xa. চার অক্ষর, চার ধাপ।"dac": কোনো derivation নেই, তাই
deriveNone ফেরত দেয়, আরlen(steps)-এ একটি TypeError আসবে। কারণ language (b ∣ da)(ca)∗-এ শেষে সবসময় a. Scratch-এ চালিয়ে ঠিক এটিই এসেছে; কোডে একটিif steps is Noneপরীক্ষা যোগ করলে পরিষ্কার “rejected” ছাপানো যায়। -
রূপান্তর: বাজারঘরের query-শর্তের সরল grammar C → C o T ∣ T, T → T n F ∣ F, F → (C) ∣ f নিন (o মানে OR, n মানে AND, f একটি শর্ত)। (ক) ε-সহ সূত্রে left recursion দূর করুন। (খ) ক্রম C, T, F ধরে পুরো GNF-এ নিন আর নিয়ম গুনুন।
(ক) C → TC′, C′ → oTC′ ∣ ε, T → FT′, T′ → nFT′ ∣ ε, F → (C) ∣ f. এটি অংশ ৩-এর expression grammar-এর হুবহু ছাঁচ (+ এর জায়গায় o, ∗ এর জায়গায় n).
(খ) ε-মুক্ত রূপ: C → T ∣ TC′, C′ → oT ∣ oTC′, T → F ∣ FT′, T′ → nF ∣ nFT′. Back-substitution: F → (CX ∣ f (X → )); T → (CX ∣ f ∣ (CXT′ ∣ fT′; C → T-এর চার নিয়ম আর TC′-এর চার নিয়ম, মোট ৮. C′ আর T′ আগেই terminal দিয়ে শুরু। মোট ৮ + ২ + ৪ + ২ + ২ + ১ = ১৯টি নিয়ম, expression grammar-এর মতোই। Scratch-এ
to_gnfচালিয়ে ১৯টি নিয়ম, GNF-এর শর্ত True, আর ১০ দৈর্ঘ্য পর্যন্ত language-এর সমতা পাওয়া গেছে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি সাধারণ CFG-কে Greibach normal form-এ নেওয়ার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- ε-নিয়ম, unit নিয়ম আর useless symbol সরানো (বা CNF-এ নেওয়া)
- Variable-গুলোকে A1, …, An ক্রমে সাজানো
- প্রতিটি Ai-তে ছোট সূচকের Aj substitute করা আর immediate left recursion সরানো
- An থেকে A1 পর্যন্ত back-substitution, তারপর নতুন A′-গুলোতে
- প্রথমের পরের terminal-গুলোকে Xa → a দিয়ে বদলানো
- ছোট দৈর্ঘ্য পর্যন্ত মূল আর নতুন grammar-এর language মিলিয়ে দেখা
কোন নিয়মটি Greibach normal form-এ (A → aα, α ∈ V∗; বড় হাতের অক্ষর variable, ছোট হাতের terminal) অনুমোদিত?
- A → BC
- A → aBb
- A → aBC
- A → ε, যেখানে A start symbol নয়
একটি grammar Greibach normal form-এ আছে আর w = abcab এই grammar-এর language-এ আছে। S ⇒∗ w-এর যেকোনো derivation-এ কয়টি ধাপ থাকবে?
- ৯টি
- ঠিক ৫টি
- leftmost-এ ৫টি, অন্য ক্রমে বেশি হতে পারে
- grammar-এর নিয়মের সংখ্যার ওপর নির্ভর করে
A → Ab ∣ Ac ∣ d grammar থেকে immediate left recursion দূর করার সঠিক ফল (ε-সহ রূপে) কোনটি?
- A → dA′, A′ → bA′ ∣ cA′
- A → d, A′ → bA′ ∣ cA′ ∣ ε
- A → bA′ ∣ cA′, A′ → dA′ ∣ ε
- A → dA′, A′ → bA′ ∣ cA′ ∣ ε
Grammar: S → Aa ∣ b, A → Sc ∣ d. কোন কথাটি সঠিক?
- এতে indirect left recursion আছে, কারণ S ⇒ Aa ⇒ Sca
- কোনো নিয়ম নিজের variable দিয়ে শুরু নয়, তাই left recursion নেই
- এতে শুধু ε-এর আড়ালে লুকানো left recursion আছে
- এতে immediate left recursion আছে, কারণ A → Sc
Left recursion দূর করার সাধারণ algorithm (variable সাজিয়ে substitution) চালানোর আগে grammar-এ কোন শর্ত দরকার?
- Grammar unambiguous হতে হবে
- Grammar অবশ্যই Chomsky normal form-এ থাকতে হবে
- কোনো ε-নিয়ম (start-এর বাইরে) আর কোনো চক্র A ⇒+ A থাকবে না
- Grammar-এ কোনো indirect left recursion থাকবে না
GNF grammar S → aSB ∣ aB, B → b থেকে বানানো এক-state PDA (প্রতিটি নিয়ম A → aα মানে: a পড়ে stack-এর ওপরের A-কে α দিয়ে বদলানো, শুরুতে stack-এ S, খালি stack-এ গ্রহণ) সম্পর্কে কোনটি সঠিক?
- এটি deterministic, কারণ এতে কোনো ε-move নেই
- এর কোনো ε-move নেই, কিন্তু এটি nondeterministic
- এটি aabb গ্রহণ করে না
- এর জন্য অন্তত একটি ε-move দরকার, stack খালি করতে
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- GNF: প্রতিটি নিয়ম A → aα, α ∈ V∗; ε ∈ L হলে শুধু S → ε, আর S ডান দিকে নয়। দৈর্ঘ্য n-এর string-এর derivation ঠিক n ধাপ।
- Left recursion মানে A ⇒+ Aα; immediate (A → Aα), indirect (S → Aa, A → Sc) বা ε-এর আড়ালে। সরল top-down parser এতে কিছু না পড়েই নিজেকে ডাকে।
- A → Aα ∣ β ⇒ A → βA′, A′ → αA′ ∣ ε (ε-মুক্ত রূপ: A → β ∣ βA′, A′ → α ∣ αA′)। Language একই, গাছ ডান-ঝোঁকা; associativity হিসাবে সাবধান।
- সাধারণ algorithm: ε আর চক্র সরান, variable সাজান, ছোট সূচক substitute করুন, immediate সরান; তারপর back-substitution আর Xa → a.
- GNF থেকে ε-move ছাড়া এক-state PDA আসে, কিন্তু সেটি nondeterministic; ক্লাসিক রূপান্তরে আকার exponential হারে বাড়তে পারে, তাই নিয়ম গুনে আর brute force-এ যাচাই করুন।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২৯ · Chomsky normal form — রূপান্তর ধাপে ধাপেফিরে দেখুনGNF রূপান্তরের শুরুর grammar, আর 2n − 1 ধাপের তুলনা।
- পর্ব ২৮ · Grammar সরলীকরণ — useless symbol, ε আর unit productionপূর্বশর্তAlgorithm ৪.২ চালানোর আগে ε-নিয়ম আর চক্র সরানোর ধাপ।
- পর্ব ২৬ · Derivation আর parse tree — leftmost, rightmost আর yieldপটভূমিউপপাদ্য ৩.২-এর প্রমাণে লাগা গাছ ⇔ derivation সংযোগ।
- পর্ব ২৭ · Ambiguity — দ্ব্যর্থক grammar আর inherent ambiguityপটভূমিকেন E → E+T বাঁ-সংযোগ দেয়, আর স্তর বসিয়ে precedence.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ৩১ CYK, তারপর মডিউল ৬-এ PDA.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৩ — Grammar আর formal languageপাশের ট্র্যাকBNF আর derivation-এর প্রথম পরিচয়, গণিতের দিক থেকে।