এই পর্বে যা শিখবেন
- Ambiguity-র formal definition, আর কেন এটি grammar-এর ধর্ম, language-এর নয়
- দুটি গাছের দুটি মান হিসাব করা, আর ambiguous grammar-এ গাছের সংখ্যা Catalan সংখ্যা কেন
- Precedence আর associativity-র স্তর দিয়ে একটি unambiguous grammar নকশা আর তার প্রমাণের রূপরেখা
- Dangling else-এর দুই গাছ, আর matched/unmatched grammar দিয়ে সমাধান
- Ambiguity কেন undecidable, আর inherently ambiguous language কী
১ · এক লেখা, দুই অর্থ — ambiguity কেন সমস্যা
মা বাজারের ফর্দে লিখলেন: “পুরোনো চাল আর ডাল আনবে।” দোকানে গিয়ে আপনি থমকে গেলেন। “পুরোনো” কি শুধু চালের বিশেষণ, নাকি চাল আর ডাল দুটোরই? বাক্যটি একটিই, কিন্তু পড়ার দুটি গঠন: [পুরোনো চাল] আর [ডাল], অথবা পুরোনো [চাল আর ডাল]। শব্দ বদলায়নি, বদলেছে শুধু কোন অংশ কোন অংশের সঙ্গে জোড়া, অর্থাৎ বাক্যের গাছ।
স্কুলের ক্যালকুলেটরে 2 + 3 × 4 চাপুন। কোনোটিতে উত্তর আসে 14, আবার পুরোনো কিছু সাধারণ ক্যালকুলেটরে, যা প্রতিটি বোতাম চাপার সঙ্গে সঙ্গে হিসাব করে, আসতে পারে 20. দুটি যন্ত্র একই চিহ্নের সারি পড়ছে, কিন্তু মনে মনে আলাদা গাছ বানাচ্ছে: একটিতে গুণ আগে, অন্যটিতে বাঁ থেকে ডানে। গণিতের বইয়ের নিয়ম (গুণ আগে) আসলে একটি গাছ বাছাইয়ের নিয়ম।
পর্ব ২৫-এ গাণিতিক expression-এর দুটি grammar দেখেছেন। ছোটটি, E → E+E ∣ E∗E ∣ (E) ∣ id, পড়তে সহজ, আর একই language তৈরি করে যা স্তরভাগ করা E, T, F grammar করে। কিন্তু সেখানেই বলা হয়েছিল, ছোটটিতে id+id∗id-এর দুটি গাছ আছে। পর্ব ২৬-এ দেখেছেন, parse tree আর leftmost derivation একে অন্যের সঙ্গে এক-এক মেলে, আর compiler বা interpreter গাছ থেকেই অর্থ পড়ে। তাই একটি string-এর দুটি গাছ মানে দুটি সম্ভাব্য অর্থ। এই পর্বের পুরো বিষয় এটিই: এমন grammar চেনা, তার ফল মাপা, ঠিক করা, আর কোথায় ঠিক করা অসম্ভব তা জানা।
বাজারঘরের order-query ভাষাতেও একই ফাঁদ আছে। ধরুন কেউ সংক্ষেপে লিখলেন C → C AND C ∣ C OR C ∣ F. তাহলে নিচের query-র দুটি গাছ:
FIND order WHERE amount >= 1000 AND district = "Dhaka" OR status = "new"
গাছ ক: (amount >= 1000 AND district = "Dhaka") OR status = "new"
গাছ খ: amount >= 1000 AND (district = "Dhaka" OR status = "new")
গাছ ক অনুযায়ী ৫০০ টাকার একটি নতুন (status = "new") রাজশাহীর order ফলাফলে আসবে; গাছ খ অনুযায়ী আসবে না, কারণ amount-এর শর্ত মানছে না। Database একই, query-র লেখা একই, তবু ফলাফলের তালিকা আলাদা। পর্ব ২৫-এর grammar-এ AND-এর নিয়ম OR-এর এক স্তর নিচে রাখা হয়েছিল ঠিক এই কারণে, যাতে শুধু গাছ ক বৈধ হয়। অংশ ৫-এ সেই কৌশলটিই নিয়ম হিসেবে শিখবেন।
২ · Formal definition — দুটি parse tree, দুটি leftmost derivation
একটি context-free grammar G = (V, Σ, R, S) ambiguous, যদি এমন একটি string w ∈ L(G) থাকে, যার দুটি আলাদা parse tree আছে, দুটিরই root S আর yield w. যে grammar ambiguous নয়, সেটি unambiguous: L(G)-এর প্রতিটি string-এর ঠিক একটি parse tree.
পর্ব ২৬-এর সংযোগের উপপাদ্য বলে: প্রতিটি parse tree-র ঠিক একটি leftmost derivation আছে, আর প্রতিটি leftmost derivation ঠিক একটি গাছ দেয়; rightmost derivation-এর ক্ষেত্রেও একই কথা। তাই নিচের তিনটি বাক্য সমতুল্য, আর পরীক্ষায় যেকোনোটি দিয়ে ambiguity দেখানো যায়:
- w-এর দুটি আলাদা parse tree আছে;
- w-এর দুটি আলাদা leftmost derivation আছে;
- w-এর দুটি আলাদা rightmost derivation আছে।
সাধারণ ভুল: “দুটি আলাদা derivation আছে, তাই ambiguous” বলা। প্রায় প্রতিটি grammar-এ একই গাছের অনেক derivation থাকে, শুধু variable বদলানোর ক্রম আলাদা। যেমন একেবারে unambiguous grammar S → AB, A → a, B → b-এ S ⇒ AB ⇒ aB ⇒ ab আর S ⇒ AB ⇒ Ab ⇒ ab দুটি আলাদা derivation, কিন্তু গাছ একটিই। গাছ বা leftmost derivation গুনতে হয়, যেকোনো derivation নয়।
এবার মূল উদাহরণ। Gamb: E → E+E ∣ E∗E ∣ (E) ∣ id, আর w = id+id∗id. নিচের stepper দুটি leftmost derivation পাশাপাশি চালায়। লক্ষ করুন, তৃতীয় ধাপের পরে দুটি derivation একই sentential form-এ পৌঁছায়, তবু তাদের গাছ আলাদা।
1E → E+E2E → E∗E3E → (E)4E → id
| ক (যোগ মূলে) | |
| খ (গুণ মূলে) | |
| খাটানো নিয়ম |
- শুরু। Grammar-এর চারটি নিয়ম, দুটি derivation-ই E থেকে। প্রতিবার সবচেয়ে বাঁয়ের E বদলানো হবে, তাই প্রতিটি derivation একটি গাছের প্রতিনিধি।
- মূল বাছাই। ক প্রথমে E → E+E নেয়: গাছের মূলে যোগ। খ নেয় E → E∗E: মূলে গুণ। এই প্রথম পছন্দই পুরো পার্থক্য; বাকি সব এর ফল।
- ভিন্ন পথ। ক-তে সবচেয়ে বাঁয়ের E এখন যোগের বাঁ অংশ, তাই E → id: id+E. খ-তে সবচেয়ে বাঁয়ের E গুণের বাঁ অংশ, সেখানে E → E+E বসে: E+E∗E.
- একই রূপ। ক ডান অংশে E → E∗E দেয়, খ বাঁয়ের E-তে E → id: দুটিতেই id+E∗E. Sentential form এক, কিন্তু ক-তে ∗ যোগের ডান সন্তানের ভেতরে, খ-তে + গুণের বাঁ সন্তানের ভেতরে।
- একই ধাপ। দুটিতেই সবচেয়ে বাঁয়ের E-তে E → id: id+id∗E. এখান থেকে দুটি derivation হুবহু একই ধাপ নেয়।
- ফল। শেষ E → id: id+id∗id. একই string, দুটি আলাদা leftmost derivation, তাই দুটি আলাদা parse tree. সংজ্ঞা ২.১ অনুযায়ী Gamb ambiguous. ∎
id+id∗id-এর দুটি parse tree
নীল বৃত্ত variable E, সবুজ terminal; ওপরে গাছ ক, নিচে গাছ খ। দুটি গাছের পাতা বাঁ থেকে ডানে একই: id + id ∗ id. id-এর জায়গায় 2, 3, 4 বসালে মান আলাদা।
দুটি গুরুত্বপূর্ণ পর্যবেক্ষণ। প্রথমত, ambiguity grammar-এর ধর্ম। একই language-এর একটি grammar ambiguous আর আরেকটি unambiguous হতে পারে, যেমন Gamb আর স্তরভাগ করা E, T, F grammar. দ্বিতীয়ত, ambiguity দেখাতে একটি string যথেষ্ট, কিন্তু unambiguity দেখাতে প্রতিটি string-এর জন্য একটি যুক্তি লাগে; সাধারণত string-এর দৈর্ঘ্যের ওপর induction. দুটি দিকই অংশ ৪ আর ৫-এ দেখবেন।
৩ · দুই গাছ, দুই ফল — অর্থ হিসাব করে দেখা
গাছ থেকে মান বের করার নিয়ম সহজ: পাতা থেকে ওপরে উঠুন, প্রতিটি node-এ তার সন্তানদের মান নিয়ে সেই node-এর operator খাটান। Compiler যে abstract syntax tree (AST) বানায়, সেটি parse tree-রই সংক্ষিপ্ত রূপ, তাই parse tree আলাদা হলে AST-ও আলাদা, আর তৈরি হওয়া machine code-ও আলাদা। নিচের ব্লক Gamb-এ বিয়োগ যোগ করে (E → E−E) একটি বন্ধনীহীন expression-এর সব গাছ তৈরি করে আর প্রতিটির মান হিসাব করে। বন্ধনীহীন হলে প্রতিটি গাছ মানে “কোন operator মূলে” তার একটি পছন্দ, তারপর দুই পাশে একই কাজ আবার।
import re
# Ambiguous grammar E -> E+E | E-E | E*E | num : every parse tree of a
# flat expression = a choice of which operator sits at the root.
OPS = {"+": lambda a, b: a + b, "-": lambda a, b: a - b,
"*": lambda a, b: a * b}
def all_trees(t): # t = tokens [num, op, num, op, ...]
if len(t) == 1:
return [(t[0], int(t[0]))]
out = []
for k in range(1, len(t), 2): # operator t[k] is the root
for ls, lv in all_trees(t[:k]):
for rs, rv in all_trees(t[k + 1:]):
out.append((f"({ls}{t[k]}{rs})", OPS[t[k]](lv, rv)))
return out
def layered(t): # E -> E+T | E-T | T, T -> T*F | F
def term(t):
v = int(t[0])
for k in range(1, len(t), 2):
v *= int(t[k + 1])
return v
cut = [k for k in range(1, len(t), 2) if t[k] in "+-"]
if not cut:
return term(t)
k = cut[-1] # last top-level + or - is the root
return OPS[t[k]](layered(t[:k]), term(t[k + 1:]))
for s in ["2+3*4", "8-4-2", "2*3+4*5"]:
t = re.findall(r"\d+|[-+*]", s)
trees = all_trees(t)
print(f"{s}: {len(trees)} trees, values {sorted({v for _, v in trees})}")
for e, v in trees:
print(f" {e} = {v}")
print(f" layered grammar: {layered(t)}")আসল আউটপুট (ব্রাউজারের Python):
2+3*4: 2 trees, values [14, 20]
(2+(3*4)) = 14
((2+3)*4) = 20
layered grammar: 14
8-4-2: 2 trees, values [2, 6]
(8-(4-2)) = 6
((8-4)-2) = 2
layered grammar: 2
2*3+4*5: 5 trees, values [26, 46, 50, 70]
(2*(3+(4*5))) = 46
(2*((3+4)*5)) = 70
((2*3)+(4*5)) = 26
((2*(3+4))*5) = 70
(((2*3)+4)*5) = 50
layered grammar: 26
তিনটি শিক্ষা। (১) 2+3∗4-এর দুটি গাছ, মান 14 আর 20; স্কুলের নিয়ম মানে প্রথমটি। (২) 8−4−2-এ একটিই operator, তবু দুটি গাছ: 8−(4−2) = 6 আর (8−4)−2 = 2. এখানে সমস্যা precedence নয়, associativity: একই স্তরের operator পরপর এলে কোনটি আগে। (৩) 2∗3+4∗5-এ তিনটি operator, পাঁচটি গাছ, কিন্তু মান চারটি (70 দুবার), কারণ গুণ নিজে associative; গাছ আলাদা হলেও মান সবসময় আলাদা হয় না। শেষ লাইন layered অংশ ৫-এর স্তরভাগ করা grammar-এর একমাত্র গাছের মান দেয়: শেষের top-level + বা − মূলে, যা ঠিক বাম-সংযোগ। প্রতিটি ক্ষেত্রে সেটি গণিতের প্রচলিত উত্তর।
এবার একটি বাস্তব parser দিয়ে একই জিনিস। Earley parser যেকোনো CFG চালাতে পারে, ambiguous grammar-ও। Python-এর lark library (MIT licence) Earley parser দেয়, আর ambiguity="explicit" দিলে একাধিক গাছ থাকলে সবগুলো একটি _ambig node-এর নিচে রাখে। Lark-এ rule-এর নাম ছোট হাতের, তাই এখানে s মানে E; ? একক-সন্তানের node মুছে দেয়, আর -> add node-এর নাম ঠিক করে। নিচের project ডেস্কটপে uv দিয়ে বানানো।
import sys
from lark import Lark, __version__
from lark.visitors import CollapseAmbiguities
print("lark", __version__, "| Python", sys.version.split()[0])
def parser(g): # Earley keeps every tree when ambiguity="explicit"
return Lark(g, start="s", parser="earley", ambiguity="explicit")
amb = parser(r"""?s: s "+" s -> add | s "*" s -> mul | "(" s ")" | ID
ID: "id" """)
lay = parser(r"""?s: s "+" t -> add | t
?t: t "*" f -> mul | f
?f: "(" s ")" | ID
ID: "id" """)
print("== E -> E+E | E*E | (E) | id : id+id*id")
print(amb.parse("id+id*id").pretty())
print("== layered E, T, F : id+id*id")
print(lay.parse("id+id*id").pretty())
for k in range(1, 6):
w = "+".join(["id"] * (k + 1))
n1 = len(CollapseAmbiguities().transform(amb.parse(w)))
n2 = len(CollapseAmbiguities().transform(lay.parse(w)))
print(f"{k} plus signs: ambiguous {n1:2} trees, layered {n2}")
# ... the dangling-else part of this file is shown in section 6সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13):
~/bazarghar-toc$ uv run python lark_ambiguity.py
lark 1.3.1 | Python 3.12.13
== E -> E+E | E*E | (E) | id : id+id*id
_ambig
add
id
mul
id
id
mul
add
id
id
id
== layered E, T, F : id+id*id
add
id
mul
id
id
1 plus signs: ambiguous 1 trees, layered 1
2 plus signs: ambiguous 2 trees, layered 1
3 plus signs: ambiguous 5 trees, layered 1
4 plus signs: ambiguous 14 trees, layered 1
5 plus signs: ambiguous 42 trees, layered 1
_ambig-এর নিচে ঠিক ছবি ২৭.১-এর দুটি গাছ: প্রথমটিতে add মূলে আর mul তার ডান সন্তান, দ্বিতীয়টিতে উল্টো। স্তরভাগ করা grammar একটিই গাছ দেয়, add মূলে। CollapseAmbiguities প্রতিটি _ambig node খুলে সব আলাদা গাছের তালিকা বানায়; তার দৈর্ঘ্য 1, 2, 5, 14, 42, যা পরের অংশের Catalan সংখ্যা। Lark-এর ডিফল্ট (ambiguity="resolve") নিজের অগ্রাধিকারের নিয়মে একটি গাছ নিঃশব্দে বেছে নেয়; তাই ambiguous grammar লিখলে lark কোনো ত্রুটি দেখায় না, শুধু হয়তো আপনার অপ্রত্যাশিত গাছটি দেয়। গাছের সংখ্যা জানতে explicit রূপটি চালানোই নিরাপদ।
৪ · কয়টি গাছ? Catalan সংখ্যা আর একটি unambiguity প্রমাণ
id+id+⋯+id-এ n-টি + থাকলে Gamb-এ কয়টি গাছ? শুধু যোগ থাকলে E → E∗E আর E → (E) কাজে আসে না, তাই আসলে grammar E → E+E ∣ id. ধরুন T(n) = n-টি + আর n + 1টি id-এর গাছের সংখ্যা।
E → E+E ∣ id grammar-এ n-টি + আছে এমন string-এর parse tree-র সংখ্যা
T(n) = Cn = C(2n, n) / (n + 1)
যেখানে C(2n, n) হলো 2n থেকে n বাছাইয়ের সংখ্যা। প্রথম কয়েকটি মান 1, 1, 2, 5, 14, 42, 132, 429, 1430.
প্রমাণ:
- n = 0 হলে string শুধু id, একমাত্র গাছ E → id. তাই T(0) = 1. — ভিত্তি
- n ≥ 1 হলে মূলে E → E+E খাটাতেই হবে (E → id শুধু একটি id দেয়)। মূলের + হলো string-এর n-টি +-এর কোনো একটি, ধরুন বাঁ থেকে (k + 1)-তম, যেখানে 0 ≤ k ≤ n − 1. — মূলের নিয়ম বাছাই
- তাহলে বাঁ সন্তান E-এর yield-এ k-টি +, ডান সন্তানের yield-এ n − 1 − k-টি +. দুই সন্তানের গাছ স্বাধীনভাবে বাছা যায়, তাই এই k-এর জন্য T(k) · T(n − 1 − k)টি গাছ। — গুণের নিয়ম; context-free বলে দুই অংশ স্বাধীন
- আলাদা k মানে মূলের আলাদা +, তাই আলাদা গাছ; যোগ করলে T(n) = Σk=0n−1 T(k) T(n − 1 − k). — যোগের নিয়ম
- এটি ঠিক Catalan সংখ্যার recurrence, একই ভিত্তি C0 = 1 সহ; তাই T(n) = Cn. বদ্ধ রূপ C(2n, n)/(n + 1)-এর প্রমাণ ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫০-এ আছে। ∎ — একই recurrence আর ভিত্তি, তাই একই ধারা
এর সঙ্গে আরেকটি মিল লক্ষ করুন: n-টি operator-এর প্রতিটি গাছ একটি পূর্ণ বন্ধনী বসানো রূপের সঙ্গে মেলে, যেমন ((id+id)+id) বা (id+(id+id)); আর Catalan number n জোড়া মেলানো বন্ধনীর সংখ্যাও গোনে। পর্ব ২৫-এর BAL-এ দৈর্ঘ্য 0, 2, 4, 6, 8-এর string-সংখ্যা 1, 1, 2, 5, 14 এসেছিল একই কারণে। Catalan সংখ্যা মোটামুটি 4n/n1.5 হারে বাড়ে, অর্থাৎ ঘাতের হারে; তাই একটি ambiguous grammar-এ বড় expression-এর সব গাছ তালিকা করা দ্রুত অসম্ভব হয়ে যায়, যদিও Earley বা GLR parser সেগুলো একটি সংক্ষিপ্ত “parse forest”-এ ভাগাভাগি করে রাখতে পারে (পর্ব ৪১)।
নিচের ব্লক যেকোনো ছোট grammar-এর জন্য একটি string-এর parse tree গোনে, dynamic programming দিয়ে: cnt(A, i, j) = A থেকে w-এর i থেকে j পর্যন্ত অংশের কয়টি গাছ। একটি নিয়মের ডান দিক কীভাবে অংশটিকে ভাগ করে, তার প্রতিটি উপায়ে সন্তানদের গাছ-সংখ্যা গুণ হয়, আর সব উপায় যোগ হয়, ঠিক উপপাদ্য ৪.১-এর প্রমাণের মতো। id-এর জায়গায় এক অক্ষরের x, যাতে প্রতিটি terminal এক অক্ষর।
from functools import lru_cache
from math import comb
def trees(G, w, start):
"""Number of parse trees of w (G: no cycles A =>+ A)."""
m = {A: 99 for A in G} # shortest string of A
for _ in G:
for A, R in G.items():
m[A] = min([m[A]] + [sum(m.get(X, 1) for X in r) for r in R])
@lru_cache(None)
def cnt(A, i, j): # trees for A =>* w[i:j]
return sum(seq(tuple(r), i, j) for r in G[A])
@lru_cache(None)
def seq(r, i, j): # ways r derives w[i:j]
if not r:
return int(i == j)
X, rest = r[0], r[1:]
if X not in G: # terminal must match
return seq(rest, i + 1, j) if i < j and w[i] == X else 0
need = sum(m.get(Y, 1) for Y in rest)
return sum(cnt(X, i, k) * seq(rest, k, j)
for k in range(i + m[X], j - need + 1))
return cnt(start, 0, len(w))
AMB = {"E": [["E", "+", "E"], ["E", "*", "E"], ["(", "E", ")"], ["x"]]}
LAY = {"E": [["E", "+", "T"], ["T"]], "T": [["T", "*", "F"], ["F"]],
"F": [["(", "E", ")"], ["x"]]}
print("n string AMB Catalan LAY")
for n in range(9):
w = "+".join("x" * (n + 1))
print(f"{n} {w if n < 6 else w[:11] + '..':13} {trees(AMB, w, 'E'):4}"
f" {comb(2 * n, n) // (n + 1):7} {trees(LAY, w, 'E'):3}")
for w in ["x+x*x", "x*x+x*x", "(x+x)*x"]:
print(f"{w:8} AMB {trees(AMB, w, 'E')} LAY {trees(LAY, w, 'E')}")আসল আউটপুট (ব্রাউজারের Python):
n string AMB Catalan LAY
0 x 1 1 1
1 x+x 1 1 1
2 x+x+x 2 2 1
3 x+x+x+x 5 5 1
4 x+x+x+x+x 14 14 1
5 x+x+x+x+x+x 42 42 1
6 x+x+x+x+x+x.. 132 132 1
7 x+x+x+x+x+x.. 429 429 1
8 x+x+x+x+x+x.. 1430 1430 1
x+x*x AMB 2 LAY 1
x*x+x*x AMB 5 LAY 1
(x+x)*x AMB 1 LAY 1
AMB কলাম n = 8 পর্যন্ত Catalan কলামের সঙ্গে হুবহু মিলেছে, আর LAY প্রতিবার 1. শেষ তিন লাইন দেখায়, গাছের সংখ্যা শুধু operator-এর সংখ্যার ওপর নির্ভর করে, operator কী তার ওপর নয়: x∗x+x∗x-এ তিনটি operator, তাই C3 = 5, ঠিক আগের ব্লকের 2∗3+4∗5-এর মতো। বন্ধনী গাছ বেঁধে দেয়: (x+x)∗x-এ AMB-তেও একটিই গাছ। m হলো প্রতিটি variable-এর সবচেয়ে ছোট string-এর দৈর্ঘ্য; এটি ভাগের সীমা ঠিক করে, যাতে E → E+E খাটাতে গিয়ে একই অংশে E-কে আবার ডেকে অসীম loop না হয়। তাই function-টির একটি শর্ত আছে: grammar-এ A ⇒+ A ধরনের চক্র থাকা চলবে না। এই ব্লকের trees পরের দুটি ব্লকেও কাজে লাগবে।
একটি সতর্কতা: ε-নিয়ম থাকলে গাছের সংখ্যা অসীমও হতে পারে। BAL-এর আরেকটি সহজ-দেখতে grammar S → (S) ∣ SS ∣ ε নিন। “()”-এর একটি গাছ S → (S), S → ε. কিন্তু S → SS, তারপর বাঁয়ের S থেকে “()” আর ডানের S → ε, আরেকটি গাছ; ডানের S-কে আবার SS করে দুটিকেই ε করলে আরেকটি; এভাবে যত ইচ্ছা। তাই এই grammar ambiguous, আর ওপরের function-টি এখানে খাটে না (S ⇒ SS ⇒ S একটি চক্র)। অথচ পর্ব ২৫-এর S → (S)S ∣ ε একই language দেয় আর unambiguous. এর প্রমাণটি দেখার মতো, কারণ unambiguity প্রমাণের ছাঁচ এটিই।
GBAL: S → (S)S ∣ ε unambiguous.
প্রমাণ (|w|-এর ওপর strong induction; দাবি: L(GBAL)-এর প্রতিটি w-এর ঠিক একটি গাছ):
- w = ε হলে মূলে S → (S)S হতে পারে না, কারণ তা অন্তত দুটি বন্ধনী দেয়; তাই একমাত্র গাছ S → ε. — ভিত্তি
- w ≠ ε হলে মূলে S → (S)S, তাই w = (u)v, যেখানে u আর v দুটিই সুষম (দুটিই S থেকে আসে)। — একমাত্র সম্ভাব্য মূল-নিয়ম
- দাবি: এই “)”-এর অবস্থান w নিজেই ঠিক করে দেয়। বাঁ থেকে পড়ে d = (খোলা − বন্ধ) হিসাব রাখুন। “(”-এর পরে d = 1; u সুষম, তাই u-র প্রতিটি prefix-এ d ≥ 1 থাকে আর u-র শেষে d = 1; তারপর “)” পড়ে d = 0. অর্থাৎ এই “)” হলো প্রথম অবস্থান যেখানে d শূন্যে নামে। — u সুষম হওয়ার সংজ্ঞা থেকে
- তাই যেকোনো গাছে u আর v একই, w থেকে একভাবেই পড়া যায়। |u|, |v| < |w|, তাই induction-এ u আর v-এর ঠিক একটি করে গাছ। মূল-নিয়ম, u-র গাছ আর v-এর গাছ সব নির্দিষ্ট, তাই w-এর গাছ একটিই। ∎ — induction hypothesis
ছাঁচটি মনে রাখুন: “মূলে কোন নিয়ম, আর string-টি কোথায় ভাঙবে, দুটিই string নিজে নির্ধারণ করে” দেখান, তারপর ছোট অংশে induction. অংশ ৫-এর স্তরভাগ করা grammar-এর প্রমাণও এভাবেই চলে।
৫ · Ambiguity দূর করা — precedence আর associativity-র স্তর
Expression grammar-এর ambiguity-র দুটি উৎস: ভিন্ন operator-এর মধ্যে কে আগে (operator precedence), আর একই operator পরপর এলে কোন দিক থেকে (associativity). দুটিই grammar-এর গঠনে বাঁধা যায়। ধারণাটি এক বাক্যে: যে operator দুর্বল (পরে হিসাব হয়), তার নিয়ম গাছের ওপরের স্তরে; যে শক্তিশালী, তার নিয়ম নিচে। নিচের stepper ধাপে ধাপে স্তরগুলো বানায়।
1E → E+E ∣ E∗E ∣ (E) ∣ id2E → E+T ∣ T3T → T∗F ∣ F4F → (E) ∣ id
| কাজ | |
| কী বাঁধা হলো |
- শুরু। Gamb-এ সব operator একই variable E-তে। তাই যেকোনো operator যেকোনো স্তরে মূল হতে পারে, আর id+id∗id-এর দুটি গাছ।
- স্তর বাছা। Precedence-এর প্রতিটি ধাপের জন্য একটি variable: E = যোগের স্তর (সবচেয়ে দুর্বল, তাই সবচেয়ে ওপরে), T = গুণের স্তর (term), F = একক বা বন্ধনী (factor). নিয়ম: একটি স্তরের variable শুধু নিজের operator আর ঠিক নিচের স্তরের variable দেখে।
- নিচের স্তর। F → (E) ∣ id. F হলো “অবিভাজ্য টুকরো”: একটি id, অথবা পুরো একটি বন্ধনী। বন্ধনীর ভেতরে আবার E, তাই বন্ধনী দিয়ে যেকোনো operator-কে নিচে নামানো যায়, যেমন (id+id)∗id.
- মাঝের স্তর। T → T∗F ∣ F. একটি T হলো এক বা একাধিক F, ∗ দিয়ে জোড়া। Recursion বাঁ দিকে (T∗F, F∗T নয়), তাই শেষের ∗ মূলে: x∗x∗x = (x∗x)∗x, অর্থাৎ বাম-সংযোগ। ডান অংশ শুধু F, তাই সেখানে আর কোনো ∗ বসতে পারে না।
- ওপরের স্তর। E → E+T ∣ T. একটি E হলো এক বা একাধিক T, + দিয়ে জোড়া, আবার বাঁ দিকে recursion. + কখনো T-এর ভেতরে ঢুকতে পারে না, বন্ধনী ছাড়া; তাই ∗ সবসময় + এর নিচে।
- যাচাই। id+id∗id: মূলে E → E+T বাধ্যতামূলক, কারণ T-তে বন্ধনীর বাইরে + থাকতে পারে না। বাঁ E ⇒ T ⇒ F ⇒ id, ডান T ⇒ T∗F ⇒ ⋯ ⇒ id∗id. একটিই গাছ, অর্থ id+(id∗id). নিচের ব্লকে দৈর্ঘ্য ৭ পর্যন্ত ৬০টি string-এর কোনোটিই ambiguous নয়।
Associativity-র দিক বদলাতে চাইলে recursion-এর দিক বদলান। ঘাত (^) সাধারণত ডান-সংযোগ: 2^3^2 = 2^(3^2) = 2^9. তার জন্য নিয়ম P → F^P ∣ F, যেখানে recursion ডান দিকে; তাহলে প্রথম ^ মূলে আর বাকিটা তার ডান সন্তানে। একটি নিয়ম মনে রাখার মতো: বাঁ-recursion মানে বাম-সংযোগ, ডান-recursion মানে ডান-সংযোগ। (বাঁ-recursion top-down parser-কে অসীম loop-এ ফেলে; সেই সমস্যা আর তার প্রতিকার পর্ব ৩০ আর ৩৮-এ।)
প্রমাণের রূপরেখা (স্তরভাগ করা grammar unambiguous): “Top-level” মানে কোনো বন্ধনীর ভেতরে নয়। তিনটি দাবি একসঙ্গে |w|-এর ওপর induction-এ প্রমাণ হয়। (ক) E থেকে আসা w-এ top-level + থাকলে মূলে E → E+T, আর মূলের + অবশ্যই শেষ top-level +, কারণ ডান সন্তান T-তে কোনো top-level + থাকতে পারে না; না থাকলে মূলে E → T. (খ) T থেকে আসা w-এ একইভাবে শেষ top-level ∗ মূলে, নইলে T → F. (গ) F থেকে আসা w “(” দিয়ে শুরু হলে F → (E), নইলে F → id. প্রতিটি ক্ষেত্রে মূল-নিয়ম আর ভাঙার জায়গা w থেকেই নির্দিষ্ট, আর ছোট অংশগুলোতে induction. উপপাদ্য ৪.২-এর ছাঁচ হুবহু। ভাষা যে বদলায়নি (L(Gamb) = L(স্তরভাগ)), তা দুই দিকের inclusion-এ প্রমাণ হয়; নিচের ব্লক সেটি দৈর্ঘ্য ৭ পর্যন্ত যাচাই করে।
অর্ধেক সমাধানের ফাঁদ: অনেকে (আর অনেক AI assistant) শুধু precedence-এর স্তর বানিয়ে থামেন: E → E+E ∣ T, T → T∗T ∣ F, F → (E) ∣ id. এতে ∗ সবসময় + এর নিচে, তাই id+id∗id-এর গাছ একটি। কিন্তু একই স্তরে E+E রয়ে গেছে, তাই id+id+id-এর দুটি গাছ, আর 8−4−2-এর মতো ক্ষেত্রে দুটি মান। Precedence আর associativity দুটি আলাদা সমস্যা; দুটির জন্যই একটি করে নিয়ম লাগে।
৬ · Dangling else — matched আর unmatched statement
Programming language-এর সবচেয়ে বিখ্যাত ambiguity: dangling else. সরল করা grammar Gite:
এখানে c একটি শর্ত, a একটি সাধারণ statement. “if c then if c then a else a” লেখাটিতে দুটি if আর একটি else. else কি ভেতরের if-এর, নাকি বাইরের? দুটিই grammar মেনে চলে। বাজারঘরের checkout-এ ভাবুন: “যদি কার্ট খালি না হয়, তবে যদি কুপন বৈধ হয়, তবে ছাড় দিন, নইলে বার্তা দেখান।” “নইলে” কি কুপন অবৈধ হলে, নাকি কার্ট খালি হলে? দুটি অর্থে গ্রাহক আলাদা বার্তা দেখবেন।
1S → if c then S2S → if c then S else S3S → if c then M else S4M → if c then M else M ∣ a
| পড়া | |
| গাছ |
- সমস্যা। Gite-এর প্রথম দুটি নিয়ম (লাইন ১ ও ২) দিয়ে “if c then if c then a else a” দুভাবে গড়া যায়। এক else, দুই if: else কার?
- গাছ ১। বাইরের if নেয় S → if c then S (else ছাড়া), আর তার S হলো ভেতরের if c then a else a. else সবচেয়ে কাছের if-এর। C, Java আর বেশিরভাগ ভাষা এই অর্থটিই নেয়।
- গাছ ২। বাইরের if নেয় S → if c then S else S, আর then-এর পরের S হলো ভেতরের if c then a (else ছাড়া)। else দূরের if-এর। grammar একে আটকায় না।
- ধারণা। গাছ ২-এর সমস্যা: then আর else-এর মাঝে একটি else-হীন if বসেছে। তাই নিয়ম করুন, then আর else-এর মাঝে শুধু matched statement M বসবে, যার প্রতিটি if-এর নিজের else আছে: M → if c then M else M ∣ a.
- নতুন grammar. S → if c then S ∣ if c then M else S ∣ a, আর M আগের মতো। else-হীন if শুধু else-এর পরে বা একেবারে বাইরে বসতে পারে, মাঝখানে নয়। Language বদলায়নি, শুধু গাছ বাছাই হলো।
- ফল। গাছ ২ এখন অসম্ভব, কারণ তার then-অংশ “if c then a” একটি M নয়। থাকে শুধু গাছ ১: else সবচেয়ে কাছের জোড়াহীন if-এর। নিচের ব্লক দৈর্ঘ্য ১১ পর্যন্ত (token-এ) যাচাই করে।
একই ভাগ পাঠ্যবইয়ে প্রায়ই তিনটি variable দিয়ে লেখা হয়: S → M ∣ U, M → if c then M else M ∣ a, U → if c then S ∣ if c then M else U. এখানে U মানে unmatched (অন্তত একটি else-হীন if আছে)। ওপরের দুই-variable রূপটি একই language দেয় আর একই রকম unambiguous; scratch-এ ৯টি token পর্যন্ত দুটি grammar-এর প্রতিটি string-এ একটি করে গাছ পাওয়া গেছে। Java-র মানক দলিলের grammar ঠিক এই কৌশল নেয়: সেখানে StatementNoShortIf নামে একটি variable আছে, যা matched statement-এর ভূমিকা পালন করে।
এবার একই প্রকল্পের বাকি অংশ, lark দিয়ে:
ite = parser(r"""?s: "if" "c" "then" s -> if_then
| "if" "c" "then" s "else" s -> if_else
| A
A: "a"
%ignore " " """)
mu = parser(r"""?s: "if" "c" "then" s -> if_then
| "if" "c" "then" m "else" s -> if_else
| A
?m: "if" "c" "then" m "else" m -> if_else
| A
A: "a"
%ignore " " """)
w = "if c then if c then a else a"
print("== dangling else:", w)
print(ite.parse(w).pretty())
print("== matched/unmatched grammar")
print(mu.parse(w).pretty())সত্যিকারের run (একই প্রকল্প, lark 1.3.1; একই run-এর শেষাংশ):
== dangling else: if c then if c then a else a
_ambig
if_then
if_else
a
a
if_else
if_then a
a
== matched/unmatched grammar
if_then
if_else
a
a
Gite-এ _ambig-এর নিচে stepper-এর দুটি গাছ: প্রথমটিতে if_then বাইরে আর if_else ভেতরে (গাছ ১), দ্বিতীয়টিতে উল্টো (গাছ ২; lark একমাত্র সন্তান a-কে একই লাইনে tab দিয়ে ছাপে)। Matched/unmatched grammar-এ শুধু গাছ ১। বাস্তবের parser generator প্রায়ই অন্য পথ নেয়: yacc বা Bison Gite-এর মতো grammar-এ একটি “shift/reduce conflict” জানায়, আর ডিফল্ট হিসেবে shift বেছে নেয়, যার ফল ঠিক গাছ ১ (পর্ব ৩৯-এ এর যান্ত্রিক কারণ)। Python-এ সমস্যাটি ওঠেই না, কারণ indentation-ই ঠিক করে else কোন if-এর।
দুটি সমাধানই (expression-এর স্তর আর matched/unmatched) brute force-এ যাচাই করা যায়: grammar-এর সব string দৈর্ঘ্য n পর্যন্ত বানান, প্রতিটির গাছ গুনুন, আর পুরোনো grammar-এর language-এর সঙ্গে মেলান। এখানে i = “if c then”, e = “else”, a = statement, যাতে প্রতিটি token এক অক্ষর। HALF হলো ওপরের সতর্কবার্তার অর্ধেক সমাধান।
from itertools import product
def lang(G, start, n): # all strings of length <= n
L = {A: set() for A in G}
changed = True
while changed:
changed = 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]):
w = "".join(c)
if len(w) <= n and w not in L[A]:
L[A].add(w); changed = True
return L[start]
def report(name, G, ref, start, n): # same language? how ambiguous?
words = sorted(lang(G, start, n), key=lambda w: (len(w), w))
amb = [w for w in words if trees(G, w, start) > 1]
print(f"{name}: {len(words)} strings, same language:",
set(words) == lang(ref, start, n), f"| ambiguous {len(amb)},",
f"shortest {amb[0] if amb else '-'}")
# precedence only, no associativity: E -> E+E | T, T -> T*T | F
HALF = {"E": [["E", "+", "E"], ["T"]], "T": [["T", "*", "T"], ["F"]],
"F": [["(", "E", ")"], ["x"]]}
report("AMB ", AMB, AMB, "E", 7)
report("HALF", HALF, AMB, "E", 7)
report("LAY ", LAY, AMB, "E", 7)
# dangling else: i = "if c then", e = "else", a = a plain statement
ITE = {"S": [["i", "S"], ["i", "S", "e", "S"], ["a"]]}
MU = {"S": [["i", "S"], ["i", "M", "e", "S"], ["a"]],
"M": [["i", "M", "e", "M"], ["a"]]}
report("ITE ", ITE, ITE, "S", 11)
report("MU ", MU, ITE, "S", 11)আসল আউটপুট (ব্রাউজারের Python):
AMB : 60 strings, same language: True | ambiguous 28, shortest x*x*x
HALF: 60 strings, same language: True | ambiguous 17, shortest x*x*x
LAY : 60 strings, same language: True | ambiguous 0, shortest -
ITE : 116 strings, same language: True | ambiguous 77, shortest iiaea
MU : 116 strings, same language: True | ambiguous 0, shortest -
দৈর্ঘ্য ৭ পর্যন্ত তিনটি expression grammar একই ৬০টি string দেয়। AMB-তে তার ২৮টি ambiguous, HALF-এ এখনো ১৭টি (সবচেয়ে ছোট x∗x∗x, associativity-র সমস্যা; shortlex ক্রমে ∗ আগে আসে বলে x+x+x-এর আগে এটি ছাপা হয়েছে), আর LAY-এ একটিও নয়। ১১টি token পর্যন্ত Gite-এর ১১৬টি string-এর ৭৭টি ambiguous, সবচেয়ে ছোট iiaea, অর্থাৎ ঠিক “if c then if c then a else a”; matched/unmatched grammar একই ১১৬টি string দেয়, একটিও ambiguous নয়। trees আর AMB, LAY এসেছে count_trees.py ব্লক থেকে (একই namespace); তাই এই ব্লক চালালে আগেরটি আগে নিজে থেকেই চলে। মনে রাখবেন, “দৈর্ঘ্য ১১ পর্যন্ত ০টি” প্রমাণ নয়; প্রমাণ অংশ ৫-এর রূপরেখার মতো induction.
৭ · Ambiguity undecidable — PCP-র পূর্বাভাস
এতক্ষণ আমরা প্রতিটি grammar হাতে দেখে ambiguity খুঁজেছি বা দূর করেছি। স্বাভাবিক প্রশ্ন: এমন কোনো program কি লেখা যায়, যা যেকোনো CFG নিয়ে সবসময় থেমে সঠিকভাবে বলে দেবে “ambiguous” বা “unambiguous”? উত্তর না।
AMBIGCFG = {⟨G⟩ : G একটি ambiguous CFG} language-টি undecidable. অর্থাৎ এমন কোনো algorithm নেই, যা প্রতিটি CFG-তে থেমে সঠিকভাবে বলে সেটি ambiguous কি না।
ফলটি ১৯৬২–৬৩ সালের দিকে একাধিক গবেষক প্রায় একই সময়ে, স্বাধীনভাবে, পেয়েছিলেন বলে পরিচিত; সাধারণত David Cantor, Robert Floyd আর Chomsky–Schützenberger-এর নাম উল্লেখ করা হয়। প্রমাণের মূল হাতিয়ার Post correspondence problem (PCP), যা Emil Post ১৯৪৬ সালে undecidable দেখান। পূর্ণ প্রমাণ পর্ব ৫৪-এ; এখানে শুধু গঠনটি দেখে রাখুন, যাতে বোঝেন ambiguity আর PCP কেন একই সমস্যা।
প্রমাণের রূপরেখা: PCP-র একটি instance হলো k-টি ডমিনো (t1, b1), …, (tk, bk); প্রশ্ন: এমন কোনো অ-ফাঁকা ক্রম i1, …, im আছে কি, যাতে ti1⋯tim = bi1⋯bim? প্রতিটি ডমিনোর জন্য একটি নতুন চিহ্ন di নিয়ে grammar বানান:
- A থেকে আসা string-এর শেষের d-চিহ্নগুলো উল্টো ক্রমে বলে দেয় কোন ডমিনো কোন ক্রমে বসেছে; তাই A একা unambiguous, B-ও একা unambiguous. — শেষের চিহ্ন derivation-কে নির্দিষ্ট করে
- তাই কোনো string-এর দুটি গাছ থাকলে একটি A দিয়ে আর অন্যটি B দিয়ে শুরু; অর্থাৎ একই ক্রম i1, …, im-এ ওপরের আর নিচের লেখা মিলেছে, যা PCP-র একটি সমাধান। উল্টো দিকে, PCP-র যেকোনো সমাধান এমন একটি string দেয়। — দুই দিক
- অতএব G ambiguous ⇔ PCP instance-টির সমাধান আছে। Ambiguity decidable হলে PCP-ও decidable হতো, যা সত্য নয়। ∎ — reduction-এর দিক: PCP ≤ AMBIGCFG, তাই AMBIGCFG কঠিন
লক্ষ করুন reduction-এর দিক: আমরা PCP-কে ambiguity-তে রূপান্তর করেছি, উল্টো নয়। এতে ambiguity-র কাঠিন্য প্রমাণ হয়। আর একটি সূক্ষ্ম কথা: AMBIGCFG undecidable হলেও এটি recognizable. String-গুলো দৈর্ঘ্যের ক্রমে একে একে নিয়ে প্রতিটির গাছ গুনুন (ওপরের trees-এর মতো; ε বা unit-চক্র থাকলে আগে পর্ব ২৮-এর সরলীকরণ লাগে); grammar ambiguous হলে কোনো এক সময় দুটি গাছওয়ালা string পাওয়া যাবে আর যন্ত্রটি থামবে। কিন্তু unambiguous হলে এই খোঁজ কখনো শেষ হয় না। তাই brute force ambiguity খুঁজে পেতে পারে, কিন্তু unambiguity কখনো প্রমাণ করতে পারে না; এই পর্বের প্রতিটি “০টি ambiguous” লাইনের পেছনে তাই একটি হাতের প্রমাণ রাখা হয়েছে।
বাস্তবে কী হয়: Parser generator undecidability এড়ায় একটি রক্ষণশীল পরীক্ষা দিয়ে। LR(1) বা LL(1) table-এ কোনো conflict না থাকলে grammar নিশ্চিতভাবে unambiguous; কিন্তু conflict থাকলেই grammar ambiguous নয়, হয়তো শুধু এই পদ্ধতির জন্য কঠিন। অর্থাৎ পরীক্ষাটি কখনো ভুল “unambiguous” বলে না, তবে কিছু সঠিক grammar-কে বাতিল করে। Undecidable সমস্যার কাছে বাস্তব প্রকৌশলের এটিই সাধারণ আপস (পর্ব ৩৮–৩৯, পর্ব ৫৫)।
৮ · Inherently ambiguous language — যে ambiguity সরানো যায় না
Expression আর if-else-এর ক্ষেত্রে আমরা একই language-এর একটি unambiguous grammar পেয়েছি। প্রশ্ন: সবসময় কি পাওয়া যায়? না।
একটি context-free language L inherently ambiguous, যদি L = L(G) এমন প্রতিটি CFG G ambiguous হয়। অর্থাৎ L-এর কোনো unambiguous grammar নেই।
সবচেয়ে পরিচিত উদাহরণ L∪ = {aibjck : i = j অথবা j = k}. এর একটি স্বাভাবিক grammar পর্ব ২৫-এর “ক্ষেত্রভিত্তিক union” কৌশলে আসে:
P অংশ লেখে anbnck (i = j), Q অংশ লেখে aibncn (j = k). প্রতিটি অংশ একা unambiguous. কিন্তু যে string দুটি শর্তই মানে, অর্থাৎ anbncn, সেটি P আর Q দুই পথেই আসে, তাই তার দুটি গাছ। নিচের ব্লক দেখায়, ঠিক এই string-গুলোই ambiguous, আর grammar-টি সত্যিই L∪ দেয়।
# L = {a^i b^j c^k : i = j or j = k} as a union of two grammars.
# Uses trees() and lang() from the two blocks above (shared namespace).
G = {"S": [["P"], ["Q"]],
"P": [["X", "C"]], "X": [["a", "X", "b"], []], "C": [["c", "C"], []],
"Q": [["A", "Y"]], "A": [["a", "A"], []], "Y": [["b", "Y", "c"], []]}
n = 12
want = {"a" * i + "b" * j + "c" * k
for i in range(n + 1) for j in range(n + 1) for k in range(n + 1)
if i + j + k <= n and (i == j or j == k)}
words = sorted(lang(G, "S", n), key=lambda w: (len(w), w))
print(f"length <= {n}: {len(words)} strings, grammar = definition:",
set(words) == want)
amb = [(w, trees(G, w, "S")) for w in words if trees(G, w, "S") > 1]
print("strings with 2+ trees:", ", ".join(f"{w or 'ε'}:{c}" for w, c in amb))আসল আউটপুট (ব্রাউজারের Python):
length <= 12: 93 strings, grammar = definition: True
strings with 2+ trees: ε:2, abc:2, aabbcc:2, aaabbbccc:2, aaaabbbbcccc:2
দৈর্ঘ্য ১২ পর্যন্ত grammar-এর ৯৩টি string সংজ্ঞার সঙ্গে হুবহু মিলেছে, আর দুটি গাছ ঠিক anbncn-এর, n = 0 থেকে 4. ε-ও আছে, কারণ i = j = k = 0 দুটি শর্তই মানে। এখানে grammar-এ ε-নিয়ম আছে কিন্তু কোনো চক্র নেই, তাই trees ঠিক কাজ করে। স্বাভাবিক প্রশ্ন: এই grammar-টি তো একটি নির্দিষ্ট পছন্দ; অন্য কোনো চতুর grammar কি ambiguity এড়াতে পারে? নিচের উপপাদ্য বলে, না।
L∪ = {aibjck : i = j অথবা j = k} inherently ambiguous: যেকোনো CFG G, যার L(G) = L∪, তাতে anbncn আকারের অন্তত একটি string-এর দুটি আলাদা parse tree আছে।
প্রমাণের ধারণা (পূর্ণ প্রমাণ বাদ): যেকোনো grammar-এ বড় p-এর জন্য apbpcp+p! নিন; এটি শুধু i = j শর্তে আছে, তাই এর গাছের পাম্প করা যায় এমন অংশ (পর্ব ৩৬-এর pumping-এর ধারণা) a আর b-কে একসঙ্গে বাড়ায়। একইভাবে ap+p!bpcp-এ পাম্প b আর c-কে একসঙ্গে বাড়ায়। দুই ধরনের পাম্প যথেষ্ট বার খাটিয়ে একই string aNbNcN-এ পৌঁছানো যায়, একবার “a-b জোড়ার” কাঠামো দিয়ে, একবার “b-c জোড়ার” কাঠামো দিয়ে; তারপর দেখাতে হয় দুটি গাছ সত্যিই আলাদা। সতর্কতার জায়গা ঠিক এখানে: সাধারণ pumping lemma পাম্পের অবস্থান বেছে দিতে দেয় না, তাই প্রমাণে Ogden's lemma (পর্ব ৩৬) লাগে, যা কোন অবস্থান “চিহ্নিত” তা ঠিক করতে দেয়। Hopcroft–Motwani–Ullman-এর বইয়ের inherent ambiguity অংশে একটি অনুরূপ language-এর ({anbncmdm} ∪ {anbmcmdn}) পূর্ণ প্রমাণ আছে; এই পর্বের language-এর প্রমাণও একই ছাঁচে চলে।
কোন language inherently ambiguous নয়, তা জানাও কাজের:
- প্রতিটি regular language: DFA থেকে পর্ব ২৫-এর গঠনে যে right-linear grammar আসে, তাতে প্রতিটি string-এর derivation DFA-র একমাত্র run-এর সঙ্গে মেলে, তাই grammar unambiguous (অনুশীলন ২)। খেয়াল করুন: NFA থেকে একই গঠনে আসা grammar ambiguous হতে পারে, কারণ NFA-তে একাধিক run থাকে।
- প্রতিটি deterministic CFL (deterministic PDA যা চেনে; পর্ব ৩৫): এদের LR(1) grammar আছে, আর LR(1) grammar সবসময় unambiguous. তাই inherently ambiguous language কখনো deterministic নয়।
- anbn, BAL, palindrome: S → aSb ∣ ε, S → (S)S ∣ ε, S → aSa ∣ bSb ∣ a ∣ b ∣ ε, সবই unambiguous.
| ধারণা | কার ধর্ম | উদাহরণ | কীভাবে দেখাবেন |
|---|---|---|---|
| Ambiguous grammar | Grammar | E → E+E ∣ E∗E ∣ id | একটি string, দুটি গাছ |
| Unambiguous grammar | Grammar | E, T, F; S → (S)S ∣ ε | প্রতিটি string-এর জন্য induction |
| Inherently ambiguous | Language | {aibjck : i = j অথবা j = k} | প্রতিটি grammar নিয়ে যুক্তি (Ogden's lemma) |
| “Ambiguous কি?” প্রশ্ন | Decision problem | AMBIGCFG | Undecidable, কিন্তু recognizable |
আরও গভীরে: প্রথম inherently ambiguous CFL-এর উদাহরণ Rohit Parikh-এর ১৯৬১ সালের একটি MIT প্রতিবেদনে দেওয়া হয়েছিল বলে পরিচিত, যা পরে ১৯৬৬ সালে তাঁর বিখ্যাত প্রবন্ধে প্রকাশিত হয়। একটি অন্য পথও আছে: unambiguous CFG-এর language-এ প্রতিটি দৈর্ঘ্যের string-সংখ্যার generating function একটি বীজগাণিতিক (algebraic) function হয় (Chomsky–Schützenberger); Philippe Flajolet ১৯৮০-এর দশকে এই ফল উল্টো দিক থেকে ব্যবহার করে, generating function বীজগাণিতিক নয় দেখিয়ে, অনেক language-এর inherent ambiguity প্রমাণ করেন। আর “একটি CFL কি inherently ambiguous?” প্রশ্নটিও সাধারণভাবে undecidable বলে পরিচিত।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- দেখান যে E → E+E ∣ E∗E ∣ (E) ∣ id ambiguous. id+id∗id-এর দুটি leftmost derivation: E ⇒ E+E ⇒ id+E ⇒ ⋯ আর E ⇒ E∗E ⇒ E+E∗E ⇒ ⋯
- একটি unambiguous grammar দিন। E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id; দুর্বল operator ওপরে, বাঁ-recursion মানে বাম-সংযোগ।
- Dangling else কী, আর সমাধান? else কোন if-এর তা অনির্দিষ্ট; matched/unmatched grammar, বা “সবচেয়ে কাছের if” নিয়ম (parser-এ shift).
- Ambiguity কি decidable? না, PCP থেকে reduction; তবে recognizable.
- Inherently ambiguous language-এর উদাহরণ দিন। {aibjck : i = j অথবা j = k}; anbncn-এর দুটি গাছ অনিবার্য।
৯ · AI-এর যুগে ambiguity যাচাই
AI assistant-কে “এই grammar-টি unambiguous করে দাও” বললে সে প্রায় সবসময় আত্মবিশ্বাসী একটি উত্তর দেয়, সঙ্গে “এখন প্রতিটি string-এর একটিই parse tree” জাতীয় দাবি। এই দাবি যাচাই না করে মানা বিপজ্জনক, কারণ অংশ ৭ অনুযায়ী কোনো সাধারণ algorithm-ও এটি নিশ্চিত করতে পারে না; AI তো নয়ই। সবচেয়ে পরিচিত ভুলটি অংশ ৫-এর HALF grammar: শুধু precedence-এর স্তর, associativity বাদ। check_fixes.py ব্লক সেটি সঙ্গে সঙ্গে ধরেছে: ১৭টি ambiguous string, সবচেয়ে ছোট x∗x∗x. AI-এর দেওয়া যেকোনো grammar ওই ব্লকের report-এ বসিয়ে একই পরীক্ষা চালাতে পারেন।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| শুধু precedence ঠিক করে “unambiguous” দাবি (E → E+E ∣ T) | x+x+x আর x∗x∗x-এর গাছ গুনুন; check_fixes.py-এর মতো report চালান |
| “দুটি আলাদা derivation আছে, তাই ambiguous” | Derivation দুটি leftmost কি না, বা গাছ দুটি সত্যিই আলাদা কি না দেখুন |
| নতুন grammar language বদলে ফেলেছে (যেমন বন্ধনী বাদ, বা ε হারিয়েছে) | দৈর্ঘ্য ৭–১১ পর্যন্ত দুই grammar-এর lang set মেলান |
| “Ambiguity পরীক্ষার algorithm আছে” বা “parser generator সব ambiguity ধরে” | উপপাদ্য ৭.১: undecidable; LR conflict-হীনতা শুধু একটি রক্ষণশীল নিশ্চয়তা |
| {anbncn}-কে inherently ambiguous বলা | এটি context-free-ই নয় (পর্ব ৩৬); inherent ambiguity শুধু CFL-এর ধর্ম |
| কোনো CFL-কে inherently ambiguous বলে “প্রমাণ” হিসেবে একটি ambiguous grammar দেখানো | একটি grammar ambiguous হওয়া কিছুই প্রমাণ করে না; প্রতিটি grammar নিয়ে যুক্তি লাগে |
| বানানো সাল, নাম বা রেফারেন্স | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে নিশ্চিত হোন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: grammar-এর সঙ্গে ambiguity-র নির্দিষ্ট সাক্ষী (দুটি গাছ), নতুন grammar-এর unambiguity-র যুক্তি, আর একটি গাছ-গোনার কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: একটি সঠিক উত্তর E → E+T ∣ E−T ∣ T, T → T∗P ∣ P, P → F^P ∣ F, F → (E) ∣ id. Scratch-এ দৈর্ঘ্য ৭ পর্যন্ত এর ২২০টি string মূল grammar-এর সঙ্গে হুবহু মিলেছে, আর প্রতিটির ঠিক একটি গাছ। AI অন্য রূপ দিলে সেটি ভুল না-ও হতে পারে; check_fixes.py-এর report চালিয়ে দেখুন।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১বিভিন্ন programming language dangling else সমস্যার মুখোমুখি কীভাবে হয়েছে? কোন সমাধান কেন বেছে নেওয়া হয়েছিল?
ALGOL 60-এর report প্রকাশের সময় থেকেই সমস্যাটি পরিচিত ছিল। ALGOL 60 একটি কঠোর পথ নেয় বলে পরিচিত: then-এর পরে সরাসরি আরেকটি শর্তযুক্ত statement বসানো যেত না; ভেতরের if লিখতে হলে তাকে begin … end দিয়ে মুড়ে দিতে হতো। ফলে লেখক নিজেই বন্ধনী বসিয়ে অর্থ বেছে নিতেন, আর grammar-এ ambiguity থাকত না। পরে ALGOL 60-এর grammar-এ আরও কিছু সূক্ষ্ম ambiguity আর অস্পষ্টতা খুঁজে পাওয়া যায় বলে পরিচিত; Donald Knuth ১৯৬৭ সালের একটি প্রবন্ধে এমন কিছু “trouble spot”-এর তালিকা করেছিলেন। Formal grammar লিখলেই যে সব ভুল এড়ানো যায় না, এটি তার একটি প্রাথমিক শিক্ষা।
C-এর পথ ভিন্ন। তার grammar-এ সমস্যাটি থেকে যায়, আর মানক দলিল কথায় বলে দেয় else সবচেয়ে কাছের জোড়াহীন if-এর সঙ্গে যাবে। yacc বা Bison দিয়ে এমন grammar চালালে একটি shift/reduce conflict-এর সতর্কবার্তা আসে, আর ডিফল্ট “shift” ঠিক এই অর্থটিই দেয়। এটি সুবিধাজনক, কিন্তু একটি ঝুঁকি আছে: conflict-এর সতর্কবার্তায় অভ্যস্ত হয়ে গেলে নতুন, সত্যিকারের ভুল conflict-ও চোখ এড়িয়ে যায়। তাই অনেক প্রকল্প প্রত্যাশিত conflict-এর সংখ্যা স্পষ্টভাবে ঘোষণা করে রাখে।
Java-র মানক দলিল তৃতীয় পথ নেয়: grammar-কেই unambiguous করা, এই পর্বের matched/unmatched কৌশলে। সেখানে Statement আর StatementNoShortIf আলাদা variable, আর if-then-else-এর then-অংশে শুধু StatementNoShortIf বসতে পারে। Ada, Modula-2 আর অনেক script ভাষা চতুর্থ পথ নেয়: প্রতিটি if-কে একটি বাধ্যতামূলক সমাপ্তি-চিহ্ন (যেমন end if) দিয়ে শেষ করা, ফলে সমস্যাটি গঠনগতভাবেই ওঠে না। Python indentation দিয়ে block বোঝায়, আর একটি পৃথক elif keyword রাখে, তাই সেখানেও কোনো ambiguity নেই। বিভিন্ন সমাধানের মধ্যে আপস: grammar-এর সরলতা, পড়ার স্বচ্ছন্দ্য, আর ভুল লেখার সম্ভাবনা।
মূল উপলব্ধি: একই ambiguity-র চারটি প্রকৌশল-সমাধান আছে: লেখা নিষেধ করা, কথায় নিয়ম দেওয়া (parser-এ shift), grammar unambiguous করা, বা সমাপ্তি-চিহ্ন বাধ্যতামূলক করা। তত্ত্ব বলে চারটিই বৈধ; কোনটি ভালো, তা মানুষের পড়া আর লেখার অভ্যাসের প্রশ্ন।
প্র ০২Grammar ambiguous রেখে আলাদা “precedence ঘোষণা” দিয়ে কাজ চালানো কি স্তরভাগ করা grammar-এর চেয়ে ভালো?
yacc ধারার parser generator-এ একটি জনপ্রিয় বিকল্প আছে: E → E+E ∣ E∗E ∣ (E) ∣ id-এর মতো ছোট, ambiguous grammar রেখে আলাদা লাইনে ঘোষণা দেওয়া, যেমন “+ বাম-সংযোগ, ∗ বাম-সংযোগ আর + এর চেয়ে শক্তিশালী”। Parser generator তখন table বানানোর সময় প্রতিটি conflict এই ঘোষণা দেখে মেটায়। ফল: grammar ছোট, পড়তে সহজ, আর parser-ও দ্রুত, কারণ E ⇒ T ⇒ F ধরনের একক-সন্তানের অনেক ধাপ বাঁচে। দশটি precedence-স্তরের একটি ভাষায় স্তরভাগ করা grammar-এ দশটি variable লাগত, আর প্রতিটি id পড়তে দশটি একক ধাপ।
দাম কী? প্রথমত, grammar আর language-এর সম্পর্ক অস্পষ্ট হয়ে যায়: grammar নিজে একটি ambiguous বস্তু, আর আসল অর্থ নির্ভর করে একটি নির্দিষ্ট parsing algorithm কীভাবে conflict মেটায় তার ওপর। অন্য একটি tool (যেমন একটি LL parser বা একটি formatter) একই grammar পড়ে একই অর্থ পাবে, এমন নিশ্চয়তা নেই। দ্বিতীয়ত, precedence ঘোষণা শুধু operator-জনিত conflict মেটায়; অন্য কোনো অপ্রত্যাশিত ambiguity থাকলে সেটিও হয়তো ঘোষণার ছায়ায় নিঃশব্দে মিটে যায়। তৃতীয়ত, গণিতে প্রমাণ লেখা কঠিন হয়, কারণ “কোন গাছ বৈধ” তা আর grammar থেকে পড়া যায় না।
Earley বা GLR-ভিত্তিক tool-এ (যেমন lark) আরেকটি পথ আছে: সব গাছ বানিয়ে পরে “disambiguation filter” দিয়ে বাছাই, যেমন rule-এর অগ্রাধিকার। এটি সবচেয়ে নমনীয়, কিন্তু ভুল grammar-এ গাছের সংখ্যা Catalan হারে বাড়তে পারে, যা অংশ ৪-এ দেখেছেন। বাস্তবে অনেক দল একটি মিশ্র পথ নেয়: ভাষার মানক দলিলে স্তরভাগ করা, প্রমাণযোগ্য grammar, আর বাস্তব parser-এ গতি ও সরলতার জন্য precedence ঘোষণা; তারপর দুটিকে বড় test-suite দিয়ে মেলানো। বাজারঘরের order-query-র মতো ছোট ভাষায় স্তরভাগ করা grammar-ই সহজ, কারণ মাত্র দুটি স্তর (OR আর AND).
মূল উপলব্ধি: Precedence ঘোষণা আর স্তরভাগ একই অর্থ দিতে পারে, কিন্তু প্রথমটিতে অর্থ থাকে tool-এর আচরণে, দ্বিতীয়টিতে grammar-এর গঠনে। যেখানে একাধিক tool বা গাণিতিক নিশ্চয়তা দরকার, সেখানে গঠনই নিরাপদ।
প্র ০৩মানুষের ভাষায় ambiguity কতটা সাধারণ, আর natural language processing এর মোকাবিলা কীভাবে করেছে?
মানুষের ভাষা ambiguity-তে ভরা, আর আমরা প্রসঙ্গ দিয়ে তা প্রায় না ভেবেই মিটিয়ে ফেলি। ইংরেজির পরিচিত উদাহরণ “I saw the man with the telescope”: telescope কি দেখার যন্ত্র, নাকি লোকটির হাতে? বাংলায় “পুরোনো চাল আর ডাল” বা “লাল শাড়ি আর ব্লাউজ” একই ধাঁচের: বিশেষণটি কতদূর পর্যন্ত খাটবে। এগুলো ঠিক grammar-এর ambiguity, শব্দের অর্থের নয়: শব্দ এক, গাছ আলাদা। এর পাশে আছে শব্দের ambiguity (“কল” মানে পানির কল, ফোন কল, না যন্ত্র?), যা grammar-এর বাইরের বিষয়।
বাক্য লম্বা হলে গাছের সংখ্যা দ্রুত বাড়ে। Kenneth Church আর Ramesh Patil-এর ১৯৮২ সালের একটি পরিচিত প্রবন্ধ দেখিয়েছিল, পরপর অনেক prepositional phrase-যুক্ত বাক্যে সম্ভাব্য গঠনের সংখ্যা Catalan সংখ্যার মতো বাড়ে, ঠিক অংশ ৪-এর id+id+⋯+id-এর মতো। তাই ১৯৮০ আর ১৯৯০-এর দশকে computational linguistics-এ দুটি কৌশল প্রধান হয়: সব গাছ একটি parse forest-এ ভাগাভাগি করে রাখা (chart parsing, পরে Earley আর GLR-এর ধারণা), আর probabilistic CFG দিয়ে প্রতিটি গাছের একটি সম্ভাবনা হিসাব করে সবচেয়ে সম্ভাব্যটি বাছা। অর্থাৎ ambiguity “দূর” করা হয়নি, তাকে মেনে নিয়ে মাপা হয়েছে।
Programming language-এর দৃষ্টিভঙ্গি ঠিক উল্টো: সেখানে প্রতিটি program-এর ঠিক একটি অর্থ থাকতে হবে, তাই ambiguity গ্রহণযোগ্য নয়। এই পার্থক্যই ব্যাখ্যা করে কেন compiler-এর জগতে deterministic parsing (LL, LR) প্রধান, আর ভাষাবিজ্ঞানে সাধারণ CFG parsing ও পরিসংখ্যান। আধুনিক ভাষা-মডেল কোনো লেখা grammar ব্যবহার করে না, কিন্তু ambiguous বাক্যে তারাও ভুল গঠন বেছে নিতে পারে; তারা ভেতরে কী ধরনের কাঠামো শেখে, তা নিয়ে গবেষণা চলছে (পর্ব ৭৯-এ এর ছোঁয়া)।
মূল উপলব্ধি: মানুষের ভাষায় ambiguity একটি স্বাভাবিক ধর্ম, যা প্রসঙ্গ আর সম্ভাবনা দিয়ে মেটানো হয়; programming language-এ এটি একটি ত্রুটি, যা grammar-এর গঠন দিয়ে সরাতে হয়। একই গণিত (parse tree, Catalan সংখ্যা) দুই জগতেই কাজ করে।
প্র ০৪“এই language inherently ambiguous” প্রমাণ করা এত কঠিন কেন, আর “এই grammar ambiguous” দেখানো এত সহজ কেন?
দুটি বাক্যের যুক্তির গঠন আলাদা। “G ambiguous” একটি অস্তিত্বের দাবি: একটি string আর দুটি গাছ দেখালেই শেষ। এই পর্বে id+id∗id বা iiaea ঠিক এমন সাক্ষী। কিন্তু “L inherently ambiguous” একটি সার্বজনীন দাবি: L-এর প্রতিটি সম্ভাব্য grammar ambiguous. Grammar অসীম সংখ্যক, আর একটি চতুর grammar ঠিক কেমন দেখতে হতে পারে তা আগে থেকে বলা যায় না। তাই প্রমাণকে grammar-এর গঠন নয়, শুধু “এটি একটি CFG” তথ্যটি ব্যবহার করতে হয়।
এই কারণেই হাতিয়ার হলো pumping-ধরনের lemma, যা যেকোনো CFG-এর গাছের সাধারণ ধর্ম বলে: বড় string-এর গাছে কোনো variable পথের ওপর দুবার আসে, তাই কিছু অংশ পাম্প করা যায়। কিন্তু সাধারণ pumping lemma পাম্পের অবস্থান বেছে দিতে দেয় না, আর inherent ambiguity-র প্রমাণে ঠিক এটি দরকার: দেখাতে হয় যে anbncn-এর কোনো গাছ a আর b-কে জোড়ায় বাঁধে, অন্য কোনো গাছ b আর c-কে। William Ogden ১৯৬৮ সালে একটি শক্তিশালী রূপ দেন, যেখানে string-এর কিছু অবস্থান “চিহ্নিত” করা যায় আর পাম্প অবশ্যই চিহ্নিত অবস্থান ছোঁয়। Hopcroft–Motwani–Ullman-এর বইয়ে inherent ambiguity-র প্রমাণ এই ধরনের যুক্তিতে চলে, আর প্রমাণটি দীর্ঘ ও সূক্ষ্ম।
এর পাশে আছে undecidability-র দেয়াল। অংশ ৭-এ দেখেছেন, একটি grammar ambiguous কি না সেটিই undecidable; আর “language-টি inherently ambiguous কি না” প্রশ্নটিও সাধারণভাবে undecidable বলে পরিচিত। তাই প্রতিটি নির্দিষ্ট language-এর জন্য মানুষকে আলাদা যুক্তি খুঁজতে হয়। একটি ভিন্ন, প্রায় অপ্রত্যাশিত পথ এসেছিল গণনা থেকে: unambiguous grammar-এ প্রতিটি দৈর্ঘ্যের string-সংখ্যার generating function বীজগাণিতিক হয়, তাই কোনো language-এর গণনার ধারা বীজগাণিতিক নয় দেখাতে পারলে সেটি inherently ambiguous. Philippe Flajolet এই analytic পথে অনেক language নিয়ে কাজ করেন।
মূল উপলব্ধি: “আছে” দেখানো সহজ, “কোথাও নেই” দেখানো কঠিন। Ambiguity-র সাক্ষী একটি string; inherent ambiguity-র প্রমাণে সব সম্ভাব্য grammar-এর বিরুদ্ধে একটি সাধারণ যুক্তি লাগে, ঠিক যেমন non-regularity-র প্রমাণে সব DFA-র বিরুদ্ধে।
প্র ০৫Ambiguity undecidable হলে বাস্তবের tool-গুলো ambiguity নিয়ে কী করে? ব্যবহারকারী হিসেবে আপনার করণীয় কী?
Undecidable মানে “সব grammar-এ সবসময় সঠিক উত্তর দিয়ে থামে এমন algorithm নেই”, এর মানে এই নয় যে কিছুই করা যায় না। Tool-গুলো তিন ধরনের আপস করে। প্রথম, রক্ষণশীল পরীক্ষা: LR(1) বা LL(1) table-এ conflict না থাকলে grammar নিশ্চিতভাবে unambiguous. এই পরীক্ষা কখনো মিথ্যা নিশ্চয়তা দেয় না, কিন্তু কিছু unambiguous grammar-কেও সন্দেহ করে। অর্থাৎ ভুলের দিকটি নিয়ন্ত্রিত: আপনি হয়তো অপ্রয়োজনে grammar বদলাবেন, কিন্তু ambiguous grammar নিয়ে নিশ্চিন্তে থাকবেন না।
দ্বিতীয়, সীমিত খোঁজ: এই পর্বের brute force-এর মতো, নির্দিষ্ট দৈর্ঘ্য পর্যন্ত string বানিয়ে গাছ গোনা। এটি ambiguity খুঁজে পেলে সেটি নিশ্চিত সত্য, কারণ সাক্ষী হাতে আছে; কিছু না পেলে কিছুই প্রমাণ হয় না। গবেষণায় এর চতুর রূপ আছে, যেমন grammar-এর আকার দেখে সন্দেহজনক অংশে খোঁজা, বা grammar-কে সরল একটি approximation-এ বদলে দ্রুত পরীক্ষা করা; এসব কৌশল কিছু ক্ষেত্রে নিশ্চিত “unambiguous”-ও বলতে পারে, সব ক্ষেত্রে নয়। তৃতীয়, ambiguity মেনে নেওয়া: Earley বা GLR parser সব গাছ রাখে, আর lark-এর ambiguity="explicit"-এর মতো সুবিধা দিয়ে আপনি নির্দিষ্ট ইনপুটে দেখতে পারেন একাধিক গাছ আছে কি না।
ব্যবহারকারী হিসেবে একটি সহজ কর্মপদ্ধতি দাঁড়ায়। (১) Grammar লেখার সময়ই precedence আর associativity-র স্তর ভাবুন, আর if-else-এর মতো পরিচিত ফাঁদ এড়ান। (২) Parser generator-এর প্রতিটি conflict পড়ুন; সতর্কবার্তা উপেক্ষা করবেন না। (৩) ছোট দৈর্ঘ্যের সব string-এ গাছ গোনার একটি পরীক্ষা test-suite-এ রাখুন, যাতে grammar বদলালে নতুন ambiguity সঙ্গে সঙ্গে ধরা পড়ে। (৪) ভাষার মূল অংশের জন্য unambiguity-র একটি ছোট হাতের যুক্তি লিখে রাখুন। বাজারঘরের order-query grammar ঠিক এভাবে রক্ষা করা যায়: AND/OR-এর স্তর, বন্ধনী, আর প্রতিটি release-এ brute-force পরীক্ষা।
মূল উপলব্ধি: Undecidability কাজ বন্ধ করে না, শুধু নিশ্চয়তার ধরন বদলায়। রক্ষণশীল পরীক্ষা, সীমিত খোঁজ আর মানুষের প্রমাণ মিলে বাস্তবে ambiguity নিয়ন্ত্রণে রাখা যায়।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। count_trees.py আর check_fixes.py ব্লকে নিজের grammar বসিয়ে উত্তর যাচাইও করতে পারেন।
-
নকশা: G: S → aSb ∣ aaSb ∣ ε. (ক) দেখান যে G ambiguous. (খ) L(G) কোন language? (গ) একই language-এর একটি unambiguous grammar নকশা করুন আর কেন unambiguous তা বলুন।
(ক) aaabb-এর দুটি leftmost derivation: S ⇒ aSb ⇒ aaaSbb ⇒ aaabb (প্রথমে aSb, তারপর aaSb), আর S ⇒ aaSb ⇒ aaaSbb ⇒ aaabb (প্রথমে aaSb, তারপর aSb). দুটি গাছে মূলের নিয়ম আলাদা। Scratch-এ এটিই সবচেয়ে ছোট ambiguous string.
(খ) প্রতিটি নিয়ম একটি b আর এক বা দুটি a যোগ করে, তাই L(G) = {aibj : j ≤ i ≤ 2j}. Ambiguity-র উৎস: একই সংখ্যক “একক” আর “জোড়া” ধাপ যেকোনো ক্রমে বসানো যায়।
(গ) ক্রম বেঁধে দিন: আগে সব একক ধাপ, তারপর সব জোড়া ধাপ। S → aSb ∣ T, T → aaTb ∣ ε. একটি string aibj-এ জোড়া ধাপের সংখ্যা ঠিক i − j আর একক ধাপের সংখ্যা 2j − i, আর ক্রম নির্দিষ্ট, তাই derivation একটিই। Scratch-এ দৈর্ঘ্য ১৫ পর্যন্ত দুই grammar-এর language এক (২৭টি string), আর নতুনটিতে প্রতিটির একটি গাছ।
-
প্রমাণ: DFA M = (Q, Σ, δ, q0, F) থেকে বানানো right-linear grammar GM: প্রতিটি δ(q, a) = r-এর জন্য q → ar, প্রতিটি q ∈ F-এর জন্য q → ε. প্রমাণ করুন GM unambiguous. NFA থেকে একই গঠনে বানানো grammar-এ কেন এই প্রমাণ খাটে না?
- GM-এর প্রতিটি sentential form-এ বড়জোর একটি variable, একেবারে শেষে; তাই প্রতিটি derivation-ই leftmost, আর গাছ গোনা মানে derivation গোনা। — নিয়মের আকার
- w = a1⋯an ∈ L(GM) নিন। k-তম ধাপের আগে sentential form a1⋯ak−1q, আর পরের terminal ak হতে হবে; q → akr নিয়মগুলোর মধ্যে r = δ(q, ak) একটিই, কারণ δ একটি function. — DFA deterministic
- তাই প্রথম n ধাপ w নিজেই নির্ধারণ করে, আর শেষ ধাপে variable-টি δ̂(q0, w), যেখানে একটিই নিয়ম q → ε. — শেষ ধাপ
- ফলে w-এর derivation একটিই, গাছও একটি। ∎
NFA-তে একই (q, a)-র জন্য একাধিক r থাকতে পারে, তাই ধাপ ২ ভেঙে যায়: প্রতিটি accepting run একটি আলাদা গাছ। যেমন NFA-তে q0 থেকে a পড়ে দুটি accepting state-এ যাওয়া গেলে “a”-এর দুটি গাছ। এই কারণেই প্রতিটি regular language-এর একটি unambiguous grammar আছে (DFA থেকে), যদিও তার অনেক ambiguous grammar-ও আছে।
-
Output অনুমান: Gite: S → iS ∣ iSeS ∣ a (i = “if c then”, e = “else”). count_trees.py-এর
trees(ITE, w, "S")নিচের প্রতিটি w-এ কত দেবে? (ক) iiaea (খ) iiiaea (গ) iiaeaea. প্রতিটির কারণ বলুন।(ক) 2. একটি else, দুটি if; else যেকোনো একটির হতে পারে (অংশ ৬-এর দুই গাছ)।
(খ) 3. তিনটি if, একটি else, আর else-এর পরে একটি a. else তিনটি if-এর যেকোনোটির সঙ্গে জোড়া বাঁধতে পারে: বাইরেরটির সঙ্গে হলে ভেতরের দুটি if else-হীন, then-অংশ “iia”; মাঝেরটির সঙ্গে হলে বাইরেরটি else-হীন; ভেতরেরটির সঙ্গে হলে বাকি দুটি else-হীন। প্রতিটি পছন্দে বাকি গঠন নির্দিষ্ট, তাই ৩টি।
(গ) 1. দুটি if, দুটি else. প্রথম e-এর আগে দুটি if, কিন্তু প্রথম e যদি বাইরের if-এর হয়, তবে তার then-অংশ “ia” একটি else-হীন if, আর দ্বিতীয় e-এর জন্য কোনো if বাকি থাকে না (else-এর পরে শুধু “a”). তাই প্রথম e ভেতরের if-এর, দ্বিতীয়টি বাইরের: একটিই গাছ। Scratch-এ চালিয়ে ঠিক 2, 3, 1 এসেছে।
-
Inherent ambiguity বিচার: নিচের প্রতিটি দাবি সত্য না মিথ্যা, কারণসহ বলুন। (ক) S → SS ∣ (S) ∣ ε ambiguous, তাই সুষম বন্ধনীর language inherently ambiguous. (খ) {aibjck : i = j অথবা j = k}-এর grammar S → P ∣ Q-তে (অংশ ৮) id+id∗id-এর মতো একটি সাক্ষী আছে: abc. (গ) কোনো regular language inherently ambiguous নয়।
(ক) মিথ্যা। Grammar-টি সত্যিই ambiguous (“()”-এর অসীম সংখ্যক গাছ), কিন্তু একই language-এর S → (S)S ∣ ε unambiguous (উপপাদ্য ৪.২)। একটি ambiguous grammar language সম্পর্কে কিছুই প্রমাণ করে না।
(খ) সত্য। abc-তে i = j = k = 1: P পথে X ⇒ aXb ⇒ ab, C ⇒ cC ⇒ c; Q পথে A ⇒ aA ⇒ a, Y ⇒ bYc ⇒ bc. দুটি গাছ, মূলের নিয়মই আলাদা (S → P বনাম S → Q). inherent.py-এর আউটপুটে abc:2 ঠিক এটি। তবে এটি শুধু এই grammar-এর ambiguity দেখায়; language-এর inherent ambiguity-র জন্য উপপাদ্য ৮.২ লাগে।
(গ) সত্য। অনুশীলন ২: DFA থেকে বানানো right-linear grammar সবসময় unambiguous, আর প্রতিটি regular language-এর একটি DFA আছে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি ambiguous expression grammar-কে unambiguous করার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- দুটি গাছওয়ালা একটি সাক্ষী string খুঁজে ambiguity নিশ্চিত করা
- Operator-গুলোকে precedence অনুযায়ী দুর্বল থেকে শক্তিশালী সাজানো
- প্রতিটি precedence-স্তরের জন্য একটি variable নেওয়া, দুর্বলটি সবচেয়ে ওপরে
- Associativity অনুযায়ী প্রতিটি স্তরের recursion বাঁ বা ডান দিকে রাখা
- সবচেয়ে নিচের স্তরে একক আর বন্ধনী রাখা, বন্ধনীর ভেতরে আবার ওপরের স্তর
- Brute force-এ language অপরিবর্তিত আর গাছ একটি কি না দেখে induction-যুক্তি লেখা
একটি CFG G ambiguous বলার সঠিক শর্ত কোনটি?
- কোনো string-এর দুটি আলাদা derivation আছে
- L(G)-এর কোনো string-এর দুটি আলাদা leftmost derivation আছে
- L(G)-এর জন্য অন্য একটি grammar আছে
- L(G) অসীম
E → E+E ∣ E∗E ∣ (E) ∣ id grammar-এ id+id∗id+id∗id string-টির কয়টি parse tree আছে?
- 1
- 4
- 14
- 24
G: S → (S) ∣ SS ∣ ε grammar-এ “()” string-টির কয়টি parse tree আছে?
- ঠিক 1টি
- ঠিক 2টি
- ঠিক 3টি
- অসীম সংখ্যক
E → E−T ∣ T, T → F, F → num grammar-এ 8−4−2-এর মান কত হবে, আর কেন?
- 2, কারণ বাঁ-recursion (8−4)−2 গাছটিই দেয়
- 6, কারণ ডান দিক থেকে হিসাব হয়
- 2 বা 6, কারণ grammar ambiguous
- কোনো মান নয়, string-টি language-এ নেই
AMBIGCFG = {⟨G⟩ : G একটি ambiguous CFG} সম্পর্কে কোন বাক্যটি সঠিক?
- এটি decidable, CYK-এর মতো dynamic programming দিয়ে
- এটি undecidable, কিন্তু Turing-recognizable
- এটি undecidable আর recognizable-ও নয়
- ε-নিয়মহীন grammar-এ এটি decidable
নিচের কোন language inherently ambiguous?
- {anbn : n ≥ 0}
- {w ∈ {0, 1}∗ : w-এ 1-এর সংখ্যা জোড়}
- {aibjck : i = j অথবা j = k}
- {anbncn : n ≥ 0}
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- G ambiguous ⇔ কোনো string-এর দুটি parse tree ⇔ দুটি leftmost derivation; শুধু দুটি derivation যথেষ্ট নয়। Ambiguity grammar-এর ধর্ম।
- গাছই অর্থ: 2+3∗4-এর দুই গাছে 14 আর 20. E → E+E ∣ id-এ n-টি +-এর গাছ Catalan সংখ্যা Cn.
- দূর করা: দুর্বল operator ওপরের স্তরে (E, T, F), বাঁ-recursion মানে বাম-সংযোগ; dangling else-এ then আর else-এর মাঝে শুধু matched statement.
- Unambiguity প্রমাণ: মূলের নিয়ম আর ভাঙার জায়গা string নিজেই ঠিক করে, তারপর induction. Brute force শুধু ভুল ধরে।
- AMBIGCFG undecidable (PCP থেকে), কিন্তু recognizable; {aibjck : i = j অথবা j = k} inherently ambiguous, আর regular ও deterministic CFL কখনো নয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২৫ · Context-free grammar — formal definition আর উদাহরণফিরে দেখুনদুটি expression grammar, BAL আর order-query grammar, যেগুলো এই পর্বে বারবার এসেছে।
- পর্ব ২৬ · Derivation আর parse tree — leftmost, rightmost আর yieldআগের পর্বLeftmost derivation আর parse tree-র এক-এক সম্পর্ক, যার ওপর ambiguity-র সংজ্ঞা দাঁড়িয়ে।
- পর্ব ২১ · বাস্তব regex engine — backtracking বনাম automaton আর ReDoSতুলনাRegex আর NFA-র ambiguity: একই string মেলানোর অনেক পথ, আর তার সময়ের দাম।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ২৮ grammar সরলীকরণ।
- পর্ব ০৬ · Chomsky hierarchy-র মানচিত্র — চার শ্রেণির language আর machineপটভূমিContext-free স্তর কোথায় বসে, আর কোন প্রশ্ন কোন পর্বে প্রমাণ হবে।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৫০ — বিশেষ সংখ্যা: Catalan, Stirling আর partitionপাশের ট্র্যাকCatalan সংখ্যার বদ্ধ রূপ আর বন্ধনী, binary tree ও পথের সঙ্গে তার মিল।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৩ — Grammar আর formal languageপাশের ট্র্যাকGrammar আর BNF-এর প্রথম পরিচয়, গণিতের দিক থেকে।