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

Grammar সরলীকরণ — useless symbol, ε আর unit production

Simplifying Context-Free Grammars — Nullable Symbols, ε-Productions, Unit Pairs, Generating and Reachable Symbols, and Why the Order Matters

Taught in Bangla, this lesson cleans a context-free grammar without changing its language. It computes the nullable set and removes ε-productions, adding S0 → S | ε when needed, removes unit productions through unit pairs, and deletes useless symbols by removing non-generating symbols before unreachable ones. It explains why the order is ε, unit, useless and shows a rule with k nullable symbols growing to 2^k − 1 rules. In-page Python (Pyodide) runs each step and measures the blow-up.

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

  • Nullable, generating আর reachable symbol-এর সংজ্ঞা আর fixpoint দিয়ে সেগুলো বের করার algorithm
  • ε-নিয়ম আর unit নিয়ম দূর করার গঠন, আর প্রতিটি গঠন যে language রক্ষা করে তার প্রমাণ
  • Useless symbol মোছার দুই ধাপ, আর ভুল ক্রম কেন ব্যর্থ হয় তার counterexample
  • তিন ধাপের স্থির ক্রম (ε → unit → useless) কেন, আর ε-elimination-এ 2k বিস্ফোরণ
  • ব্রাউজারের Python-এ পুরো সরলীকরণ চালিয়ে আগে-পরের language brute force-এ মেলানো

১ · কেন সরলীকরণ — অগোছালো নিয়মের খাতা

পর্ব ২৫-এ আপনি context-free grammar G = (V, Σ, R, S) লিখতে শিখেছেন। বাস্তবে grammar প্রায়ই একবারে লেখা হয় না। বাজারঘরের order-query ভাষার grammar-এ কয়েক মাস ধরে নতুন field যোগ হয়েছে, পুরোনো field বাদ গেছে, কেউ “থাকতেও পারে, নাও থাকতে পারে” বোঝাতে ε-নিয়ম বসিয়েছেন, কেউ এক নাম থেকে আরেক নামে পাঠানোর জন্য X → Y লিখেছেন। Language হয়তো ঠিকই আছে, কিন্তু নিয়মের খাতাটি অগোছালো।

মাসের বাজারের ফর্দের কথা ভাবুন। তিন মাস ধরে একই কাগজে লেখা হচ্ছে। কিছু লাইন কেটে দেওয়া, কিছু লাইনে লেখা “আগের লাইনের মতো”, কিছু জিনিস লেখা আছে যা কোনো দোকানে পাওয়াই যায় না, আর এক কোণে একটি তালিকা, যার কথা মূল ফর্দের কোথাও নেই। দোকানে গিয়ে কাজ একই হবে, কিন্তু পড়তে সময় লাগে আর ভুলের সুযোগ বাড়ে। নতুন কাগজে পরিষ্কার করে লিখলে জিনিসের তালিকা বদলায় না, শুধু আবর্জনা বাদ যায়। Grammar সরলীকরণ ঠিক এই কাজ, শুধু “তালিকা বদলায় না” কথাটি এখানে একটি প্রমাণ করার মতো উপপাদ্য।

তিন রকম আবর্জনা আলাদা করে চিনে রাখুন। নিচের সংজ্ঞায় α, β ∈ (V ∪ Σ)∗, আর w ∈ Σ∗ মানে শুধু terminal দিয়ে গড়া একটি string.

সংজ্ঞা ১.১ (ε-নিয়ম, unit নিয়ম, useless symbol)

১. A → ε আকারের নিয়ম একটি ε-নিয়ম (ε-production).
২. A → B আকারের নিয়ম, যেখানে A, B ∈ V, একটি unit নিয়ম (unit production). ডান দিকে ঠিক একটি variable, আর কিছু নয়।
৩. একটি চিহ্ন X ∈ V ∪ Σ useful, যদি কোনো derivation S ⇒∗ αXβ ⇒∗ w থাকে, যেখানে w ∈ Σ∗. যে চিহ্ন useful নয়, সেটি useless.
৪. X generating, যদি কোনো w ∈ Σ∗-এর জন্য X ⇒∗ w; X reachable, যদি কোনো α, β-এর জন্য S ⇒∗ αXβ.

প্রতিটি terminal নিজেই generating (শূন্য ধাপে a ⇒∗ a). Useful হতে হলে চিহ্নটিকে দুটি শর্তই মানতে হয়: start থেকে পৌঁছানো যায় (reachable), আর সেখান থেকে একটি পূর্ণ terminal string-এ শেষ করা যায় (generating). পরে দেখবেন, শুধু “দুটি শর্ত আলাদা করে মানে” বললে যথেষ্ট নয়; কোন ক্রমে পরীক্ষা করছেন তাও জরুরি।

এই পর্বের পুরোটা জুড়ে একটি ছোট grammar ব্যবহার হবে। এর নাম দিই G; এতে তিন রকম আবর্জনাই আছে:

S → AB ∣ aC ∣ D
A → aA ∣ ε
B → bB ∣ A
C → cC
D → S ∣ d
E → e

একটু পড়লেই কয়েকটি জিনিস চোখে পড়ে। A → ε একটি ε-নিয়ম। B → A, S → D, D → S তিনটি unit নিয়ম, আর S ও D একে অপরকে ডাকে। C → cC থেকে কখনো বের হওয়া যায় না, কারণ প্রতিবার C আবার ফিরে আসে; তাই C non-generating. E-এর কথা কোনো নিয়মের ডান দিকে নেই, তাই E unreachable. Language-টি কী? A থেকে a∗, B থেকে b∗a∗, তাই AB থেকে a∗b∗a∗; aC কিছুই দেয় না; D থেকে বাড়তি পাওয়া যায় শুধু d. ফলে L(G) = a∗b∗a∗ ∪ {d}, আর ε ∈ L(G). Scratch-এ দৈর্ঘ্য ৭ পর্যন্ত G থেকে ঠিক ৯৩টি string আসে, আর সেগুলো এই বর্ণনার সঙ্গে হুবহু মেলে।

কেন এত ঝামেলা? তিনটি কারণ। প্রথমত, পরের পর্বের Chomsky normal form (পর্ব ২৯) আর Greibach normal form (পর্ব ৩০) এমন grammar চায়, যাতে ε-নিয়ম আর unit নিয়ম নেই; সরলীকরণ সেই রূপান্তরের প্রথম অর্ধেক। দ্বিতীয়ত, অনেক প্রমাণ সহজ হয়, যদি জানা থাকে প্রতিটি নিয়ম string-কে অন্তত লম্বা রাখে বা অন্তত একটি terminal যোগ করে। তৃতীয়ত, useless symbol খোঁজার algorithm নিজেই একটি প্রশ্নের উত্তর দেয়: L(G) ফাঁকা কি না। এটি CFG-এর emptiness problem, আর এর উত্তর এই পর্বেই পাবেন।

এই পর্বের notation: মডিউলের রীতিই চলবে: G = (V, Σ, R, S); বড় হাতের অক্ষর variable, ছোট হাতের অক্ষর terminal; একই বাঁ দিকের নিয়ম A → α ∣ β; ⇒ এক ধাপ, ⇒∗ শূন্য বা বেশি ধাপ। ফাঁকা string সবসময় ε. কোনো নিয়মের ডান দিকে একই চিহ্ন একাধিকবার থাকলে প্রতিটি উপস্থিতিকে আলাদা “অবস্থান” ধরা হবে; সরলীকরণে এই পার্থক্যটি গুরুত্বপূর্ণ।

২ · Nullable symbol — কোন variable ফাঁকা হয়ে যেতে পারে

ε-নিয়ম দূর করার আগে জানতে হবে, ঠিক কোন variable-গুলো ফাঁকা string-এ মিলিয়ে যেতে পারে। শুধু A → ε দেখে বলা যায় না। G-তে B → A আছে, তাই B ⇒ A ⇒ ε; B নিজে কোনো ε-নিয়ম না থাকলেও ফাঁকা হতে পারে। আবার S → AB, তাই S-ও।

সংজ্ঞা ২.১ (Nullable)

A ∈ V nullable, যদি A ⇒∗ ε. Nullable variable-গুলোর set-কে N বলি।

N বের করার উপায় একটি fixpoint iteration, ঠিক পর্ব ২৫-এর string-generator-এর মতো ধারণা: শুরু ফাঁকা set দিয়ে, তারপর একটি নিয়ম বারবার খাটানো, যতক্ষণ না আর কিছু বদলায়।

Algorithm ২.২ (Nullable set)

N0 = ∅. প্রতি রাউন্ডে Ni+1 = { A : R-এ কোনো নিয়ম A → X1X2⋯Xm আছে, যার প্রতিটি Xj ∈ Ni }. যখন Ni+1 = Ni, থামুন; উত্তর N = Ni.

m = 0 হলে, অর্থাৎ A → ε নিয়মে, “প্রতিটি Xj ∈ Ni” শর্তটি ফাঁকাভাবেই সত্য, তাই A → ε-ওয়ালা variable প্রথম রাউন্ডেই N-এ আসে। কোনো ডান দিকে একটি terminal থাকলে সেই নিয়ম কখনো কাজে লাগে না, কারণ terminal মুছে যায় না। Set-গুলো শুধু বড় হয় (Ni ⊆ Ni+1, রাউন্ডের ওপর induction-এ দেখা যায়), আর V সসীম; তাই বড়জোর |V| + 1 রাউন্ডে algorithm থামে। নিচের stepper G-তে রাউন্ডগুলো দেখায়।

1S → AB ∣ aC ∣ D2A → aA ∣ ε3B → bB ∣ A4C → cC5D → S ∣ d6E → e
এই রাউন্ডের অবস্থা
রাউন্ড
N
কোন নিয়ম কাজে লাগল
  1. শুরু। N0 = ∅. এখনো কোনো variable ফাঁকা হতে পারে বলে জানা নেই। প্রতি রাউন্ডে সব নিয়ম দেখা হবে, আর আগের রাউন্ডের N দিয়ে বিচার হবে।
  2. রাউন্ড ১। A → ε-এর ডান দিক ফাঁকা, তাই শর্ত ফাঁকাভাবে সত্য: A ∈ N1. অন্য কোনো নিয়মের ডান দিক পুরোপুরি N0 = ∅-এর ভেতরে নেই।
  3. রাউন্ড ২। B → A, আর A ∈ N1; তাই B ∈ N2. S → AB এখনো খাটে না, কারণ রাউন্ড ১-এর শেষে B জানা ছিল না। N2 = {A, B}.
  4. রাউন্ড ৩। S → AB-এর দুটি চিহ্নই N2-এ, তাই S ∈ N3. S → aC খাটে না, কারণ a একটি terminal; ফাঁকা হতে পারে না।
  5. রাউন্ড ৪। D → S, আর S ∈ N3; তাই D ∈ N4. লক্ষ করুন, nullable হওয়ার খবর unit নিয়মের শিকল ধরে এক ধাপ এক ধাপ ছড়ায়।
  6. থামা। রাউন্ড ৫-এ নতুন কিছু আসে না। C → cC আর E → e-তে terminal আছে, তাই C আর E কখনো N-এ ঢোকে না। N = {A, B, S, D}. S ∈ N, তাই ε ∈ L(G); ধাপ ১-এ একটি নতুন start S0 লাগবে।
উপপাদ্য ২.৩

Algorithm ২.২ যে N দেয়, তার জন্য: A ∈ N ⇔ A ⇒∗ ε.

প্রমাণ (⇒ দিক):

  1. দাবি: প্রতিটি i-তে, A ∈ Ni হলে A ⇒∗ ε. i-এর ওপর induction. ভিত্তি i = 0: N0 = ∅, বলার কিছু নেই। — ফাঁকা দাবি
  2. ধাপ: A ∈ Ni+1, তাই একটি নিয়ম A → X1⋯Xm আছে, যার প্রতিটি Xj ∈ Ni. Induction hypothesis-এ প্রতিটি Xj ⇒∗ ε. — algorithm-এর সংজ্ঞা
  3. তাহলে A ⇒ X1⋯Xm ⇒∗ X2⋯Xm ⇒∗ ⋯ ⇒∗ ε; প্রতিটি Xj-কে পালা করে মুছে। m = 0 হলে এক ধাপেই A ⇒ ε. ∎ — context-free নিয়ম প্রসঙ্গ দেখে না

প্রমাণ (⇐ দিক):

  1. দাবি: A ⇒∗ ε যদি n ধাপে হয়, তবে A ∈ N. n-এর ওপর strong induction. n ≥ 1, কারণ A ≠ ε. — induction-এর কাঠামো
  2. প্রথম ধাপ কোনো নিয়ম A → X1⋯Xm. বাকি n − 1 ধাপে X1⋯Xm ⇒∗ ε. কোনো Xj terminal হতে পারে না, কারণ terminal কখনো মুছে যায় না। — terminal-এর ধর্ম
  3. Context-free derivation প্রতিটি চিহ্নের ওপর আলাদা আলাদা derivation-এ ভাঙে, তাই প্রতিটি Xj ⇒∗ ε, প্রতিটি n − 1-এর কম বা সমান ধাপে। Induction hypothesis-এ প্রতিটি Xj ∈ N. — derivation ভাঙার নীতি
  4. N একটি fixpoint: N-এর ওপর রাউন্ড চালালে আবার N আসে। প্রতিটি Xj ∈ N, তাই নিয়মটি A-কে পরের রাউন্ডে তোলে, অর্থাৎ A ∈ N. ∎ — থামার শর্ত

এই প্রমাণের ধাঁচ বারবার আসবে: “algorithm যা খুঁজে পায় তা সত্যি” (soundness, রাউন্ডের ওপর induction) আর “যা সত্যি তা algorithm খুঁজে পায়” (completeness, derivation-এর দৈর্ঘ্যের ওপর induction). Generating symbol-এর প্রমাণ অংশ ৫-এ হুবহু একই ছকে, শুধু ε-এর জায়গায় “কোনো terminal string”.

৩ · ε-নিয়ম দূর করা — প্রতিটি উপসেট বাদ দিয়ে

N হাতে পেলে গঠনটি সহজ। মূল ধারণা: G-এর একটি derivation-এ কোনো nullable চিহ্ন হয়তো পরে ε হয়ে মুছে যেত। নতুন grammar-এ আমরা আগে থেকেই ঠিক করে নিই, কোন nullable চিহ্ন “থাকবে” আর কোনটি “না থাকার” সিদ্ধান্ত এখনই নেওয়া হলো। যেহেতু কোন চিহ্ন মুছবে তা আগে জানা নেই, প্রতিটি সম্ভাবনার জন্য একটি করে নিয়ম লাগে।

গঠন ৩.১ (ε-elimination)

G থেকে G′ = (V, Σ, R′, S) বানান: R-এর প্রতিটি নিয়ম A → X1⋯Xm-এর জন্য, ডান দিকের nullable অবস্থানগুলোর প্রতিটি উপসেট বেছে সেগুলো বাদ দিয়ে A → (বাকিগুলো) নিয়মটি R′-এ রাখুন, যদি বাকি অংশ ফাঁকা না হয়। কোনো A → ε R′-এ যাবে না। শেষে, যদি S ∈ N, একটি নতুন variable S0 আর দুটি নিয়ম S0 → S ∣ ε যোগ করুন, আর S0-কে start symbol করুন।

G-এর নিয়মে খাটিয়ে দেখি। S → AB-তে দুটি অবস্থানই nullable, তাই চারটি উপসেট: কিছুই না বাদ দিলে AB, A বাদ দিলে B, B বাদ দিলে A, দুটিই বাদ দিলে ফাঁকা, যা রাখা হয় না। S → aC-তে কোনো nullable নেই, নিয়মটি যেমন ছিল। B → A থেকে A বাদ দিলে ফাঁকা, তাই শুধু B → A থাকে। A → aA থেকে A → aA আর A → a. ফল:

S0 → S ∣ ε
S  → AB ∣ B ∣ A ∣ aC ∣ D
A  → aA ∣ a
B  → bB ∣ b ∣ A
C  → cC
D  → S ∣ d
E  → e

দুটি জিনিস খেয়াল করুন। এক, S0 কোনো নিয়মের ডান দিকে নেই, তাই S0 → ε কখনো কোনো derivation-এর মাঝখানে খাটে না; এটি শুধু “ε নিজেই language-এ আছে” কথাটি লেখে। দুই, নতুন দুটি unit নিয়ম জন্মেছে: S → A আর S → B, আর S0 → S-ও একটি unit নিয়ম। ধাপ ১ পরের ধাপের কাজ বাড়িয়ে দিল; ক্রমের প্রশ্নে এটি মনে রাখুন।

উপপাদ্য ৩.২

গঠন ৩.১-এর G′, S0 যোগ করার আগে, মানে L(G′) = L(G) − {ε}. S0 → S ∣ ε যোগ করার পর L(G′) = L(G).

প্রমাণ: আসলে একটু শক্তিশালী দাবি প্রমাণ করব: প্রতিটি A ∈ V আর প্রতিটি অ-ফাঁকা w ∈ Σ∗-এর জন্য, A ⇒∗G′ w ⇔ A ⇒∗G w.

  1. (⇒) G′-এর প্রতিটি নিয়ম A → α′ এসেছে G-এর কোনো A → α থেকে, কিছু nullable অবস্থান বাদ দিয়ে। G-তে A ⇒ α, তারপর বাদ পড়া প্রতিটি nullable চিহ্নকে ε পর্যন্ত derive করলে α′. তাই G′-এর প্রতিটি ধাপ G-তে কয়েক ধাপে নকল করা যায়। — উপপাদ্য ২.৩
  2. (⇐) G-তে derivation-এর দৈর্ঘ্যের ওপর strong induction. ধরুন A ⇒G X1⋯Xm ⇒∗G w. তাহলে w = w1⋯wm, যেখানে প্রতিটি Xj ⇒∗ wj, প্রতিটি ছোট derivation-এ (terminal হলে wj = Xj). — derivation ভাঙার নীতি
  3. J = { j : wj ≠ ε }. w ≠ ε, তাই J ফাঁকা নয়। j ∉ J হলে Xj ⇒∗ ε, তাই Xj একটি nullable variable. ফলে J-এর বাইরের সব অবস্থান বাদ দেওয়া নিয়ম A → (Xj : j ∈ J) R′-এ আছে, আর এটি ফাঁকা নয়। — গঠন ৩.১
  4. j ∈ J-এর জন্য wj অ-ফাঁকা, আর derivation ছোট; induction hypothesis-এ Xj ⇒∗G′ wj. জুড়ে দিলে A ⇒G′ (Xj : j ∈ J) ⇒∗G′ w. — induction hypothesis
  5. R′-এর প্রতিটি নিয়মের ডান দিক অ-ফাঁকা, তাই প্রতিটি sentential form-এর দৈর্ঘ্য অন্তত ১; ε ∉ L(G′). দাবিটি A = S-এ খাটালে L(G′) = L(G) − {ε}. S0 → S যোগ করলে অ-ফাঁকা string একই থাকে, আর S0 → ε শুধু ε যোগ করে, যা ঠিক তখনই দরকার যখন S ∈ N. ∎ — দুই ক্ষেত্র মিলিয়ে

এবার কোডে। নিচের ব্লক G-কে একটি dict হিসেবে রাখে: প্রতিটি নিয়ম space দিয়ে আলাদা করা চিহ্নের একটি string, আর "" মানে ε. nullable রাউন্ড ধরে N ছাপে, আর remove_eps গঠন ৩.১ হুবহু চালায়: প্রতিটি নিয়মের nullable অবস্থানগুলো থেকে combinations দিয়ে প্রতিটি উপসেট বাদ দেয়। এই পর্বের চারটি Python ব্লক একই namespace ভাগ করে (data-shared), তাই পরের ব্লকগুলো এখানকার function আর grammar ব্যবহার করবে। পরের কোনো ব্লক আগে চালালে এটি নিজে থেকেই আগে চলবে।

from itertools import combinations
# a rule is a space-separated string of symbols; "" is ε
G = {"S": ["A B", "a C", "D"], "A": ["a A", ""], "B": ["b B", "A"],
     "C": ["c C"], "D": ["S", "d"], "E": ["e"]}
start = "S"
def show(G, title):
    print(title)
    for A, R in G.items():
        short = lambda r: r.replace(" ", "") if max(map(len, r.split()), default=1) == 1 else r
        print(f"  {A:2} -> " + " | ".join(short(r) or "ε" for r in R))
def nullable(G, log=True):              # least fixpoint, round by round
    N, k = set(), 0
    while True:
        new = {A for A, R in G.items() for r in R
               if all(X in N for X in r.split())}
        if new == N: return N
        k += 1; N = new
        if log: print(f"  round {k}: N = {sorted(N)}")
def remove_eps(G, start, log=True):
    N, H = nullable(G, log), {}
    for A, R in G.items():
        H[A] = []
        for r in R:
            s = r.split()
            pos = [i for i, X in enumerate(s) if X in N]
            for k in range(len(pos) + 1):        # every subset to drop
                for drop in combinations(pos, k):
                    t = " ".join(X for i, X in enumerate(s) if i not in drop)
                    if t and t not in H[A]: H[A].append(t)
    if start in N:                       # ε ∈ L(G): new start S0
        return {"S0": [start, ""], **H}, "S0"
    return H, start
show(G, "G:")
G1, start1 = remove_eps(G, start)
show(G1, "after phase 1 (ε-rules removed):")

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

G:
  S  -> AB | aC | D
  A  -> aA | ε
  B  -> bB | A
  C  -> cC
  D  -> S | d
  E  -> e
  round 1: N = ['A']
  round 2: N = ['A', 'B']
  round 3: N = ['A', 'B', 'S']
  round 4: N = ['A', 'B', 'D', 'S']
after phase 1 (ε-rules removed):
  S0 -> S | ε
  S  -> AB | B | A | aC | D
  A  -> aA | a
  B  -> bB | b | A
  C  -> cC
  D  -> S | d
  E  -> e

রাউন্ডগুলো stepper-এর সঙ্গে হুবহু মেলে: A, তারপর B, তারপর S, তারপর D. sorted অক্ষরের ক্রমে ছাপে, তাই রাউন্ড ৪-এ D আগে এসেছে। পাঁচ নম্বর রাউন্ডে কিছু বদলায়নি বলে লাইন ছাপা হয়নি, শুধু function ফিরে এসেছে। Phase 1-এর ফল হাতে করা হিসাবের সঙ্গেও মেলে, আর A → ε কোথাও নেই। ε শুধু S0 → ε-তে আছে। এই অংশটি নিজে বদলে দেখুন: B → bB ∣ A-এর জায়গায় B → bB ∣ b লিখলে B আর S nullable হবে না, তাই D-ও হবে না, আর S0 তৈরিই হবে না, কারণ তখন ε ∉ L(G).

দুটি পরিচিত ভুল: (ক) “শুধু একটি করে nullable চিহ্ন বাদ দিলেই হবে” ভাবা। S → ABC-তে A, B, C তিনটিই nullable হলে S → C পেতে A আর B দুটিকে একসঙ্গে বাদ দিতে হয়; একবারে একটি বাদ দিলে a, b, c-এর মতো string হারায় (অংশ ৭-এর ব্লক এটি দেখাবে)। (খ) ε ∈ L(G) হলেও S0 → ε যোগ না করা। তখন grammar ফাঁকা string হারায়, আর language এক সদস্য ছোট হয়ে যায়। উল্টো ভুলও আছে: S0 ছাড়াই পুরোনো S-এ S → ε রেখে দেওয়া; S অন্য নিয়মের ডান দিকে থাকলে ε-নিয়ম আবার derivation-এর মাঝখানে ঢুকে পড়ে।

৪ · Unit নিয়ম আর unit pair — নাম বদলের শিকল কাটা

A → B নিয়মটি কোনো terminal যোগ করে না, string লম্বাও করে না; শুধু একটি নাম বদলে আরেকটি নাম বসায়। মোবাইল ব্যাংকিংয়ের PIN মেনুর কথা ভাবুন: “৩ চাপুন: হিসাব; তারপর ১ চাপুন: ব্যালান্স”. মাঝের মেনুটি কোনো কাজ করে না, শুধু আপনাকে আরেকটি মেনুতে পাঠায়। ঘনঘন ব্যবহারকারীর জন্য একটি “সরাসরি ব্যালান্স” বোতাম রাখলে ফল একই, ধাপ কম। Unit নিয়ম দূর করাও তাই: A থেকে unit নিয়মের শিকল ধরে যেখানে যেখানে পৌঁছানো যায়, সেখানকার “আসল কাজের” নিয়মগুলো সরাসরি A-তে বসিয়ে দেওয়া।

সংজ্ঞা ৪.১ (Unit pair)

ধরুন G-তে কোনো ε-নিয়ম নেই (S0 → ε ছাড়া, আর S0 কোনো ডান দিকে নেই)। (A, B) একটি unit pair, যদি শুধু unit নিয়ম খাটিয়ে A ⇒∗ B. প্রতিটি (A, A) একটি unit pair (শূন্য ধাপ)।

Unit pair বের করা একটি গ্রাফের প্রশ্ন। প্রতিটি variable একটি node, আর প্রতিটি unit নিয়ম A → B একটি তীর A থেকে B-তে। তাহলে (A, B) unit pair ঠিক তখনই, যখন এই গ্রাফে A থেকে B-তে পৌঁছানো যায়; অর্থাৎ এটি একটি reachability প্রশ্ন, যার উত্তর প্রতিটি A থেকে একটি BFS দেয় (DSA কোর্সের পর্ব ৪০)। পর্ব ১১-এর ε-closure-এর সঙ্গে মিলটি লক্ষ করুন: সেখানে ε-তীর ধরে যত state-এ যাওয়া যায়, এখানে unit নিয়ম ধরে যত variable-এ। Right-linear grammar-এ A → B আসলে একটি ε-transition-ই।

ধাপ ১-এর পরে G-এর unit গ্রাফ

প্রতিটি তীর একটি unit নিয়ম। একটি variable থেকে যত node-এ পৌঁছানো যায়, সেগুলোই তার unit pair. S আর D-এর মধ্যে চক্র আছে।

Unit graph after phase 1: S0→S, S→A, S→B, S→D, D→S, B→A S0SD BA S → DD → S B → A C, E: কোনো unit তীর নেই
ছবি ২৮.১ — S থেকে পৌঁছানো যায় S, B, A, D-তে (D থেকে আবার S-এ ফেরা যায়, তাই চক্রটি কোনো নতুন node দেয় না)। S0 থেকে পাঁচটিতেই। A থেকে শুধু A-তে।
গঠন ৪.২ (Unit-elimination)

ε-নিয়মহীন G থেকে G″ বানান: প্রতিটি unit pair (A, B) আর B-এর প্রতিটি non-unit নিয়ম B → α-এর জন্য A → α রাখুন। কোনো unit নিয়ম রাখবেন না। (A, A) জোড়াটির কারণে A-এর নিজের non-unit নিয়মগুলোও থেকে যায়।

ক্রমটি কেন “ε আগে, unit পরে”, তা এই সংজ্ঞাতেই লুকিয়ে আছে। ε-নিয়ম থাকলে A → BC আর C ⇒∗ ε মিলে A ⇒∗ B হয়, অথচ কোনো unit নিয়ম খাটানো হয়নি। তখন unit গ্রাফ সব “নাম বদলের পথ” দেখাত না। ধাপ ১ সেই লুকোনো পথগুলোকে স্পষ্ট unit নিয়মে বদলে দেয় (S → AB থেকে S → A আর S → B), আর তারপর ধাপ ২ সেগুলো ধরতে পারে।

1S0 → S ∣ ε2S → AB ∣ B ∣ A ∣ aC ∣ D3A → aA ∣ a4B → bB ∣ b ∣ A5C → cC6D → S ∣ d7E → e
এই ধাপের হিসাব
variable
unit pair
নতুন নিয়ম
  1. Unit নিয়ম চেনা। ধাপ ১-এর পরে ছয়টি unit নিয়ম: S0 → S, S → B, S → A, S → D, B → A, D → S. aC, AB, aA-এর মতো ডান দিক unit নয়, কারণ সেখানে একের বেশি চিহ্ন বা একটি terminal আছে। b বা d-ও unit নয়: একটিমাত্র চিহ্ন, কিন্তু terminal.
  2. B-এর জোড়া। B থেকে unit তীর শুধু A-তে, আর A থেকে কোনো unit তীর নেই। তাই B-এর unit pair (B, B) আর (B, A). B-এর non-unit নিয়ম bB, b, আর A-এর aA, a; মিলিয়ে B → bB ∣ b ∣ aA ∣ a.
  3. S-এর জোড়া। S থেকে B, A আর D-তে সরাসরি; B থেকে A (আগেই আছে); D থেকে S (আগেই আছে)। চক্রটি থাকলেও BFS থামে, কারণ একই node দুবার যোগ হয় না। ফল S, B, A, D.
  4. S-এর নতুন নিয়ম। S-এর নিজের non-unit নিয়ম AB, aC; B থেকে bB, b; A থেকে aA, a; D থেকে d. ফল S → AB ∣ aC ∣ bB ∣ b ∣ aA ∣ a ∣ d, সাতটি নিয়ম, একটিও unit নয়।
  5. D আর S0. D-এর জোড়া D, S, B, A; তাই D-ও একই সাতটি নিয়ম পায় (d আগে)। S0-এর জোড়া পাঁচটিই, আর S0-এর নিজের non-unit নিয়ম S0 → ε. ফল S0 → ε ∣ AB ∣ aC ∣ bB ∣ b ∣ aA ∣ a ∣ d.
  6. ফল। A, C, E-এর কোনো unit তীর নেই, তাদের নিয়ম যেমন ছিল। মোট নিয়ম ১৬ থেকে বেড়ে ৩০, কিন্তু একটিও unit নয়। নিচের ব্লক দৈর্ঘ্য ৭ পর্যন্ত দেখায়, language বদলায়নি।
উপপাদ্য ৪.৩

G-তে ε-নিয়ম না থাকলে (S0 → ε ছাড়া), গঠন ৪.২-এর G″-এ L(G″) = L(G), আর G″-এ কোনো unit নিয়ম নেই।

প্রমাণের রূপরেখা: (⊆) G″-এর একটি নিয়ম A → α এসেছে একটি unit pair (A, B) আর B → α থেকে। G-তে A ⇒∗ B শুধু unit নিয়মে, তারপর B ⇒ α; তাই G″-এর প্রতিটি ধাপ G-তে নকল করা যায়। (⊇) w ∈ L(G)-এর একটি leftmost derivation নিন। এর ধাপগুলোকে ভাগ করুন: একটানা কয়েকটি unit ধাপ, তারপর একটি non-unit ধাপ। Leftmost derivation-এ সবচেয়ে বাঁয়ের variable-এর বাঁ পাশে শুধু terminal, আর unit ধাপ variable-টিকে একই জায়গায় আরেকটি variable দিয়ে বদলায়; তাই পরের ধাপও ঠিক সেই জায়গাতেই হয়। ফলে প্রতিটি দল দেখতে A ⇒ B1 ⇒ ⋯ ⇒ Bk ⇒ α, একই অবস্থানে, যেখানে (A, Bk) একটি unit pair আর Bk → α non-unit. G″-এ এই পুরো দলটি একটি ধাপ A → α. Derivation unit ধাপ দিয়ে শেষ হতে পারে না, কারণ শেষ string-এ কোনো variable নেই। তাই প্রতিটি দলকে বদলে G″-এর একটি derivation পাওয়া যায়। ∎

Leftmost derivation বেছে নেওয়াটি কৌশল, বাধ্যবাধকতা নয়: যেকোনো derivation-এ unit ধাপগুলো অন্য অবস্থানের ধাপের সঙ্গে মিশে থাকতে পারে, তখন “দল” আলাদা করা ঝামেলার। পর্ব ২৬-এ দেখেছেন, প্রতিটি parse tree-এর একটি leftmost derivation আছে, তাই এই বাছাইয়ে কিছু হারায় না। গাছের ভাষায় প্রমাণটি আরও সহজ: unit নিয়মগুলো গাছে “একটি সন্তানের শিকল”, আর ধাপ ২ সেই শিকলগুলো চেপে একটি node বানায়।

নিচের ব্লক একই namespace-এ চলে। remove_units প্রতিটি variable থেকে একটি তালিকা P বাড়াতে বাড়াতে unit pair খোঁজে (Python-এ চলতে চলতে তালিকায় যোগ করলে loop নতুন সদস্যও দেখে; এটি আসলে একটি BFS). তারপর lang দৈর্ঘ্য ≤ n-এর সব string বানায়, পর্ব ২৫-এর fixpoint generator-এর মতো, আর প্রতিটি ধাপের পরে language মূল G-এর সঙ্গে brute force-এ মেলানো হয়।

from itertools import product
def remove_units(G):
    H = {}
    for A in G:
        P = [A]                          # unit pairs (A, B), by search
        for B in P:                      # P grows while we scan it
            P += [r for r in G[B] if r in G and r not in P]
        print(f"  unit pairs of {A:2}: {' '.join(P)}")
        H[A] = list(dict.fromkeys(r for B in P for r in G[B] if r not in G))
    return H
def lang(G, start, n):                   # all strings of length <= n
    L = {A: set() for A in G}
    while True:
        new = {A: L[A] | {w for r in G[A] for c in product(*[L[X]
               if X in G else {X} for X in r.split()]) if len(w := "".join(c)) <= n}
               for A in G}
        if new == L: return L[start]
        L = new
G2 = remove_units(G1)
show(G2, "after phase 2 (unit rules removed):")
L0 = lang(G, start, 7)
print(f"G: {sum(map(len, G.values()))} rules, {len(L0)} strings of length <= 7")
for name, H in [("phase 1", G1), ("phase 2", G2)]:
    print(f"{name}: {sum(map(len, H.values()))} rules, same strings:",
          lang(H, start1, 7) == L0)

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

  unit pairs of S0: S0 S B A D
  unit pairs of S : S B A D
  unit pairs of A : A
  unit pairs of B : B A
  unit pairs of C : C
  unit pairs of D : D S B A
  unit pairs of E : E
after phase 2 (unit rules removed):
  S0 -> ε | AB | aC | bB | b | aA | a | d
  S  -> AB | aC | bB | b | aA | a | d
  A  -> aA | a
  B  -> bB | b | aA | a
  C  -> cC
  D  -> d | AB | aC | bB | b | aA | a
  E  -> e
G: 11 rules, 93 strings of length <= 7
phase 1: 16 rules, same strings: True
phase 2: 30 rules, same strings: True

Unit pair-গুলো ছবি ২৮.১-এর reachability-র সঙ্গে মেলে, আর নতুন নিয়মগুলো stepper-এর সঙ্গে। একটি রুল-বডি ডান দিকে একটি variable-এর নাম হলেই (r in G) সেটি unit; "b" বা "d" terminal, তাই unit নয়। dict.fromkeys একই নিয়ম দুবার যোগ হতে দেয় না। শেষ তিন লাইন বলছে: মূল G-এ ১১টি নিয়ম আর দৈর্ঘ্য ৭ পর্যন্ত ৯৩টি string; phase 1-এ ১৬টি আর phase 2-এ ৩০টি নিয়ম, কিন্তু দুবারই একই ৯৩টি string. নিয়ম বেড়েছে, language নয়। মনে রাখবেন, “দৈর্ঘ্য ৭ পর্যন্ত মিলেছে” প্রমাণ নয়; প্রমাণ উপপাদ্য ৩.২ আর ৪.৩. Brute force শুধু কোডের ভুল ধরার জাল।

৫ · Useless symbol — আগে generating, তারপর reachable

ধাপ ২-এর ফলাফলে আবর্জনা আরও স্পষ্ট। C → cC এখনো চিরকাল ঘুরছে; E-কে কেউ ডাকে না; আর নতুন একটি ঘটনা ঘটেছে: S0 এখন S বা D-কে আর ডাকে না, কারণ তাদের নিয়মগুলো সরাসরি S0-এ কপি হয়ে গেছে। দুটি আলাদা প্রশ্নের দুটি আলাদা algorithm.

Algorithm ৫.১ (Generating আর reachable)

Generating: Γ0 = Σ (প্রতিটি terminal). প্রতি রাউন্ডে A-কে যোগ করুন, যদি কোনো নিয়ম A → X1⋯Xm-এর প্রতিটি Xj ইতিমধ্যে set-এ থাকে। আর কিছু না বাড়লে থামুন। (m = 0 হলে শর্ত ফাঁকাভাবে সত্য, তাই S0 → ε থেকে S0 generating.)
Reachable: S থেকে শুরু করে গ্রাফ-খোঁজ: A reachable হলে A-এর প্রতিটি নিয়মের ডান দিকের প্রতিটি variable-ও reachable.

Nullable-এর algorithm-এর সঙ্গে মিলটি দেখুন: দুটিই একই fixpoint ছক, শুধু শুরুর set আলাদা (nullable-এ ∅, generating-এ Σ)। প্রমাণও একই ছকে: soundness রাউন্ডের ওপর induction, completeness derivation-এর দৈর্ঘ্যের ওপর induction. তাই সেটি আর লিখছি না; অনুশীলন ২-এ এর একটি নিকট আত্মীয় পাবেন।

উপপাদ্য ৫.২ (Useless symbol মোছা)

ধরুন L(G) ≠ ∅. (১) G থেকে সব non-generating symbol আর যে নিয়মে এমন কোনো symbol আছে সেগুলো মুছে G1 পান। (২) G1-এ যে symbol S থেকে reachable নয়, সেগুলো আর তাদের নিয়ম মুছে G2 পান। তাহলে L(G2) = L(G), আর G2-এর প্রতিটি symbol useful.

প্রমাণ:

  1. Language রক্ষা: S ⇒∗ w (w ∈ Σ∗) derivation-এ যে symbol আসে, সেটি reachable (derivation-এর মাঝপথে আছে) আর generating (তার অংশটুকু w-এর একটি টুকরোয় শেষ হয়)। তাই সেই derivation-এর কোনো নিয়ম মোছা হয় না, আর একই derivation G2-এ চলে। উল্টো দিকে G2-এর নিয়ম G-রই নিয়ম। — useful-এর সংজ্ঞা
  2. G1-এ প্রতিটি symbol generating, আর G1-এর ভেতরেই: X generating হলে X ⇒∗ w-এর derivation-এর প্রতিটি symbol নিজেও generating, তাই সেই derivation-এর কোনো নিয়ম ধাপ (১)-এ মোছা হয়নি। — generating-এর সংজ্ঞা
  3. ধরুন X ∈ G2. তাহলে X G1-এ reachable: S ⇒∗G1 αXβ. এই derivation-এর প্রতিটি symbol S থেকে reachable, তাই ধাপ (২)-এ কিছু মোছা হয়নি, আর derivation G2-এও চলে। — ধাপ (২)-এর সংজ্ঞা
  4. αXβ-এর প্রতিটি symbol Y G1-এ generating (ধাপ ২-এর কারণে): Y ⇒∗ wY. এই derivation-এর প্রতিটি symbol Y থেকে reachable, আর Y নিজে S থেকে reachable, তাই এরা G2-এ আছে। ফলে S ⇒∗G2 αXβ ⇒∗G2 w, অর্থাৎ X useful. ∎ — reachability transitive

প্রমাণের ৪ নম্বর ধাপেই ক্রমের রহস্য: unreachable symbol মোছা কোনো generating symbol-কে non-generating করে না, কারণ একটি symbol-এর generating derivation-এ যা আছে, সবই সেটি থেকে reachable. কিন্তু উল্টোটি সত্য নয়। Non-generating symbol মুছতে গিয়ে নিয়ম মোছা হয়, আর সেই নিয়মটিই হয়তো কোনো symbol-এর কাছে পৌঁছানোর একমাত্র পথ ছিল। তাই “আগে reachable, পরে generating” করলে দ্বিতীয় ধাপ নতুন unreachable symbol তৈরি করতে পারে, যা আর কেউ মোছে না। নিচের stepper সবচেয়ে ছোট উদাহরণে দুই ক্রম পাশাপাশি দেখায়।

1S → AB ∣ a2A → b3B → bB
এই ধাপের অবস্থা
ক্রম
খুঁজে পাওয়া set
বাকি নিয়ম
  1. Grammar W. B → bB থেকে কখনো বের হওয়া যায় না, তাই B non-generating, আর S → AB কোনো string দেয় না। L(W) = {a}. A নিজে generating (A → b), কিন্তু একমাত্র পথে A-এর পাশে B, তাই A-ও useless. ঠিক ফল হওয়া উচিত শুধু S → a.
  2. ঠিক ক্রম, ৩ক. Generating: A (A → b), S (S → a); B কখনো নয়। B আর যে নিয়মে B আছে (S → AB) মুছে ফেলা হলো। বাকি: S → a, A → b.
  3. ঠিক ক্রম, ৩খ. এখন S থেকে reachable শুধু S, কারণ S → AB আর নেই। A unreachable, মুছে ফেলা হলো। ফল S → a. প্রতিটি symbol useful.
  4. ভুল ক্রম, আগে reachable. মূল W-এ S → AB আছে, তাই A আর B দুটিই reachable. কিছুই মোছা হলো না। পরীক্ষাটি “আসল” derivation দেখেনি, শুধু নিয়মের ডান দিক দেখেছে।
  5. ভুল ক্রম, পরে generating. B non-generating, তাই B আর S → AB মুছল। বাকি S → a, A → b. কিন্তু এখন A-তে পৌঁছানোর একমাত্র পথটি ছিল S → AB, যা এইমাত্র মুছে গেল; A unreachable, অথচ কেউ আর পরীক্ষা করছে না।
  6. তুলনা। দুই ক্রমেই language {a}, কিন্তু ভুল ক্রমে A → b রয়ে গেল, তাই “প্রতিটি symbol useful” দাবি ভাঙল। কারণটি প্রমাণের ৪ নম্বর ধাপ: non-generating মোছা reachability নষ্ট করতে পারে, কিন্তু unreachable মোছা কখনো generating-কে নষ্ট করে না।

পরের ব্লকে drop_nongen আর drop_unreach দুটি আলাদা function, যাতে দুই ক্রমই চালানো যায়। একটি চিহ্ন variable কি না, তা ঠিক হয় grammar-এর key দেখে (X in G), তাই FIND বা NUM-এর মতো বড় হাতের terminal-ও ঠিকভাবে terminal থাকে। প্রথমে G-এর ধাপ ৩, তারপর W-এর দুই ক্রম, আর শেষে বাজারঘরের order-query grammar-এর একটি সত্যিকারের ধরনের bug: একজন developer “district IN ( … )” শর্ত যোগ করেছেন, কিন্তু তালিকার variable L-এর ভিত্তি-নিয়ম (L → STR) লিখতে ভুলে গেছেন; আর পুরোনো phone-field-এর P নিয়মটি রয়ে গেছে, যদিও F আর P-কে ডাকে না।

def drop_nongen(G):
    ok = lambda r, g: all(X in g for X in r.split() if X in G)
    gen = set()
    while gen != (new := {A for A, R in G.items() if any(ok(r, gen) for r in R)}):
        gen = new
    print("  generating:", " ".join(sorted(gen)))
    return {A: [r for r in R if ok(r, gen)] for A, R in G.items() if A in gen}
def drop_unreach(G, start):
    seen, todo = {start}, [start]        # graph search from start
    while todo:
        for X in " ".join(G[todo.pop()]).split():
            if X in G and X not in seen: seen.add(X); todo.append(X)
    print("  reachable: ", " ".join(sorted(seen)))
    return {A: R for A, R in G.items() if A in seen}
G3 = drop_unreach(drop_nongen(G2), start1)
show(G3, "after phase 3 (useless symbols removed):")
print("phase 3:", sum(map(len, G3.values())), "rules, same strings:",
      lang(G3, start1, 7) == L0)
W = {"S": ["A B", "a"], "A": ["b"], "B": ["b B"]}
show(drop_unreach(drop_nongen(W), "S"), "W, right order (generating first):")
show(drop_nongen(drop_unreach(W, "S")), "W, wrong order (reachable first):")
Q = {"Q": ["FIND order WHERE C"], "C": ["C OR T", "T"], "T": ["T AND F", "F"],
     "F": ["( C )", "amount R NUM", "district = STR", "district IN ( L )"],
     "R": ["=", ">=", "<"], "L": ["STR , L"], "P": ["phone = STR"]}
show(drop_unreach(drop_nongen(Q), "Q"), "order-query grammar, cleaned:")

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

  generating: A B D E S S0
  reachable:  A B S0
after phase 3 (useless symbols removed):
  S0 -> ε | AB | bB | b | aA | a | d
  A  -> aA | a
  B  -> bB | b | aA | a
phase 3: 13 rules, same strings: True
  generating: A S
  reachable:  S
W, right order (generating first):
  S  -> a
  reachable:  A B S
  generating: A S
W, wrong order (reachable first):
  S  -> a
  A  -> b
  generating: C F P Q R T
  reachable:  C F Q R T
cleaned order-query grammar:
  Q  -> FIND order WHERE C
  C  -> C OR T | T
  T  -> T AND F | F
  F  -> (C) | amount R NUM | district = STR
  R  -> = | >= | <

প্রথম অংশে G-এর ধাপ ৩: C non-generating, তাই C আর aC-ওয়ালা তিনটি নিয়ম মুছল। তারপর S0 থেকে শুধু A আর B-তে যাওয়া যায়; S, D, E unreachable. লক্ষ করুন, S আর D ধাপ ২-এর আগে মোটেই unreachable ছিল না; ধাপ ২ তাদের নিয়ম S0-এ কপি করে তাদের অপ্রয়োজনীয় করেছে। চূড়ান্ত grammar-এ ১৩টি নিয়ম, আর language এখনো সেই ৯৩টি string. দ্বিতীয় অংশ stepper-এর দুই ক্রম হুবহু দেখায়: ভুল ক্রমে A → b টিকে থাকে। তৃতীয় অংশে order-query grammar: L non-generating (কোনো ভিত্তি নেই, প্রতিটি তালিকা আরেকটি তালিকা চায়), তাই “district IN ( L )” নিয়মটি নীরবে মুছে গেছে; আর P unreachable. Parser generator এমন grammar পেলে কোনো ত্রুটি না দেখিয়েও IN-শর্ত চিনবে না। সমাধান L → STR , L ∣ STR; নিজে Q-তে যোগ করে চালিয়ে দেখুন, “district IN ( L )” ফিরে আসবে।

Emptiness decidable: L(G) = ∅ ঠিক তখনই, যখন S non-generating. Generating set একটি সসীম fixpoint, তাই এটি একটি algorithm, যা সব grammar-এ থামে। অর্থাৎ CFG-এর emptiness problem decidable; পর্ব ২০-এ DFA-র emptiness ছিল reachability, এখানে generating. উপপাদ্য ৫.২-এ L(G) ≠ ∅ ধরা হয়েছিল এই কারণেই: S নিজে non-generating হলে ধাপ (১)-এর পরে start symbol-ই থাকে না, আর উত্তর সোজা “language ফাঁকা”। CFG-এর decision problem-এর পূর্ণ তালিকা পর্ব ৩৭-এ।

৬ · তিন ধাপের স্থির ক্রম — কোন ধাপ কোন আবর্জনা তৈরি করে

এতক্ষণ যা দেখলেন, এক ছবিতে। প্রতিটি ধাপ কিছু আবর্জনা সরায়, কিন্তু পরের ধাপের ধরনের আবর্জনা তৈরি করতে পারে। ক্রমটি এমনভাবে সাজানো, যাতে কোনো ধাপ আগের ধাপের কাজ নষ্ট না করে।

সরলীকরণের পাইপলাইন

নীল, সবুজ আর বেগুনি বাক্স তিনটি ধাপ। হলুদ ফিতায় লেখা, সেই ধাপ পরের ধাপের জন্য কী নতুন আবর্জনা রেখে যেতে পারে।

Simplification pipeline: ε-rules, then unit rules, then useless symbols মূল grammar G ধাপ ১ · ε-নিয়ম দূর nullable → উপসেট বাদ → S0 নতুন unit নিয়ম: S → A ধাপ ২ · unit নিয়ম দূর unit pair → নিয়ম কপি নতুন unreachable: S, D ধাপ ৩ · useless symbol দূর ৩ক · non-generating (আগে) ৩খ · unreachable (পরে) নতুন ε বা unit আসে না G′ : L(G′) = L(G)
ছবি ২৮.২ — তীর একদিকে চলে: প্রতিটি ধাপ শুধু পরের ধাপের ধরনের আবর্জনা তৈরি করতে পারে, আগের ধাপের ধরনের নয়। তাই এক পাসেই কাজ শেষ।
ধাপε-নিয়ম তৈরি করে?Unit নিয়ম তৈরি করে?Useless symbol তৈরি করে?
১ · ε দূরনা (শুধু S0 → ε, যা কোনো ডান দিকে নেই)হ্যাঁ: S → AB থেকে S → A, আর S0 → Sহতে পারে
২ · unit দূরনা: শুধু non-unit নিয়ম কপি হয়, আর S0 → ε শুধু S0-এরনাহ্যাঁ: S আর D unreachable হলো
৩ · useless দূরনানানা (৩ক আগে, ৩খ পরে হলে)

ভুল ক্রমের দুটি পরিণতি এখন স্পষ্ট। যদি useless আগে মুছতেন, তারপর ε আর unit: G-তে ধাপ ২-এর পরে S আর D unreachable হতো, আর grammar-এ আবার useless symbol থাকত। যদি unit আগে, তারপর ε: ε-elimination S → A আর S → B তৈরি করত, আর grammar-এ আবার unit নিয়ম থাকত। দুটি ক্ষেত্রেই language ঠিক থাকে, কিন্তু “পরিষ্কার” দাবিটি ভুল হয়; আবার চালালে অবশ্য পরিষ্কার হয়, কিন্তু তখন আর এক পাসের algorithm থাকে না। পরীক্ষার খাতায় এই পার্থক্যটি প্রায়ই নম্বরের পার্থক্য।

উপপাদ্য ৬.১ (সরলীকরণ)

প্রতিটি CFG G-এর জন্য, যেখানে L(G) ≠ ∅, এমন একটি CFG G′ আছে, যাতে L(G′) = L(G), আর G′-এ (ক) S0 → ε ছাড়া কোনো ε-নিয়ম নেই, এবং S0 থাকলে সেটি কোনো নিয়মের ডান দিকে নেই; (খ) কোনো unit নিয়ম নেই; (গ) কোনো useless symbol নেই। G′ বানানো যায় ধাপ ১, ২, ৩ এই ক্রমে একবার চালিয়ে।

প্রমাণ: ধাপ ১-এর পরে (ক) সত্য আর language একই (উপপাদ্য ৩.২)। ধাপ ২ শুধু non-unit নিয়ম কপি করে; কপি হওয়া একমাত্র ε-নিয়ম S0 → ε, আর (A, S0) unit pair শুধু A = S0-এর জন্য, কারণ S0 কোনো ডান দিকে নেই; তাই (ক) টিকে থাকে, (খ) সত্য হয়, language একই (উপপাদ্য ৪.৩)। ধাপ ৩ শুধু নিয়ম মোছে, তাই (ক) আর (খ) নষ্ট হয় না; (গ) সত্য হয় আর language একই (উপপাদ্য ৫.২)। ∎

এই উপপাদ্যের ফল ব্যবহার হবে সরাসরি। পর্ব ২৯-এ Chomsky normal form-এর রূপান্তর ঠিক এই তিন ধাপের পরে বাকি দুটি কাজ করে: লম্বা ডান দিককে দুই চিহ্নের নিয়মে ভাঙা, আর লম্বা নিয়মের ভেতরের terminal-কে নতুন variable দিয়ে বদলানো। আর আমাদের G-এর চূড়ান্ত রূপটি দেখুন: S0 → ε ∣ AB ∣ bB ∣ b ∣ aA ∣ a ∣ d, A → aA ∣ a, B → bB ∣ b ∣ aA ∣ a. এটি ইতিমধ্যে CNF-এর বেশ কাছে।

৭ · আকারের হিসাব — 2k বিস্ফোরণ আর সময়

প্রথম ধাপ বিনামূল্যে নয়। একটি নিয়মের ডান দিকে k-টি nullable অবস্থান থাকলে 2kটি উপসেট, তাই ২kটি পর্যন্ত নতুন নিয়ম; পুরো ডান দিকটি nullable হলে ফাঁকা উপসেটটি বাদ, তাই 2k − 1. পর্ব ১০-এর subset construction-এর মতোই, “সব সম্ভাব্য উপসেট” মানে exponential. নিচের ব্লক S → X1X2⋯Xk আর প্রতিটি Xi → xi ∣ ε grammar-এ k = 1 থেকে ১০ পর্যন্ত ধাপ ১ চালিয়ে S-এর নিয়ম গোনে। তারপর অংশ ৩-এর সতর্কবার্তার ভুলটি, “একবারে একটি nullable বাদ”, brute force-এ ধরে।

print("S -> X1 X2 ... Xk, every Xi -> xi | ε: rules for S after phase 1")
sizes = []
for k in range(1, 11):
    H = {"S": [" ".join(f"X{i}" for i in range(k))]}
    H.update({f"X{i}": [f"x{i}", ""] for i in range(k)})
    sizes.append(len(remove_eps(H, "S", log=False)[0]["S"]))
print("  k = 1..10:", sizes)
def ai_remove_eps(G, start):             # drops only ONE nullable at a time
    N = nullable(G, log=False)
    H = {A: list(dict.fromkeys(t for r in R for s in [r.split()] for t in
         [r] + [" ".join(s[:i] + s[i+1:]) for i in range(len(s)) if s[i] in N]
         if t)) for A, R in G.items()}
    return ({"S0": [start, ""], **H}, "S0") if start in N else (H, start)
K = {"S": ["A B C"], "A": ["a", ""], "B": ["b", ""], "C": ["c", ""]}
(good, s1), (bad, s2) = remove_eps(K, "S", False), ai_remove_eps(K, "S")
show(bad, "AI-style phase 1:")
want = lang(good, s1, 3)
print("correct phase 1 gives:", sorted(want, key=lambda w: (len(w), w)))
print("AI-style version misses:", sorted(want - lang(bad, s2, 3)))

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

S -> X1 X2 ... Xk, every Xi -> xi | ε: rules for S after phase 1
  k = 1..10: [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023]
AI-style phase 1:
  S0 -> S | ε
  S  -> ABC | BC | AC | AB
  A  -> a
  B  -> b
  C  -> c
correct phase 1 gives: ['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
AI-style version misses: ['a', 'b', 'c']

প্রথম লাইনে সংখ্যাগুলো ঠিক 2k − 1: একটি মাত্র নিয়ম, দশটি nullable চিহ্ন, আর ধাপ ১-এর পরে S-এর ১০২৩টি নিয়ম। দ্বিতীয় অংশে “একবারে একটি” সংস্করণ S → ABC থেকে শুধু চারটি নিয়ম বানিয়েছে; S → A, S → B, S → C নেই, কারণ সেগুলোর জন্য দুটি চিহ্ন একসঙ্গে বাদ দিতে হয়। ফলে a, b, c তিনটি string হারিয়ে গেছে, যদিও মূল grammar এগুলো দেয় (S ⇒ ABC ⇒ aBC ⇒ aC ⇒ a). ভুলটি চোখে দেখতে নিরীহ, কিন্তু brute force এক সেকেন্ডে ধরে।

বিস্ফোরণ এড়ানোর প্রচলিত কৌশল: ε দূর করার আগে লম্বা ডান দিকগুলোকে দুই চিহ্নের নিয়মে ভেঙে নেওয়া, যেমন S → X1Y1, Y1 → X2Y2, … তখন প্রতিটি নিয়মে বড়জোর দুটি nullable অবস্থান, তাই প্রতিটি নিয়ম বড়জোর তিনটি নিয়ম হয়, আর মোট আকার linear-ভাবে বাড়ে। এর অর্থ, CNF রূপান্তরের ধাপগুলোর ক্রম সাবধানে বাছলে মোট আকার polynomial থাকে; কোন ক্রমে ঠিক কতটা, তা পর্ব ২৯-এ। এই পর্বের মানক ক্রম (ε → unit → useless) সঠিক, কিন্তু সবচেয়ে সাশ্রয়ী নাও হতে পারে।

কাজসরল রাউন্ড-পদ্ধতিতে সময়ফলের আকার
Nullable / generating setবড়জোর |V| + 1 রাউন্ড, প্রতিটি O(|G|)একটি set
ε-eliminationনতুন নিয়মের সংখ্যার সমানুপাতিকএকটি নিয়ম থেকে 2k − 1 পর্যন্ত
Unit pairপ্রতিটি variable থেকে একটি BFS: O(|V| · |G|)বড়জোর |V|2 জোড়া
Unit-eliminationজোড়া × নিয়মবড়জোর |V| · |R| নিয়ম, অর্থাৎ বর্গাকার বৃদ্ধি
Reachable setএকটি গ্রাফ-খোঁজ: O(|G|)একটি set

এখানে |G| মানে সব নিয়মের মোট দৈর্ঘ্য (প্রতিটি নিয়মের বাঁ আর ডান দিকের চিহ্ন যোগ করে)। আমাদের G-তে unit-elimination ১৬টি নিয়মকে ৩০টি করেছে, কারণ তিনটি variable একই সাতটি কাজের নিয়ম পেয়েছে; ধাপ ৩ তার মধ্যে দুটি variable মুছে ১৩-তে নামিয়েছে।

আরও গভীরে: Nullable আর generating set রাউন্ড ছাড়াই linear সময়ে বের করা যায়: প্রতিটি নিয়মের জন্য একটি counter রাখুন, “ডান দিকের কতগুলো চিহ্ন এখনো প্রমাণিত নয়”, আর একটি variable প্রমাণিত হলে শুধু যে নিয়মগুলোতে সেটি আছে সেগুলোর counter কমান। এটি আসলে Horn formula-র satisfiability পরীক্ষা, যার linear-time algorithm Dowling আর Gallier ১৯৮৪ সালে প্রকাশ করেন বলে পরিচিত; প্রতিটি নিয়ম A → X1⋯Xm একটি Horn clause “X1 ∧ ⋯ ∧ Xm → A”. এই ছকটি compiler-এর dataflow analysis আর Datalog-এর মূল্যায়নেও ফিরে আসে: সবচেয়ে ছোট যে set নিয়মগুলোর অধীনে বদ্ধ, সেটিই উত্তর (least fixed point). Exponential বিস্ফোরণ নিয়ে CNF রূপান্তরের ক্রম কীভাবে বাছতে হয়, তার একটি পরিচিত আলোচনা Lange ও Leiß-এর ২০০৯ সালের প্রবন্ধে।

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

  • Nullable symbol কী, আর কীভাবে বের করবেন? A ⇒∗ ε হলে A nullable; ∅ থেকে শুরু করে A → X1⋯Xm-এর সব Xj nullable হলে A যোগ, যতক্ষণ না কিছু বাড়ে।
  • S → AB, A → a ∣ ε, B → b ∣ ε থেকে ε-নিয়ম দূর করুন। S0 → S ∣ ε, S → AB ∣ A ∣ B, A → a, B → b.
  • Useless symbol মোছার ক্রম কী, আর কেন? আগে non-generating, পরে unreachable; S → AB ∣ a, A → b-তে (B-এর কোনো নিয়ম নেই) উল্টো ক্রমে A থেকে যায়।
  • তিন ধাপ কোন ক্রমে? ε → unit → useless; ε-elimination unit নিয়ম বানায়, unit-elimination unreachable symbol বানায়।
  • একটি CFG-এর language ফাঁকা কি না, কীভাবে জানবেন? S generating কি না দেখুন; এটি একটি algorithm, তাই emptiness decidable.

৮ · AI-এর যুগে grammar সরলীকরণ

AI assistant-কে একটি grammar দিয়ে “simplify করো” বললে সে দ্রুত একটি পরিচ্ছন্ন-দেখতে উত্তর দেয়। দেখতে পরিচ্ছন্ন হলেই ঠিক, এমন নয়। অংশ ৭-এর ব্লকের “একবারে একটি nullable বাদ” ভুলটি এই ধরনের উত্তরে প্রায়ই দেখা যায়; আরও কয়েকটি পরিচিত ভুল নিচের তালিকায়। সবচেয়ে কাজের অভ্যাস: AI যে grammar দিল, সেটি এই পর্বের lang function দিয়ে দৈর্ঘ্য ৬–৮ পর্যন্ত মূল grammar-এর সঙ্গে মেলানো, আর প্রতিটি ধাপের পরে বাকি আবর্জনা আছে কি না দেখা।

AI-এর সাধারণ ভুলকীভাবে ধরবেন
একবারে শুধু একটি nullable চিহ্ন বাদ দেওয়া (S → ABC থেকে S → C আসে না)৩টি nullable চিহ্নের একটি নিয়ম দিয়ে পরীক্ষা: 23 − 1 = 7টি নিয়ম আসছে কি না; brute force-এ missing string
ε ∈ L(G) হলেও S0 → ε না রাখা, বা পুরোনো S-এ S → ε রেখে দেওয়ামূল grammar-এ S nullable কি না দেখুন; ফলাফলে ε আছে কি না, আর ε-নিয়ম শুধু এমন start-এ কি না যা কোনো ডান দিকে নেই
Unit pair-এর transitive অংশ ভুলে যাওয়া (A → B, B → C থাকলে A-তে C-এর নিয়ম না আনা)Unit গ্রাফ এঁকে প্রতিটি variable থেকে reachability নিজে হিসাব করুন
Useless symbol মোছার ক্রম উল্টো, বা তিন ধাপের ক্রম উল্টোচূড়ান্ত grammar-এ আবার generating আর reachable চালান; কিছু মুছলে উত্তর অসম্পূর্ণ
Nullable set-এ শুধু সরাসরি A → ε-ওয়ালা variable রাখা (B → A দিয়ে ছড়ানো বাদ)রাউন্ড ধরে N হাতে হিসাব করুন; অংশ ২-এর stepper-এর মতো
“Simplify করা মানে সবচেয়ে ছোট grammar” জাতীয় দাবি, বা বানানো রেফারেন্সসরলীকরণ ক্ষুদ্রতম grammar দেয় না (ভাবনার প্রশ্ন ৩); দাবি Sipser বা Hopcroft–Motwani–Ullman-এ নিজে মিলিয়ে নিন

AI-কে কাজে লাগানোর ভালো উপায়: প্রতিটি ধাপের মাঝের ফল, প্রতিটি সিদ্ধান্তের কারণ আর নিজে চালানোর মতো যাচাই-কোড চাওয়া।

আমি গণনার তত্ত্ব শিখছি। এই context-free grammar-টি সরল করো (start symbol S): S → ABC ∣ aD A → aA ∣ ε B → bB ∣ A C → c ∣ ε D → Dd E → e ১. প্রথমে nullable set রাউন্ড ধরে দেখাও, প্রতিটি রাউন্ডে কোন নিয়ম কাজে লাগল তা বলো। ২. ε-নিয়ম দূর করো: প্রতিটি নিয়মে nullable অবস্থানের প্রতিটি উপসেট বাদ দিয়ে; ε ∈ L(G) হলে নতুন start S0 → S ∣ ε যোগ করো। ৩. তারপর unit pair-গুলোর তালিকা দাও আর unit নিয়ম দূর করো। ৪. শেষে আগে non-generating, তারপর unreachable symbol মুছো; প্রতিটির কারণ এক লাইনে বলো। ৫. শুধু standard library দিয়ে একটি ছোট Python কোড দাও, যা দৈর্ঘ্য 6 পর্যন্ত মূল আর চূড়ান্ত grammar-এর সব string বানিয়ে তুলনা করে। ৬. কোনো ধাপে নিশ্চিত না হলে স্পষ্ট করে বলো; বানানো রেফারেন্স দিও না।

(নিজে যাচাই করুন: এই grammar-এ nullable set {A, B, C, S}; D non-generating, E unreachable. ঠিক উত্তরে S0-এর ১০টি নিয়ম থাকে: ε, ABC, BC, AC, AB, aA, a, bB, b, c; আর A → aA ∣ a, B → bB ∣ b ∣ aA ∣ a, C → c. দৈর্ঘ্য ৬ পর্যন্ত scratch-এ এটি মূল grammar-এর সঙ্গে মিলেছে। AI-এর উত্তরে নিয়মের ক্রম আলাদা হলে ক্ষতি নেই; set হিসেবে মেলান।)

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

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

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

প্র ০১ε-নিয়ম নিয়ে এত সাবধানতা কেন? Chomsky hierarchy-তে context-free language কীভাবে context-sensitive-এর ভেতরে বসে, যখন CFG-তে ε-নিয়ম চলে কিন্তু context-sensitive grammar-এ চলে না?

পর্ব ০৬-এ দেখেছেন, Type 1 (context-sensitive) grammar-এর একটি প্রচলিত সংজ্ঞায় প্রতিটি নিয়ম α → β-এ |α| ≤ |β|: নিয়ম কখনো string ছোট করে না (noncontracting). এই শর্তের কারণে, একটি string w-এর derivation-এ প্রতিটি sentential form-এর দৈর্ঘ্য বড়জোর |w|, তাই সম্ভাব্য sentential form সসীম, আর membership decidable. A → ε নিয়মটি string এক চিহ্ন ছোট করে, তাই এই সংজ্ঞায় নিষিদ্ধ; শুধু start symbol থেকে ε-এর একটি ব্যতিক্রম রাখা হয়, যখন start কোনো ডান দিকে নেই।

তাহলে “প্রতিটি CFL context-sensitive” কথাটি সংজ্ঞা থেকে সরাসরি আসে না: একটি CFG-তে ε-নিয়ম থাকতে পারে, যা noncontracting নয়। ঠিক এখানেই উপপাদ্য ৩.২ দরকার। ε-elimination-এর পরে প্রতিটি নিয়মের ডান দিক অ-ফাঁকা, আর বাঁ দিকে একটি চিহ্ন, তাই |α| = 1 ≤ |β|; grammar-টি noncontracting. S0 → ε থাকলে সেটি ঠিক সেই অনুমোদিত ব্যতিক্রম, কারণ S0 কোনো ডান দিকে নেই। ফলে CFL ⊆ CSL একটি প্রমাণিত ঘটনা, আর তার প্রমাণের হৃদয় এই পর্বের প্রথম ধাপ।

ইতিহাসে ε-নিয়ম দূর করা আর useless symbol মোছার মতো ফলাফল সাধারণত Bar-Hillel, Perles ও Shamir-এর ১৯৬১ সালের “simple phrase structure grammar” বিষয়ক প্রবন্ধের সঙ্গে যুক্ত করা হয়, যেখানে CFL-এর pumping lemma-ও প্রথম এসেছিল; তবে কোন ফল ঠিক কার, তা নিয়ে বইভেদে বর্ণনা আলাদা, তাই নিশ্চিত হতে মূল সূত্র দেখা ভালো। Chomsky-র ১৯৫৯ সালের normal form-ও ε-কে আলাদাভাবে সামলাত বলে বর্ণনা পাওয়া যায়। ব্যবহারিক দিকেও ε-এর গুরুত্ব আছে: LL(1) parser বানাতে nullable set সরাসরি লাগে (পর্ব ৩৮-এর FIRST আর FOLLOW), আর Earley parser-এর ε-নিয়ম সামলানোর একটি সূক্ষ্ম সমস্যা Aycock ও Horspool ২০০২ সালের প্রবন্ধে পরিষ্কারভাবে সমাধান করেন বলে পরিচিত (পর্ব ৪১)।

মূল উপলব্ধি: ε-নিয়ম দূর করা শুধু পরিচ্ছন্নতা নয়; এটি “নিয়ম কখনো string ছোট করে না” নিশ্চয়তা দেয়, যার ওপর CFL ⊆ CSL, membership-এর সসীম খোঁজ আর অনেক parser-এর নকশা দাঁড়িয়ে আছে।

প্র ০২ε-elimination-এ 2k বিস্ফোরণ কি সত্যিকারের বাধা? CNF রূপান্তরে ধাপগুলোর ক্রম বদলালে কী হয়?

অংশ ৭-এর ব্লক দেখিয়েছে, দশটি nullable চিহ্নের একটি মাত্র নিয়ম ১০২৩টি নিয়ম হয়ে যায়। হাতে লেখা ছোট grammar-এ এটি কমই দেখা যায়, কারণ মানুষ সাধারণত দুই-তিন চিহ্নের ডান দিক লেখে। কিন্তু যন্ত্রে বানানো grammar ভিন্ন। EBNF-এর প্রতিটি [ x ] (থাকতেও পারে) একটি nullable variable হয়ে যায় (পর্ব ২৫)। একটি command-এর grammar-এ দশটি ঐচ্ছিক flag পাশাপাশি থাকলেই ঠিক অংশ ৭-এর অবস্থা।

সমাধানটি সরল আর পুরোনো: আগে লম্বা ডান দিককে দুই চিহ্নের নিয়মের শিকলে ভাঙা (binarization), তারপর ε দূর করা। দুই চিহ্নের নিয়ম থেকে বড়জোর তিনটি নিয়ম আসে, তাই আকার শুধু একটি ধ্রুবক গুণে বাড়ে। এর দাম: ভাঙার ফলে নতুন variable আসে, যেগুলো নিজেই nullable হতে পারে, তাই nullable set আবার হিসাব করতে হয়। CNF রূপান্তরের মানক বর্ণনায় (যেমন Sipser-এ) ধাপগুলোর ক্রম আলাদা, আর কোন ক্রমে আকার কত, তা নিয়ে শিক্ষামূলক সাহিত্যে আলোচনা আছে; Lange ও Leiß-এর ২০০৯ সালের প্রবন্ধ দেখায়, ক্রম সাবধানে বাছলে CNF grammar-এর আকার মূল grammar-এর আকারের বর্গের মধ্যে রাখা যায়, আর ভুল ক্রমে exponential হতে পারে বলে পরিচিত। এই হিসাবের বিস্তারিত সীমা পর্ব ২৯-এ, সাবধানী ভাষায়।

একই ধরনের ঘটনা অন্য জায়গাতেও দেখেছেন। NFA থেকে DFA (পর্ব ১০) সবচেয়ে খারাপ ক্ষেত্রে 2n state দেয়, আর সেখানে এটি অনিবার্য, কারণ কিছু language-এর ছোট NFA আছে কিন্তু ছোট DFA নেই। ε-elimination-এর বিস্ফোরণ সেরকম অনিবার্য নয়; এটি গঠনের একটি দুর্বলতা, যা ভালো ক্রম দিয়ে এড়ানো যায়। এই পার্থক্য চেনা একটি মূল্যবান দক্ষতা: “এই রূপান্তর exponential” শুনলে প্রশ্ন করুন, এটি সমস্যার ধর্ম, নাকি শুধু এই algorithm-এর?

মূল উপলব্ধি: সব উপসেট নেওয়া মানে exponential, কিন্তু উপসেটের মাপ ছোট রাখলে (দুই চিহ্নের নিয়ম) বিস্ফোরণ থামে। রূপান্তরের ধাপগুলোর ক্রম শুধু সঠিকতার প্রশ্ন নয়, খরচেরও।

প্র ০৩সরলীকরণের পরে কি grammar সবচেয়ে ছোট হয়? DFA-র মতো একটি “minimal CFG” কেন বের করা যায় না?

না, আর এই পার্থক্যটি গভীর। সরলীকরণ শুধু তিন রকম নির্দিষ্ট আবর্জনা সরায়; আমাদের G-তে নিয়মের সংখ্যা ১১ থেকে ১৩ হয়েছে, অর্থাৎ বেড়েছে। একই language a∗b∗a∗ ∪ {d}-এর আরও ছোট grammar সহজেই লেখা যায়। সরলীকরণের লক্ষ্য “ছোট” নয়, “নিয়মিত আকার”: পরের রূপান্তর আর প্রমাণের জন্য সুবিধাজনক রূপ।

DFA-র ক্ষেত্রে পর্ব ১৯-এ দেখেছেন, প্রতিটি regular language-এর একটি অনন্য minimal DFA আছে (isomorphism পর্যন্ত), আর Hopcroft-এর algorithm তা দক্ষভাবে বের করে। CFG-তে এর কোনো সাধারণ সমতুল্য নেই। কারণটি পর্ব ৫৪-এ প্রমাণ হবে: দুটি CFG একই language দেয় কি না, এমনকি একটি CFG Σ∗-এর সব string দেয় কি না, এই প্রশ্নগুলো undecidable. যদি সব CFG-র জন্য একটি “সবচেয়ে ছোট সমতুল্য grammar” বের করার algorithm থাকত, তবে Σ∗-এর জন্য একটি নির্দিষ্ট ছোট grammar-এর সঙ্গে মিলিয়ে universality-র মতো প্রশ্নও সমাধান করা যেত। তাই সাধারণভাবে minimal CFG বের করা algorithm দিয়ে সম্ভব নয়।

একটি সসীম ক্ষেত্রেও প্রশ্নটি কঠিন। “একটি মাত্র string তৈরি করে এমন সবচেয়ে ছোট CFG” হলো smallest grammar problem, যা data compression-এর সঙ্গে জড়িত (grammar-ভিত্তিক compression-এ পুনরাবৃত্ত অংশগুলো variable হয়ে যায়)। Charikar ও সহকর্মীদের ২০০৫ সালের প্রবন্ধে এটি NP-hard দেখানো হয়েছে বলে পরিচিত, আর approximation-এর সীমা নিয়েও সেখানে আলোচনা আছে। অর্থাৎ এক string-এর জন্যও কোনো দ্রুত সঠিক algorithm জানা নেই (P ≠ NP না জানা পর্যন্ত এর বেশি বলা যায় না)।

মূল উপলব্ধি: Grammar সরলীকরণ একটি নির্দিষ্ট, সবসময় থামে এমন পরিষ্কারের কাজ; “সবচেয়ে ছোট grammar” একটি সম্পূর্ণ ভিন্ন, সাধারণভাবে uncomputable প্রশ্ন। Regular জগতের সুন্দর minimization context-free জগতে আসে না।

প্র ০৪বাস্তবের parser generator কি useless symbol বা ε নিয়ে কিছু বলে? বাজারঘরের দলের জন্য এর ব্যবহারিক শিক্ষা কী?

হ্যাঁ। GNU Bison-এর মতো yacc-ধারার parser generator grammar পড়ার সময় useless nonterminal আর useless rule খোঁজে, আর “nonterminal useless in grammar” বা “rule useless in grammar” ধরনের সতর্কবার্তা দেয়; মূলত এই পর্বের ধাপ ৩-এর হিসাব। কিন্তু এটি সতর্কবার্তা, ত্রুটি নয়: build চলতে থাকে, আর সতর্কবার্তার লম্বা তালিকার মাঝে এটি সহজেই চোখ এড়িয়ে যায়। অংশ ৫-এর order-query উদাহরণে ঠিক এটিই বিপজ্জনক: L → STR , L-এ ভিত্তি-নিয়ম না থাকায় পুরো “district IN ( … )” শর্তটি language থেকে নীরবে বাদ পড়েছে, অথচ grammar file দেখতে সম্পূর্ণ মনে হয়।

Nullable set-এরও সরাসরি ব্যবহার আছে। LL(1) parser-এর FIRST আর FOLLOW set (পর্ব ৩৮) হিসাব করতে প্রথমেই জানতে হয় কোন variable ফাঁকা হতে পারে; কারণ A → BC-তে B nullable হলে C-এর প্রথম token-ও A-এর প্রথম token হতে পারে। LR parser generator-ও (পর্ব ৩৯) ε-নিয়মকে সরাসরি সামলায়, grammar না বদলে; তাই বাস্তবের parser generator সাধারণত ব্যবহারকারীর grammar-এ ধাপ ১ বা ধাপ ২ চালায় না, কারণ তাতে parse tree-র আকার বদলে যেত আর semantic action-গুলো (প্রতিটি নিয়মের সঙ্গে জোড়া কোড) ভুল জায়গায় চলে যেত। সরলীকরণ তাই মূলত তত্ত্ব, CYK-এর মতো algorithm আর প্রমাণের জন্য; বাস্তবের grammar-এ এর সবচেয়ে বড় কাজ “আবর্জনা খোঁজা”, “আবর্জনা নিজে থেকে বদলানো” নয়।

বাজারঘরের দলের জন্য একটি সহজ নিয়ম দাঁড়ায়: grammar-এর প্রতিটি পরিবর্তনের পর continuous integration-এ একটি ছোট পরীক্ষা চালানো, যা generating আর reachable set হিসাব করে আর কোনো useless symbol থাকলে build ব্যর্থ করে। সঙ্গে কয়েকটি নমুনা query, যেমন একটি IN-শর্ত, parser-এ চালিয়ে দেখা। প্রথম পরীক্ষা কাঠামোর ভুল ধরে, দ্বিতীয়টি অর্থের ভুল।

মূল উপলব্ধি: বাস্তবের tool এই পর্বের algorithm-গুলো ব্যবহার করে মূলত ভুল ধরতে। Useless symbol প্রায় সবসময় একটি bug-এর চিহ্ন, তাই সতর্কবার্তাকে ত্রুটির মতো গুরুত্ব দিন।

প্র ০৫Nullable, generating, reachable আর unit pair — চারটি algorithm একই রকম দেখায় কেন? এর পেছনের সাধারণ গণিত কী?

চারটি algorithm-ই একটি ছকে পড়ে: একটি সসীম set, একটি একঘেয়ে (monotone) নিয়ম “এই শর্ত পূর্ণ হলে এই সদস্য যোগ করো”, আর বারবার খাটানো যতক্ষণ না কিছু বাড়ে। গণিতে এর নাম least fixed point: সবচেয়ে ছোট যে set নিয়মটির অধীনে বদ্ধ। সসীম set-এ একঘেয়ে নিয়ম সবসময় এমন একটি বিন্দুতে থামে, আর এর সাধারণ রূপটি Knaster–Tarski fixed-point theorem-এর একটি সহজ বিশেষ ক্ষেত্র। Nullable-এ শুরু ∅, generating-এ শুরু Σ, reachable-এ শুরু {S}, আর unit pair-এ প্রতিটি variable থেকে শুরু {A}.

যুক্তিবিদ্যার ভাষায় প্রতিটি নিয়ম একটি Horn clause: “B আর C nullable হলে A nullable”. পুরো হিসাবটি তাই একটি Horn-SAT-এর সবচেয়ে ছোট সত্য-মূল্যায়ন খোঁজা, যা linear সময়ে করা যায় (আরও গভীরে বাক্সে Dowling–Gallier). Datalog নামের query ভাষা ঠিক এই ছকে চলে, আর compiler-এর dataflow analysis-ও (কোন variable কোথায় “জীবিত”, কোন কোড কখনো পৌঁছানো যায় না) একই ধরনের fixpoint হিসাব। মডিউল ১৩-এর program analysis-এর পর্বে (পর্ব ৭৮) দেখবেন, compiler যে “unreachable code” সতর্কবার্তা দেয়, তার যুক্তি এই পর্বের reachable set-এর নিকট আত্মীয়; তবে program-এর ক্ষেত্রে আসল প্রশ্ন সাধারণভাবে undecidable, তাই সেখানে নিরাপদ আনুমানিক উত্তর নেওয়া হয়।

দুটি প্রমাণ-ছকও তাই বারবার একই। Soundness: রাউন্ডের ওপর induction, “যা যোগ হয়েছে তা সত্যি”। Completeness: সাক্ষীর (derivation-এর) দৈর্ঘ্যের ওপর induction, “যা সত্যি তা কোনো এক রাউন্ডে যোগ হয়”। একবার ছকটি চিনলে নতুন fixpoint algorithm-এর সঠিকতা প্রমাণ প্রায় যান্ত্রিক হয়ে যায়, আর পরীক্ষায় একই কাঠামো পাঁচ জায়গায় খাটানো যায়।

মূল উপলব্ধি: এই পর্বের algorithm-গুলো একটি সাধারণ গাণিতিক বস্তুর চারটি রূপ, least fixed point. ছকটি চিনলে grammar, logic, database আর compiler, চার জায়গায় একই চিন্তা খাটে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। simplify_eps.py ব্লকের G বদলে নিজের উত্তর যাচাইও করতে পারেন।

  1. পূর্ণ সরলীকরণ: G: S → AbA ∣ C, A → aA ∣ B, B → b ∣ ε, C → aC, E → a. তিনটি ধাপ ঠিক ক্রমে খাটিয়ে একটি grammar গঠন করুন, যাতে ε-নিয়ম, unit নিয়ম আর useless symbol নেই। প্রতিটি ধাপের মাঝের ফল লিখুন।

    ধাপ ১: রাউন্ড ১-এ B (B → ε), রাউন্ড ২-এ A (A → B); S nullable নয় (AbA-তে b, আর C-তে কিছুই ফাঁকা হয় না)। তাই N = {A, B}, আর S0 লাগে না। S → AbA-র দুটি nullable অবস্থান থেকে চারটি নিয়ম: AbA, bA, Ab, b. ফল: S → AbA ∣ bA ∣ Ab ∣ b ∣ C, A → aA ∣ a ∣ B, B → b, C → aC, E → a.

    ধাপ ২: Unit নিয়ম S → C আর A → B. Unit pair: S: S, C; A: A, B. ফল: S → AbA ∣ bA ∣ Ab ∣ b ∣ aC, A → aA ∣ a ∣ b, B → b, C → aC, E → a.

    ধাপ ৩: Generating: B, E, A, S; C নয় (C → aC). C আর S → aC মোছা। তারপর S থেকে reachable শুধু S আর A; B (আর কেউ ডাকে না) আর E মোছা। চূড়ান্ত: S → AbA ∣ bA ∣ Ab ∣ b, A → aA ∣ a ∣ b.

    Scratch-এ দৈর্ঘ্য ৬ পর্যন্ত মূল আর চূড়ান্ত grammar-এর language মিলেছে (৫৬টি string). লক্ষ করুন, B ধাপ ২-এর পরেই unreachable হয়েছে, ঠিক অংশ ৬-এর সারণির মতো।

  2. প্রমাণ: ধরুন G1-এর প্রতিটি symbol generating. G1 থেকে S থেকে unreachable সব symbol আর তাদের নিয়ম মুছে G2 পাওয়া গেল। প্রমাণ করুন, G2-এর প্রতিটি symbol G2-এর ভেতরেই generating. এরপর এক বাক্যে বলুন, এই ফল কেন “আগে generating, পরে reachable” ক্রমের ন্যায্যতা দেয়।
    1. X ∈ G2 নিন। X G1-এ generating, তাই G1-এ একটি derivation X ⇒∗ w আছে, w ∈ Σ∗. — অনুমান
    2. এই derivation-এ আসা প্রতিটি variable Y X থেকে reachable, কারণ Y কোনো sentential form-এ আছে, যা X থেকে derive হয়েছে। — reachable-এর সংজ্ঞা
    3. X ∈ G2, তাই X S থেকে reachable; reachability transitive, তাই Y-ও S থেকে reachable, আর Y ∈ G2. — transitivity
    4. Derivation-এর প্রতিটি নিয়মের বাঁ দিক এমন একটি Y, আর ডান দিকের সব variable-ও এমন; তাই প্রতিটি নিয়ম G2-এ টিকে আছে। ফলে X ⇒∗G2 w. ∎ — ধাপ ৩খ শুধু unreachable-এর নিয়ম মোছে

    ন্যায্যতা: unreachable মোছা generating-কে নষ্ট করে না, কিন্তু non-generating মোছা reachability নষ্ট করতে পারে (W-এর উদাহরণ), তাই যে ধাপ অন্যটিকে নষ্ট করতে পারে, সেটি আগে।

  3. Output অনুমান: simplify_eps.py-এর প্রথম তিন লাইনে G-এর জায়গায় G = {"S": ["A B C d"], "A": ["a", ""], "B": ["A A"], "C": ["c"]} বসালে কোন রাউন্ড-লাইনগুলো ছাপা হবে, আর "after phase 1" অংশে S আর B-এর নিয়ম কী হবে? S0 তৈরি হবে কি?

    রাউন্ড ১-এ A (A → ε), রাউন্ড ২-এ B (B → AA, দুটিই A). C আর S কখনো নয়: c আর d terminal. তাই দুটি লাইন: round 1: N = ['A'] আর round 2: N = ['A', 'B'].

    S → ABCd-তে nullable অবস্থান দুটি (A আর B), তাই চারটি নিয়ম: S -> ABCd | BCd | ACd | Cd. B → AA-তে দুটি অবস্থান: কিছু না বাদ দিলে AA, একটি বাদ দিলে A (দুবার আসে, একবার রাখা হয়), দুটি বাদ দিলে ফাঁকা, রাখা হয় না: B -> AA | A. A → a, C → c. S nullable নয়, তাই S0 তৈরি হবে না। Scratch-এ চালিয়ে ঠিক এই ফল এসেছে। লক্ষ করুন, B → A একটি নতুন unit নিয়ম, যা ধাপ ২-এ যাবে।

  4. Unit চক্র: G: A → B ∣ a, B → C ∣ b, C → A ∣ c ∣ AB, start A. (ক) unit pair-গুলো লিখুন। (খ) unit নিয়ম দূর করুন। (গ) তারপর useless symbol থাকলে মুছুন।

    (ক) Unit গ্রাফে A → B → C → A একটি চক্র, তাই প্রতিটি variable বাকি দুটিতে পৌঁছায়: A: A, B, C; B: B, C, A; C: C, A, B. মোট ৯টি unit pair.

    (খ) Non-unit নিয়ম: A → a, B → b, C → c ∣ AB. প্রতিটি variable তিনটির সব পায়: A → a ∣ b ∣ c ∣ AB, B → b ∣ c ∣ AB ∣ a, C → c ∣ AB ∣ a ∣ b.

    (গ) তিনটিই generating. কিন্তু A থেকে এখন শুধু AB-এর মাধ্যমে A আর B-তে যাওয়া যায়; C-কে কেউ ডাকে না, কারণ একমাত্র তীর B → C ছিল একটি unit নিয়ম, যা মুছে গেছে। তাই C unreachable, মোছা হয়: A → a ∣ b ∣ c ∣ AB, B → b ∣ c ∣ AB ∣ a. Language: {a, b, c}+; scratch-এ দৈর্ঘ্য ৬ পর্যন্ত মূল grammar-এর সঙ্গে মিলেছে (১০৯২টি string).

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

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

ক্রমএকটি CFG-এর পূর্ণ সরলীকরণের কাজগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. Nullable set রাউন্ড ধরে বের করা
  2. প্রতিটি নিয়মে nullable অবস্থানের উপসেট বাদ দিয়ে নিয়ম বানানো, দরকারে S0 → S ∣ ε
  3. Unit গ্রাফ থেকে unit pair বের করা
  4. Unit নিয়মের জায়গায় non-unit নিয়ম কপি করা
  5. Non-generating symbol আর তাদের নিয়ম মোছা
  6. Start থেকে unreachable symbol মোছা

G: S → AB ∣ a, A → aA ∣ ε, B → A ∣ b. G-এর nullable set কোনটি?

  • {A}
  • {A, B}
  • {A, S}
  • {A, B, S}

S → ABC নিয়মে A, B, C তিনটিই nullable. ε-elimination-এর পরে এই একটি নিয়ম থেকে S-এর কয়টি নিয়ম আসবে?

  • ৪
  • ৮
  • ৭
  • ৩

W: S → AB ∣ a, A → b, B → bB. Useless symbol মোছার কোন ক্রম শেষে শুধু S → a রেখে যায়?

  • আগে unreachable মোছা, তারপর non-generating
  • আগে non-generating মোছা, তারপর unreachable
  • যেকোনো ক্রম, ফল একই
  • শুধু non-generating মোছা, reachable দেখার দরকার নেই

একটি CFG G-তে S nullable. গঠন ৩.১-এর মতো সব ε-নিয়ম দূর করে S0 যোগ না করলে নতুন grammar G′-এর language কী?

  • L(G) − {ε}
  • L(G)
  • L(G)-এর একটি অজানা উপসেট, অনেক string হারাতে পারে
  • L(G) ∪ {ε}

G: A → B ∣ a, B → C, C → c (start A; কোনো ε-নিয়ম নেই)। Unit নিয়ম দূর করার পরে A-এর নিয়ম কী?

  • A → a ∣ B
  • A → a
  • A → a ∣ c
  • A → a ∣ C

G: S → aS ∣ AB, A → a, B → bB. L(G) সম্পর্কে কোনটি সঠিক?

  • L(G) = {a}+
  • L(G) = ∅, কারণ S non-generating
  • L(G) = {anab : n ≥ 0}
  • L(G) ফাঁকা কি না, তা কোনো algorithm বলতে পারে না

শব্দকোষ

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

মনে রাখুন

  1. তিন রকম আবর্জনা: ε-নিয়ম A → ε, unit নিয়ম A → B, আর useless symbol, যা start থেকে পৌঁছানো যায় না বা কোনো terminal string-এ শেষ হয় না।
  2. Nullable, generating, reachable আর unit pair, চারটিই fixpoint হিসাব: একটি set, একটি “যোগ করো” নিয়ম, আর কিছু না বাড়া পর্যন্ত পুনরাবৃত্তি।
  3. ε দূর: প্রতিটি নিয়মে nullable অবস্থানের প্রতিটি উপসেট বাদ দিয়ে নিয়ম; ফল L(G) − {ε}, তাই S nullable হলে S0 → S ∣ ε. k-টি nullable অবস্থান থেকে 2k − 1টি পর্যন্ত নিয়ম।
  4. Unit দূর: প্রতিটি unit pair (A, B)-এর জন্য B-এর non-unit নিয়ম A-তে কপি; unit pair মানে unit গ্রাফে reachability, আর এটি ε দূর করার পরেই ঠিক।
  5. ক্রম স্থির: ε → unit → useless, আর useless-এর ভেতরে আগে non-generating, পরে unreachable. S generating না হলে L(G) = ∅, তাই CFG-এর emptiness decidable.

পরের পর্বে: Chomsky normal form: প্রতিটি নিয়ম A → BC বা A → a. এই পর্বের তিন ধাপের পরে লম্বা নিয়ম ভাঙা আর terminal আলাদা করা, ধাপে ধাপে, আর কেন CNF-এ দৈর্ঘ্য n-এর string-এর derivation ঠিক 2n − 1 ধাপের।

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

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