সরাসরি পর্বে যান
পর্ব ২৯ · ৮৫-এর মধ্যে · মডিউল ৫

Chomsky normal form — রূপান্তর ধাপে ধাপে

Chomsky Normal Form — Definition, Binary Parse Trees, the 2n − 1 Theorem, Step-by-Step Conversion and Grammar Size

Taught in Bangla, this lesson defines Chomsky normal form and proves its consequences: every parse tree is nearly a full binary tree, every derivation of a length-n string takes exactly 2n − 1 steps, and tree height bounds string length. It walks through the five conversion steps START, DEL, UNIT, TERM and BIN on aSb, balanced brackets and an arithmetic grammar, checks the result with in-page Python (Pyodide), confirms it with a real nltk CNF run, and shows how step order controls grammar growth.

এই পর্বে যা শিখবেন

  • CNF-এর সঠিক সংজ্ঞা, কোন নিয়ম চলে আর কোনটি চলে না, আর ε নিয়ে দুই বইয়ের দুই রীতি
  • CNF-এ derivation-এর দৈর্ঘ্য 2n − 1 আর গাছের উচ্চতার সীমার প্রমাণ
  • যেকোনো CFG থেকে CNF বানানোর পাঁচ ধাপ, প্রতিটি ধাপ কেন language বদলায় না
  • anbn, সুষম বন্ধনী আর গাণিতিক expression-এর পূর্ণ রূপান্তর, Python-এ brute force দিয়ে যাচাই
  • ধাপের ক্রম বদলালে grammar-এর আকার কেন 2k হারে বাড়তে পারে

১ · কেন normal form — একই language, বাঁধা আকার

পর্ব ২৫-এ আপনি দেখেছেন, একই language-এর অনেক grammar থাকে। anbn-এর জন্য S → aSb ∣ ε যেমন ঠিক, তেমনি S → aSb ∣ ab ∣ ε-ও ঠিক। Context-free grammar-এর নিয়মের ডান দিকে যেকোনো দৈর্ঘ্যের যেকোনো মিশ্রণ থাকতে পারে: ফাঁকা (ε), একটি variable, দশটি terminal, যা খুশি। মানুষের লেখার জন্য এই স্বাধীনতা ভালো, কিন্তু algorithm আর প্রমাণের জন্য ঝামেলা। প্রতিটি algorithm-কে তখন সব রকম নিয়মের জন্য আলাদা ব্যবস্থা রাখতে হয়।

পরীক্ষার OMR শিটের কথা ভাবুন। উত্তর একই, কিন্তু খাতায় যে যার মতো লিখলে যন্ত্র পড়তে পারে না। OMR শিট প্রতিটি উত্তরকে একটি বাঁধা ছকে আনে: প্রতিটি প্রশ্নে চারটি বৃত্ত, একটি ভরাট। ছকটি উত্তর বদলায় না, শুধু আকার বেঁধে দেয়, আর তাই যন্ত্র এক নিয়মে হাজার খাতা পড়তে পারে। Normal form হলো grammar-এর OMR শিট: language একই থাকে, কিন্তু প্রতিটি নিয়ম কয়েকটি নির্দিষ্ট আকারের একটিতে আসে।

Chomsky normal form সবচেয়ে বেশি ব্যবহৃত normal form. এর নিয়মগুলো এত সরল যে প্রতিটি parse tree (পর্ব ২৬) একটি binary tree হয়ে যায়: প্রতিটি ভেতরের node-এর দুটি সন্তান, শুধু পাতার ঠিক আগে একটি। এর তিনটি বড় ফল এই মডিউল আর পরের মডিউলে আসবে:

  • Membership-এর algorithm: পর্ব ৩১-এর CYK algorithm একটি string-কে প্রতিটি জায়গায় দুই ভাগে কেটে dynamic programming চালায়। “দুই ভাগ” কাজ করে শুধু কারণ প্রতিটি নিয়মের ডান দিকে ঠিক দুটি variable.
  • প্রমাণ: পর্ব ৩৬-এর CFL pumping lemma binary tree-র উচ্চতা গুনে একটি variable-এর পুনরাবৃত্তি খুঁজে পায়।
  • Decision problem: CFL ফাঁকা কি না, সসীম কি না, এসব প্রশ্নের সহজ algorithm CNF ধরে নিয়ে লেখা হয় (পর্ব ৩৭)।

এই পর্বের কাজ তাই দুটি: CNF ঠিক কী আর কেন এত কাজের, তা প্রমাণসহ বোঝা; আর যেকোনো CFG থেকে CNF বানানোর algorithm হাতে-কলমে চালানো। ε-নিয়ম, unit নিয়ম আর অকেজো symbol সরানোর বিস্তারিত পর্ব ২৮-এর বিষয়; এখানে সেগুলো রূপান্তরের দুটি ধাপ হিসেবে সংক্ষেপে আসবে।

২ · সংজ্ঞা — কোন নিয়ম চলে, কোনটি চলে না

সংজ্ঞা ২.১ (Chomsky normal form)

একটি context-free grammar G = (V, Σ, R, S0) Chomsky normal form-এ আছে, যদি R-এর প্রতিটি নিয়ম নিচের তিন আকারের একটি হয়:
১. A → BC, যেখানে A, B, C ∈ V আর B, C দুটির কোনোটিই start symbol S0 নয়;
২. A → a, যেখানে A ∈ V আর a ∈ Σ;
৩. S0 → ε, শুধু start symbol-এর জন্য (ε ∈ L(G) হলে)।

সংজ্ঞাটি কথায়: ডান দিকে হয় ঠিক দুটি variable, নয়তো ঠিক একটি terminal. মিশ্রণ (aB), একা একটি variable (A → B), দুইয়ের বেশি চিহ্ন (ABC), বা ফাঁকা ডান দিক (A → ε), কোনোটিই চলে না। একমাত্র ব্যতিক্রম S0 → ε, কারণ ε ∈ L হলে ফাঁকা string তৈরির আর কোনো উপায় থাকে না: A → BC বা A → a থেকে শেষ পর্যন্ত অন্তত একটি terminal আসেই।

S0 কেন ডান দিকে আসতে পারে না? যদি B → S0C-এর মতো নিয়ম থাকত, তবে derivation-এর মাঝখানে S0 → ε খাটিয়ে B → C-এর মতো একটি “গোপন” unit নিয়ম পাওয়া যেত, আর 2n − 1 ধাপের হিসাব (অংশ ৩) ভেঙে যেত। শর্তটি নিশ্চিত করে, ε-নিয়ম শুধু পুরো string ε হলেই ব্যবহার হয়।

নিয়ম (V = {S0, S, A, B})CNF-এ চলে?কারণ
S → ABহ্যাঁদুটি variable, কোনোটি S0 নয়
A → aহ্যাঁএকটি terminal
S0 → εহ্যাঁstart symbol-এর ε-নিয়ম, S0 ডান দিকে না থাকলে
S → aBনাterminal আর variable মিশ্রিত (TERM ধাপ লাগবে)
S → ABAনাতিনটি variable (BIN ধাপ লাগবে)
A → Bনাunit নিয়ম (UNIT ধাপ লাগবে)
B → εনাstart ছাড়া অন্য variable-এর ε-নিয়ম (DEL ধাপ লাগবে)
A → S0Bনাstart symbol ডান দিকে (START ধাপ লাগবে)

দুই বইয়ের দুই রীতি: এই কোর্স Sipser-এর রীতি মানে, যেখানে S0 → ε চলে। Hopcroft–Motwani–Ullman-এর বইয়ে CNF-এ কোনো ε-নিয়মই থাকে না; সেখানে উপপাদ্যটি বলা হয় L − {ε}-এর জন্য, অর্থাৎ ε-কে আলাদা করে সামলানো হয়। দুটি রীতির পার্থক্য শুধু ε-তে; বাকি সব ফলাফল এক। পরীক্ষায় কোন রীতি মানছেন, এক লাইনে বলে দেওয়া নিরাপদ।

৩ · CNF-এর ফল — binary tree, 2n − 1 ধাপ আর উচ্চতার সীমা

CNF grammar S0 → AX1 ∣ AB ∣ ε, S → AX1 ∣ AB, X1 → SB, A → a, B → b (অংশ ৪-এ এটি anbn থেকে বানানো হবে) থেকে aabb-এর একটি derivation:

S0 ⇒ AX1 ⇒ aX1 ⇒ aSB ⇒ aABB ⇒ aaBB ⇒ aabB ⇒ aabb

৭টি ধাপ, আর 7 = 2 · 4 − 1. মূল grammar S → aSb ∣ ε-এ একই string আসে ৩ ধাপে: S ⇒ aSb ⇒ aaSbb ⇒ aabb. CNF-এ ধাপ বেশি, কিন্তু সংখ্যাটি শুধু string-এর দৈর্ঘ্যের ওপর নির্ভর করে, কোন নিয়ম কোন ক্রমে খাটানো হলো তার ওপর নয়।

CNF-এ aabb-এর parse tree

নীল বৃত্ত variable, সবুজ terminal. কমলা রেখার node-গুলোর দুটি করে সন্তান (A → BC), বাকি variable-গুলোর একটি terminal সন্তান, অর্থাৎ নিয়মটি A → a. ৩টি দুই-সন্তানের node আর ৪টি এক-সন্তানের node মিলে ৭টি নিয়ম-প্রয়োগ।

CNF parse tree of aabb: S0 → A X1, X1 → S B, S → A B S0X1S ABAB abab পাতা বাঁ থেকে ডানে: a a b b
ছবি ২৯.১ — পাতাগুলো ভিন্ন গভীরতায় থাকলেও বাঁ থেকে ডানে পড়লে aabb. সবচেয়ে লম্বা পথ S0 → X1 → S → A → a, অর্থাৎ উচ্চতা ৪.
উপপাদ্য ৩.১ (derivation-এর দৈর্ঘ্য)

G CNF-এ থাকলে আর w ∈ L(G), |w| = n ≥ 1 হলে, S0 থেকে w-এর প্রতিটি derivation-এ ঠিক 2n − 1টি ধাপ: n − 1টি A → BC ধাপ আর nটি A → a ধাপ।

প্রমাণ:

  1. w ≠ ε, আর S0 কোনো ডান দিকে নেই, তাই S0 → ε এই derivation-এ কখনো খাটে না; প্রথম ধাপেই খাটলে ফল হতো ε. — সংজ্ঞা ২.১-এর শর্ত
  2. যেকোনো sentential form-এর জন্য দুটি সংখ্যা ধরুন: v = variable-এর সংখ্যা, t = terminal-এর সংখ্যা। শুরুতে (v, t) = (1, 0), শেষে (0, n). — derivation-এর সংজ্ঞা
  3. A → BC-এর একটি ধাপ একটি variable সরিয়ে দুটি বসায়: v এক বাড়ে, t একই থাকে। A → a-এর একটি ধাপ v এক কমায়, t এক বাড়ায়। অন্য কোনো ধাপ নেই। — CNF-এ মাত্র দুই আকারের নিয়ম
  4. ধরুন derivation-এ bটি A → BC ধাপ আর kটি A → a ধাপ। t-এর হিসাবে k = n. v-এর হিসাবে 1 + b − k = 0, তাই b = n − 1. — দুটি সংখ্যার মোট পরিবর্তন
  5. মোট ধাপ b + k = (n − 1) + n = 2n − 1, কোন ক্রমে নিয়ম খাটানো হলো তাতে কিছু যায় আসে না। ∎ — যোগফল

Parse tree-র ভাষায় একই কথা: গাছে n − 1টি দুই-সন্তানের node, nটি এক-সন্তানের node (প্রতিটি পাতার ঠিক ওপরে), আর nটি পাতা; মোট node 3n − 1 (অনুশীলন ২)। এক-সন্তানের node আর তার পাতাকে একসঙ্গে একটি পাতা ধরলে গাছটি একটি full binary tree, যার nটি পাতা আর n − 1টি ভেতরের node.

উপপাদ্য ৩.২ (উচ্চতার সীমা)

G CNF-এ থাকলে, w-এর কোনো parse tree-র উচ্চতা h হলে (মূল থেকে সবচেয়ে দূরের পাতা পর্যন্ত edge-এর সংখ্যা), |w| ≤ 2h−1.

প্রমাণ (h-এর ওপর induction):

  1. ভিত্তি h = 1: মূলের একটিমাত্র সন্তান, একটি পাতা। মূলে নিয়মটি A → a, তাই |w| = 1 = 20. (|w| ≥ 1 ধরছি; ε-এর গাছ S0 → ε আলাদা।) — উচ্চতা ১-এর গাছ
  2. ধাপ h ≥ 2: মূলে নিয়মটি A → a হতে পারে না (তাহলে h = 1), তাই A → BC. B আর C-এর উপগাছ দুটির উচ্চতা ≤ h − 1. — CNF-এর দুই আকার
  3. Induction hypothesis-এ দুই উপগাছের yield-এর দৈর্ঘ্য ≤ 2h−2 করে। w তাদের concatenation, তাই |w| ≤ 2 · 2h−2 = 2h−1. ∎ — যোগ

উল্টো করে পড়লে: |w| = 9 হলে প্রতিটি parse tree-র উচ্চতা অন্তত ৫, কারণ 23 = 8 < 9. পর্ব ৩৬-এর CFL pumping lemma ঠিক এই যুক্তি ব্যবহার করবে: |V| = k হলে, আর |w| ≥ 2k হলে, গাছের উচ্চতা অন্তত k + 1, তাই সবচেয়ে লম্বা পথে অন্তত k + 1টি variable, আর pigeonhole নীতিতে কোনো একটি variable দুবার আসে। সেই পুনরাবৃত্তিই “pump” করার জায়গা। CNF ছাড়া একটি node-এর সন্তান-সংখ্যা যেকোনো হতে পারে, তখন হিসাবটি অগোছালো হয়।

CYK-এর ধারণাও এই গাছ থেকেই আসে। CNF-এ মূলের নিয়ম A → BC হলে w-কে কোথাও দুই ভাগে কাটা যায়: বাঁ ভাগ B থেকে, ডান ভাগ C থেকে। তাই “কোন কোন variable w-এর টুকরো w[i..j] derive করে?” প্রশ্নের উত্তর ছোট টুকরোর উত্তর থেকে বানানো যায়: দৈর্ঘ্য ১-এর টুকরোর জন্য A → a নিয়ম দেখা, বড় টুকরোর জন্য প্রতিটি কাটার জায়গা আর প্রতিটি A → BC পরখ করা। দৈর্ঘ্য n-এর string-এ টুকরো প্রায় n2/2টি, প্রতিটিতে কাটার জায়গা n-এর কম, তাই মোট সময় O(n3 · |G|). পূর্ণ algorithm আর টেবিল পর্ব ৩১-এ; অংশ ৬-এর lengths function এর একটি ছোট রূপ।

৪ · রূপান্তরের পাঁচ ধাপ — START, DEL, UNIT, TERM, BIN

উপপাদ্য ৪.১ (Chomsky, ১৯৫৯)

প্রতিটি context-free grammar G-এর জন্য একটি CNF grammar G′ আছে, যাতে L(G′) = L(G). আরও, G′ একটি algorithm দিয়ে G থেকে বানানো যায়।

প্রমাণটি একটি গঠন: পাঁচটি ধাপ, প্রতিটি একটি করে “অবৈধ” নিয়মের ধরন দূর করে, আর প্রতিটি ধাপ language রক্ষা করে। গুরুত্বপূর্ণ: কোনো ধাপ আগের ধাপে দূর করা ধরন আবার ফিরিয়ে আনে না।

  1. START: নতুন start symbol S0 আর নিয়ম S0 → S. পুরোনো S ডান দিকে থাকলেও এখন start symbol আর কোনো ডান দিকে নেই। Language বদলায় না, কারণ প্রতিটি derivation শুধু একটি বাড়তি প্রথম ধাপ পায়।
  2. DEL: nullable variable-এর set N বের করা, অর্থাৎ যেসব A থেকে A ⇒∗ ε পাওয়া যায় তাদের সবাই। প্রতিটি নিয়মের ডান দিকের প্রতিটি nullable চিহ্ন রাখা বা বাদ দেওয়ার সব রকম কপি যোগ, তারপর সব ε-নিয়ম মুছে ফেলা; S0 ∈ N হলে শুধু S0 → ε রাখা। ফল: L(G) − {ε} একই, আর ε-এর প্রশ্ন S0 → ε সামলায়।
  3. UNIT: প্রতিটি variable A-এর জন্য unit pair বের করা (A ⇒∗ B শুধু unit নিয়মে), তারপর A-কে প্রতিটি এমন B-এর সব non-unit নিয়ম দেওয়া আর সব A → B মুছে ফেলা।
  4. TERM: দৈর্ঘ্য ≥ 2-এর ডান দিকে প্রতিটি terminal a-এর জায়গায় একটি নতুন variable Ta, আর নিয়ম Ta → a.
  5. BIN: প্রতিটি A → Y1Y2⋯Yk (k ≥ 3)-কে একটি শিকলে ভাঙা: A → Y1X1, X1 → Y2X2, …, Xk−2 → Yk−1Yk, নতুন variable Xi দিয়ে।

ক্রম কেন এমন? DEL নতুন unit নিয়ম তৈরি করতে পারে: S → AB আর B nullable হলে DEL যোগ করে S → A, একটি unit নিয়ম। তাই UNIT আসে DEL-এর পরে। UNIT কোনো ε-নিয়ম তৈরি করে না, কারণ যে নিয়মগুলো কপি হয় সেগুলোর কোনোটি ε নয় (S0 → ε ছাড়া, যা শুধু S0-এর)। TERM আর BIN শুধু দৈর্ঘ্য ≥ 2-এর নিয়ম ছোঁয় আর দৈর্ঘ্য ১ বা ২-এর নিয়ম বানায়, তাই এরা ε বা unit নিয়ম ফেরায় না। DEL আর UNIT-এর সঠিকতার পূর্ণ প্রমাণ পর্ব ২৮-এ; এখানে শেষ দুই ধাপের প্রমাণ দেখি।

সাধারণ ভুল (DEL): nullable চিহ্নের সব মিশ্রণ না বানানো। A → aBaB আর B nullable হলে চারটি কপি লাগে: aBaB, aaB, aBa আর aa. অনেকে শুধু “সব রেখে” আর “সব বাদ দিয়ে” দুটি লেখেন, তখন aaB বা aBa থেকে আসা string হারায়। kটি nullable চিহ্নে 2kটি কপি (ফাঁকা কপি বাদে) গুনে মিলিয়ে নিন।

প্রমাণের রূপরেখা (TERM আর BIN language রক্ষা করে): TERM-এ Ta-এর একটিমাত্র নিয়ম Ta → a, তাই নতুন grammar-এর যেকোনো derivation-এ Ta দেখা দেওয়ামাত্র তাকে a বানিয়ে দিলে পুরোনো grammar-এর একটি derivation পাওয়া যায়, আর উল্টো দিকে পুরোনো প্রতিটি ধাপের পরে Ta → a খাটালেই চলে। BIN-এ A ⇒ Y1X1 ⇒ Y1Y2X2 ⇒ ⋯ ⇒ Y1⋯Yk, তাই পুরোনো প্রতিটি ধাপ নতুন grammar-এ k − 1 ধাপ হয় (⊇)। উল্টো দিকে, Xi-এর নিয়ম শুধু শিকলের পরের অংশ দেয়, আর context-free নিয়ম স্বাধীনভাবে খাটে; তাই যেকোনো derivation-কে এমনভাবে সাজানো যায় যাতে প্রতিটি শিকল পরপর খাটে, আর সেটি পুরোনো একটি ধাপের সমান (⊆)। ∎

নিচের stepper S → aSb ∣ ε-কে পাঁচ ধাপে CNF-এ আনে। প্রতিটি ধাপের নিয়ম-সংখ্যা আর ফলটি পরের Python ব্লকের আউটপুটের সঙ্গে হুবহু মেলে।

1মূল grammar2START: S₀ → S3DEL: ε-নিয়ম4UNIT: A → B5TERM: a → A, b → B6BIN: ASB → A X₁
এই ধাপের grammar
নিয়ম
নিয়ম-সংখ্যা
  1. শুরু। S → aSb-এর ডান দিকে তিনটি চিহ্ন, তার দুটি terminal; আর S → ε একটি ε-নিয়ম, অথচ S নিজের ডান দিকে আছে। দুটিই CNF-এ চলে না।
  2. START. নতুন S0 → S. S আগের মতো aSb-এর ভেতরে থাকতে পারে, কিন্তু S0 কোথাও ডান দিকে নেই। নিয়ম তিনটি।
  3. DEL. S → ε আছে, তাই S nullable; S0 → S, তাই S0-ও nullable. aSb-এর S রাখা বা বাদ দিয়ে aSb আর ab; S0 → S থেকে S0 → S, আর S0 nullable বলে S0 → ε. S → ε মুছে গেল।
  4. UNIT. S0 → S একটি unit নিয়ম। তার জায়গায় S-এর দুটি নিয়ম S0-এ কপি হলো: S0 → aSb ∣ ab ∣ ε. মোট ৫টি নিয়ম।
  5. TERM. লম্বা নিয়মের a আর b-এর জায়গায় A আর B, সঙ্গে A → a, B → b. এখন ASB আর AB-তে শুধু variable. ৭টি নিয়ম।
  6. BIN. ASB-এর দৈর্ঘ্য ৩: A → … রেখে বাকি SB-এর জন্য নতুন X1 → SB. S0 আর S দুটিতেই একই X1. মোট ৮টি নিয়ম, সব CNF আকারে, আর X1 → SB-তে S আছে কিন্তু S0 নেই।

এবার algorithm-টি কোডে। প্রথম ব্লকে DEL আর UNIT (পর্ব ২৮-এর দুটি algorithm, সংক্ষেপে), সুষম বন্ধনীর grammar BAL: S → (S)S ∣ ε-এর ওপর। Grammar একটি dict: প্রতিটি variable-এর নিয়মগুলো tuple, ε মানে ফাঁকা tuple. এই পর্বের চারটি Python ব্লক একই namespace ভাগ করে, তাই পরের ব্লক আগের function ব্যবহার করে।

from itertools import product
def show(G, title):
    print(title)
    for A, R in G.items():
        print("  ", A, "->", " | ".join(" ".join(r) or "ε" for r in R))
def DEL(G, S):                  # ε-rules out; S -> ε stays if S is nullable
    N, ch = set(), True
    while ch:
        ch = False
        for A, R in G.items():
            if A not in N and any(all(x in N for x in r) for r in R):
                N.add(A); ch = True
    opt = lambda x: ((x,), ()) if x in N else ((x,),)  # keep or drop x
    H = {A: list(dict.fromkeys(t for r in R for c in product(*map(opt, r))
                               if (t := sum(c, ())))) for A, R in G.items()}
    if S in N: H[S].append(())
    return H
def UNIT(G):                    # A -> B is replaced by B's non-unit rules
    unit = lambda r: len(r) == 1 and r[0] in G
    H = {}
    for A in G:
        U, todo = [A], [A]      # U = every B with A =>* B by unit rules
        while todo:
            for r in G[todo.pop()]:
                if unit(r) and r[0] not in U: U.append(r[0]); todo.append(r[0])
        rules = dict.fromkeys(r for B in U for r in G[B] if not unit(r))
        H[A] = sorted(rules, key=lambda r: not r)      # ε printed last
    return H
bal = {"S0": [("S",)], "S": [("(", "S", ")", "S"), ()]}
show(bal, "START  (BAL with a new start S0)")
show(g := DEL(bal, "S0"), "DEL")
show(UNIT(g), "UNIT")

আসল আউটপুট (ব্রাউজারের Python):

START  (BAL with a new start S0)
   S0 -> S
   S -> ( S ) S | ε
DEL
   S0 -> S | ε
   S -> ( S ) S | ( S ) | ( ) S | ( )
UNIT
   S0 -> ( S ) S | ( S ) | ( ) S | ( ) | ε
   S -> ( S ) S | ( S ) | ( ) S | ( )

DEL-এ (S)S-এর দুটি S nullable, তাই 22 = 4টি কপি: দুটিই রাখা, শুধু প্রথমটি, শুধু দ্বিতীয়টি, কোনোটিই না। এখানে কোনো কপি ফাঁকা হয় না, কারণ বন্ধনী দুটি terminal. opt প্রতিটি চিহ্নের জন্য “রাখা” বা (nullable হলে) “বাদ” দুটি পছন্দ দেয়, আর product সব মিশ্রণ বানায়। UNIT-এ S0 → S-এর জায়গায় S-এর চারটি নিয়ম এসেছে, ε শেষে। এখনো তিনটি সমস্যা বাকি: বন্ধনী terminal আর variable মিশে আছে, আর তিনটি নিয়মের দৈর্ঘ্য ৩ বা ৪. সেগুলো পরের দুই ধাপের কাজ।

৫ · TERM আর BIN — terminal আলাদা করা, লম্বা নিয়ম ভাঙা

TERM-এর ধারণাটি সরল: লম্বা নিয়মে একটি terminal সরাসরি থাকতে পারে না, তাই তাকে একটি “প্রতিনিধি” variable দিয়ে বদলানো হয়। BAL-এ L → ( আর R → ). দৈর্ঘ্য ১-এর নিয়ম, যেমন F → id, বদলায় না, কারণ A → a আকারটি নিজেই বৈধ। একই terminal-এর জন্য একটিই প্রতিনিধি, সব নিয়মে।

নামের সংঘর্ষ: নতুন variable-এর নাম অবশ্যই নতুন হতে হবে। Grammar-এ আগে থেকেই A নামের variable থাকলে a-এর প্রতিনিধিকে A বলা যাবে না; তাহলে A-এর পুরোনো নিয়ম আর A → a মিশে গিয়ে language বদলে যায়, ঠিক পর্ব ২৫-এ নাম না বদলানো union-এর মতো। নিরাপদ রীতি: Ta, Tb বা X1, X2-এর মতো এমন নাম, যা মূল grammar-এ নেই। এই পর্বের উদাহরণগুলোতে A, B, L, R, P, M নাম চলেছে শুধু কারণ মূল grammar-এ এগুলো ছিল না।

BIN-এর ধারণা: ডান দিকের প্রথম চিহ্ন রেখে বাকি অংশের জন্য একটি নতুন variable, তারপর সেই variable-এর ওপর একই কাজ, যতক্ষণ না দুটি চিহ্ন বাকি থাকে। দৈর্ঘ্য k-এর একটি নিয়ম থেকে আসে k − 1টি নিয়ম আর k − 2টি নতুন variable. একটি ছোট কৌশল আকার কমায়: একই “বাকি অংশ” আগে দেখা হলে আগের variable-টিই আবার ব্যবহার করা।

1S → L S R S2S → L S R3S → L R S4S → L R
এই ধাপের হিসাব
নতুন নিয়ম
নতুন variable
  1. শুরু। TERM-এর পরে S-এর চারটি নিয়ম: LSRS, LSR, LRS আর LR (S0-এরও একই চারটি, সঙ্গে ε)। LR-এর দৈর্ঘ্য ২, তাই সেটি ইতিমধ্যে CNF. বাকি তিনটি ভাঙতে হবে।
  2. প্রথম কাটা। LSRS-এর প্রথম চিহ্ন L রেখে বাকি SRS-এর জন্য নতুন X1: S → LX1, X1 → SRS. X1-এর নিয়ম এখনো দৈর্ঘ্য ৩.
  3. দ্বিতীয় কাটা। X1 → SRS-এ S রেখে RS-এর জন্য X2: X1 → SX2, X2 → RS. দৈর্ঘ্য ৪ থেকে ৩টি নিয়ম, ২টি নতুন variable, ঠিক k − 1 আর k − 2.
  4. LSR. লেজ SR আগে দেখা হয়নি, তাই X3 → SR আর S → LX3.
  5. LRS. লেজ RS-এর জন্য X2 আগেই আছে, তাই শুধু S → LX2, নতুন variable নেই। S0-এর চারটি নিয়মও একই X1, X2, X3 ব্যবহার করে।
  6. ফল। S → LX1 ∣ LX3 ∣ LX2 ∣ LR, S0 → একই চারটি ∣ ε, X1 → SX2, X2 → RS, X3 → SR, L → (, R → ). মোট ৫ + ৪ + ৩ + ২ = ১৪টি নিয়ম। ভাগাভাগি না করলে S আর S0-এ আলাদা করে ৪টি করে, মোট ৮টি নতুন variable লাগত।

দ্বিতীয় ব্লকে TERM, BIN আর পুরো pipeline. প্রথমে anbn-এর প্রতিটি ধাপ ছাপা হয় (ওপরের প্রথম stepper-এর সঙ্গে মেলান), তারপর BAL-এর শুধু শেষ ফল। names বলে দেয় কোন terminal-এর প্রতিনিধি কোন নাম পাবে।

def TERM(G, names):             # a terminal inside a long rule -> variable
    H = {A: [r if len(r) == 1 else tuple(names.get(x, x) for x in r)
             for r in R] for A, R in G.items()}
    used = dict.fromkeys(x for R in G.values() for r in R
                         if len(r) > 1 for x in r if x in names)
    return {**H, **{names[t]: [(t,)] for t in used}}
def BIN(G):                     # A -> Y1 Y2 ... Yk becomes a chain of pairs
    H, memo = {A: [] for A in G}, {}
    def name(r):                # one variable per tail, shared by all rules
        if len(r) == 1: return r[0]
        if r not in memo:
            memo[r] = f"X{len(memo) + 1}"
            H[memo[r]] = [(r[0], name(r[1:]))]
        return memo[r]
    for A, R in G.items():
        H[A] += [r if len(r) <= 2 else (r[0], name(r[1:])) for r in R]
    return H
def CNF(G, S, names, verbose=False):
    G = {"S0": [(S,)], **G}
    for title, f in [("START", lambda g: g), ("DEL", lambda g: DEL(g, "S0")),
                     ("UNIT", UNIT), ("TERM", lambda g: TERM(g, names)),
                     ("BIN", BIN)]:
        G = f(G)
        if verbose: show(G, title)
    return G
anbn = {"S": [("a", "S", "b"), ()]}
CNF(anbn, "S", {"a": "A", "b": "B"}, verbose=True)
show(CNF({"S": [("(", "S", ")", "S"), ()]}, "S", {"(": "L", ")": "R"}),
     "BAL in CNF")

আসল আউটপুট (ব্রাউজারের Python):

START
   S0 -> S
   S -> a S b | ε
DEL
   S0 -> S | ε
   S -> a S b | a b
UNIT
   S0 -> a S b | a b | ε
   S -> a S b | a b
TERM
   S0 -> A S B | A B | ε
   S -> A S B | A B
   A -> a
   B -> b
BIN
   S0 -> A X1 | A B | ε
   S -> A X1 | A B
   A -> a
   B -> b
   X1 -> S B
BAL in CNF
   S0 -> L X1 | L X3 | L X2 | L R | ε
   S -> L X1 | L X3 | L X2 | L R
   L -> (
   R -> )
   X2 -> R S
   X1 -> S X2
   X3 -> S R

anbn-এর পাঁচটি ধাপ প্রথম stepper-এর সঙ্গে হুবহু এক: শেষে ৮টি নিয়ম। BAL-এর ফল দ্বিতীয় stepper-এর ১৪টি নিয়ম; X2 তালিকায় X1-এর আগে ছাপা হয়েছে, কারণ name recursion-এ ভেতরের লেজ RS-এর নিয়ম আগে লেখে। memo-ই ভাগাভাগির কৌশল: একই লেজ দ্বিতীয়বার এলে নতুন variable তৈরি হয় না। TERM-এ len(r) == 1 শর্তটি A → a আর F → id-এর মতো বৈধ নিয়মকে ছুঁতে দেয় না।

৬ · পূর্ণ উদাহরণ — গাণিতিক expression-এর grammar

এবার একটি বড় উদাহরণ, যা পরীক্ষায় প্রায়ই আসে: স্তরভাগ করা expression grammar

E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id

এখানে কোনো ε-নিয়ম নেই, তাই DEL কিছু বদলায় না। কিন্তু দুটি unit নিয়ম (E → T, T → F) আর তিনটি লম্বা মিশ্র নিয়ম আছে। START-এর পর unit pair: S0-এর জন্য E, T, F; E-এর জন্য T, F; T-এর জন্য F. UNIT-এর পর ১৩টি নিয়ম:

S0 → E+T ∣ T∗F ∣ (E) ∣ id
E  → E+T ∣ T∗F ∣ (E) ∣ id
T  → T∗F ∣ (E) ∣ id
F  → (E) ∣ id
1UNIT-এর পরের grammar2+ → P3∗ → M4( → L,  ) → R5id একা: বদলায় না6BIN: তিনটি লেজ
এই ধাপের হিসাব
বদল
কোথায়
নিয়ম-সংখ্যা
  1. শুরু। UNIT-এর পর ১৩টি নিয়ম; S0 আর E-এর নিয়ম হুবহু এক। লম্বা নিয়ম তিন রকম: E+T, T∗F আর (E), প্রতিটির মাঝে বা দুই পাশে terminal.
  2. যোগ। + চিহ্নের প্রতিনিধি P → +. E+T দুই জায়গায় আছে (S0 আর E), দুটিই হলো EPT. নিয়ম ১৪টি।
  3. গুণ। M → ∗, আর T∗F তিন জায়গায় (S0, E, T) হলো TMF. নিয়ম ১৫টি।
  4. বন্ধনী। L → ( আর R → ). (E) চার জায়গায় হলো LER. নিয়ম ১৭টি।
  5. id. চারটি নিয়ম X → id-এর ডান দিকে একটিমাত্র terminal, যা CNF-এর A → a আকার। কোনো বদল নেই, নিয়ম এখনো ১৭টি।
  6. BIN. তিনটি দৈর্ঘ্য-৩ লেজ: X1 → PT, X2 → MF, X3 → ER. EPT → EX1, TMF → TX2, LER → LX3. মোট ২০টি নিয়ম, সব A → BC বা A → a.

শেষ ফল: S0 → EX1 ∣ TX2 ∣ LX3 ∣ id, E → একই চারটি, T → TX2 ∣ LX3 ∣ id, F → LX3 ∣ id, X1 → PT, X2 → MF, X3 → ER, P → +, M → ∗, L → (, R → ). লক্ষ করুন, এখানে ε নেই, তাই Hopcroft–Motwani–Ullman-এর রীতিতে S0 লাগত না; E-কেই start রাখলে ১৬টি নিয়মে কাজ হতো। Sipser-এর রীতিতে start symbol ডান দিকে থাকতে পারে না, আর E আছে X3 → ER-এ, তাই START সবসময় করা হয়।

রূপান্তর সঠিক কি না, শুধু চোখে দেখে বলা কঠিন। তৃতীয় ব্লক তিনটি grammar রূপান্তর করে দুটি জিনিস যাচাই করে: মূল আর CNF grammar দৈর্ঘ্য n পর্যন্ত হুবহু একই string দেয় কি না (fixpoint iteration-এ, পর্ব ২৫-এর মতো), আর CNF-এ প্রতিটি string-এর প্রতিটি derivation-এর দৈর্ঘ্য 2n − 1 কি না। দ্বিতীয়টির জন্য lengths প্রতিটি variable আর w-এর প্রতিটি টুকরোর জন্য সম্ভাব্য সব ধাপ-সংখ্যার set হিসাব করে, string-কে প্রতিটি জায়গায় দুই ভাগে কেটে; এটি পর্ব ৩১-এর CYK-এর ঠিক পূর্বসূরি। id-কে এখানে একটি অক্ষর i দিয়ে লেখা হয়েছে।

from functools import lru_cache
def lang(G, S, n):              # every string of length <= n (fixpoint)
    L, ch = {A: set() for A in G}, True
    while ch:
        ch = False
        for A, R in G.items():
            for r in R:
                for c in product(*[L[X] if X in G else {X} for X in r]):
                    if len(w := "".join(c)) <= n and w not in L[A]:
                        L[A].add(w); ch = True
    return L[S]
def lengths(G, S, w):           # all possible derivation lengths of w
    @lru_cache(None)
    def f(A, i, j):             # A =>* w[i:j] in how many steps?
        out = set()
        for r in G[A]:
            if len(r) == 1 and j - i == 1 and r[0] == w[i]: out.add(1)
            if len(r) == 2:
                for k in range(i + 1, j):
                    out |= {1 + x + y for x in f(r[0], i, k) for y in f(r[1], k, j)}
        return frozenset(out)
    return set(f(S, 0, len(w)))
expr = {"E": [("E", "+", "T"), ("T",)], "T": [("T", "*", "F"), ("F",)],
        "F": [("(", "E", ")"), ("i",)]}               # i stands for id
names = {"a": "A", "b": "B", "(": "L", ")": "R", "+": "P", "*": "M"}
for title, G, S, n in [("anbn", anbn, "S", 10), ("expr", expr, "E", 9),
                       ("BAL", {"S": [("(", "S", ")", "S"), ()]}, "S", 10)]:
    H = CNF(G, S, names)
    old, new = lang(G, S, n), lang(H, "S0", n)
    ok = all(lengths(H, "S0", w) == {2 * len(w) - 1} for w in new if w)
    print(f"{title:4}: {sum(map(len, H.values())):2} CNF rules, same language "
          f"up to {n}: {old == new} ({len(new)} strings), all 2n-1: {ok}")
ai = {"S0": [("A", "X1"), ()], "S": [("A", "X1")], "X1": [("S", "B")],
      "A": [("a",)], "B": [("b",)]}       # an assistant's "CNF" for anbn
print("AI answer makes:", sorted(lang(ai, "S0", 10)))

আসল আউটপুট (ব্রাউজারের Python):

anbn:  8 CNF rules, same language up to 10: True (6 strings), all 2n-1: True
expr: 20 CNF rules, same language up to 9: True (257 strings), all 2n-1: True
BAL : 14 CNF rules, same language up to 10: True (65 strings), all 2n-1: True
AI answer makes: ['']

তিনটি রূপান্তরই দৈর্ঘ্য ৯ বা ১০ পর্যন্ত মূল language রক্ষা করেছে: anbn-এ ৬টি string, expression-এ ২৫৭টি, BAL-এ ৬৫টি (Catalan সংখ্যাগুলো 1 + 1 + 2 + 5 + 14 + 42 যোগ করে)। প্রতিটি অ-ফাঁকা string-এর সম্ভাব্য derivation-দৈর্ঘ্যের set ঠিক {2n − 1}, অর্থাৎ উপপাদ্য ৩.১ এখানে গণনাতেও মিলেছে; set-এ একটিমাত্র সংখ্যা মানে কোনো derivation-ক্রমেই ধাপ-সংখ্যা বদলায় না। শেষ লাইনের “AI answer” দেখতে খাঁটি CNF, কিন্তু S → AB বাদ পড়েছে; ফলে S থেকে কোনো terminal string আসে না, আর পুরো language শুধু {ε}, যেখানে আসার কথা ছিল ε, ab, aabb, … সহ ৬টি string. অংশ ৮-এ এই ধরনের ভুল নিয়ে আবার আসব।

সত্যিকারের run: nltk-এর CNF রূপান্তর

Python-এর পরিচিত ভাষা-প্রক্রিয়াকরণ library nltk (Apache-2.0 লাইসেন্স)-এ CFG.chomsky_normal_form() নামে একটি method আছে। Scratch-এর একটি uv project-এ (Python 3.12, nltk 3.10.4, কোনো corpus download ছাড়া) একই দুটি grammar দিয়ে এটি চালানো হয়েছে। এটি একটি সত্যিকারের run; আউটপুট ছোট করা হয়নি, শুধু path বাদ।

~/bazarghar-toc$ uv run python nltk_cnf.py
nltk 3.10.4
anbn: ValueError: Grammar has Empty rules. Cannot deal with them at the moment
expr: AttributeError: 'str' object has no attribute 'symbol'
is CNF: True | start: S0_SIGMA | rules: 20
   E -> 'i'
   E -> E E@$@E
   E -> L F@$@L
   E -> T T@$@T
   E@$@E -> P T
   F -> 'i'
   F -> L F@$@L
   F@$@L -> E R
   L -> '('
   M -> '*'
   P -> '+'
   R -> ')'
   S0_SIGMA -> 'i'
   S0_SIGMA -> E E@$@E
   S0_SIGMA -> L F@$@L
   S0_SIGMA -> T T@$@T
   T -> 'i'
   T -> L F@$@L
   T -> T T@$@T
   T@$@T -> M F
same language up to length 9: True (257 strings)

তিনটি শিক্ষা। প্রথম, nltk-এর এই সংস্করণ ε-নিয়মসহ grammar নেয় না (anbn), অর্থাৎ DEL ধাপটি এতে নেই। দ্বিতীয়, (E)-এর মতো নিয়মে, যেখানে শুরুতেই terminal, এটি ভেঙে পড়ে: এর ক্রম START, BIN, TERM, UNIT, আর BIN ধরে নেয় লম্বা নিয়মে শুধু variable. তাই দ্বিতীয় চেষ্টায় grammar-টি প্রতিনিধি variable P, M, L, R আগে থেকে বসিয়ে দেওয়া হয়েছে (E → E P T ইত্যাদি)। তৃতীয়, তখন ফল আমাদের হাতে-করা রূপান্তরের সঙ্গে গঠনে হুবহু এক: ২০টি নিয়ম, নতুন start S0_SIGMA, আর E@$@E, T@$@T, F@$@L আমাদের X1, X2, X3. আমাদের lang দিয়ে দৈর্ঘ্য ৯ পর্যন্ত language-ও মিলেছে। বাস্তবের tool-এরও সীমা থাকে; রূপান্তরের পর language মিলিয়ে দেখা তাই অভ্যাস হওয়া উচিত।

৭ · Grammar কত বড় হয় — ধাপের ক্রমের দাম

রূপান্তরের পর grammar-এর আকার গুরুত্বপূর্ণ, কারণ CYK-এর সময় O(n3 · |G|), যেখানে |G| মোটামুটি নিয়মের সংখ্যা বা সব ডান দিকের মোট দৈর্ঘ্য (grammar-এর আকার)। কোন ধাপ আকার বাড়ায়?

  • DEL: একটি নিয়মের ডান দিকে kটি nullable চিহ্ন থাকলে 2k পর্যন্ত কপি। লম্বা নিয়মে এটি exponential.
  • UNIT: প্রতিটি variable তার সব unit-pair-এর নিয়ম পায়, তাই আকার মোটামুটি বর্গ হতে পারে।
  • TERM আর BIN: আকার শুধু একটি ধ্রুবক গুণে বাড়ে।

সমাধান: DEL-এর আগে BIN করা। তখন প্রতিটি নিয়মের ডান দিকে বড়জোর দুটি চিহ্ন, তাই DEL প্রতিটি নিয়মের বড়জোর তিনটি কপি বানায়। নিচের ব্লক একটি পরিবার নেয়: S → A1A2⋯Ak, প্রতিটি Ai → ai ∣ ε (ai একটি করে আলাদা অক্ষর)। দুই ক্রমে রূপান্তর করে নিয়ম-সংখ্যা গোনে, আর তিনটি language মেলায়। এটি আগের ব্লকগুলোর DEL, UNIT, BIN আর lang ব্যবহার করে।

size = lambda G: sum(len(R) for R in G.values())
print(" k   |G|   DEL first   BIN first")
for k in [2, 4, 6, 8, 10, 12]:
    A = [f"A{i}" for i in range(1, k + 1)]           # S -> A1 A2 ... Ak
    G = {"S0": [("S",)], "S": [tuple(A)]}
    G.update({X: [(chr(96 + i),), ()] for i, X in enumerate(A, 1)})
    one = BIN(UNIT(DEL(G, "S0")))                  # Ai -> ai | ε
    two = UNIT(DEL(BIN(G), "S0"))
    same = lang(one, "S0", k) == lang(two, "S0", k) == lang(G, "S0", k)
    print(f"{k:2} {size(G):5} {size(one):11} {size(two):11}   same: {same}")

আসল আউটপুট (ব্রাউজারের Python):

 k   |G|   DEL first   BIN first
 2     6           9           9   same: True
 4    10          39          27   same: True
 6    14         159          53   same: True
 8    18         639          87   same: True
10    22        2559         129   same: True
12    26       10239         179   same: True

মূল grammar-এর আকার 2k + 2, রৈখিক। আগে DEL করলে S-এর একটি নিয়ম থেকে 2k − 1টি অ-ফাঁকা কপি হয়, তাই ফল প্রতি দুই ধাপে প্রায় চার গুণ: k = 12-এ ১০,২৩৯টি নিয়ম। আগে BIN করলে বৃদ্ধি বর্গ হারে: পার্থক্যগুলো 18, 26, 34, 42, 50, প্রতিবার ৮ করে বাড়ে, যা একটি দ্বিঘাত সূত্রের চিহ্ন। দুই ক্রমেই language একই, আর দুটি ফলই CNF (TERM এখানে লাগেনি, কারণ প্রতিটি terminal একা)। বাড়তি নিয়মগুলো আসে UNIT থেকে: BIN-এর পর DEL করলে X → Ai-এর মতো অনেক unit নিয়ম তৈরি হয়।

তাত্ত্বিক ফলাফলটি এরকম: Lange আর Leiß ২০০৯ সালের একটি প্রবন্ধে দেখিয়েছেন বলে পরিচিত যে ক্রম START, TERM, BIN, DEL, UNIT হলে CNF grammar-এর আকার মূল |G|-এর বড়জোর বর্গের ক্রমের (O(|G|2)), আর পাঠ্যবইয়ের DEL-আগে ক্রমে সবচেয়ে খারাপ ক্ষেত্রে exponential. পরীক্ষার ছোট grammar-এ দুই ক্রমই চলে, কিন্তু program-এ বড় grammar রূপান্তর করলে ক্রমটি মনে রাখবেন।

আরেকটি ব্যবহারিক কথা: CNF-এর সংজ্ঞা useless symbol নিষেধ করে না, কিন্তু রূপান্তরের পর এগুলো থেকে যেতে পারে (যেমন UNIT-এর পর পুরোনো S আর কোথাও থেকে পৌঁছানো যায় না)। শেষে পর্ব ২৮-এর useless-symbol অপসারণ চালালে grammar ছোট আর পরিষ্কার হয়, আর CNF আকার নষ্ট হয় না, কারণ শুধু নিয়ম মোছা হয়।

আরও গভীরে: CNF একমাত্র normal form নয়। Sheila Greibach ১৯৬৫ সালে দেখান, প্রতিটি ε-মুক্ত CFL-এর এমন grammar আছে যেখানে প্রতিটি নিয়ম A → aα (α ∈ V∗), অর্থাৎ প্রতি ধাপে একটি terminal (Greibach normal form, পর্ব ৩০)। আবার Lange–Leiß একটি শিথিল “2NF” প্রস্তাব করেন বলে পরিচিত, যেখানে ডান দিকে বড়জোর দুটি চিহ্ন থাকলেই চলে, আর CYK-কে সামান্য বদলে সরাসরি চালানো যায়; এতে রূপান্তরের পর আকার রৈখিক থাকে। প্রশ্নটি তাই “কোন normal form” নয়, “কোন algorithm-এর জন্য কতটা কঠোর আকার দরকার”।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • CNF-এর সংজ্ঞা দিন। প্রতিটি নিয়ম A → BC বা A → a; শুধু S0 → ε চলে, আর S0 ডান দিকে নেই।
  • S → aSb ∣ ε-কে CNF-এ রূপান্তর করুন। S0 → AX1 ∣ AB ∣ ε, S → AX1 ∣ AB, X1 → SB, A → a, B → b.
  • CNF-এ দৈর্ঘ্য n-এর string-এর derivation-এ কয়টি ধাপ? ঠিক 2n − 1: n − 1টি A → BC আর nটি A → a.
  • রূপান্তরে UNIT কেন DEL-এর পরে? DEL নতুন unit নিয়ম বানাতে পারে (S → AB-এ B nullable হলে S → A আসে)।
  • A → BCDE ভাঙলে কয়টি নিয়ম? ৩টি নিয়ম, ২টি নতুন variable: A → BX1, X1 → CX2, X2 → DE.

৮ · AI-এর যুগে CNF রূপান্তর

AI assistant-কে “এই grammar-টি CNF-এ রূপান্তর করো” বললে সে সাধারণত গোছানো ধাপসহ একটি উত্তর দেয়। ভুলগুলো প্রায়ই সূক্ষ্ম, কারণ ফল দেখতে CNF-এর মতোই। অংশ ৬-এর শেষ লাইনের উদাহরণটি এমনই: প্রতিটি নিয়ম বৈধ আকারে, অথচ DEL-এর সময় S → ab-এর কপিটি হারিয়ে গেছে, তাই language শুধু {ε}. উল্টো ভুলও হয়: language ঠিক, কিন্তু আকার ভুল, যেমন S → ε রেখে দেওয়া অথচ S ডান দিকে আছে।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
DEL-এ সব কপি না বানানো (যেমন (S)S থেকে চারটির জায়গায় দুটি)kটি nullable চিহ্নে 2kটি কপি গুনুন; দৈর্ঘ্য ৮–১০ পর্যন্ত language মেলান
ε ভুলে যাওয়া: ε ∈ L, কিন্তু S0 → ε নেই; বা S → ε রাখা, অথচ S ডান দিকেε আছে কি না আলাদা করে দেখুন; start symbol ডান দিকে আছে কি না খুঁজুন
UNIT আগে, DEL পরে করে নতুন unit নিয়ম রেখে দেওয়াশেষ grammar-এর প্রতিটি নিয়মের আকার মিলিয়ে দেখুন (A → B আছে কি না)
দৈর্ঘ্য-৩ নিয়মে terminal রেখে দেওয়া (A → aB বা A → BCa)দুই-চিহ্নের প্রতিটি ডান দিকে শুধু variable আছে কি না দেখুন
“CNF-এ derivation n ধাপে” বা “উচ্চতা ঠিক log n” জাতীয় ভুল দাবিউপপাদ্য ৩.১ আর ৩.২ মনে রাখুন: ঠিক 2n − 1 ধাপ, আর n ≤ 2h−1 একটি সীমা, সমতা নয়
বানানো রেফারেন্স বা ভুল সাল (যেমন CNF-এর উৎস)Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে নিশ্চিত হোন

AI-কে ভালোভাবে কাজে লাগানোর উপায়: প্রতিটি ধাপের পর পূর্ণ grammar, প্রতিটি ধাপের কারণ, আর একটি যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।

আমি গণনার তত্ত্ব শিখছি। এই grammar-টি Chomsky normal form-এ রূপান্তর করো: S → ASA ∣ aB, A → B ∣ S, B → b ∣ ε (Sipser-এর রীতি, S₀ → ε চলবে)। ১. START, DEL, UNIT, TERM, BIN প্রতিটি ধাপের পর পুরো grammar লেখো। ২. DEL-এ nullable set কী, আর প্রতিটি নিয়মের কোন কপি কেন যোগ হলো তা বলো। ৩. শেষ grammar-এর প্রতিটি নিয়ম A → BC বা A → a কি না, আর start symbol কোনো ডান দিকে আছে কি না, একটি তালিকায় দেখাও। ৪. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য 6 পর্যন্ত মূল আর নতুন grammar-এর সব string বানিয়ে মেলায়। ৫. কোনো দাবি নিয়ে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

(এই grammar-টি Sipser-এর বইয়ের পরিচিত উদাহরণের মতো; এতে S নিজের ডান দিকে আছে, A আর B দুটিই nullable, আর A → S, A → B unit নিয়ম, তাই পাঁচটি ধাপই কাজে লাগে। AI-এর উত্তর পেলে এই পর্বের Python ব্লকে CNF দিয়ে নিজেও রূপান্তর করুন (names-এ a-এর প্রতিনিধির জন্য এমন নাম দিন যা grammar-এ নেই, যেমন {"a": "U"}), আর lang দিয়ে তিনটি grammar মিলিয়ে দেখুন।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

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

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Chomsky normal form কোথা থেকে এল, আর একজন ভাষাবিজ্ঞানীর কাছে এমন একটি “যান্ত্রিক” আকার কেন দরকার ছিল?

Noam Chomsky ১৯৫৬ সালের প্রবন্ধে grammar-এর তিনটি মডেলের তুলনা করেন, আর ১৯৫৯ সালে Information and Control পত্রিকায় “On certain formal properties of grammars” প্রবন্ধে grammar-এর শ্রেণিগুলোর গাণিতিক ধর্ম নিয়ে বিস্তারিত কাজ করেন। এই দ্বিতীয় প্রবন্ধেই সাধারণত normal form-এর ফলটির উৎস ধরা হয়: প্রতিটি context-free grammar-কে এমন একটি grammar-এ বদলানো যায়, যার নিয়ম শুধু A → BC বা A → a. পাঠ্যবইয়ে আজ যে পাঁচ ধাপের algorithm দেখেন, তার রূপ পরে অনেক লেখকের হাতে গুছিয়েছে।

একজন ভাষাবিজ্ঞানীর কাছে এর দরকার ছিল শ্রেণিগুলো তুলনা করার জন্য। Chomsky জানতে চাইছিলেন, কোন ধরনের grammar কোন ধরনের ভাষা তৈরি করতে পারে, আর এক শ্রেণি অন্যটির চেয়ে কঠোরভাবে বড় কি না। এই প্রশ্নে প্রমাণ লিখতে হলে grammar-এর আকার যত সরল, তত ভালো: প্রতিটি নিয়ম দুই ধরনের হলে induction-এ মাত্র দুটি ক্ষেত্র দেখতে হয়। একই কারণে গণিতবিদেরা বহুপদীকে মানক রূপে, বা ম্যাট্রিক্সকে row echelon রূপে আনেন: বস্তু একই থাকে, কিন্তু আকার বাঁধা থাকলে তার ধর্ম পড়া সহজ হয়।

মজার ব্যাপার হলো, যে গঠন ভাষাবিজ্ঞানের তাত্ত্বিক প্রশ্নের জন্য এসেছিল, সেটিই কয়েক বছরের মধ্যে কম্পিউটারে parsing-এর algorithm-এর ভিত্তি হয়ে ওঠে। ১৯৬০-এর দশকে Cocke, Younger আর Kasami আলাদাভাবে CNF grammar-এর ওপর dynamic programming-ভিত্তিক membership algorithm দেন বলে পরিচিত (পর্ব ৩১), আর Bar-Hillel, Perles ও Shamir-এর ১৯৬১ সালের কাজের ধারা থেকে CFL-এর pumping lemma আসে, যার আধুনিক প্রমাণ CNF-এর binary tree ব্যবহার করে।

মূল উপলব্ধি: Normal form হলো প্রমাণ আর algorithm-এর জন্য একটি চুক্তি: আকার বেঁধে দিলে বিশ্লেষণে ক্ষেত্র কমে। CNF ভাষাবিজ্ঞানের প্রশ্ন থেকে এসে কম্পিউটার বিজ্ঞানের মানক হাতিয়ার হয়েছে।

প্র ০২বাস্তবের parser কি grammar-কে CNF-এ রূপান্তর করে চলে? না করলে CNF-এর ব্যবহারিক মূল্য কোথায়?

Programming language-এর প্রচলিত parser সাধারণত করে না। মডিউল ৭-এর LL আর LR parser মূল grammar-এর ওপরই কাজ করে, কারণ তাদের সময় linear আর grammar-এর গঠন থেকেই syntax tree আসে। CNF-এ রূপান্তর করলে গাছের আকার বদলে যায়: E → E+T একটি node ছিল, এখন E → EX1 আর X1 → PT দুটি node, আর একটি নতুন P. Compiler-এর পরের ধাপগুলো মূল গাছটি চায়, তাই CNF-এর গাছকে আবার “উল্টো রূপান্তর” করতে হতো। বাস্তবের অনেক grammar সাধারণ parser-এর জন্য যথেষ্ট নিয়মিত, তাই এই ঝামেলা কেউ নেয় না।

তবে কয়েকটি জায়গায় CNF বা তার কাছাকাছি রূপ সরাসরি ব্যবহার হয়। প্রাকৃতিক ভাষা প্রক্রিয়াকরণে probabilistic context-free grammar-এর parser দীর্ঘদিন ধরে CKY (CYK-এর আরেক নাম) algorithm চালিয়েছে বলে পরিচিত; সেখানে treebank থেকে শেখা grammar-কে binary করা হয়, আর parse শেষে গাছকে আবার মূল আকারে ফেরানো হয়। প্রাকৃতিক ভাষার grammar প্রায়ই ambiguous আর বিশাল, তাই সব সম্ভাব্য গাছ একসঙ্গে রাখার মতো dynamic programming সেখানে স্বাভাবিক। ওপরের nltk run-ও এই ঐতিহ্যের অংশ।

তত্ত্বে CNF-এর মূল্য সবচেয়ে বেশি। “প্রতিটি CFL-এর membership polynomial সময়ে decidable” দাবিটির সবচেয়ে সরল প্রমাণ: CNF-এ রূপান্তর, তারপর CYK. Pumping lemma, emptiness আর finiteness-এর algorithm, closure-এর কিছু প্রমাণ, সবই CNF ধরে নিয়ে লেখা সহজ। সাধারণ grammar-এর জন্য বাস্তবে Earley বা GLR-এর মতো algorithm আছে, যা রূপান্তর ছাড়াই যেকোনো CFG parse করে (পর্ব ৪১)।

মূল উপলব্ধি: CNF মূলত একটি তাত্ত্বিক আর algorithmic হাতিয়ার, programming language parser-এর দৈনন্দিন রূপ নয়। যেখানে grammar ambiguous আর সব গাছ দরকার, সেখানে CNF আর CYK বাস্তবেও কাজে লাগে।

প্র ০৩ধাপের ক্রম বদলালে grammar এত বড় হয় কেন? পাঠ্যবই কেন তবু DEL-আগের ক্রম শেখায়?

কারণটি DEL-এর গঠনে। একটি নিয়মের ডান দিকে kটি nullable চিহ্ন থাকলে প্রতিটির জন্য “রাখা” বা “বাদ” দুটি পছন্দ, তাই 2kটি কপি। অংশ ৭-এর পরিবারে S → A1⋯Ak থেকে ঠিক এটাই হয়েছে। BIN আগে করলে প্রতিটি নিয়মের ডান দিকে বড়জোর দুটি চিহ্ন, তাই কপি বড়জোর তিনটি, আর দীর্ঘ নিয়মের exponential বিস্ফোরণ আর হয় না। পরে UNIT কিছুটা বাড়ায়, কিন্তু সেটি বর্গের সীমায় থাকে।

Martin Lange আর Hans Leiß ২০০৯ সালে “To CNF or not to CNF?” নামের একটি প্রবন্ধে এই বিষয়টি গুছিয়ে দেখান বলে পরিচিত। তাঁরা লক্ষ করেন, বিভিন্ন পাঠ্যবই বিভিন্ন ক্রম দেয়, আর কিছু ক্রমে সবচেয়ে খারাপ ক্ষেত্রে আকার exponential হয়। তাঁদের প্রস্তাবিত ক্রমে (START, TERM, BIN, DEL, UNIT) আকার মূল grammar-এর বর্গের ক্রমে থাকে। তাঁরা আরও যুক্তি দেন, CYK-এর জন্য পূর্ণ CNF দরকারই নেই; ডান দিকে বড়জোর দুটি চিহ্ন থাকলে একটি সামান্য বদলানো CYK চলে, আর তখন grammar রৈখিক আকারেই থাকে। (প্রবন্ধের বিস্তারিত দাবি মূল লেখায় দেখে নেওয়া ভালো।)

পাঠ্যবই তবু DEL-আগের ক্রম শেখায় কারণ সেটি পড়তে আর প্রমাণে সহজ। ছোট উদাহরণে ε আর unit আগে সরালে grammar দ্রুত পরিষ্কার হয়, আর পরের ধাপগুলো যান্ত্রিক। পরীক্ষার grammar-এ ডান দিকে সাধারণত দু-তিনটি চিহ্ন থাকে, তাই বিস্ফোরণ চোখে পড়ে না। সমস্যা দেখা দেয় যখন কেউ বড়, যন্ত্রে তৈরি grammar-এ পাঠ্যবইয়ের ক্রম অন্ধভাবে চালায়। তত্ত্বের সঠিকতা আর algorithm-এর দক্ষতা দুটি আলাদা প্রশ্ন; দুটি ক্রমই সঠিক, কিন্তু একটি বেশি দক্ষ।

মূল উপলব্ধি: একই রূপান্তরের দুটি ক্রম একই language দেয়, কিন্তু আকারে exponential পার্থক্য হতে পারে। একটি algorithm “সঠিক” হওয়াই যথেষ্ট নয়; তার খরচও মাপতে হয়।

প্র ০৪CNF-এ প্রতিটি derivation ঠিক 2n − 1 ধাপের। এই সরল তথ্যটি কোথায় কোথায় কাজে লাগে?

প্রথম ব্যবহার সসীমতার প্রমাণে। সাধারণ CFG-তে একটি string-এর derivation কত লম্বা হতে পারে, তার কোনো সীমা নেই: A → B, B → A-এর মতো unit চক্র বা ε-নিয়ম দিয়ে derivation-কে ইচ্ছামতো লম্বা করা যায়। তাই “w ∈ L(G)?” প্রশ্নে সব derivation খোঁজা একটি অসীম অনুসন্ধান। CNF-এ সীমা ঠিক 2n − 1, তাই সব সম্ভাব্য derivation একটি সসীম তালিকা। এটাই “CFL-এর membership decidable” দাবির সবচেয়ে সরল প্রমাণ: CNF-এ রূপান্তর করুন, তারপর 2n − 1 ধাপের সব derivation পরখ করুন। পদ্ধতিটি exponential সময় নেয়, কিন্তু decidability-র জন্য সেটি যথেষ্ট; দক্ষতার জন্য পর্ব ৩১-এর CYK.

দ্বিতীয় ব্যবহার PDA-র সঙ্গে সংযোগে। পর্ব ৩৪-এ grammar থেকে PDA বানানোর সময় PDA প্রতিটি নিয়ম-প্রয়োগ stack-এ অনুকরণ করে। CNF হলে প্রতিটি ধাপে stack-এ বড়জোর একটি চিহ্ন বাড়ে, আর মোট ধাপের হিসাব সরাসরি input-এর দৈর্ঘ্যের সঙ্গে বাঁধা থাকে। Complexity-র দিক থেকেও এর অর্থ আছে: একটি parse tree-র আকার O(n), তাই একটি “সাক্ষী” গাছ দেখিয়ে কেউ দ্রুত প্রমাণ করতে পারে যে w ভাষায় আছে।

তৃতীয় ব্যবহার পরীক্ষার প্রশ্নে আর নিজের কাজ যাচাইয়ে। কেউ CNF grammar থেকে aabb-এর derivation লিখে ৬ বা ৮ ধাপ পেলে নিশ্চিতভাবে ভুল আছে। Python ব্লকের lengths ঠিক এই যাচাই করেছে: তিনটি grammar-এর শত শত string-এ সম্ভাব্য ধাপ-সংখ্যার set একটিই, 2n − 1. গাছের ভাষায় তথ্যটি আরও সুন্দর: nটি পাতার full binary tree-তে সবসময় n − 1টি ভেতরের node, গাছের আকার যেমনই হোক; DM-এর tree-র হিসাবেও এই সূত্র আসে।

মূল উপলব্ধি: CNF derivation-এর দৈর্ঘ্যকে input-এর দৈর্ঘ্যে বেঁধে দেয়। এই একটি সীমা থেকেই decidability, সসীম অনুসন্ধান আর যাচাইয়ের সহজ উপায় আসে।

প্র ০৫CNF-এ রূপান্তর কি সবসময় grammar-এর “অর্থ” রক্ষা করে? Ambiguity বা parse tree-র কী হয়?

Language রক্ষা হয়, কিন্তু parse tree হুবহু রক্ষা হয় না। রূপান্তরের প্রতিটি ধাপ L(G) রক্ষা করে, অর্থাৎ কোন string ভাষায় আছে তা বদলায় না। কিন্তু গাছের আকার বদলায়: TERM আর BIN নতুন node যোগ করে, UNIT কিছু node মুছে দেয় (E → T → F-এর শিকল এক ধাপে চলে আসে), আর DEL ε-পাতাগুলো সরিয়ে দেয়। সুখবর হলো, এই বদলগুলো উল্টানো যায়: Xi আর Ta-এর node মুছে তাদের সন্তানদের ওপরে তুলে দিলে, আর মুছে যাওয়া unit ও ε-অংশ ফিরিয়ে দিলে, মূল grammar-এর একটি গাছ পাওয়া যায়।

Ambiguity-র প্রশ্ন আরও সূক্ষ্ম। পর্ব ২৭-এ দেখেছেন, ambiguous মানে একটি string-এর দুটি parse tree. রূপান্তরের পর গাছের সংখ্যা বদলাতে পারে। মূল grammar-এর আলাদা দুটি গাছ একই CNF গাছে মিশে যেতে পারে, যদি তাদের পার্থক্য শুধু unit শিকল বা ε-অংশে থাকে। যেমন S → AB, A → a ∣ ε, B → a ∣ ε-এ “a”-এর দুটি গাছ (a আসে A থেকে, নয়তো B থেকে), কিন্তু CNF-এ দুটি কপি একটিই নিয়ম S0 → a হয়ে যায়, তাই গাছ একটি; scratch-এ গুনে ঠিক এটাই পাওয়া গেছে। অন্যদিকে BAL: S → (S)S ∣ ε ambiguous নয়, আর scratch-এ গুনে দেখা গেছে এর CNF-ও দৈর্ঘ্য ১০ পর্যন্ত প্রতিটি string-এ ঠিক একটি গাছ দেয়। প্রাকৃতিক ভাষার parser-এ গাছ গোনা গুরুত্বপূর্ণ, কারণ সম্ভাবনা গাছের ওপর বসে; তাই সেখানে রূপান্তর এমনভাবে করা হয় যাতে গাছের মধ্যে এক-এক মিল থাকে।

অর্থের দিক থেকে, compiler-এ গাছের গঠনই অর্থ বহন করে: id+id∗id-এ কোনটি আগে, তা গাছ বলে। CNF গাছে এই তথ্য হারায় না, শুধু অতিরিক্ত node-এর নিচে চাপা পড়ে: EX1-এর X1 → PT অংশটি এখনো বলে, যোগের ডান দিকে পুরো T. তাই CYK-এর ফল থেকে মূল গাছ পুনর্গঠন করা যায়, আর বাস্তবের CKY parser ঠিক তা-ই করে।

মূল উপলব্ধি: CNF রূপান্তর language রক্ষা করে, গাছ নয়; তবে গাছের বদল উল্টানো যায়। Ambiguity-র মতো গাছ-নির্ভর ধর্ম নিয়ে কাজ করলে রূপান্তরের পর আলাদা করে যাচাই লাগে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। cnf_term_bin.py ব্লকের CNF আর cnf_check.py-এর lang দিয়ে নিজের উত্তর যাচাইও করতে পারেন।

  1. রূপান্তর: {a, b}-এর ওপর palindrome-এর grammar S → aSa ∣ bSb ∣ a ∣ b ∣ ε-কে পাঁচ ধাপে CNF-এ রূপান্তর করুন। প্রতিটি ধাপের পর grammar লিখুন আর শেষে নিয়ম গুনুন।

    START: S0 → S. DEL: nullable = {S, S0}; S → aSa ∣ aa ∣ bSb ∣ bb ∣ a ∣ b, S0 → S ∣ ε. UNIT: S0 → aSa ∣ aa ∣ bSb ∣ bb ∣ a ∣ b ∣ ε. TERM: A → a, B → b; লম্বা নিয়ম ASA, AA, BSB, BB (একা a আর b বদলায় না)। BIN: X1 → SA, X2 → SB.

    শেষ grammar: S0 → AX1 ∣ AA ∣ BX2 ∣ BB ∣ a ∣ b ∣ ε, S → AX1 ∣ AA ∣ BX2 ∣ BB ∣ a ∣ b, X1 → SA, X2 → SB, A → a, B → b. মোট ৭ + ৬ + ২ + ২ = ১৭টি নিয়ম। Scratch-এ দৈর্ঘ্য ১০ পর্যন্ত মূল grammar-এর সঙ্গে হুবহু মিলেছে। সাধারণ ভুল: DEL-এ aa আর bb বাদ দেওয়া, তখন জোড় দৈর্ঘ্যের palindrome হারায়।

  2. প্রমাণ: G CNF-এ আর w ∈ L(G), |w| = n ≥ 1. প্রমাণ করুন, w-এর প্রতিটি parse tree-তে ঠিক 3n − 1টি node. তারপর দেখান, প্রতিটি গাছের উচ্চতা h ≥ ⌈log2 n⌉ + 1.
    1. গাছের প্রতিটি ভেতরের node একটি নিয়ম-প্রয়োগ। উপপাদ্য ৩.১-এ যেকোনো derivation-এ n − 1টি A → BC আর nটি A → a প্রয়োগ; একটি গাছ থেকে একটি leftmost derivation পাওয়া যায়, তাই গাছে n − 1টি দুই-সন্তানের আর nটি এক-সন্তানের node. — গাছ আর derivation-এর মিল
    2. পাতা ঠিক nটি, কারণ yield w আর প্রতিটি পাতা একটি terminal (ε-পাতা নেই, কারণ S0 → ε খাটে না)। — yield-এর সংজ্ঞা
    3. মোট (n − 1) + n + n = 3n − 1. — যোগ
    4. উপপাদ্য ৩.২-এ n ≤ 2h−1, তাই log2 n ≤ h − 1, আর h পূর্ণসংখ্যা বলে h ≥ ⌈log2 n⌉ + 1. ∎ — log নেওয়া

    যাচাই: aabb-এর গাছে (ছবি ২৯.১) ১১টি node = 3 · 4 − 1, আর উচ্চতা ৪ ≥ ⌈log2 4⌉ + 1 = ৩. সীমাটি সমতা নয়: aabb-এর গাছের উচ্চতা ৪, সীমা ৩.

  3. ভুল খুঁজুন: একজন লিখলেন: “G: S → AB, A → a, B → b ∣ ε. আমি আগে UNIT করলাম (কোনো unit নিয়ম নেই), তারপর DEL: B nullable, তাই S → AB ∣ A, A → a, B → b. TERM আর BIN-এ কিছু করার নেই। তাই G এখন CNF-এ।” ভুল কোথায়, আর সঠিক ফল কী?

    DEL নতুন unit নিয়ম S → A তৈরি করেছে, যা CNF-এ চলে না। ধাপের ক্রম উল্টো হওয়ায় UNIT আর চালানো হয়নি। এ ছাড়া START বাদ গেছে; এখানে S ডান দিকে নেই আর ε ∉ L, তাই সেটি এই ক্ষেত্রে ক্ষতি করেনি, কিন্তু algorithm হিসেবে দরকার।

    সঠিক ক্রমে: START S0 → S; DEL: nullable = {B}, তাই S → AB ∣ A, B → b; UNIT: S0 → AB ∣ a, S → AB ∣ a. ফল: S0 → AB ∣ a, S → AB ∣ a, A → a, B → b. L = {a, ab}, মূল grammar-এর মতোই; scratch-এ চালানো converter-ও ঠিক এই দুটি string দিয়েছে। এখানে S useless (S0 থেকে পৌঁছানো যায় না), তাই শেষে মুছে ফেলা যায়।

  4. Trace আর অনুমান: CNF grammar S0 → AX1 ∣ AB ∣ ε, S → AX1 ∣ AB, X1 → SB, A → a, B → b থেকে aaabbb-এর leftmost derivation লিখুন। চালানোর আগে অনুমান করুন: কয়টি ধাপ, আর তার কয়টি X1 → SB?

    অনুমান: n = 6, তাই 2 · 6 − 1 = ১১ ধাপ, তার ৫টি দুই-variable ধাপ: S0 → AX1 একবার, X1 → SB দুবার, S → AX1 একবার, S → AB একবার।

    S0 ⇒ AX1 ⇒ aX1 ⇒ aSB ⇒ aAX1B ⇒ aaX1B ⇒ aaSBB ⇒ aaABBB ⇒ aaaBBB ⇒ aaabBB ⇒ aaabbB ⇒ aaabbb

    ১১টি ধাপ, অনুমান মিলেছে। প্রতিটি X1 একটি করে b-কে “অপেক্ষায়” রাখে, ঠিক মূল aSb-এর ডান b-এর মতো; মূল grammar-এ একই string আসে ৪ ধাপে।

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমএকটি CFG-কে Chomsky normal form-এ আনার ধাপগুলো Sipser-এর রীতিতে সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. নতুন start symbol S0 আর S0 → S যোগ করা
  2. nullable set বের করে ε-নিয়ম দূর করা
  3. unit pair দিয়ে A → B নিয়ম দূর করা
  4. লম্বা নিয়মের terminal-কে প্রতিনিধি variable দিয়ে বদলানো আর লম্বা নিয়ম দুই-দুই করে ভাঙা
  5. ছোট দৈর্ঘ্যে মূল আর নতুন grammar-এর language brute force-এ মেলানো

S start symbol হলে নিচের কোন grammar Chomsky normal form-এ আছে?

  • S → AB ∣ a, A → BA ∣ b, B → a
  • S → aB ∣ b, B → b
  • S → AB, A → B, B → b
  • S → ABC, A → a, B → b, C → c

G একটি Chomsky normal form grammar আর w ∈ L(G), যেখানে |w| = 6. S থেকে w-এর যেকোনো derivation-এ কয়টি ধাপ?

  • 6
  • 7
  • 11
  • 12

Sipser-এর রীতির Chomsky normal form-এ নতুন start symbol S0 কোনো নিয়মের ডান দিকে থাকতে পারে না কেন?

  • যাতে grammar unambiguous হয়
  • যাতে S0 → ε শুধু ফাঁকা string-এর জন্য ব্যবহার হয়
  • যাতে নিয়মের সংখ্যা কমে
  • যাতে প্রতিটি terminal-এর একটি প্রতিনিধি থাকে

G: S → AB, A → a, B → b ∣ ε-এর ε-নিয়ম (nullable পদ্ধতিতে) দূর করলে কোন নতুন নিয়মটি আসে, যা Chomsky normal form-এ চলে না?

  • S → ε
  • A → ε
  • S → BA
  • S → A

Chomsky normal form grammar-এ |w| = 9 হলে w-এর যেকোনো parse tree-র উচ্চতা (মূল থেকে সবচেয়ে দূরের পাতা পর্যন্ত edge) কমপক্ষে কত?

  • 3
  • 4
  • 5
  • 9

Chomsky normal form-এ রূপান্তরের BIN ধাপে A → BCDE নিয়মটি (লেজ ভাগাভাগি ছাড়া) ভাঙলে কয়টি নতুন variable আর মোট কয়টি নিয়ম হয়?

  • ১টি variable, ২টি নিয়ম
  • ২টি variable, ৩টি নিয়ম
  • ৩টি variable, ৪টি নিয়ম
  • ৪টি variable, ৪টি নিয়ম

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. CNF: প্রতিটি নিয়ম A → BC বা A → a; শুধু S0 → ε চলে, আর S0 কোনো ডান দিকে নেই।
  2. CNF-এ |w| = n ≥ 1 হলে প্রতিটি derivation ঠিক 2n − 1 ধাপ, প্রতিটি parse tree-তে 3n − 1টি node, আর উচ্চতা h হলে n ≤ 2h−1.
  3. রূপান্তর: START → DEL → UNIT → TERM → BIN; DEL নতুন unit নিয়ম আনতে পারে, তাই UNIT পরে।
  4. প্রতিটি ধাপ language রক্ষা করে, কিন্তু parse tree-র আকার বদলায়; রূপান্তরের পর brute force-এ language মেলানো অভ্যাস করুন।
  5. আগে DEL করলে লম্বা নিয়মে 2k কপি হতে পারে; আগে BIN করলে আকার polynomial থাকে।

পরের পর্বে: Greibach normal form, যেখানে প্রতিটি ধাপে ঠিক একটি terminal আসে, আর তার পথে left recursion দূর করার কৌশল, যা top-down parser-এর জন্য অপরিহার্য।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান