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

ক্যাপস্টোন — বাজারঘরের জন্য formal language toolkit

Capstone — A Formal-Language Toolkit for Bazarghar: Minimal-DFA Validators, a Lark Query Language, a Model-Checked Mealy Machine, Decidability Limits and NP-Complete Scheduling with a SAT Solver

Taught in Bangla, this lesson is the course capstone. It maps six tasks of a fictional shop onto the course: a 22-state minimal-DFA validator checked by brute force and against automata-lib, a query language built from a Lark grammar, a Mealy machine checked for safety and liveness with z3 bounded model checking, decidability limits from Rice's theorem, and an NP-complete slot problem solved with CaDiCaL through PySAT with unsat cores. In-page Python (Pyodide) runs each part, and 47 pytest tests pass.

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

  • একটি বাস্তব চাহিদাকে ঠিক কোন শ্রেণির language বা সমস্যা হিসেবে লিখতে হয়, আর কেন সবচেয়ে দুর্বল যথেষ্ট যন্ত্রটি বাছা ভালো
  • DFA নকশা, product, minimisation আর brute force ও differential test দিয়ে একটি validator শেষ পর্যন্ত বানানো
  • Grammar থেকে lexer, parser আর evaluator, আর হাতে লেখা parser-কে parser generator-এর বিরুদ্ধে test করা
  • একটি Mealy machine-কে Kripke structure হিসেবে দেখে safety ও liveness ধর্ম, fairness আর bounded model checking
  • নতুন একটি scheduling সমস্যার NP-completeness প্রমাণ, SAT encoding, unsat core, আর পুরো প্রকল্পের test, rubric ও পরের ধাপ

১ · প্রকল্পের ছক — ছয়টি কাজ, কোর্সের ছয়টি স্তর

আশি পর্ব ধরে বাজারঘর নামের কাল্পনিক অনলাইন দোকান আমাদের সঙ্গী ছিল: কখনো তার অর্ডার কোড, কখনো কুপন, কখনো admin panel-এর query, কখনো delivery-র slot. এই পর্বে সব টুকরো জোড়া লাগবে একটি প্রকল্পে, যার নাম দেওয়া যাক “বাজারঘর toolkit”. লক্ষ্য দুটি: প্রতিটি কাজের জন্য ঠিক তত্ত্বটি চিনে নেওয়া, আর প্রতিটি দাবি একটি সত্যিকারের tool বা brute force দিয়ে যাচাই করা।

পুরান ঢাকার একজন অভিজ্ঞ রাজমিস্ত্রির কথা ভাবুন। দেয়াল গাঁথতে তিনি বুলডোজার আনেন না, আবার ছাদ ঢালাইয়ে শুধু কর্নিক নিয়েও যান না। কাজের মাপে যন্ত্র। গণনার তত্ত্বও একই শিক্ষা দেয়: যেখানে DFA যথেষ্ট, সেখানে Turing machine-এর শক্তি আনলে লাভ নেই, বরং ক্ষতি, কারণ শক্তিশালী যন্ত্রের আচরণ নিয়ে প্রশ্নগুলো আর উত্তরযোগ্য থাকে না।

অংশবাজারঘরের চাহিদাতত্ত্ব (পর্ব)সত্যিকারের tool
১অর্ডার কোড আর কুপন যাচাইDFA, product, minimisation (০৮, ১৯, ২০)automata-lib 9.2.0
২Admin-এর order-query ভাষাLexer, CFG, LALR, evaluator (২২, ৪০, ৪২)lark 1.3.1
৩অর্ডারের অবস্থা আর টাকার নিরাপত্তাMealy machine, model checking (১২, ২৪, ৭৭)z3-solver 5.4.1.0
৪কোন প্রশ্নের algorithm আছে?Decidability, Rice (২০, ৩৭, ৫০, ৫৩, ৫৫)প্রমাণ
৫Delivery slot-এর পরিকল্পনাNP-completeness, SAT (৬১, ৭৩)python-sat (CaDiCaL)
৬সব জোড়া, test আর হস্তান্তরDifferential test, brute forcepytest 9.2.0

ছবিতে প্রকল্পটি কোর্সের মানচিত্রের ওপর বসানো। চারটি অংশ সবুজ ফ্রেমের ভেতরে: এদের প্রতিটি প্রশ্নের জন্য এমন algorithm আছে যা সবসময় থামে, অর্থাৎ প্রশ্নগুলো decidable. ওপর থেকে নিচে যন্ত্র শক্তিশালী হয়, আর খরচও বাড়ে। ফ্রেমের বাইরে লাল অংশটি সতর্কবার্তা: যন্ত্রকে Turing-complete করে দিলে কিছু প্রশ্নের উত্তর আর কোনো algorithm দিতে পারে না।

বাজারঘর toolkit — কোর্সের কোন স্তরে কোন অংশ

সবুজ ফ্রেম = decidable প্রশ্ন। নিচে নামলে যন্ত্র শক্তিশালী, খরচ বেশি। লাল ড্যাশ বাক্স = সাধারণভাবে undecidable.

Bazarghar toolkit on the map of the course decidable — সবসময় থামে এমন algorithm আছে ১ · Validator ২ · Query ভাষা ৩ · অর্ডার-যন্ত্র ৫ · Delivery slot ৪ · যেকোনো plug-in code-এর আচরণ regex → minimal DFA · regular lexer → LALR → evaluator · context-free Mealy + model checking · সসীম state SAT solver · NP-complete Rice-এর theorem · undecidable
ছবি ৮০.১ — প্রকল্পের প্রতিটি অংশ সবচেয়ে দুর্বল যে যন্ত্রে কাজ চলে, সেখানে বসানো। অংশ ৪ ছবির বাইরে কারণ সেটি কোনো tool নয়, একটি সীমার মানচিত্র।

প্রতিটি অংশের ছাঁচ: চাহিদা → মডেল → প্রমাণ → সত্যিকারের run → test. নিচের stepper একটি দিন ধরে ছয়টি অংশ ঘোরায়।

1কোড আর কুপন → DFA2admin query → parser3অর্ডারের ঘটনা → Mealy4টাকার ধর্ম → model checker5slot পরিকল্পনা → SAT6partner-এর plug-in → সীমা
এই ধাপে
ইনপুট
যন্ত্র
ফল
  1. সকালে, চেকআউট। একজন ক্রেতা অর্ডার কোড BG-0042 আর কুপন XSALE9 দিলেন। দুটি string একই minimal DFA-তে চলে, প্রতিটি অক্ষরে একটি state-বদল; দুটিই গ্রহণ। এখানে memory-র দরকার সসীম: regular language.
  2. দুপুরে, admin panel. ব্যবস্থাপক লিখলেন amount >= 1000 AND district = "Dhaka". বন্ধনী আর precedence-এর জন্য stack লাগে, তাই এটি context-free: Lark-এর LALR parser গাছ বানায়, evaluator ২০০টি অর্ডার থেকে ২৫টি দেয় (পর্ব ৪০-এর একই ফল)।
  3. বিকেলে, একটি অর্ডারের জীবন। BG-0042-এ ঘটনা আসে pay, pack, cancel, refund. Mealy machine প্রতিটি ঘটনায় একটি output দেয়: charge, sms, ok, pay_back. ফলাফলে টাকা ফেরত গেল, অবস্থা Refunded.
  4. রাতে, নিরাপত্তা-যাচাই। দাবি: “টাকা নেওয়া থাকলে একসময় অর্ডার পৌঁছাবে বা টাকা ফেরত যাবে”। যন্ত্রটি সসীম, তাই সব অবস্থা খুঁজে দেখা যায়: ঠিক সংস্করণে দাবি মানে, আর লাগানো bug-এ z3 মাত্র দুই ধাপের counterexample দেয়।
  5. পরদিনের slot. ৬০টি অর্ডার, ৮টি slot, প্রতিটির সময়-জানালা আর কিছু বিরোধী জোড়া। সমস্যাটি NP-complete, তবু SAT solver capacity 8-এ একটি পরিকল্পনা পায় ৪০১টি বিরোধে, আর আলাদা checker তা মেলায়।
  6. Partner-এর অনুরোধ। একটি partner নিজের Python code-এ ছাড়ের নিয়ম চালাতে চায়: “কখনো ৫০%-এর বেশি ছাড় দেবে না তো?” এটি code-এর আচরণ নিয়ে non-trivial প্রশ্ন, তাই Rice-এর theorem অনুযায়ী সাধারণ algorithm নেই। সমাধান অংশ ৪-এ: ভাষাটিকে দুর্বল রাখা।

প্রকল্পের কোড একটি uv প্রকল্পে (Python 3.12.13) সাজানো: validator.py, qengine.py, mc_bmc.py, sched.py আর tests/. পাতার চারটি Python ব্লক ব্রাউজারেই চলে, আর সত্যিকারের run-এর আউটপুট হুবহু দেওয়া। চারটি library-ই MIT লাইসেন্সের; installed উৎস-কোডে network বা usage-reporting-এর কোনো অংশ পাওয়া যায়নি।

২ · অংশ ১: কোড আর কুপনের validator — product, minimisation আর brute force

চাহিদা। চেকআউটের একটি বাক্সে ক্রেতা অর্ডার কোড বা কুপন, যেকোনোটি লিখতে পারেন। নিয়ম দুটি কোর্সের শুরু থেকে চেনা (পর্ব ১৩): অর্ডার কোড BG- আর তারপর ঠিক চারটি অঙ্ক; কুপন ঠিক ছয়টি চিহ্নের, প্রতিটি বড় হাতের অক্ষর বা অঙ্ক, আর ভেতরে কোথাও SALE. বাক্সটি একটিই, তাই language VALID = ORDER ∪ COUPON.

মডেল। ৩৬টি আসল চিহ্ন নিয়ে কাজ করলে টেবিল বড় হয়, অথচ বেশিরভাগ চিহ্ন একই আচরণ করে। তাই alphabet-কে শ্রেণিতে ভাঙা হলো: Σ = {B, G, S, A, L, E, d, o, -}, যেখানে d মানে যেকোনো অঙ্ক আর o মানে বাকি যেকোনো বড় হাতের অক্ষর। এটি নিরাপদ, কারণ কোনো নিয়ম একই শ্রেণির দুটি চিহ্নকে আলাদা করে না। বাকি সব চিহ্ন সঙ্গে সঙ্গে বাতিল।

নির্মাণ। দুটি DFA, তারপর product construction (পর্ব ০৮): state = (কোডে কতটা মিলেছে, কুপনে কয়টি চিহ্ন পড়া হলো, SALE-এর কতটা মিলেছে), আর গ্রহণ যদি যেকোনো অংশ গ্রহণ করে। কুপনের অংশে SALE খোঁজা হয় পর্ব ২৩-এর matching automaton দিয়ে; SALE-এর কোনো prefix তার suffix নয়, তাই মিল ভাঙলে শুধু দেখতে হয় চিহ্নটি S কি না। শেষে Moore-এর algorithm (পর্ব ১৯) সমতুল্য state জোড়া লাগায়।

যাচাই। প্রমাণের পাশে পাহারাদার হিসেবে brute force: স্পেসিফিকেশনটি সরাসরি একটি ফাংশনে লেখা (ref), আর DFA-র উত্তর তার সঙ্গে মেলানো সব string-এ, দৈর্ঘ্য ৫ পর্যন্ত পুরো Σ-এ, আর দৈর্ঘ্য ৬ ও ৭-এ সেই চিহ্নগুলোতে যেখানে ভুল হওয়ার সম্ভাবনা সবচেয়ে বেশি।

# Validator: product DFA for "order code OR coupon", Moore minimisation, brute-force test
from itertools import product
from functools import reduce
SIG = "BGSALEdo-"                       # d = any digit, o = any other capital letter
PAT, CODE = "SALE", "BG-dddd"
def kmp(k, c):                          # matched prefix of SALE after reading c
    return 4 if k == 4 else k + 1 if PAT[k] == c else int(c == "S")
def step(q, c):                         # q = (code progress, coupon length, kmp)
    a, n, k = q
    a = a + 1 if a is not None and a < 7 and CODE[a] == c else None
    n, k = (n + 1, kmp(k, c)) if n is not None and n < 6 and c != "-" else (None, 0)
    return (a, n, k)
fin = lambda q: q[0] == 7 or (q[1] == 6 and q[2] == 4)
Q, todo = {(0, 0, 0)}, [(0, 0, 0)]
while todo:                             # explore reachable product states
    q = todo.pop()
    for c in SIG:
        r = step(q, c)
        if r not in Q: Q.add(r); todo.append(r)
part = {q: fin(q) for q in Q}           # Moore: split blocks until stable
while True:
    sig = {q: (part[q],) + tuple(part[step(q, c)] for c in SIG) for q in Q}
    ids = {s: i for i, s in enumerate(sorted(set(sig.values()), key=str))}
    new = {q: ids[sig[q]] for q in Q}
    if len(set(new.values())) == len(set(part.values())): break
    part = new
print("reachable product states:", len(Q), "| minimal DFA states:", len(set(part.values())))
def ref(w):                             # the specification, written directly
    return w[:3] == "BG-" and len(w) == 7 and set(w[3:]) == {"d"} or \
           len(w) == 6 and "-" not in w and PAT in w
run = lambda w: fin(reduce(step, w, (0, 0, 0)))  # feed the string to the DFA
tests = [w for n in range(6) for w in product(SIG, repeat=n)]
tests += [*product("SALEo-", repeat=6), *product("SALE", repeat=7), *product("BGd-", repeat=7)]
bad = [w for w in tests if run(w) != ref("".join(w))]
print("strings tested:", len(tests), "| accepted:", sum(map(run, tests)), "| mismatches:", len(bad))

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

reachable product states: 33 | minimal DFA states: 22
strings tested: 145854 | accepted: 76 | mismatches: 0

Product-এ ৩৩টি state পৌঁছানো যায়, কিন্তু অনেকগুলো আচরণে একই: যেমন কুপনের দৈর্ঘ্য ছাড়িয়ে গেছে আর কোডও ভেঙেছে, এমন সব state আসলে একটি dead state. Minimise করে থাকে ২২টি, dead state সহ। ১,৪৫,৮৫৪টি string-এ একটিও অমিল নেই। গৃহীত ৭৬টি হিসাব করেও মেলানো যায়: দৈর্ঘ্য ৬-এর {S, A, L, E, o, -} string-এর মধ্যে SALE তিনটি অবস্থানে বসতে পারে, বাকি দুটি ঘরে “-” ছাড়া ৫টি চিহ্ন, তাই 3 × 52 = ৭৫ (ছয় ঘরে দুটি SALE ধরে না, তাই দ্বিগুণ গোনা নেই), আর দৈর্ঘ্য ৭-এ শুধু BG-dddd, মোট ৭৬. এই হাতের হিসাবও একটি স্বাধীন যাচাই।

কেন ২২-এর কম সম্ভব নয়? পর্ব ১৮ অনুযায়ী Moore-এর algorithm শেষের দলগুলো Myhill–Nerode-এর equivalence class, তাই যেকোনো complete DFA-তে অন্তত ততগুলো state লাগে; এটিই minimal DFA. যেমন “BG” আর “GB” আলাদা class: suffix “-1234” প্রথমটিকে গ্রহণযোগ্য করে, দ্বিতীয়টিকে নয়।

সত্যিকারের run: library দিয়ে দ্বিতীয় মত। নিজের কোডে নিজের পরীক্ষা যথেষ্ট নয়; একই কাজ একটি স্বাধীন library-তে করা হলো। automata-lib 9.2.0 (MIT) regex থেকে NFA, তারপর DFA বানায়, union আর minimise করে, আর দুটি DFA-র সমতা (equivalence) পরীক্ষা করে। তারপর একটি differential test: ২,০০,০০০টি এলোমেলো আর প্রায়-বৈধ আসল string (অক্ষর ঢোকানো, মোছা, বদলানো) একসঙ্গে DFA আর Python-এর re-তে হাতে লেখা একটি regex-এ।

G = "(B|G|S|A|L|E|d|o)"
ORDER = "BG-dddd"
COUPON = f"{G}{G}SALE|{G}SALE{G}|SALE{G}{G}"
def build(rx):
    return DFA.from_nfa(NFA.from_regex(rx, input_symbols=set(CLS)))
order, coupon = build(ORDER), build(COUPON)
valid = order.union(coupon); vm = valid.minify()
both = order.intersection(coupon)          # can one string be both?
REF = re.compile(r"BG-[0-9]{4}|(?=[A-Z0-9]{6}\Z)[A-Z0-9]*SALE[A-Z0-9]*")
# 200,000 random / mutated strings: accepts(vm, s) vs bool(REF.fullmatch(s))

সত্যিকারের run (ডেস্কটপ, automata-lib 9.2.0, Python 3.12.13):

~/bazarghar-toc$ uv run python validator.py
automata-lib 9.2.0
order code DFA: 8 states -> minimal 8
coupon DFA:     15 states -> minimal 15
union (product): 21 states -> minimal 21
order and coupon overlap is empty: True
minimal union equals union: True
differential test: 200000 strings, 28073 accepted, disagreements 0
  'BG-0042'   -> True
  'bg-0042'   -> False
  'BG-042'    -> False
  'EIDSALE'   -> False
  'XSALE9'    -> True
  'SALE'      -> False
  'BG-SALE'   -> False

Library-র সংখ্যা ২১, আমাদের ২২: অমিল নয়। automata-lib এখানে partial DFA বানায়, যেখানে dead state আঁকা হয় না (অর্ডার কোডের ৮টি state-এ শুরুর state থেকে শুধু B-এর তীর)। Dead state যোগ করলে ২২. isempty() দেখায় দুই language-এর ছেদ ফাঁকা (কোডে “-” আছে, কুপনে থাকতে পারে না), অর্থাৎ বাক্সের উত্তর থেকে বলা যায় এটি কোড না কুপন। ২,০০,০০০টি input-এ regex আর DFA-র একটিও অমিল নেই; সঙ্গে test suite-এ (অংশ ৬) library-র DFA আর পাতার DFA দৈর্ঘ্য ৭ পর্যন্ত মেলানো হয়েছে। ছোট হাতের bg-0042 বাতিল, কারণ স্পেসিফিকেশনে বড় হাতের কথা বলা।

Regex থাকতে DFA কেন? ওপরের REF-এ একটি lookahead আছে; এটি গণিতের regular expression-এর অংশ নয়, আর Python-এর re একটি backtracking engine. পর্ব ২১-এ দেখেছেন, এমন engine-এ কিছু pattern সূচকীয় সময় নেয় (ReDoS), অথচ DFA-র সময় সবসময় input-এর দৈর্ঘ্যের রৈখিক। জনসমক্ষে খোলা বাক্সে এই নিশ্চয়তা মূল্যবান।

৩ · অংশ ২: order-query ভাষা — lexer, grammar আর evaluator

চাহিদা। Admin panel-এর query ভাষার দ্বিতীয় সংস্করণ পর্ব ৪২-এ চূড়ান্ত হয়েছে: OR, AND, NOT, বন্ধনী, ছয়টি তুলনা আর IN-তালিকা। এখানে নতুন কোনো syntax বানানো হবে না; সেই query_v2.lark ফাইলটিই হুবহু নেওয়া হলো। নতুন কাজ তিনটি: grammar থেকে একটি পুরো interpreter, ব্যবহারকারীর ভাষায় error message, আর একটি স্বাধীন হাতে লেখা parser, যার সঙ্গে মিলিয়ে দুটিকেই test করা যায়।

মডেল। দুই স্তর। নিচে lexer, যার প্রতিটি token-শ্রেণি (NUM, STR, তুলনা, keyword) একটি regular language, তাই একটি DFA যথেষ্ট (পর্ব ২২)। ওপরে একটি context-free grammar, তিনটি precedence-স্তর নিয়ে:

C → C OR T ∣ T   T → T AND N ∣ N   N → NOT N ∣ A

A হলো পরমাণু: বন্ধনীর ভেতরে C, একটি তুলনা, বা একটি IN-তালিকা। বন্ধনী যত গভীরেই থাকুক মেলাতে হয়, তাই এই অংশ কোনো DFA পারে না (পর্ব ১৭-এর যুক্তি); stack লাগে। Lark grammar-টিকে LALR(1) টেবিলে রূপ দেয়, conflict ছাড়া, যা থেকে grammar-টি unambiguous বলেও জানা যায় (পর্ব ৩৯)।

নিচের stepper একটি কঠিন-দেখতে query হাতে লেখা recursive descent parser-এ চালায়। প্রতিটি precedence-স্তরের জন্য একটি function: C-এর জন্য level("OR", T), T-এর জন্য level("AND", N), আর N নিজে।

1lexer: অক্ষর → token2C: OR দিয়ে ভাগ3T: AND দিয়ে ভাগ4N: NOT, তারপর IN5AST6evaluator: চারটি অর্ডার
এই ধাপে
কে কাজ করছে
ফল
  1. Lexer. Query: NOT district IN ("Dhaka") AND amount < 2000 OR status = "cancelled" (শুরুর FIND order WHERE বাদে)। Lexer অক্ষর থেকে ১৪টি token দেয়; "Dhaka" হয় STR, 2000 হয় NUM. এই ধাপ পুরোপুরি regular.
  2. C-স্তর। C-এর function আগে একটি পুরো T পড়ে, তারপর OR দেখে আরেকটি T. ফলে মূলে OR বসে: সবচেয়ে দুর্বল বন্ধনের operator গাছের সবচেয়ে ওপরে।
  3. T-স্তর। প্রথম T-এর ভেতরে N₁ AND N₂. AND এখানে থামে, কারণ পরের token OR, যা T-এর কাজ নয়; নিয়ন্ত্রণ C-তে ফেরে।
  4. N-স্তর। N₁ শুরু হয় NOT দিয়ে, তাই NOT-এর operand আবার একটি N, পুরো C নয়: district IN ("Dhaka"). অর্থাৎ NOT শুধু জেলার শর্তকে ঢাকে। N₂ একটি তুলনা: amount < 2000.
  5. AST. ফলাফল AST: OR(AND(NOT(IN district [Dhaka]), amount < 2000), status = cancelled). বন্ধনী বা keyword আর নেই, শুধু অর্থ।
  6. Evaluator. চারটি নমুনা অর্ডারে গাছটি নিচ থেকে ওপরে মূল্যায়ন। BG-0001 ঢাকার আর paid: দুই দিকই মিথ্যা। BG-0002 (রাজশাহী, ১৯০০) আর BG-0003 (সিলেট, ৪৫০) বাম দিকে সত্য; BG-0004 cancelled, তাই ডান দিকে সত্য।
import re, operator as op
TOK = re.compile(r'\s*(\d+|"[^"]*"|>=|<=|!=|[=<>(),]|\w+|\S)')
REL = {">=": op.ge, "<=": op.le, "!=": op.ne, ">": op.gt, "<": op.lt, "=": op.eq}
kind = lambda t: "NUM" if t.isdigit() else "STR" if t[0] == '"' else t
def parse(q):
    toks, pos = TOK.findall(q) + ["$"], 0
    def eat(*kinds):
        nonlocal pos; t = toks[pos]
        if kind(t) not in kinds: raise SyntaxError(f"token {pos + 1}: found {t}, expected {kinds}")
        pos += 1; return int(t) if t.isdigit() else t.strip('"')
    def level(o, sub):                    # X -> sub { o sub }, left-associative
        t = sub()
        while toks[pos] == o: eat(o); t = (o, t, sub())
        return t
    def N():
        if toks[pos] == "NOT": eat("NOT"); return ("NOT", N())
        if toks[pos] == "(": eat("("); t = level("OR", T); eat(")"); return t
        f = eat("amount", "district", "status"); v = "NUM" if f == "amount" else "STR"
        if toks[pos] == "IN":
            eat("IN"); eat("("); vs = [eat(v)]
            while toks[pos] == ",": eat(","); vs.append(eat(v))
            eat(")"); return ("IN", f, vs)
        return ("CMP", f, eat(*(REL if f == "amount" else ("=", "!="))), eat(v))
    T = lambda: level("AND", N)
    eat("FIND"); eat("order"); eat("WHERE"); tree = level("OR", T); eat("$")
    return tree
def ev(t, o):
    if t[0] in ("OR", "AND"): return (any if t[0] == "OR" else all)(ev(c, o) for c in t[1:])
    if t[0] == "NOT": return not ev(t[1], o)
    return o[t[1]] in t[2] if t[0] == "IN" else REL[t[2]](o[t[1]], t[3])
ORD = [dict(zip(("id", "amount", "district", "status"), r)) for r in [("BG-0001", 3000, "Dhaka", "paid"),
       ("BG-0002", 1900, "Rajshahi", "pending"), ("BG-0003", 450, "Sylhet", "paid"), ("BG-0004", 1200, "Dhaka", "cancelled")]]
q = 'FIND order WHERE NOT district IN ("Dhaka") AND amount < 2000 OR status = "cancelled"'
print(" ".join(kind(t) for t in TOK.findall(q)[3:]), parse(q), sep="\n")
print([o["id"] for o in ORD if ev(parse(q), o)])

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

NOT district IN ( STR ) AND amount < NUM OR status = STR
('OR', ('AND', ('NOT', ('IN', 'district', ['Dhaka'])), ('CMP', 'amount', '<', 2000)), ('CMP', 'status', '=', 'cancelled'))
['BG-0002', 'BG-0003', 'BG-0004']

তিনটি লাইন stepper-এর তিন স্তর: token-ধারা, গাছ আর উত্তর। grammar-এর প্রতিটি নিয়ম কোডে একটি লাইনে চেনা যায়: level হলো EBNF-এর X → sub { op sub }, যা left recursion ছাড়াই বাম-সংযোগ দেয় (পর্ব ৩০-এর কৌশল); amount-এর পরে শুধু সংখ্যা, district-এর পরে শুধু উদ্ধৃতির লেখা, অর্থাৎ ধরন grammar-এই বাঁধা। eat ভুল token পেলে প্রত্যাশিত শ্রেণির তালিকাসহ SyntaxError দেয়, যা expected-token set-এর সরল রূপ।

সত্যিকারের run: Lark দিয়ে interpreter. হাতে লেখা parser শেখায়, কিন্তু প্রকল্পের আসল ইঞ্জিন parser generator থেকে আসে, কারণ grammar ফাইলই তখন একমাত্র সত্য-উৎস। অর্থের অংশ একটি tree transformer: প্রতিটি নিয়মের নামে একটি method, যা node-কে “অর্ডার নিয়ে True/False দেওয়া” ফাংশনে বদলায়। অর্ডারের টেবিল পর্ব ৪০-এর সেই ২০০টি কাল্পনিক অর্ডার (seed 40). Error-এর অংশ পর্ব ৪২-এর অনুবাদ-টেবিল ব্যবহার করে।

P = Lark(Path(__file__).with_name("query_v2.lark").read_text(), parser="lalr")
class ToPred(Transformer):                    # AST node -> function(order) -> bool
    def or_(self, k):      a, b = k; return lambda o: a(o) or b(o)
    def and_(self, k):     a, b = k; return lambda o: a(o) and b(o)
    def not_(self, k):     a, = k;   return lambda o: not a(o)
    def num_in(self, k):
        vals = {int(x) for x in k}; return lambda o: o["amount"] in vals
    # num_cmp, text_cmp, text_in, start: the same pattern
def compile_query(q):
    try:
        return ToPred().transform(P.parse(q))
    except UnexpectedToken as e:              # column + expected set, in the user's words
        ...
        raise QueryError(f"col {col}: found {got}, expected one of: {want}") from None

সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13):

~/bazarghar-toc$ uv run python query_demo.py
lark 1.3.1 | python 3.12.13 | orders 200
amount >= 1000 AND district = "Dhaka"
   -> 25 orders: BG-0001, BG-0024, BG-0036 ...
NOT district IN ("Dhaka", "Chattogram") AND status = "pending"
   -> 36 orders: BG-0002, BG-0013, BG-0017 ...
amount IN (500, 1000) OR NOT (status != "cancelled")
   -> 58 orders: BG-0006, BG-0009, BG-0019 ...
district = "Sylhet" AND (amount < 300 OR status = "paid")
   -> 7 orders: BG-0044, BG-0088, BG-0100 ...
amount >= AND district = "Dhaka"
   -> error, col 28: found 'AND', expected one of: a number
district IN ("Dhaka", )
   -> error, col 40: found ')', expected one of: a "quoted text"
status == "paid"
   -> error, col 26: found '=', expected one of: a "quoted text"
start
  and_
    not_
      text_in
        district
        "Dhaka"
        "Chattogram"
    text_cmp
      status
      =
      "pending"

প্রথম query-র ২৫টি অর্ডার পর্ব ৪০-এর v1 interpreter-এর উত্তরের সঙ্গে হুবহু মেলে: নতুন grammar পুরোনো লেখার অর্থ বদলায়নি। তিনটি ভাঙা query-তে বার্তায় কলাম, পাওয়া token আর প্রত্যাশিত জিনিস, সবই ব্যবহারকারীর ভাষায়। শেষে দ্বিতীয় query-র গাছ: মূলে and_, আর not_ শুধু text_in-কে ঢাকে, stepper-এর ধাপ ৪-এর মতোই।

দুই parser, এক সত্য। হাতে লেখা parser আর Lark একই grammar-এর দুটি স্বাধীন বাস্তবায়ন। Test suite (অংশ ৬) ১,০০০টি এলোমেলো AST লেখায় ছাপিয়ে দুটিতে পাঠায়, আর ২০০টি অর্ডারে AST, Lark আর হাতে লেখা parser-এর উত্তর মেলায়: সবখানে মিল। এটি সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮-এর property-based ধারণার একটি প্রয়োগ, আর grammar নিজেই test-input বানানোর যন্ত্র (পর্ব ৪২-এর fuzzing).

৪ · অংশ ৩: অর্ডারের Mealy machine আর model checking

চাহিদা। অর্ডারের জীবনচক্র পর্ব ২৪-এ স্থির হয়েছে: Placed → Paid → Packed → Shipped → Delivered; Shipped-এর আগে বাতিল (Cancelled); টাকা দেওয়া থাকলে বাতিলের পর ফেরত (Refunded). এবার প্রতিটি ঘটনার সঙ্গে একটি কাজও হয়: টাকা কাটা, SMS, টাকা ফেরত। ব্যবসার সবচেয়ে জরুরি দাবি টাকা নিয়ে: ক্রেতার টাকা নেওয়া থাকলে একসময় হয় পণ্য পৌঁছাবে, নয় টাকা ফেরত যাবে।

মডেল: Mealy machine. ঘটনা পড়ে কাজ লেখা যন্ত্রটি একটি Mealy machine (পর্ব ১২): M = (Q, Σ, Δ, δ, ω, q0). এখানে Σ = {pay, pack, ship, deliver, cancel, refund}, output-এর alphabet Δ = {charge, sms, ok, pay_back, reject}. Refund বৈধ কি না নির্ভর করে আগে টাকা দেওয়া হয়েছিল কি না তার ওপর, তাই state একটি জোড়া: Q = {Placed, Paid, Packed, Shipped, Delivered, Cancelled, Refunded} × {p = 0, p = 1}, যেখানে p একটি “টাকা দেওয়া হয়েছে” পতাকা। δ আর ω total: কোনো ঘটনা অবৈধ হলে state একই থাকে, output reject.

state (p)ঘটনা / outputপরের state (p)
Placed (0)pay / chargePaid (1)
Paid, Packed, Shipped (1)pack, ship, deliver / smsপরের ধাপ (1)
Placed, Paid, Packed (p)cancel / okCancelled (p)
Cancelled (1)refund / pay_backRefunded (0)
অন্য যেকোনো জোড়াx / rejectএকই state

ধর্মটিকে formal করা। যন্ত্রের সঙ্গে একটি পর্যবেক্ষক জোড়া হলো: bal = (charge-এর সংখ্যা) − (pay_back-এর সংখ্যা), যা শুধু output দেখে হিসাব হয়, যন্ত্রের ভেতরের পতাকা দেখে নয়। দুটি মিলে একটি Kripke structure: অবস্থা (state, p, bal), সম্পর্ক R = যেকোনো ঘটনায় এক ধাপ (reject-এর self-loop থাকায় R total), আর দুটি atomic proposition: held = (bal = 1) আর done = (state ∈ {Delivered, Refunded})। দাবিটি তখন একটি LTL সূত্র:

φ = G(held → F done)

পড়া হয়: “সবসময় (G), যদি টাকা ধরা থাকে, তবে একসময় (F) অর্ডার শেষ হবে।” এটি একটি liveness property: কোনো সসীম পথ একে ভাঙতে পারে না, ভাঙার সাক্ষী একটি অসীম পথ, যেখানে টাকা ধরা অবস্থায় যন্ত্র চিরকাল ঘোরে। সসীম যন্ত্রে এমন পথ মানে একটি lasso: শুরু থেকে একটি খারাপ অবস্থা, তারপর সেখান থেকে একটি চক্র। Model checking-এর তত্ত্ব, অর্থাৎ ¬φ-এর Büchi automaton আর product-এ accepting চক্র খোঁজা, পর্ব ৭৭-এ; এখানে তার একটি সরল রূপ যথেষ্ট, কারণ এই যন্ত্রে reject-এর self-loop ছাড়া কোনো চক্র নেই (প্রতিটি বৈধ ঘটনা অর্ডারকে সামনে নেয়)।

Fairness. একটি সমস্যা আছে: ক্রেতা টাকা দিলেন, তারপর গুদাম চিরকাল কিছুই করল না। Paid অবস্থায় শুধু reject-এর চক্র: φ ভাঙে! দোষটি পরিবেশের, যন্ত্রের নয়। তাই একটি অনুমান, weak fairness: কোনো বৈধ ঘটনা যদি এক সময় থেকে চিরকাল সম্ভব থাকে, তবে একসময় কোনো বৈধ ঘটনা ঘটবেই। এই যন্ত্রে এর মানে, fair পথ শুধু সেই অবস্থায় চিরকাল থামতে পারে, যেখানে কোনো বৈধ ঘটনাই নেই: Delivered, Refunded, আর p = 0 সহ Cancelled. নিচের checker সব পৌঁছানো অবস্থা BFS-এ ঘোরে, fairness চালু ও বন্ধ রেখে, আর একটি bug-সংস্করণে, যেখানে cancel-এর কোড p পতাকা মুছে দেয়।

# Order Mealy machine + explicit-state check of G(bal=1 -> F(Delivered or Refunded))
from collections import deque
EV = ["pay", "pack", "ship", "deliver", "cancel", "refund"]
def mealy(s, paid, e, bug=False):          # -> (next state, paid flag, output)
    go = {("Placed", "pay"): "Paid", ("Paid", "pack"): "Packed", ("Packed", "ship"): "Shipped",
          ("Shipped", "deliver"): "Delivered"}
    if (s, e) in go: return go[s, e], paid or e == "pay", "charge" if e == "pay" else "sms"
    if e == "cancel" and s in ("Placed", "Paid", "Packed"):
        return "Cancelled", paid and not bug, "ok"   # bug: "clean up" the paid flag
    if e == "refund" and s == "Cancelled" and paid: return "Refunded", False, "pay_back"
    return s, paid, "reject"
def check(bug, fair):
    start = ("Placed", False, 0)               # (state, paid flag, bal = charges - paybacks)
    par, todo = {start: None}, deque([start])
    while todo:
        x = todo.popleft(); s, paid, bal = x
        moves = [(e,) + mealy(s, paid, e, bug) for e in EV]
        progress = [m for m in moves if m[3] != "reject"]
        if bal == 1 and s not in ("Delivered", "Refunded") and not (fair and progress):
            trace, y = [], x                    # bad state with a fair loop: rebuild path
            while par[y]: y, e = par[y]; trace.append(e)
            return f"VIOLATED: {' '.join(reversed(trace))} -> {s} (bal={bal}), then loop forever"
        for e, t, p, out in progress:
            y = (t, p, bal + (out == "charge") - (out == "pay_back"))
            if y not in par: par[y] = (x, f"{e}/{out}"); todo.append(y)
    return f"holds ({len(par)} reachable states)"
for bug in (False, True):
    for fair in (False, True):
        print(f"bug={bug!s:5} fairness={fair!s:5}:", check(bug, fair))

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

bug=False fairness=False: VIOLATED: pay/charge -> Paid (bal=1), then loop forever
bug=False fairness=True : holds (8 reachable states)
bug=True  fairness=False: VIOLATED: pay/charge -> Paid (bal=1), then loop forever
bug=True  fairness=True : VIOLATED: pay/charge cancel/ok -> Cancelled (bal=1), then loop forever

চারটি লাইন চারটি শিক্ষা। Fairness ছাড়া ঠিক যন্ত্রও “ভাঙে”: counterexample-টি গুদামের অলসতা, যন্ত্রের ভুল নয়; তাই fairness-এর অনুমান লিখে রাখা মডেলের অংশ। Fairness-সহ ঠিক যন্ত্রে দাবি মানে, আর পৌঁছানো অবস্থা মাত্র ৮টি, অর্থাৎ খোঁজটি পুরো, নমুনা নয়। Bug-এর সংস্করণে fairness-সহও দাবি ভাঙে, আর BFS সবচেয়ে ছোট সাক্ষী দেয়: টাকা নেওয়া, বাতিল, তারপর Cancelled-এ আটকে থাকা, কারণ p মুছে যাওয়ায় refund আর বৈধ নয়, অথচ bal = 1. লক্ষ করুন, bal যন্ত্রের পতাকা থেকে নয়, output থেকে গোনা; পতাকা নিজেই bug-এর শিকার, তাই তাকে বিশ্বাস করে যাচাই করলে bug ধরা পড়ত না।

সত্যিকারের run: z3 দিয়ে bounded model checking. একই প্রশ্ন একটি সম্পূর্ণ আলাদা কৌশলে। প্রতিটি ধাপ i-এর জন্য চলক si, pi, bi আর ঘটনা ei; transition একটি সূত্র; আর শেষ ধাপে চাওয়া হয় “bk = 1, আর অবস্থাটি এমন যেখানে কোনো বৈধ ঘটনা নেই, আর সেটি Delivered নয়” (fairness-সহ খারাপ lasso-র শুরু)। SMT solver z3 (z3-solver 5.4.1.0, MIT) k = 1, 2, … সূত্রের satisfiability দেখে (ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৭৭-এ BMC-র পরিচয়)।

def stuck(s, p):       # no progress event enabled: a fair run may stay here forever
    return Or(s == S["Delivered"], s == S["Refunded"], And(s == S["Cancelled"], Not(p)))
def bmc(bug, k):
    ...                # Int s0..sk, Bool p0..pk, Int b0..bk, Int e0..e(k-1)
    sol.add(sv[0] == S["Placed"], Not(pv[0]), bv[0] == 0)
    for i in range(k):
        sol.add(step(sv[i], pv[i], bv[i], ev[i], sv[i + 1], pv[i + 1], bv[i + 1], bug))
    sol.add(bv[k] == 1, stuck(sv[k], pv[k]), sv[k] != S["Delivered"])
    # sat -> read the trace from the model; unsat -> no bad run of length k

সত্যিকারের run (ডেস্কটপ, z3-solver 5.4.1.0):

~/bazarghar-toc$ uv run python mc_bmc.py
z3 5.4.1
bug=False k=1: no violation of length k
bug=False k=2: no violation of length k
bug=False k=3: no violation of length k
bug=False k=4: no violation of length k
bug=False k=5: no violation of length k
bug=False k=6: no violation of length k
bug=True  k=1: no violation of length k
bug=True  k=2: counterexample: Placed -> pay -> Paid -> cancel -> Cancelled

Bug-এর সংস্করণে z3 ঠিক সেই দুই ধাপের trace দিল, যা BFS দিয়েছিল: দুটি স্বাধীন পদ্ধতি একমত। ঠিক সংস্করণে k = 6 পর্যন্ত কিছু নেই। সাধারণভাবে BMC-র “না” শুধু “k ধাপের মধ্যে নেই” বোঝায়। কিন্তু এখানে একটি completeness threshold আছে: বৈধ ঘটনার কোনো চক্র নেই, আর সবচেয়ে লম্বা বৈধ পথ ৪ ধাপের (যেমন pay, pack, ship, deliver), তাই প্রতিটি পৌঁছানো অবস্থা ৪ ধাপের মধ্যেই আসে। k = 6 পর্যন্ত “না” তাই এখানে একটি সম্পূর্ণ প্রমাণ।

যন্ত্রটি সসীম বলেই প্রশ্নটি decidable. কিন্তু n-টি অর্ডারের যন্ত্র একসঙ্গে জুড়লে অবস্থা ৮n-এর মতো বাড়ে: state explosion (প্রতিকার পর্ব ৭৭-এ)।

৫ · অংশ ৪: কোন প্রশ্নের algorithm আছে — Turing machine-এর চোখে প্রকল্প

এই অংশে কোনো নতুন কোড নেই; আছে একটি মানচিত্র। প্রকল্পের প্রতিটি অংশ নিয়ে ব্যবস্থাপক যেসব প্রশ্ন করতে পারেন, সেগুলোকে language হিসেবে দেখলে (পর্ব ০৫) প্রশ্ন দাঁড়ায়: এমন কোনো Turing machine কি আছে, যা প্রতিটি input-এ থেমে সঠিক উত্তর দেয়? অর্থাৎ language-টি কি decidable?

প্রশ্নউত্তরকারণ (পর্ব)
একটি string বৈধ কোড বা কুপন?decidable, O(n)DFA চালানো (০৭)
পুরোনো আর নতুন validator কি একই language চেনে?decidableSymmetric difference-এর product আর emptiness (২০)
একটি query কি grammar মানে?decidable; LALR-এ O(n)CFL-এর membership (৩১, ৩৭, ৩৯)
দুটি যেকোনো CFG কি একই language দেয়? কোনো CFG কি ambiguous?সাধারণভাবে undecidablePCP থেকে reduction (৫৪)
কোনো query কি কোনো সম্ভাব্য অর্ডারে মেলে? দুটি query কি সমতুল্য?decidable, polynomialউপপাদ্য ৫.১, নিচে
অর্ডারের যন্ত্র কি φ মানে?decidableসসীম state, model checking (৭৭)
Slot-বণ্টন সম্ভব?decidable, কিন্তু NP-completeসসীম খোঁজ; অংশ ৫
Partner-এর যেকোনো Python plug-in কি কখনো ৫০%-এর বেশি ছাড় দেয়? সবসময় থামে?undecidableRice (৫৩), halting (৫১)

চতুর্থ সারির কারণে পর্ব ৪২-এ v1 আর v2-এর মিল fuzzing দিয়ে দেখা হয়েছিল, প্রমাণ দিয়ে নয়: দুটি যেকোনো CFG-এর সমতা পর্ব ৫৪-এ undecidable প্রমাণিত, তাই সব grammar-এ কাজ করে এমন কোনো সাধারণ algorithm নেই। একইভাবে “ambiguous কি না” সাধারণভাবে undecidable, অথচ LALR টেবিলে conflict না থাকা একটি যথেষ্ট শর্ত, যা আমরা পেয়েছি।

উপপাদ্য ৫.১ (query-র satisfiability polynomial সময়ে decidable)

SATQ = {⟨q⟩ ∣ q একটি v2 query, আর এমন একটি অর্ডার o আছে (amount যেকোনো অঋণাত্মক পূর্ণসংখ্যা, district আর status নিজ নিজ সসীম তালিকা থেকে) যাতে q(o) সত্য}. v2-তে field-এর সংখ্যা স্থির (ঠিক তিনটি), আর এই শর্তেই SATQ ∈ P.

প্রমাণ:

  1. q-এর প্রতিটি পরমাণু একটিমাত্র field নিয়ে, আর প্রতিটি তুলনা একটি ধ্রুবকের সঙ্গে। ধরুন q-এ amount-এর ধ্রুবকগুলো c1 < c2 < ⋯ < cm, যেখানে m ≤ |q|. — grammar-এর নিয়ম A
  2. সংখ্যারেখাকে ভাগ করা হলো 2m + 1টি অঞ্চলে: প্রতিটি ci নিজে, আর পাশাপাশি দুটি ধ্রুবকের মাঝের (এবং দুই প্রান্তের) খোলা অংশ। একটি অঞ্চলের সব পূর্ণসংখ্যায় amount-এর প্রতিটি পরমাণুর মান একই, কারণ সেখানে কোনো ধ্রুবক পার হওয়া হয় না। ফাঁকা অঞ্চল বাদ, বাকিগুলো থেকে একটি করে প্রতিনিধি। — তুলনার সংজ্ঞা
  3. district-এর জন্য q-এ উল্লেখিত মানগুলো, আর তালিকার একটি অনুল্লেখিত মান (যদি থাকে): বড়জোর d + 1টি প্রতিনিধি; status-এর জন্যও একইভাবে s + 1টি। অনুল্লেখিত সব মান প্রতিটি পরমাণুতে একই আচরণ করে। — = , != আর IN শুধু উল্লেখিত মান দেখে
  4. q-এর মান শুধু পরমাণুগুলোর মানের ওপর নির্ভর করে, আর পরমাণুগুলোর মান শুধু প্রতিটি field কোন অঞ্চলে আছে তার ওপর। তাই q satisfiable ⇔ কোনো প্রতিনিধি-ত্রয়ীতে q সত্য। — AND, OR, NOT-এর সংজ্ঞা
  5. ত্রয়ীর সংখ্যা ≤ (2m + 1)(d + 1)(s + 1) ≤ (2|q| + 1)3, আর প্রতিটি মূল্যায়ন O(|q|) সময়ে। মোট সময় |q|-এর polynomial. ∎

উপসিদ্ধান্ত। দুটি query q1, q2 সমতুল্য ⇔ (q1 AND NOT q2) OR (NOT q1 AND q2) unsatisfiable; সেটিও একটি v2 query, তাই সমতুল্যতাও P-তে। যেমন De Morgan: NOT (A OR B) আর NOT A AND NOT B সব প্রতিনিধিতে মেলে।

কেন এত সহজ? কারণ ভাষাটি দুর্বল। মাত্র তিনটি field, আর প্রতিটি তুলনা একটি ধ্রুবকের সঙ্গে। যদি ভাষায় n-টি স্বাধীন হ্যাঁ/না field থাকত (gift, express, fragile …), তবে যেকোনো CNF সূত্রকে একটি query-তে লেখা যেত, আর satisfiability হতো NP-complete (পর্ব ৬০)। আবার যদি অনেকগুলো পূর্ণসংখ্যার field আর তাদের গুণ-যোগে গড়া সমীকরণ লেখা যেত, প্রশ্নটি Hilbert-এর দশম সমস্যার দিকে এগোত, যা পর্ব ৫৫-এ undecidable. ভাষার প্রতিটি নতুন বৈশিষ্ট্য তাই শুধু সুবিধা নয়, একটি তাত্ত্বিক সিদ্ধান্তও।

Partner-এর plug-in. একটি partner অনুরোধ করল: “আমাদের ছাড়ের নিয়ম Python-এ লিখে আপনাদের সার্ভারে চালাতে দিন।” বাজারঘরের দল জানতে চায়, plug-in কখনো ৫০%-এর বেশি ছাড় দেবে কি না। প্রশ্নটি program-এর আচরণ নিয়ে, লেখার আকার নিয়ে নয়: এটি একটি semantic property. কিছু program ধর্মটি মানে, কিছু মানে না, অর্থাৎ ধর্মটি non-trivial. Rice-এর theorem (পর্ব ৫৩) বলে, Turing-complete ভাষার program-এর এমন প্রতিটি ধর্ম undecidable. সরাসরি একটি reduction-ও দেখা যায়: যেকোনো ⟨M, w⟩ থেকে এমন plug-in বানানো যায়, যা আগে M-কে w-তে চালায়, আর থামলে ৬০% ছাড় দেয়। Plug-in বিপজ্জনক ⇔ M w-তে থামে, তাই আমাদের প্রশ্নের decider থাকলে halting problem-এর decider থাকত (পর্ব ৫১)।

প্রকৌশলের উত্তর দুটি: plug-in-এর ফলাফলকে একটি runtime guard দিয়ে ৫০%-এর নিচে কেটে রাখা, অথবা partner-কে Python না দিয়ে query ভাষার মতো একটি দুর্বল নিয়ম-ভাষা দেওয়া, যেখানে উপপাদ্য ৫.১-এর মতো প্রশ্ন যন্ত্রেই উত্তর দেওয়া যায়। দ্বিতীয়টিই এই প্রকল্পের মূল নকশা-নীতি।

৬ · অংশ ৫: delivery slot — NP-complete প্রমাণ আর SAT solver

চাহিদা। পর্ব ৭৩-এ slot সমস্যায় শুধু বিরোধী জোড়া ছিল (graph colouring). বাস্তবের বাজারঘরে আরও দুটি শর্ত: প্রতিটি অর্ডারের একটি সময়-জানালা (ক্রেতা শুধু কিছু slot-এ বাসায় থাকেন), আর প্রতিটি slot-এ রাইডারের সংখ্যা সীমিত, তাই বড়জোর c-টি অর্ডার। সিদ্ধান্ত-সমস্যাটি:

সংজ্ঞা ও উপপাদ্য ৬.১

SLOT = {⟨O, k, W, C, c⟩ ∣ এমন a: O → {1, …, k} আছে যাতে প্রতিটি o-এর জন্য a(o) ∈ W(o), প্রতিটি (u, v) ∈ C-এর জন্য a(u) ≠ a(v), আর প্রতিটি slot-এ বড়জোর c-টি অর্ডার}. SLOT NP-complete.

প্রমাণ:

  1. SLOT ∈ NP: certificate হলো a নিজেই। Verifier প্রতিটি অর্ডারের জানালা, প্রতিটি বিরোধ আর প্রতিটি slot-এর গণনা দেখে, মোট O(|O| + |C| + k) সময়ে। — verifier-এর সংজ্ঞা (৫৮)
  2. Reduction 3-COLOR ≤p SLOT: graph G = (V, E) থেকে f(G) = ⟨V, 3, W, E, |V|⟩, যেখানে প্রতিটি W(v) = {1, 2, 3}. অর্থাৎ vertex = অর্ডার, edge = বিরোধ, রং = slot, আর capacity এত বড় যে কোনো বাধা দেয় না। f স্পষ্টতই polynomial সময়ে গণনাযোগ্য। — polynomial-time reduction-এর সংজ্ঞা (৫৯)
  3. ⇒: G-এর একটি সঠিক 3-colouring χ থাকলে a = χ সব জানালা মানে (জানালা পুরো {1, 2, 3}), প্রতিটি বিরোধ মানে (edge-এর দুই প্রান্তে আলাদা রং), আর কোনো slot-এ |V|-এর বেশি অর্ডার থাকতে পারে না। — সরাসরি
  4. ⇐: f(G)-এর একটি বৈধ a থাকলে, a প্রতিটি edge-এর দুই প্রান্তে আলাদা slot দেয়, তাই a নিজেই G-এর একটি 3-colouring. — সরাসরি
  5. 3-COLOR NP-complete (পর্ব ৬১), তাই ধাপ ২–৪ থেকে SLOT NP-hard; ধাপ ১-সহ NP-complete. ∎

দিকটি লক্ষ করুন: জানা কঠিন সমস্যা (3-COLOR) থেকে নতুন সমস্যার দিকে। আরও শিক্ষণীয় হলো কঠিনতার সীমানা, অর্থাৎ কোন বৈশিষ্ট্য সমস্যাকে কঠিন করে:

  • বিরোধ না থাকলে P-তে: শুধু জানালা আর capacity থাকলে এটি একটি bipartite বণ্টন: উৎস থেকে প্রতিটি অর্ডারে ১, অর্ডার থেকে জানালার slot-এ ১, slot থেকে গন্তব্যে c. সব অর্ডার বসানো যায় ⇔ maximum flow = |O| (integral flow-এর উপপাদ্য; DSA কোর্সের পর্ব ৪৭)।
  • Capacity না থাকলে: জানালা আর বিরোধ মিলে list colouring; সব জানালা {1, 2, 3} হলে এটিই 3-COLOR, তাই NP-complete. কিন্তু প্রতিটি জানালায় বড়জোর দুটি slot থাকলে প্রতিটি অর্ডারের পছন্দ একটি Boolean চলক, প্রতিটি বিরোধ দুই-literal-এর clause: 2SAT, polynomial.

Encoding. SAT solver-এর জন্য CNF: চলক xo,s = “অর্ডার o slot s-এ”, শুধু জানালার ভেতরের s-এর জন্য (জানালার বাইরের চলক বানানোই হয় না)। নিচের stepper পাঁচটি অর্ডারের একটি ছোট instance-এ clause-গোষ্ঠীগুলো একে একে যোগ করে: A{1, 2}, B{1, 2}, C{2, 3}, D{1, 3}, E{1, 2, 3}; বিরোধ A–B, B–C, C–D, D–E, A–E; capacity c = 2.

1চলক: জানালার ভেতরে শুধু2A1 ∨ A2, …, E1 ∨ E2 ∨ E33¬A1 ∨ ¬A2, …4¬A1 ∨ ¬B1, ¬A2 ∨ ¬B2, …5¬A1 ∨ ¬B1 ∨ ¬D1, …6solver / brute force
হিসাব
এই গোষ্ঠী
মোট clause
  1. চলক। প্রতিটি অর্ডারের জানালার প্রতিটি slot-এর জন্য একটি: ২ + ২ + ২ + ২ + ৩ = ১১টি। জানালার শর্ত তাই আলাদা clause ছাড়াই মানা হয়ে যায়।
  2. অন্তত একটি। প্রতিটি অর্ডারে একটি clause, মোট ৫টি: যেমন A1 ∨ A2, আর E1 ∨ E2 ∨ E3.
  3. বড়জোর একটি। প্রতিটি অর্ডারের প্রতিটি slot-জোড়ায় একটি: A, B, C, D-তে একটি করে, E-তে তিনটি, মোট ৭টি।
  4. বিরোধ। প্রতিটি বিরোধী জোড়ার প্রতিটি সাধারণ slot-এ একটি: A–B দুটি (১, ২), B–C একটি (২), C–D একটি (৩), D–E দুটি (১, ৩), A–E দুটি (১, ২): মোট ৮টি।
  5. Capacity. “বড়জোর ২” মানে কোনো তিনজন একসঙ্গে নয়: slot ১-এ A, B, D, E থেকে প্রতিটি তিনজনের দলে একটি clause (৪টি), slot ২-এ A, B, C, E থেকে ৪টি, slot ৩-এ C, D, E থেকে ১টি। মোট ৯টি; সব মিলে ২৯টি clause. বড় instance-এ এই সরল রূপ বিস্ফোরিত হয়, তাই সেখানে cardinality constraint-এর counter encoding.
  6. সমাধান। একটি model: A1, B2, C3, D1, E2. সব বিরোধ আলাদা slot-এ, slot ১ আর ২-এ দুজন করে। মোট ঠিক ৫টি model, আর brute force-এ বৈধ পরিকল্পনাও ৫টি। c = 1 হলে ৩৫টি clause আর কোনো model নেই: পাঁচজন তিন slot-এ একজন করে ধরে না।

নিচের ব্লক stepper-এর সংখ্যাগুলো গোনে, CNF-এর model (সব 211 মান-বসানো ঘুরে) আর সংজ্ঞা থেকে বৈধ পরিকল্পনা আলাদা গুনে মেলায়, আর উপপাদ্য ৬.১-এর reduction দুটি graph-এ চালায়।

# Delivery slots -> CNF, checked against brute force; then 3-COLOR <=p SLOT on two graphs
from itertools import combinations, product
def encode(win, conf, cap):              # win: order -> allowed slots
    var = {(o, s): i + 1 for i, (o, s) in enumerate((o, s) for o in win for s in win[o])}
    cnf = [[var[o, s] for s in win[o]] for o in win]                       # at least one
    cnf += [[-var[o, a], -var[o, b]] for o in win for a, b in combinations(win[o], 2)]
    cnf += [[-var[u, s], -var[v, s]] for u, v in conf for s in win[u] if s in win[v]]
    for s in {s for o in win for s in win[o]}:                             # capacity
        cnf += [[-var[o, s] for o in g] for g in combinations([o for o in win if s in win[o]], cap + 1)]
    return var, cnf
def models(var, cnf):                     # brute force over all 2^n assignments
    n = len(var)
    return sum(all(any((l > 0) == bits[abs(l) - 1] for l in c) for c in cnf)
               for bits in product((False, True), repeat=n))
def schedules(win, conf, cap):           # the problem itself, by brute force
    out = []
    for pick in product(*win.values()):
        a = dict(zip(win, pick))
        if all(a[u] != a[v] for u, v in conf) and max(map(pick.count, set(pick))) <= cap:
            out.append(a)
    return out
win = {"A": [1, 2], "B": [1, 2], "C": [2, 3], "D": [1, 3], "E": [1, 2, 3]}
conf = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "E"), ("A", "E")]
for cap in (2, 1):
    var, cnf = encode(win, conf, cap)
    sch = schedules(win, conf, cap)
    print(f"cap={cap}: vars {len(var)}, clauses {len(cnf)}, CNF models {models(var, cnf)},"
          f" schedules {len(sch)}", sch[0] if sch else "-")
for name, edges in [("C5", [(i, (i + 1) % 5) for i in range(5)]), ("K4", list(combinations(range(4), 2)))]:
    nodes = sorted({x for e in edges for x in e})          # 3-COLOR -> SLOT: 3 slots, no limit
    var, cnf = encode({v: [1, 2, 3] for v in nodes}, edges, len(nodes))
    print(f"{name}: SLOT instance has {models(var, cnf)} schedules -> 3-colourable: {models(var, cnf) > 0}")

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

cap=2: vars 11, clauses 29, CNF models 5, schedules 5 {'A': 1, 'B': 2, 'C': 3, 'D': 1, 'E': 2}
cap=1: vars 11, clauses 35, CNF models 0, schedules 0 -
C5: SLOT instance has 30 schedules -> 3-colourable: True
K4: SLOT instance has 0 schedules -> 3-colourable: False

CNF-এর model আর বৈধ পরিকল্পনা দুই ক্ষেত্রেই সমান (৫ আর ০)। এটি “SAT কি না”-র চেয়ে কড়া মিল: model আর পরিকল্পনার মধ্যে এক-এক সম্পর্ক। Reduction-এর অংশে পাঁচ-চক্র C5-এর SLOT instance-এ ৩০টি পরিকল্পনা, আর C5-এর তিন রঙের সঠিক colouring-ও ঠিক ৩০টি (chromatic polynomial (k − 1)n + (−1)n(k − 1), k = 3, n = 5-এ 32 − 2); K4-এর কোনো 3-colouring নেই, তাই instance-টিও অসম্ভব। উপপাদ্যের দুই দিক ছোট উদাহরণে সংখ্যায় মিলল।

সত্যিকারের run: ৬০টি অর্ডার, CaDiCaL. uv প্রকল্পে python-sat 1.9.dev23 (PySAT, MIT; ভেতরের CaDiCaL 1.9.5-ও MIT) আর networkx 3.7 (BSD-3-Clause). ৮টি slot, প্রতিটি অর্ডারের জানালা পাশাপাশি ৩ থেকে ৫টি slot, প্রতিটি জোড়া ০.২ সম্ভাবনায় বিরোধী (seed 80). “বড়জোর এক” আর capacity দুটিই sequential counter-এ। প্রতিটি SAT উত্তর একটি solver-ছাড়া checker-এ মেলানো, আর তুলনার জন্য বিরোধ বাদ দিয়ে max-flow-এর উত্তর। দ্বিতীয় instance-এ জানালা সরু (৩ থেকে ৪টি slot).

def core(win, conf, cap):               # a minimal set of orders that cannot all be served
    cls, pool, x = encode(win, conf, cap, sel=True)   # sel: (-on_o OR x_o1 OR ...)
    on = {o: pool.id(("on", o)) for o in win}
    with Solver(name="cadical195", bootstrap_with=cls) as S:
        assert not S.solve(assumptions=list(on.values()))
        keep = sorted(o for o in win if on[o] in set(S.get_core()))
        for o in list(keep):                # deletion-based shrinking
            trial = [on[q] for q in keep if q != o]
            if not S.solve(assumptions=trial): keep.remove(o)
    return keep

সত্যিকারের run (ডেস্কটপ, python-sat 1.9.dev23 / CaDiCaL, networkx 3.7):

~/bazarghar-toc$ uv run python sched.py
python-sat 1.9.dev23 | networkx 3.7
orders 60, slots 8, windows 3-5 slots, conflicts 349
  ignoring conflicts, max-flow says capacity 8 is enough
  cap= 7: vars  1717 clauses  4108 UNSAT conflicts 29507 0.66s
  cap= 8: vars  1838 clauses  4334 SAT   conflicts  401 0.01s  checker: True
  cap=12: vars  2162 clauses  4930 SAT   conflicts   44 0.00s  checker: True
orders 60, slots 8, windows 3-4 slots, conflicts 389
  ignoring conflicts, max-flow says capacity 8 is enough
  cap= 7: vars  1447 clauses  3437 UNSAT conflicts   58 0.00s
  cap= 8: vars  1538 clauses  3603 UNSAT conflicts   86 0.00s
  cap=12: vars  1742 clauses  3971 UNSAT conflicts   41 0.00s
  minimal core (orders): [7, 8, 15, 18, 33, 39, 42]
    order 7: slots [1, 2, 3], conflicts with [18, 33, 42]
    order 8: slots [1, 2, 3], conflicts with [15, 18, 33, 39]
    order 15: slots [0, 1, 2, 3], conflicts with [8, 18, 33, 39, 42]
    order 18: slots [1, 2, 3], conflicts with [7, 8, 15, 33, 39, 42]
    order 33: slots [0, 1, 2], conflicts with [7, 8, 15, 18, 42]
    order 39: slots [1, 2, 3], conflicts with [8, 15, 18]
    order 42: slots [0, 1, 2], conflicts with [7, 15, 18, 33]

প্রথম instance-এ capacity 8-এ পরিকল্পনা মিলেছে, checker সন্তুষ্ট; max-flow-এর নিম্নসীমা ৮-ই উত্তর। সবচেয়ে শিক্ষণীয় লাইন cap = 7: ৬০টি অর্ডার ৮ × ৭ = ৫৬টি জায়গায় ধরে না, এটি এক লাইনের গণনা, অথচ CDCL solver-এর লেগেছে ২৯,৫০৭টি বিরোধ। এটি পর্ব ৭৩-এর pigeonhole-এর দেয়াল: resolution-ভিত্তিক solver গোনা জানে না। প্রতিকার: encoding-এর আগে k × c ≥ |O| নিজে দেখা। দ্বিতীয় instance কোনো capacity-তেই সম্ভব নয়, তাই সমস্যা জানালা আর বিরোধে। Selector চলক দিয়ে solver একটি unsat core দিল, আর একে একে বাদ দিয়ে ছোট করে পাওয়া গেল ৭টি অর্ডার, যাদের জানালা সবই slot ০–৩-এর মধ্যে আর পরস্পরে ঘন বিরোধ। Test suite brute force দিয়ে প্রমাণ করেছে যে এই ৭টি একসঙ্গে অসম্ভব, আর যেকোনো একটি বাদ দিলে বাকি ছয়টি সম্ভব। ব্যবস্থাপকের জন্য এটিই কাজের উত্তর: “এই সাতজনের একজনের জানালা বাড়ান।”

৭ · অংশ ৬: পুরো প্রকল্প জোড়া — test, মূল্যায়ন আর পরের ধাপ

প্রতিটি অংশ আলাদা চলে, কিন্তু প্রকল্প হস্তান্তরের যোগ্য হয় তখনই, যখন একটি আদেশে সব দাবি আবার যাচাই করা যায়। এর জন্য একটি test suite: প্রতিটি test একটি অংশকে একটি স্বাধীন উৎসের বিরুদ্ধে মেলায়; পাতার চারটি ব্লকও suite-এ load হয়।

অংশকী মেলানো হয়test
Validatorminimal state-সংখ্যা; library-র DFA = পাতার DFA = স্পেসিফিকেশন, দৈর্ঘ্য ০–৭-এর সব string৯
QueryLark = হাতে লেখা parser = AST থেকে সরাসরি, ১,০০০টি এলোমেলো query; পাঁচটি ভাঙা query-র কলাম১৫
অর্ডার-যন্ত্রBFS checker = z3 BMC, bug-সহ ও ছাড়া; ২,০০০টি এলোমেলো ঘটনা-ধারা২
SlotCaDiCaL = brute force, ২০০টি ছোট এলোমেলো instance; core-এর minimality brute force-এ২১
~/bazarghar-toc$ uv run pytest --version
pytest 9.2.0
~/bazarghar-toc$ uv run python -m pytest -q -p no:cacheprovider tests
...............................................                          [100%]
47 passed in 4.45s

সত্যিকারের run (pytest 9.2.0, MIT): ৪৭টি test, সাড়ে চার সেকেন্ডে। কয়েকটি test সসীম ক্ষেত্রে পুরো প্রমাণ, বাকিগুলো নমুনা; তাই প্রতিটি অংশের পাশে একটি প্রমাণও আছে (ভাবনার প্রশ্ন ২)।

প্রকল্পের checklist

নিজেকে মূল্যায়ন — rubric

দিকশুরুদক্ষচমৎকার
মডেল বাছাইকোড চলে, শ্রেণি অস্পষ্টপ্রতিটি অংশের শ্রেণি (regular, CFL, …) লেখাকেন দুর্বলতর যন্ত্র যথেষ্ট নয়, তার প্রমাণ
নির্মাণহাতে লেখা যন্ত্রproduct, minimisation, LALR, encodingপ্রতিটি নির্মাণের সঠিকতার যুক্তি
যাচাইকয়েকটি উদাহরণbrute force + differential test+ ইচ্ছাকৃত bug ধরা + solver/BMC + test suite
সীমাউল্লেখ নেইNP-hard আর undecidable অংশ চিহ্নিতসীমানা দেখানো: কোন বৈশিষ্ট্য বাদ দিলে সহজ হয়
যোগাযোগশুধু আউটপুটআউটপুট + এক বাক্যের অর্থcore বা trace থেকে ব্যবস্থাপকের সিদ্ধান্ত

আরও এগোতে চাইলে

  • নতুন syntax নিরাপদে: query ভাষায় amount BETWEEN 500 AND 1000 যোগ করুন (অনুশীলন ১), আর পুরোনো সব test আবার চালান।
  • Optimisation: সবচেয়ে কম capacity-র বদলে “সবচেয়ে কম অর্ডার বাদ পড়ুক” চাইলে MaxSAT লাগে; selector চলকগুলোকে soft clause বানিয়ে চেষ্টা করুন।
  • Plug-in-এর নিয়ম-ভাষা: query grammar-এর মতো একটি ছোট ছাড়-ভাষা নকশা করুন, যেখানে “ছাড় কখনো ৫০%-এর বেশি নয়” উপপাদ্য ৫.১-এর কৌশলে যন্ত্রে যাচাই করা যায়।

আরও গভীরে: “ইনপুটের ভাষা যত দুর্বল, তত নিরাপদ” ধারণাটি গবেষণায় language-theoretic security (LangSec) নামে পরিচিত; Len Sassaman, Meredith Patterson, Sergey Bratus প্রমুখ ২০১০-এর দশকের শুরুতে যুক্তি দেন যে বহু নিরাপত্তা-ত্রুটির মূলে আছে ইনপুট-যাচাইকারী, যার ভাষা অজান্তে context-free বা তার চেয়েও শক্তিশালী। একই সুরে W3C-র “Rule of Least Power” (২০০৬ সালের দিকে Tim Berners-Lee ও Noah Mendelsohn-এর লেখা) বলে, যে কাজে দুর্বল ভাষা যথেষ্ট সেখানে দুর্বল ভাষাই বাছুন, কারণ তখন অন্যরা তার লেখা বিশ্লেষণ করতে পারে।

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

  • Validator-কে regex না DFA দিয়ে লিখবেন? গণিতে সমান শক্তি; বাস্তবে DFA রৈখিক সময়ের নিশ্চয়তা দেয়, backtracking regex দেয় না (ReDoS).
  • Query ভাষার parser-এ কেন CFG, regex নয়? যেকোনো গভীরতার বন্ধনী মেলানো non-regular; pumping lemma দিয়ে প্রমাণ।
  • Safety আর liveness-এর পার্থক্য? Safety ভাঙে সসীম trace-এ, liveness ভাঙার সাক্ষী অসীম (lasso); liveness-এ প্রায়ই fairness লাগে।
  • নতুন সমস্যা NP-complete দেখাতে কোন দিকে reduce? জানা NP-complete A থেকে নতুন B-তে, A ≤p B, আর B ∈ NP আলাদা করে।
  • “এই plug-in কখনো ভুল করবে না” কি যন্ত্রে যাচাইযোগ্য? Turing-complete ভাষায় সাধারণভাবে না (Rice); ভাষা সীমিত করলে বা runtime guard দিলে হ্যাঁ।

৮ · AI-এর যুগে ক্যাপস্টোন — AI সহকারীর সঙ্গে formal toolkit

এই পুরো প্রকল্পের প্রতিটি ফাইল একটি AI assistant কয়েক মিনিটে লিখে দিতে পারে, আর সবগুলোই চলবে। বিপদ সেখানে: চলা আর ঠিক হওয়া আলাদা। এই বিষয়ে AI-এর পরিচিত ভুল: ভুল language-এর DFA (দৈর্ঘ্যে off-by-one, dead state বা ফাঁকা string ভুলে যাওয়া); NOT-কে পুরো C-এর ওপর বসিয়ে precedence উল্টানো; pumping lemma-য় split নিজে বেছে নেওয়া; fairness ভুলে ভুল “bug”, বা fairness এত শক্ত যে আসল bug লুকায়; উল্টো দিকের reduction; decidable আর recognizable গুলিয়ে ফেলা; “timeout দিলে halting মিটে যায়” বলা; P বনাম NP-কে মীমাংসিত বলা; আর বানানো reference দেওয়া।

ভালো ব্যবহার: AI-কে কোড আর খসড়া প্রমাণ লিখতে দিন, কিন্তু প্রতিটি দাবির সঙ্গে একটি যাচাই-কোড চান, আর সেটি নিজে চালান।

আমি গণনার তত্ত্বের একটি ক্যাপস্টোন প্রকল্প করছি। বাজারঘর নামে একটি কাল্পনিক দোকানের জন্য: ১. অর্ডার কোড (BG- আর চারটি অঙ্ক) বা কুপন (ছয় চিহ্ন, বড় হাতের অক্ষর বা অঙ্ক, ভেতরে SALE) চেনার একটি DFA দাও। সঙ্গে একটি আলাদা ref(w) ফাংশন দাও যা নিয়মটি সরাসরি লেখে, আর দৈর্ঘ্য ৭ পর্যন্ত সব string-এ DFA আর ref মেলানোর কোড দাও। ২. আমার Lark grammar (নিচে দিচ্ছি) বদলাবে না। শুধু একটি Transformer দাও যা query থেকে Python ফাংশন বানায়। ৩. অর্ডারের Mealy machine-এর জন্য G(held → F done) যাচাইয়ের BFS code দাও। Fairness-এর অনুমান আলাদা করে লেখো, আর দেখাও fairness ছাড়া কী counterexample আসে। ৪. সময়-জানালা, বিরোধ আর capacity-সহ slot সমস্যা NP-complete, প্রমাণ লেখো। Reduction কোন দিকে আর কেন, স্পষ্ট বলো। ৫. যে দাবি তুমি নিশ্চিত নও, বা যে reference তুমি যাচাই করোনি, সেটি চিহ্নিত করো; বানিয়ো না।

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

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

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

প্র ০১বাজারঘরের দল query ভাষায় loop আর নিজের function যোগ করতে চায়, “যাতে ক্ষমতা বাড়ে”। গণনার তত্ত্বের দৃষ্টিতে এই সিদ্ধান্তের দাম কী?

দাম হলো প্রশ্ন করার অধিকার হারানো। আজকের v2 ভাষায় একটি query শুধু একটি Boolean সূত্র, যার পরমাণু একটি field আর একটি ধ্রুবক। এ কারণেই উপপাদ্য ৫.১ খাটে: “কোনো অর্ডার কি মিলবে?” আর “দুটি query কি সমতুল্য?” polynomial সময়ে উত্তরযোগ্য। Admin panel তাই একটি query সংরক্ষণের আগেই বলতে পারে, “এই শর্ত কখনো কোনো অর্ডারে মিলবে না”, বা পুরোনো আর নতুন report একই কি না। প্রতিটি query থামে, কারণ মূল্যায়ন গাছের আকারে সসীম।

Loop আর recursive function যোগ করলে ভাষাটি Turing-complete হয়ে যেতে পারে। তখন Rice-এর theorem (পর্ব ৫৩) প্রতিটি non-trivial আচরণগত প্রশ্ন undecidable করে দেয়: query থামবে কি না, কোনো অর্ডার মেলে কি না, দুটি query সমান কি না। একটি query সার্ভার আটকে রাখতে পারে, আর আগে থেকে তা ধরা যাবে না; timeout শুধু থামায়, decide করে না (পর্ব ৫৫)। নিরাপত্তার দিকেও একই কথা: ভাষা যত শক্তিশালী, যাচাই তত কঠিন। LangSec গবেষকেরা ঠিক এই যুক্তি দেন, আর W3C-র “Rule of Least Power” (২০০৬ সালের দিকে প্রকাশিত) প্রকৌশলের ভাষায় একই কথা বলে: কাজটি যে সবচেয়ে দুর্বল ভাষায় সম্ভব, সেটিই বাছুন। SQL-এর মূল query অংশ দীর্ঘদিন ইচ্ছা করে সীমিত ছিল, আর পরে recursive query যোগ হওয়ার পর তার বিশ্লেষণ জটিল হয়েছে, এটি একটি পরিচিত উদাহরণ।

মধ্যপথও আছে। সীমিত পুনরাবৃত্তি (যেমন “প্রতিটি অর্ডারের প্রতিটি পণ্যের জন্য”, যার সংখ্যা ডেটায় সসীম) যোগ করলে ভাষা শক্তিশালী হয় কিন্তু থামা নিশ্চিত থাকে; এমন ভাষায় অনেক প্রশ্ন decidable থাকে, যদিও জটিলতা বাড়তে পারে (NP বা PSPACE). সিদ্ধান্তটি তাই প্রকৌশল আর তত্ত্বের যৌথ: কোন নতুন প্রশ্ন সম্ভব হবে, আর কোন পুরোনো প্রশ্ন হারাবে, দুটি তালিকা পাশাপাশি লিখে সিদ্ধান্ত নিন।

মূল উপলব্ধি: ভাষায় ক্ষমতা যোগ করা মানে তার সম্পর্কে প্রশ্নের উত্তর দেওয়ার ক্ষমতা হারানো; Turing-complete হলে Rice-এর theorem সব আচরণগত যাচাই বন্ধ করে দেয়।

প্র ০২এই প্রকল্পে চার ধরনের যাচাই আছে: সব ছোট ইনপুটে brute force, এলোমেলো differential test, BMC আর প্রমাণ। কোনটি কখন “প্রমাণ”, আর কোনটি শুধু আস্থা বাড়ায়?

Edsger Dijkstra ১৯৭০-এর আশপাশে লিখেছিলেন, program testing bug-এর উপস্থিতি দেখাতে পারে, অনুপস্থিতি কখনো নয়। কথাটি সাধারণভাবে সত্য, কিন্তু এর একটি গুরুত্বপূর্ণ ব্যতিক্রম আছে: যদি সম্ভাব্য সব ক্ষেত্র সসীম আর সবগুলোই পরীক্ষা করা হয়, তবে test-ই প্রমাণ। Validator-এর brute force দৈর্ঘ্য ৫ পর্যন্ত Σ-এর সব string পরীক্ষা করেছে: ওই দৈর্ঘ্যের জন্য এটি সম্পূর্ণ প্রমাণ। কিন্তু সব দৈর্ঘ্যের জন্য প্রমাণ আসে অন্য পথে: দুটি DFA-র equivalence একটি decidable প্রশ্ন (পর্ব ২০), আর automata-lib-এর equivalence পরীক্ষা ঠিক সেই product-আর-emptiness algorithm চালায়। এর ওপর ভরসা করতে হলে library-কে বিশ্বাস করতে হয়, তাই আমরা নিজের Moore-এর algorithm দিয়েও সংখ্যা মিলিয়েছি: দুটি স্বাধীন পথ।

Differential test (২,০০,০০০টি এলোমেলো string, ১,০০০টি এলোমেলো query) প্রমাণ নয়; এটি একটি পরিসংখ্যানগত আস্থা, যার শক্তি নির্ভর করে input কতটা “কোণ” ছোঁয় তার ওপর। এ কারণে প্রায়-বৈধ input (একটি অক্ষর বদল) ইচ্ছা করে বেশি দেওয়া হয়েছিল: বেশিরভাগ ভুল সীমানাতেই থাকে।

BMC-র “না” সাধারণত শুধু k ধাপ পর্যন্ত নিশ্চয়তা দেয়; Armin Biere ও সহকর্মীরা ১৯৯৯ সালের দিকে কৌশলটি জনপ্রিয় করার সময় থেকেই completeness threshold-এর প্রশ্নটি আলোচিত। আমাদের যন্ত্রে বৈধ ঘটনার চক্র নেই, আর সবচেয়ে লম্বা পথ ৪ ধাপ, তাই k = 6 পর্যন্ত “না” আসলে পূর্ণ প্রমাণ। এই যুক্তি না লিখলে একই আউটপুট শুধু “ছয় ধাপে bug পাইনি” বলত। শেষে NP-completeness-এর reduction বা Rice-এর প্রয়োগ পুরোপুরি গাণিতিক প্রমাণ; সেখানে কোড শুধু ছোট উদাহরণে প্রমাণের দাবি মেলায় (C5-এর ৩০টি colouring).

মূল উপলব্ধি: সসীম ক্ষেত্রে সম্পূর্ণ খোঁজ প্রমাণ, এলোমেলো test শুধু আস্থা; BMC প্রমাণ হয় যখন k completeness threshold ছোঁয়, আর প্রতিটি যাচাই কোন শ্রেণির, তা লিখে রাখা প্রকল্পের অংশ।

প্র ০৩৬০টি অর্ডার ৫৬টি জায়গায় ধরে না, এটি এক লাইনের গণনা। তবু CaDiCaL-এর ২৯,৫০৭টি বিরোধ লাগল, অথচ capacity 8-এর আসল সমাধান মাত্র ৪০১টিতে। কেন, আর একজন প্রকৌশলী কী করবেন?

কারণটি পর্ব ৭৩-এর সবচেয়ে গভীর ফল। CDCL solver-এর প্রতিটি UNSAT উত্তর আসলে একটি resolution প্রমাণ, আর Armin Haken ১৯৮৫ সালে প্রমাণ করেন যে pigeonhole সূত্রের (n + 1 কবুতর, n খোপ) প্রতিটি resolution প্রমাণ n-এর সূচকীয় আকারের। আমাদের cap = 7-এর সূত্রের ভেতরে ঠিক এমন একটি pigeonhole লুকানো: ৬০টি অর্ডারকে ৫৬টি “জায়গায়” বসানোর চেষ্টা। Resolution “গুনতে” জানে না; সে শুধু clause জুড়ে নতুন clause বানায়, আর কবুতরের সব সম্ভাব্য বিন্যাস বাতিল করতে তার বিপুল কাজ লাগে। আমাদের instance ছোট বলে ২৯,৫০৭টি বিরোধে শেষ হয়েছে; অর্ডার বাড়লে এই সংখ্যা সূচকীয়ভাবে বাড়ার আশঙ্কা।

উল্টো দিকে capacity 8-এ satisfiable সূত্রে solver-কে কিছু “প্রমাণ” করতে হয় না, শুধু একটি সমাধান খুঁজতে হয়, আর জায়গা যথেষ্ট থাকায় unit propagation আর কয়েকটি অনুমানই যথেষ্ট। এটি NP-এর সংজ্ঞার একটি জীবন্ত রূপ: “হ্যাঁ”-এর ছোট সাক্ষী আছে, “না”-এর ছোট সাক্ষী আছে কি না (coNP), তা খোলা প্রশ্ন।

প্রকৌশলীর করণীয় তিনটি। (১) সস্তা পূর্ব-পরীক্ষা: encoding-এর আগে k × c ≥ |O| আর প্রতিটি slot-সমষ্টির জন্য Hall-ধাঁচের শর্ত max-flow দিয়ে দেখা; flow polynomial, আর ব্যর্থ হলে solver চালানোর দরকারই নেই। (২) শক্তিশালী প্রমাণ-পদ্ধতির solver: cutting planes-ভিত্তিক pseudo-Boolean solver বা ILP-র LP relaxation pigeonhole তাৎক্ষণিক বাতিল করে, কারণ যোগফলের অসমতা সরাসরি লেখা যায় (পর্ব ৭৩-এর ILP run). (৩) বাড়তি অপ্রয়োজনীয় কিন্তু সত্য clause যোগ করা, যেমন মোট গণনার শর্ত, যা solver-কে গোনার “ইঙ্গিত” দেয়। প্রতিটি পথের মূল শিক্ষা একই: worst case-এর তত্ত্ব জানলে আগে থেকেই বোঝা যায় কোন instance solver-কে আটকাবে।

মূল উপলব্ধি: CDCL-এর UNSAT উত্তর resolution প্রমাণ, তাই pigeonhole-ধাঁচের অসম্ভবতা গণনায় সহজ হলেও solver-এর জন্য কঠিন; সস্তা গণনা বা flow দিয়ে আগে পরীক্ষা করুন।

প্র ০৪Model checker fairness ছাড়া ঠিক যন্ত্রেও “bug” দেখাল। Fairness কি একটি ফাঁকি, যা দিয়ে অপছন্দের counterexample লুকানো হয়? কখন এটি বৈধ অনুমান, আর কখন বিপজ্জনক?

Fairness একটি অনুমান, আর প্রতিটি অনুমানের মতো এটিও সত্য বা মিথ্যা হতে পারে। Liveness-এর দাবি (“একসময় ভালো কিছু ঘটবে”) পরিবেশের সহযোগিতা ছাড়া প্রায় কখনো সত্য নয়: গুদাম চিরকাল বন্ধ থাকলে কোনো যন্ত্রই অর্ডার পৌঁছাতে পারে না। তাই Paid অবস্থায় চিরকাল আটকে থাকার lasso যন্ত্রের নয়, পরিবেশের ব্যর্থতা। Weak fairness বলে: যে বৈধ ঘটনা চিরকাল সম্ভব, তা একসময় ঘটবে। Concurrent program-এর যাচাইয়ে এটি প্রচলিত, কারণ একটি ন্যায্য scheduler সাধারণত এটুকু নিশ্চয়তা দেয়। Amir Pnueli ১৯৭৭ সালে program যাচাইয়ে temporal logic প্রস্তাবের সময় থেকেই fairness-এর প্রশ্ন এই আলোচনার কেন্দ্রে, আর পরে model checking tool-গুলোতে fairness শর্ত আলাদা করে লেখার ব্যবস্থা থাকে।

বিপদ দুই দিকে। প্রথমত, অনুমানটি বাস্তবে মিথ্যা হতে পারে: যদি গুদামে সত্যিই কোনো অর্ডার হারিয়ে যায়, তবে fairness সেই ঝুঁকি মডেল থেকে মুছে দেয়। প্রতিকার: অনুমানটি নিজেই একটি প্রকৌশল-দাবি হিসেবে লেখা, আর বাস্তবে তার পাহারা বসানো (যেমন “Paid অবস্থায় ৪৮ ঘণ্টার বেশি থাকলে সতর্কবার্তা”)। দ্বিতীয়ত, fairness খুব শক্ত করলে আসল bug লুকিয়ে যায়: যেমন যদি লিখতাম “প্রতিটি অর্ডার একসময় Refunded বা Delivered হয়” আর একে fairness হিসেবে ধরতাম, তবে bug-এর Cancelled-এ আটকে থাকা পথটিকেও “অন্যায্য” বলে বাদ দেওয়া হতো। আমাদের নকশায় fairness শুধু বৈধ ঘটনার কথা বলে, তাই bug-এর পথটি fair থেকে যায় আর ধরা পড়ে।

যাচাইয়ের ভালো অভ্যাস তাই: fairness-সহ আর ছাড়া দুইভাবেই চালানো, আর ছাড়া-সংস্করণের প্রতিটি counterexample হাতে পড়ে নিশ্চিত হওয়া যে সেটি সত্যিই পরিবেশের দোষ।

মূল উপলব্ধি: Fairness liveness যাচাইয়ের প্রয়োজনীয় অনুমান, কিন্তু অনুমানই; এটিকে দুর্বলতম রূপে লিখুন, বাস্তবে পাহারা দিন, আর দুইভাবে চালিয়ে counterexample পড়ুন।

প্র ০৫বাজারঘর দশগুণ বড় হলো: হাজার হাজার অর্ডার, শতাধিক slot, অনেক কর্মী একসঙ্গে। প্রকল্পের কোন অংশ আগে ভাঙবে, আর তত্ত্ব আগে থেকে কী বলে দেয়?

Validator ভাঙবে না: DFA প্রতিটি অক্ষরে একটি টেবিল-দেখা, সময় input-এর দৈর্ঘ্যের রৈখিক, আর state-সংখ্যা ২২-এই স্থির, অর্ডার যত বাড়ুক। Query parser-ও নিরাপদ: LALR parser একটি query-তে রৈখিক সময় নেয় (পর্ব ৩৯), আর evaluator প্রতিটি অর্ডারে গাছের আকারের সময়। এখানে খরচ বাড়বে ডেটার সঙ্গে রৈখিকভাবে, যা ডেটাবেসের index-এর সমস্যা, তত্ত্বের নয়।

Model checking-এ সমস্যা আসবে অন্যভাবে। একটি অর্ডারের যন্ত্রে ৮টি পৌঁছানো অবস্থা, কিন্তু অনেক কর্মী আর ভাগ করা resource (তালা, মজুত) একসঙ্গে মডেল করলে অবস্থা গুণ হয়ে বাড়ে: state explosion. LTL model checking-এর জটিলতা মডেলের আকারে রৈখিক কিন্তু সূত্রের আকারে সূচকীয়, আর concurrent program-এর বর্ণনা থেকে মাপলে PSPACE-complete বলে জানা (পর্ব ৬৪–৬৫-এর শ্রেণি)। প্রতিকার আছে: অর্ডারগুলো পরস্পরের প্রতিসম হলে symmetry reduction, ঘটনাগুলো স্বাধীন হলে partial order reduction, আর abstraction; ১৯৯০-এর দশকের BDD-ভিত্তিক symbolic পদ্ধতি এই দৌড়ের বড় ধাপ ছিল। Edmund Clarke, Allen Emerson আর Joseph Sifakis এই ক্ষেত্রের সূচনার জন্য ২০০৭ সালের Turing Award পান বলে সাধারণত উল্লেখ করা হয়।

Slot পরিকল্পনা সবচেয়ে অনিশ্চিত। NP-completeness বলে worst case সূচকীয় (P ≠ NP অনুমানে, যা খোলা প্রশ্ন), কিন্তু বাস্তবের গঠনযুক্ত instance প্রায়ই দ্রুত মেলে। তত্ত্ব কোথায় বিপদ, তা আগে বলে: pigeonhole-ধাঁচের টানটান capacity, আর অনেক প্রতিসম slot. প্রকৌশলের উত্তর: সমস্যা ভাগ করা (এলাকা ধরে), symmetry ভাঙা, সময়সীমা দিয়ে “সেরা পাওয়া সমাধান” নেওয়া, বা approximation (পর্ব ৭১)। আর partner plug-in-এর প্রশ্ন বড় হলেও undecidable-ই থাকবে; মাপ সেখানে কিছু বদলায় না।

মূল উপলব্ধি: রৈখিক অংশ (DFA, LALR) মাপে নিরাপদ; model checking-এ state explosion আর SAT-এ NP-hardness হলো প্রত্যাশিত দেয়াল, আর তত্ত্ব আগে থেকেই বলে দেয় কোন instance কঠিন হবে।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। ওপরের Python ব্লকগুলোতে নিজের input বসিয়ে যাচাইও করতে পারেন।

  1. নকশা (grammar): বাজারঘরের ব্যবস্থাপক চান amount BETWEEN 500 AND 1000 লেখা যাক, অর্থ 500 ≤ amount ≤ 1000. পর্ব ৪২-এর Lark grammar-এ একটি নিয়ম যোগ করুন। AND এখন দুই অর্থে (BETWEEN-এর অংশ আর শর্ত জোড়া): LALR-এ conflict হবে কি? FIND order WHERE amount BETWEEN 500 AND 1000 AND district = "Dhaka"-এর গাছ কেমন হবে?

    atom-এ একটি বিকল্প: | "amount" "BETWEEN" NUM "AND" NUM -> num_between. Conflict হয় না: BETWEEN আর একটি NUM পড়ার পর parser একটি atom-এর ভেতরে, যেখানে একমাত্র বৈধ কাজ AND shift করা; শর্ত-জোড়া AND-এর জন্য দরকার একটি পুরো T-এর পরের state, যেখানে parser এখনো পৌঁছায়নি। Lark 1.3.1-এ চালিয়ে দেখা: টেবিল conflict ছাড়া তৈরি, আর গাছ and_(num_between(500, 1000), text_cmp(district, =, "Dhaka")). দ্বিতীয় NUM বাদ দিলে (BETWEEN 500 AND district …) parser জানায় expected NUM. Evaluator-এ নতুন method: lo ≤ o["amount"] ≤ hi. সতর্কতা: কেউ BETWEEN 1000 AND 500 লিখলে ফাঁকা পরিসর; এটি grammar-এর নয়, পরের যাচাই-ধাপের কাজ (উপপাদ্য ৫.১ এমন query-কে unsatisfiable বলে চিহ্নিত করবে)।

  2. প্রমাণের ভুল খুঁজুন: একজন লিখলেন: “SLOT-কে CNF-এ লিখে SAT solver-এ দেওয়া যায়, আর SAT NP-complete. তাই SLOT ≤p SAT থেকে SLOT NP-hard. আবার বিরোধ বাদ দিলে max-flow-এ polynomial সময়ে মেলে, তাই SLOT ∈ P.” দুটি ভুল দেখান আর সঠিক যুক্তি লিখুন।

    প্রথম ভুল: reduction-এর দিক উল্টো। SLOT ≤p SAT দেখায় SLOT বড়জোর SAT-এর মতো কঠিন, অর্থাৎ SLOT ∈ NP; কঠিনতা প্রমাণে জানা কঠিন সমস্যা থেকে SLOT-এ যেতে হয়: 3-COLOR ≤p SLOT (উপপাদ্য ৬.১-এর ধাপ ২–৪)। দ্বিতীয় ভুল: একটি বিশেষ ক্ষেত্র (বিরোধ নেই) সহজ হলে পুরো সমস্যা সহজ হয় না। বিরোধ-সহ সাধারণ instance-এ 3-COLOR লুকানো, তাই SLOT ∈ P হলে 3-COLOR ∈ P, অর্থাৎ P = NP, যা খোলা প্রশ্ন। সঠিক বক্তব্য: SLOT NP-complete; বিরোধহীন উপ-সমস্যা P-তে, আর প্রতিটি জানালায় বড়জোর দুটি slot আর capacity না থাকলে 2SAT হয়ে P-তে।

  3. Trace (আউটপুট অনুমান): অর্ডারের Mealy machine-এ (ঠিক আর bug-সহ দুই সংস্করণ) ঘটনা-ধারা pay, ship, pack, cancel, refund, deliver. প্রতিটি ঘটনার output আর পরের state লিখুন। শেষে bal কত? কোন সংস্করণ G(held → F done) ভাঙার পথে আছে?

    ঠিক সংস্করণ: pay/charge → Paid; ship/reject → Paid (Paid থেকে ship অবৈধ, আগে pack); pack/sms → Packed; cancel/ok → Cancelled (p = 1 থাকে); refund/pay_back → Refunded; deliver/reject → Refunded. শেষে bal = 1 − 1 = 0.

    Bug-এর সংস্করণ: প্রথম চারটি একই, কিন্তু cancel p মুছে দেয়; তাই refund/reject → Cancelled, deliver/reject → Cancelled, আর bal = 1. টাকা ধরা অবস্থায় যন্ত্র এমন জায়গায় আটকে, যেখানে কোনো বৈধ ঘটনা নেই: fairness-সহও φ ভাঙে। (order_checker.py-র mealy function এই ধারায় চালিয়ে scratch-এ মেলানো।)

  4. শ্রেণিবিন্যাস: প্রতিটি প্রশ্নের জন্য বলুন decidable কি না, আর হলে কোন জটিলতা-শ্রেণিতে বা কোন algorithm-এ: (ক) একটি string বৈধ কুপন কি না; (খ) দুটি query grammar একই language দেয় কি না (যেকোনো দুটি CFG); (গ) v2-এর দুটি query সমতুল্য কি না; (ঘ) ২০০টি অর্ডারের slot-বণ্টন, জানালা আর বিরোধসহ; (ঙ) partner-এর Python plug-in সব input-এ থামে কি না।

    (ক) decidable, DFA দিয়ে O(n) সময়ে (পর্ব ০৭)। (খ) সাধারণ CFG-এর জন্য undecidable (পর্ব ৫৪, PCP থেকে); নির্দিষ্ট দুটির জন্য হাতে প্রমাণ বা test, কিন্তু কোনো সাধারণ algorithm নেই। (গ) decidable আর polynomial: সমতুল্যতা = একটি query-র unsatisfiability, উপপাদ্য ৫.১-এর প্রতিনিধি-কৌশলে। (ঘ) decidable (সসীম খোঁজ) কিন্তু NP-complete (উপপাদ্য ৬.১); বাস্তবে SAT solver, worst case-এ সূচকীয় বলে বিশ্বাস। (ঙ) undecidable, কারণ এটি halting problem-এর একটি রূপ (পর্ব ৫১), আর Rice-এর theorem-এর আওতায়। আসলে এটি recognizable-ও নয়, co-recognizable-ও নয়: একটি input-এ থামা দেখা যায়, কিন্তু সব input-এ থামা কোনো সসীম পর্যবেক্ষণে নিশ্চিত হয় না।

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

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

ক্রমএকটি নতুন সিদ্ধান্ত-সমস্যা B-কে NP-complete প্রমাণের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. B-এর জন্য একটি certificate আর polynomial সময়ের verifier দেখিয়ে B ∈ NP প্রমাণ
  2. একটি জানা NP-complete সমস্যা A বাছাই, যেমন 3-COLOR
  3. A-এর প্রতিটি instance থেকে B-এর একটি instance বানানোর রূপান্তর f নকশা
  4. f polynomial সময়ে গণনাযোগ্য, তা দেখানো
  5. w ∈ A ⇔ f(w) ∈ B, দুই দিকই প্রমাণ করে A ≤p B থেকে B NP-complete সিদ্ধান্ত

একটি বাক্সে অর্ডার কোড বা কুপন, যেকোনোটি গ্রহণ করতে হবে। দুটির DFA D1 আর D2 থেকে product construction-এ (q1, q2) state-এর যন্ত্র বানানো হলো। কোন state accepting হবে?

  • যেখানে q1 আর q2 দুটিই accepting
  • যেখানে q1 বা q2-এর অন্তত একটি accepting
  • যেখানে ঠিক একটি accepting, দুটি একসঙ্গে নয়
  • যেখানে q1 accepting নয় আর q2 accepting

একটি query grammar থেকে Lark LALR(1) টেবিল কোনো conflict ছাড়া তৈরি হলো। এ থেকে grammar সম্পর্কে কী নিশ্চিত বলা যায়?

  • Language-টি regular
  • Grammar-টি আগের সংস্করণের সমান language দেয়
  • Grammar-টি unambiguous
  • Evaluator-এর প্রতিটি উত্তর সঠিক

একটি সসীম workflow-যন্ত্রে বৈধ ঘটনার কোনো চক্র নেই, আর সবচেয়ে লম্বা বৈধ পথ ৪ ধাপের। Bounded model checking k = 1 থেকে 6 পর্যন্ত কোনো খারাপ পথ পায়নি। কোনটি সঠিক?

  • শুধু বলা যায়: ৬ ধাপের মধ্যে কোনো bug নেই
  • কিছুই বলা যায় না, কারণ প্রশ্নটি undecidable
  • k = 100 পর্যন্ত না চালালে নিশ্চিত নয়
  • ধর্মটি এই মডেলে প্রমাণিত, কারণ k completeness threshold ছাড়িয়েছে

নতুন সমস্যা SLOT (জানালা, বিরোধ, capacity-সহ slot-বণ্টন) NP-hard দেখাতে কোন reduction লাগে?

  • 3-COLOR ≤p SLOT
  • SLOT ≤p 3-COLOR
  • SLOT ≤p SAT
  • MAX-FLOW ≤p SLOT

অর্ডারের যন্ত্রে φ = G(held → F done) যাচাই করতে গিয়ে fairness ছাড়া checker একটি counterexample দিল: pay, তারপর Paid-এ চিরকাল কোনো বৈধ ঘটনা নেই। এর সঠিক ব্যাখ্যা কী?

  • যন্ত্রে একটি bug আছে: Paid থেকে বের হওয়ার পথ নেই
  • পরিবেশ চিরকাল নিষ্ক্রিয়, তাই একটি fairness অনুমান লাগবে
  • φ একটি safety property, তাই অসীম পথ প্রাসঙ্গিক নয়
  • Model checking এখানে undecidable, তাই ফল অর্থহীন

বাজারঘর partner-দের Python-এ ছাড়ের plug-in লিখতে দেয়। “এই plug-in কি কখনো ৫০%-এর বেশি ছাড় দেয়?” প্রশ্নটি সম্পর্কে কোনটি সঠিক?

  • decidable, কারণ প্রতিটি plug-in-এর code সসীম
  • decidable, যথেষ্ট বড় timeout দিলে
  • সাধারণভাবে undecidable (Rice-এর theorem)
  • NP-complete, কারণ এটি একটি search সমস্যা

শব্দকোষ

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

মনে রাখুন

  1. প্রতিটি চাহিদাকে আগে একটি language বা সিদ্ধান্ত-সমস্যা হিসেবে লিখুন, তারপর সবচেয়ে দুর্বল যথেষ্ট যন্ত্র বাছুন: validator-এ DFA, query-তে CFG, workflow-এ সসীম যন্ত্র।
  2. নির্মাণের সঙ্গে যাচাই: product আর minimisation-এর পর স্পেসিফিকেশন-ফাংশনের বিরুদ্ধে brute force, একটি স্বাধীন tool-এ equivalence, আর differential test.
  3. Mealy machine আর output-গোনা পর্যবেক্ষক মিলে Kripke structure; G(held → F done)-এর মতো liveness-এ fairness লাগে, আর BMC-র “না” প্রমাণ হয় শুধু completeness threshold পেরোলে।
  4. দুর্বল ভাষায় অনেক প্রশ্ন decidable, এমনকি polynomial (query-র satisfiability); Turing-complete plug-in-এর আচরণগত প্রশ্ন Rice-এর theorem-এ undecidable.
  5. নতুন সমস্যার NP-hardness: জানা কঠিন সমস্যা থেকে reduction (3-COLOR ≤p SLOT); বাস্তবে SAT solver, প্রতিটি উত্তর checker-এ, আর UNSAT-এ unsat core বা গণনার যুক্তি।

পরের পর্বে: শেখা শেষ, এবার হাত পাকানো। পর্ব ৮১ “Automaton আর grammar নকশার অনুশীলন — DFA, regex, CFG, PDA আর TM”-এ ধাপে ধাপে সমাধানসহ নকশার প্রশ্ন, আর প্রতিটি উত্তর brute force দিয়ে যাচাইয়ের অভ্যাস।

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

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