এই পর্বে যা শিখবেন
- একটি লিখিত নিয়ম থেকে workflow-এর formal মডেল: state, event, guard, action আর configuration
- DFA-র dead state বনাম software-এর “প্রত্যাখ্যান করে একই জায়গায় থাকা”, আর বৈধ event-ক্রমের language
- UI-এর boolean flag-এর জঙ্গল থেকে স্পষ্ট state machine, আর double click ও দেরিতে আসা উত্তরের race
- Reachability, deadlock আর খারাপ state খোঁজার theorem, প্রমাণ আর BFS, সঙ্গে সরলীকৃত TCP-র উদাহরণ
- Statechart, library, typestate, model-based ও stateful testing, আর সত্যিকারের tool চালিয়ে যাচাই
১ · Software-এ state machine কেন — flag-এর জঙ্গল থেকে স্পষ্ট অবস্থা
রেলস্টেশনের টিকিট কাউন্টারের কথা ভাবুন। আপনি লাইনে আছেন, তারপর গন্তব্য বললেন, তারপর টাকা দিলেন, তারপর টিকিট পেলেন। টাকা দেওয়ার আগে কাউন্টারের লোক টিকিট ছাপেন না; টিকিট হাতে পাওয়ার পরে আবার টাকা চাইলে আপনি অবাক হবেন। কাউন্টারের লোক মাথায় একটি জিনিস রাখেন: “এই যাত্রী এখন কোন ধাপে”। ঠিক এই “ধাপ”-ই state, আর প্রতিটি কথা বা কাজ একটি event. কোন ধাপে কোন event চলে, তা একটি ছোট table-এ লেখা যায়।
এ পর্যন্ত এই কোর্সে finite state machine-কে দেখেছেন string-এর বিচারক হিসেবে (পর্ব ০৭, DFA-র ভিত্তি) আর output লেখার যন্ত্র হিসেবে (পর্ব ১২, Mealy আর Moore, যেখানে বাজারঘরের চেকআউট কিয়স্কও ছিল)। এই মডিউলের আগের পর্বগুলোতে automaton কাজে লেগেছে regex engine-এ (পর্ব ২১, বাস্তব regex engine) আর লেখার ভেতরে নকশা খোঁজায় (পর্ব ২৩, String matching automaton), দুটিই string-এর জগতে। এই পর্বে প্রশ্নটি প্রকৌশলের: বাস্তব software-এ, যেখানে ইনপুট মানে ব্যবহারকারীর ক্লিক, server-এর উত্তর আর network-এর packet, সেখানে এই গাণিতিক বস্তু কীভাবে কাজে লাগে, আর কোন theorem আমাদের ভুল ধরতে সাহায্য করে।
প্রথমে সমস্যাটি দেখুন। অনেক কোড অবস্থা রাখে কয়েকটি আলাদা boolean flag-এ: isLoading, isError, isSuccess. তিনটি flag মানে 23 = ৮টি সম্ভাব্য মিশ্রণ, অথচ অর্থবহ অবস্থা মাত্র চারটি: অপেক্ষায়, চলছে, ব্যর্থ, সফল। বাকি চারটি মিশ্রণ, যেমন “একসঙ্গে ব্যর্থ আর সফল”, কোনো অর্থ বহন করে না, তবু কোডে তৈরি হতে পারে। k-টি flag-এ মিশ্রণ 2k, আর কোন মিশ্রণ বৈধ তা কোথাও লেখা থাকে না; নিয়মটি ছড়িয়ে থাকে বিভিন্ন if-এর ভেতরে।
Explicit state machine উল্টো পথ নেয়: বৈধ অবস্থাগুলোর একটি সসীম তালিকা, প্রতিটি অবস্থায় কোন event-এ কোথায় যাওয়া যায় তার একটি table, আর বাকি সব কিছু ঘোষিতভাবে অবৈধ। লাভ তিনটি। প্রথমত, অর্থহীন মিশ্রণ তৈরিই হতে পারে না। দ্বিতীয়ত, table নিজেই একটি নথি, যা product owner আর tester পড়তে পারেন। তৃতীয়ত, এবং এই কোর্সের জন্য সবচেয়ে জরুরি, table একটি গাণিতিক বস্তু, তাই তার ওপর প্রশ্ন করা যায় আর যন্ত্র দিয়ে উত্তর বের করা যায়: “শিপ হওয়া অর্ডার কি কোনোভাবে বাতিল হতে পারে?” প্রশ্নটি আসলে একটি graph-এ reachability-র প্রশ্ন।
২ · বাজারঘরের অর্ডার — workflow-এর formal মডেল
সফটওয়্যার টেস্টিং কোর্সের পর্ব ১০-এ বাজারঘরের অর্ডারের নিয়ম একবার স্থির করা হয়েছে, আর এখানে হুবহু সেটিই ব্যবহার করব: অর্ডার দেওয়া হলে Placed; টাকা দিলে Paid, প্যাক হলে Packed, কুরিয়ারে দিলে Shipped, পৌঁছালে Delivered. Shipped হওয়ার আগে যেকোনো সময় বাতিল (Cancelled) করা যায়। বাতিলের আগে টাকা দেওয়া হয়ে থাকলে টাকা ফেরত হয় (Refunded). Delivered আর Refunded শেষ অবস্থা। সেখানে এই মডেল থেকে test বানানো হয়েছিল; এখানে মডেলটিকে গণিতের চোখে দেখব আর তার ধর্ম প্রমাণ বা খণ্ডন করব।
বাজারঘরের অর্ডার workflow — ৭টি state, ৮টি বৈধ transition
উপর থেকে আসা তীর শুরু, দুই দাগের ডিম্বাকার শেষ অবস্থা। লাল ভাঙা তীরটি spec-এ নেই।
সংজ্ঞা: guard-সহ workflow
ছবিতে একটি জিনিস বাক্সে নেই: অর্ডারে টাকা দেওয়া হয়েছিল কি না। Refund-এর তীরে guard condition [paid] সেই লুকানো তথ্য পড়ে। এমন মডেলের নাম extended finite state machine (সংক্ষেপে EFSM): state-এর পাশে কিছু variable, আর transition-এ শর্ত ও হালনাগাদ।
একটি extended FSM হলো W = (S, V, E, T, s0, v0, F), যেখানে
- S সসীম state-এর সেট, s0 ∈ S শুরু, F ⊆ S শেষ অবস্থার সেট;
- V variable-এর মানের সেট (এখানে paid ∈ {F, T}, তাই V = {F, T}), v0 ∈ V শুরুর মান;
- E event-এর সসীম সেট, অর্থাৎ যন্ত্রের alphabet;
- T হলো transition-এর সেট, প্রতিটি (s, e, g, a, s′) আকারের: state s-এ event e এলে, guard g(v) সত্য হলে, action a variable-কে a(v)-তে বদলায় আর যন্ত্র s′-এ যায়।
যন্ত্রের পূর্ণ অবস্থা হলো একটি configuration c = (s, v) ∈ S × V. Configuration c-তে event e বৈধ, যদি কোনো transition (s, e, g, a, s′)-এর g(v) সত্য হয়; তখন c ⊢e (s′, a(v)). Deterministic যন্ত্রে প্রতিটি c আর e-তে এমন transition বড়জোর একটি।
এখানে ⊢e চিহ্নটি পড়ুন “event e-তে এক ধাপে যায়”। বাজারঘরে S-এ ৭টি state, E = {pay, pack, ship, deliver, cancel, refund}, শুরু (Placed, F). T1-এর action paid := T, T8-এর guard paid = T আর action paid := F (টাকা ফেরত গেল)। বাকি transition-এ guard সবসময় সত্য, action কিছু বদলায় না।
V সসীম হলে প্রতিটি extended FSM একটি সাধারণ (partial) DFA-র সমতুল্য, যার state-সেট S × V, শুরু (s0, v0) আর δ((s, v), e) = c′ ঠিক তখন, যখন (s, v) ⊢e c′. State সংখ্যা বড়জোর |S| · |V|.
প্রমাণের রূপরেখা: সংজ্ঞা অনুযায়ী EFSM-এর প্রতিটি ধাপ শুধু বর্তমান configuration আর event-এর ওপর নির্ভর করে, আর deterministic বলে ফল বড়জোর একটি। তাই “configuration”-কেই state ধরলে δ একটি partial function S × V × E → S × V. দুই যন্ত্রের run ধাপে ধাপে একই, |w|-এর ওপর induction-এ। ∎
বাজারঘরে |S| · |V| = ৭ × ২ = ১৪টি সম্ভাব্য configuration, কিন্তু শুরু থেকে পৌঁছানো যায় মাত্র ৮টিতে: (Placed, F), (Paid, T), (Packed, T), (Shipped, T), (Delivered, T), (Cancelled, F), (Cancelled, T), (Refunded, F). Cancelled দুই ভাগ হয়েছে, কারণ টাকা দেওয়া আর না-দেওয়া বাতিল অর্ডারের ভবিষ্যৎ আলাদা। এটি পর্ব ১৮-এর Myhill–Nerode ভাবনারই প্রতিধ্বনি: যে দুটি ইতিহাসের ভবিষ্যৎ আলাদা, তারা এক state-এ থাকতে পারে না।
অবৈধ event: dead state, না “প্রত্যাখ্যান করে থাকো”?
DFA-র রীতিতে (পর্ব ০৭-এর partial DFA) না-থাকা transition একটি dead state-এ যায়: একবার ভুল চিহ্ন পড়লে string আর গৃহীত হয় না। Software তা করে না। শিপ হওয়া অর্ডারে কেউ “বাতিল” চাপলে অর্ডারটি নষ্ট হয়ে যায় না; system বার্তা দেয় “এখন বাতিল করা যাবে না” আর অর্ডার Shipped-এই থাকে। দুটি দৃষ্টিভঙ্গি আসলে দুটি আলাদা গাণিতিক বস্তু, আর দুটিই কাজের:
- Language-এর চোখে: বৈধ event-ক্রমের language Llegal(W) = {w ∈ E∗ : w-এর প্রতিটি event তার মুহূর্তে বৈধ}. এটি partial DFA-র language, যেখানে প্রতিটি configuration accepting. সংজ্ঞা থেকেই Llegal prefix-বন্ধ: একটি বৈধ ক্রমের প্রতিটি prefix-ও বৈধ। সম্পূর্ণ জীবনচক্রের language Ldone(W) হলো সেই বৈধ ক্রমগুলো, যা শেষ অবস্থায় থামে। দুটিই regular.
- চলমান system-এর চোখে: প্রতিটি অবৈধ (c, e)-তে একটি self-loop যার output “✗ প্রত্যাখ্যাত”, আর বৈধ transition-এর output “✓”. এটি একটি total Mealy machine, যার output প্রতিটি event-এর সাড়া। টেস্টিং কোর্সের “প্রত্যাখ্যান আর state অপরিবর্তিত” নিয়মটি ঠিক এই Mealy machine-এর আচরণ।
নিচের stepper অর্ডার BG-0044-কে একটি এলোমেলো event-ক্রমে চালায়, যাতে বৈধ আর অবৈধ দুই রকম event-ই আছে।
1new order2pay3ship4pack5cancel6refund7refund
| state | |
| paid | |
| সাড়া | |
| action |
- শুরু। নতুন অর্ডার, configuration (Placed, F). এখান থেকে শুধু pay আর cancel বৈধ।
- pay. (Placed, pay) ঘরে T1: state Paid, action টাকা কাটা, paid := T. এই action একবারই চলা উচিত; দ্বিতীয় pay অবৈধ।
- ship, ভুল সময়ে। (Paid, ship) ঘর খালি। DFA হলে যন্ত্র dead state-এ চলে যেত; এখানে system প্রত্যাখ্যান করে, configuration (Paid, T) অপরিবর্তিত। এটি Mealy-র self-loop, output ✗.
- pack. T2: (Paid, T) ⊢ (Packed, T). প্রত্যাখ্যাত event-টি ইতিহাসে কোনো দাগ রাখেনি, ঠিক যেমন হওয়া উচিত।
- cancel. Packed এখনো Shipped নয়, তাই T7 বৈধ: (Cancelled, T), action “refund বাকি”। paid এখনো T, কারণ টাকা এখনো ফেরত যায়নি।
- refund. T8-এর guard paid = T সত্য, তাই (Refunded, F): টাকা ফেরত, paid := F. Guard মিথ্যা হলে (টাকা না দিয়ে বাতিল) একই event প্রত্যাখ্যাত হতো।
- আবার refund. Refunded শেষ অবস্থা, কোনো event বৈধ নয়। দ্বিতীয়বার টাকা ফেরত হলো না। পুরো ক্রমের বৈধ অংশ “pay pack cancel refund” হলো Ldone-এর একটি string.
৩ · Library-তে workflow — transitions দিয়ে সত্যিকারের run
বাস্তবে এই table হাতে লেখা if-এ ছড়িয়ে না রেখে একটি state machine library-তে ঘোষণা করা হয়। Python-এ দুটি পরিচিত library হলো transitions আর python-statemachine (দুটিরই MIT licence); JavaScript/TypeScript-এ XState (MIT), যা statechart-এর ধারণা মেনে চলে (§৭)। নিচে transitions 0.9.3 দিয়ে বাজারঘরের অর্ডার। এটি এই কোর্সের লেখার সময় একটি uv venv-এ (Python 3.12) সত্যিকারের run; installed library-র কোডে network ব্যবহারের কোনো অংশ নেই (খুঁজে দেখা হয়েছে), তাই usage তথ্য বাইরে যাওয়ার প্রশ্ন নেই।
from transitions import Machine, MachineError
STATES = ["Placed", "Paid", "Packed", "Shipped", "Delivered", "Cancelled", "Refunded"]
RULES = [
dict(trigger="pay", source="Placed", dest="Paid", after="charge"),
dict(trigger="pack", source="Paid", dest="Packed"),
dict(trigger="ship", source="Packed", dest="Shipped"),
dict(trigger="deliver", source="Shipped", dest="Delivered"),
dict(trigger="cancel", source=["Placed", "Paid", "Packed"], dest="Cancelled"),
dict(trigger="refund", source="Cancelled", dest="Refunded",
conditions="was_paid", after="pay_back"),
]
class Order:
def __init__(self, code):
self.code, self.paid = code, False
Machine(model=self, states=STATES, transitions=RULES, initial="Placed")
def charge(self): self.paid = True
def pay_back(self): self.paid = False
def was_paid(self): return self.paid
def run(code, events):
o = Order(code)
for e in events:
before = o.state
try:
ok = o.trigger(e)
print(f"{code} {before:9} --{e}--> {o.state:9}" + ("" if ok else " (guard false)"))
except MachineError as err:
print(f"{code} {before:9} --{e}--> REJECTED: {err.value}")
if __name__ == "__main__":
run("BG-0042", ["pay", "pack", "ship", "cancel", "deliver"])
run("BG-0043", ["cancel", "refund"])
run("BG-0044", ["pay", "cancel", "refund"])~/bazarghar-toc $ uv add transitions hypothesis
+ hypothesis==6.170.15
+ transitions==0.9.3
~/bazarghar-toc $ uv run python order_flow.py
BG-0042 Placed --pay--> Paid
BG-0042 Paid --pack--> Packed
BG-0042 Packed --ship--> Shipped
BG-0042 Shipped --cancel--> REJECTED: Can't trigger event cancel from state Shipped!
BG-0042 Shipped --deliver--> Delivered
BG-0043 Placed --cancel--> Cancelled
BG-0043 Cancelled --refund--> Cancelled (guard false)
BG-0044 Placed --pay--> Paid
BG-0044 Paid --cancel--> Cancelled
BG-0044 Cancelled --refund--> Refunded
RULES তালিকাটি ছবি ২৪.১-এর আটটি তীর, প্রায় হুবহু: source আর dest তীরের দুই মাথা, conditions হলো guard, after হলো action. BG-0042-এ শিপের পরে cancel আসতেই library একটি MachineError ছুড়েছে, আর অর্ডার Shipped-এই থেকে পরের deliver ঠিকমতো নিয়েছে: অবৈধ ঘর বন্ধ। লক্ষ করার মতো একটি খুঁটিনাটি BG-0043-এ। টাকা না দিয়ে বাতিল অর্ডারে refund-এর guard মিথ্যা, আর তখন library কোনো error ছোড়ে না, শুধু False ফেরত দেয়। একই “প্রত্যাখ্যান” দুই রকমভাবে আসছে: না-থাকা transition-এ exception, মিথ্যা guard-এ নীরব False. Library বদলালে বা version বদলালে এই আচরণ বদলাতে পারে, তাই অবৈধ event-এর test দুই রকম ক্ষেত্রেই লিখতে হয়।
৪ · UI-এর state machine — চেকআউট বোতাম আর race
অর্ডারের workflow server-এ চলে আর ঘণ্টা বা দিন ধরে। UI-এর state machine চলে মিলিসেকেন্ডে, আর সেখানে বিপদ আসে সময় থেকে: ক্রেতা অধৈর্য হয়ে দুবার ক্লিক করেন, mobile network-এ একটি উত্তর দেরিতে আসে, আগের অনুরোধের উত্তর পরের অনুরোধের পরে পৌঁছায়। এমন ভুলের সাধারণ নাম race condition: ফল নির্ভর করে event কোন ক্রমে এল তার ওপর।
বাজারঘরের “অর্ডার নিশ্চিত করুন” বোতামের চারটি state: idle (অপেক্ষায়), loading (অনুরোধ গেছে), success, error. বৈধ transition: idle --click--> loading, loading --ok--> success, loading --fail--> error, error --click--> loading (আবার চেষ্টা)। নিচের JavaScript ব্লক একই event-ক্রম দুই রকম কোডে চালায়: একটিতে তিনটি boolean flag, অন্যটিতে এই table আর প্রতিটি অনুরোধের একটি id. Event-ক্রমে আছে double click, একটি ব্যর্থ উত্তর, আবার চেষ্টা, আর প্রথম অনুরোধের দেরিতে আসা উত্তর।
// Checkout button: boolean flags vs an explicit state machine.
// Double click, a failed reply, a retry, then a late reply to request 1.
const events = ["click", "click", "fail#1", "click", "ok#1", "ok#2"];
function flags() { // "boolean soup" version
let loading = false, error = false, success = false, sent = 0;
for (const e of events) {
if (e === "click") { loading = true; sent++; } // no state check!
else if (e.startsWith("fail")) { loading = false; error = true; }
else { loading = false; success = true; }
console.log(`flags ${e.padEnd(6)} L=${+loading} E=${+error} S=${+success} orders=${sent}`);
}
}
const NEXT = { // state -> event -> next state
idle: { click: "loading" },
loading: { ok: "success", fail: "error" },
error: { click: "loading" },
success: {},
};
function machine() {
let state = "idle", sent = 0, current = 0;
for (const e of events) {
const [kind, id] = e.split("#");
const next = NEXT[state][kind];
if (!next) { console.log(`fsm ${e.padEnd(6)} ignored in ${state}`); continue; }
if (kind === "click") current = ++sent; // request id
else if (Number(id) !== current) { console.log(`fsm ${e.padEnd(6)} stale reply ignored`); continue; }
state = next;
console.log(`fsm ${e.padEnd(6)} -> ${state.padEnd(8)} orders=${sent}`);
}
}
flags(); machine();আসল আউটপুট (ব্রাউজারের JavaScript):
flags click L=1 E=0 S=0 orders=1
flags click L=1 E=0 S=0 orders=2
flags fail#1 L=0 E=1 S=0 orders=2
flags click L=1 E=1 S=0 orders=3
flags ok#1 L=0 E=1 S=1 orders=3
flags ok#2 L=0 E=1 S=1 orders=3
fsm click -> loading orders=1
fsm click ignored in loading
fsm fail#1 -> error orders=1
fsm click -> loading orders=2
fsm ok#1 stale reply ignored
fsm ok#2 -> success orders=2
Flag-এর কোডে তিনটি ভুল একসঙ্গে। Double click দুটি অনুরোধ পাঠিয়েছে (orders=2), retry-সহ মোট তিনটি অনুরোধ, অর্থাৎ ক্রেতার নামে তিনটি অর্ডার হতে পারে। E=1 S=1 একসঙ্গে: “ব্যর্থ আর সফল” মিশ্রণ, যা ৮টি মিশ্রণের অর্থহীন অংশ থেকে এসেছে। আর ok#1 এসে loading মুছে দিয়েছে, যদিও তৃতীয় অনুরোধ তখনো চলছে। State machine-এ দ্বিতীয় click loading-এ অবৈধ, তাই উপেক্ষিত; মোট দুটি অনুরোধ, দুটিই ক্রেতার ইচ্ছায় (প্রথমটি, আর ব্যর্থতার পরে আবার চেষ্টা)। দেরিতে আসা ok#1 পুরোনো অনুরোধের উত্তর, id মেলে না বলে বাদ। Event-ক্রমটি বদলে আবার চালিয়ে দেখুন।
একটি সতর্কতা: “ok#1 বাদ” সিদ্ধান্তটি UI-এর দিক থেকে ঠিক, কিন্তু server-এর দিক থেকে প্রথম অনুরোধ হয়তো সফলই হয়েছিল। তাই UI-এর state machine একা যথেষ্ট নয়; server-এ প্রতিটি অনুরোধে একটি idempotency key রাখা হয়, যাতে একই অর্ডার দুবার তৈরি না হয়। দুই যন্ত্র মিলে একটি বড় যন্ত্র, আর সেই মিলিত যন্ত্রের ধর্মই আসল প্রশ্ন (§৫ আর §৬)।
1page loaded2click3click (double)4fail#15click (retry)6ok#1 (late)7ok#2
| flag: L E S | |
| flag: অনুরোধ | |
| FSM: state | |
| FSM: অনুরোধ |
- শুরু। Flag-এর কোডে তিনটি flag 0; FSM idle-এ। দুই কোডের সামনে একই event-ক্রম আসবে।
- click. দুই কোডই অনুরোধ পাঠায়। FSM-এ idle --click--> loading, অনুরোধের id 1 মনে রাখা হলো।
- দ্বিতীয় click, ২০০ মিলিসেকেন্ড পরে। Flag-এর কোড state দেখে না, তাই আবার পাঠায়: অনুরোধ ২টি। FSM-এর table-এ (loading, click) ঘর খালি, তাই event উপেক্ষিত। Double click-এর পুরো সমাধান একটি খালি ঘর।
- fail#1. প্রথম অনুরোধ ব্যর্থ। দুই কোডই error দেখায়; FSM-এ loading --fail--> error, id মিলেছে।
- click, আবার চেষ্টা। এবার click বৈধ, কারণ (error, click) ঘরে পথ আছে: FSM loading-এ, নতুন id 2. Flag-এর কোড L=1 করে, কিন্তু E মুছতে ভুলে যায়: “চলছে আর ব্যর্থ” একসঙ্গে।
- দেরিতে আসা ok#1. Network-এ আটকে থাকা পুরোনো উত্তর এখন পৌঁছাল। FSM দেখে id 1 ≠ বর্তমান id 2, তাই বাদ; state loading থাকে। Flag-এর কোড L=0 করে বোতাম আবার চালু করে দেয়, যদিও অনুরোধ ৩ চলছে।
- ok#2. FSM loading --ok--> success, মোট দুটি অনুরোধ, দুটিই ইচ্ছাকৃত। Flag-এর কোডে তিনটি অনুরোধ আর E=1 S=1, যা কোনো বৈধ অবস্থা নয়।
৫ · Protocol-এর state machine — সরলীকৃত TCP সংযোগ
Network protocol-এর নকশা প্রায় সবসময় state machine হিসেবে লেখা হয়, কারণ দুই প্রান্তকে একমত হতে হয় “এখন আমরা কোন ধাপে”। TCP-র নির্দিষ্টকরণে (প্রথমে RFC 793, ১৯৮১; এখন RFC 9293, ২০২২) একটি সংযোগের ১১টি state আছে। কম্পিউটার নেটওয়ার্ক কোর্সের পর্ব ২৯-এ three-way handshake, সংযোগ বন্ধ করা আর TIME-WAIT-এর কারণ বিস্তারিত আছে; এখানে শুধু যন্ত্রের কাঠামো দেখব। নিচের table একটি সরলীকৃত রূপ: শুধু client-এর খোলা আর বন্ধ করার স্বাভাবিক পথ, timeout-এর বিস্তারিত, reset আর একসঙ্গে বন্ধ করার (CLOSING) পথ বাদ।
| state | event | action (যা পাঠায়) | পরের state |
|---|---|---|---|
| → CLOSED | app: connect | SYN | SYN-SENT |
| SYN-SENT | recv SYN+ACK | ACK | ESTABLISHED |
| ESTABLISHED | app: close | FIN | FIN-WAIT-1 |
| FIN-WAIT-1 | recv ACK | — | FIN-WAIT-2 |
| FIN-WAIT-2 | recv FIN | ACK | TIME-WAIT |
| TIME-WAIT | timer শেষ | — | CLOSED |
এই table-এর “action” কলামটি লক্ষ করুন: প্রতিটি transition একটি event পড়ে আর একটি বার্তা পাঠায়, অর্থাৎ protocol-এর একটি প্রান্ত আসলে একটি Mealy machine. আরও আকর্ষণীয় হলো দুই প্রান্তকে একসঙ্গে দেখা। Client-এর পাঠানো SYN server-এর ইনপুট, server-এর SYN+ACK client-এর ইনপুট। দুটি যন্ত্র আর তাদের মাঝের বার্তার সারি মিলে একটি বড় যন্ত্র, যার configuration হলো (client-এর state, server-এর state, পথে থাকা বার্তা)। পথে থাকা বার্তার সংখ্যার সীমা থাকলে এই মিলিত যন্ত্রও সসীম, আর পর্ব ০৮-এর product construction-এর মতো তার state জোড় বা তিনগুণ।
এই মিলিত যন্ত্রেই protocol-এর আসল প্রশ্ন জাগে: এমন কোনো ক্রম কি আছে, যেখানে client ESTABLISHED ভাবছে অথচ server CLOSED? দুই প্রান্তই কি কখনো একে অপরের বার্তার জন্য চিরকাল অপেক্ষা করতে পারে? প্রথমটি একটি খারাপ configuration-এ পৌঁছানোর প্রশ্ন, দ্বিতীয়টি deadlock-এর। দুটিই পরের অংশের theorem-এর আওতায় পড়ে।
৬ · গুণ যাচাই — reachability, deadlock আর খারাপ state
একটি state machine নিয়ে তিন ধরনের প্রশ্ন বারবার আসে। কোন state-এ কখনো পৌঁছানোই যায় না (unreachable state, সাধারণত spec-এর ভুল বা মরা কোড)? কোন configuration-এ যন্ত্র আটকে যায়? আর কোনো “খারাপ” configuration-এ, যেমন “শিপ হওয়া অর্ডার বাতিল”, পৌঁছানো যায় কি না? তিনটির জন্য দুটি সংজ্ঞা লাগে।
- W-এর configuration graph G(W): vertex প্রতিটি configuration, আর c থেকে c′-এ e-লেখা তীর ঠিক তখন, যখন c ⊢e c′. শুরু থেকে পৌঁছানো যায় এমন vertex-এর সেট Reach(W).
- c ∈ Reach(W) একটি deadlock, যদি c-এর state শেষ অবস্থা না হয় আর c-তে কোনো event বৈধ না হয়।
- একটি safety property লেখা হয় একটি খারাপ সেট Bad দিয়ে: “Reach(W) ∩ Bad = ∅”, অর্থাৎ খারাপ কিছু কখনো ঘটে না।
G(W) সসীম হলে (যেমন V সসীম হলে), প্রদত্ত Bad-এর জন্য “Reach(W) ∩ Bad = ∅?” প্রশ্নটি O(|C| + |TG|) সময়ে decidable, যেখানে |C| পৌঁছানো configuration আর |TG| তাদের তীরের সংখ্যা। উত্তর “না” হলে একই হিসাব শুরু থেকে একটি খারাপ configuration-এ যাওয়ার সবচেয়ে ছোট event-ক্রম দেয়। সব deadlock খোঁজাও একই সময়ে হয়।
প্রমাণ: শুরু থেকে BFS চালাই, প্রতিটি configuration প্রথমবার দেখার সময় তার “আগের configuration আর event” লিখে রাখি।
- BFS যে vertex চিহ্নিত করে, তা পৌঁছানো যায়: প্রতিটি চিহ্নিত vertex একটি চিহ্নিত vertex থেকে একটি তীরে এসেছে, আর শুরু পৌঁছানো যায়; চিহ্নিত হওয়ার ক্রম ধরে induction. — BFS-এর নিয়ম
- প্রতিটি পৌঁছানো vertex চিহ্নিত হয়: শুরু থেকে c-এর দূরত্ব d-এর ওপর induction. d = 0 হলে c শুরু। d > 0 হলে পথের আগের vertex-টির দূরত্ব d − 1, তাই সেটি চিহ্নিত, আর সেটি queue থেকে বের হওয়ার সময় তার সব তীর দেখা হয়, তাই c-ও চিহ্নিত হয়। — induction
- প্রতিটি vertex একবারই queue-তে ঢোকে আর প্রতিটি তীর একবারই দেখা হয়, তাই সময় O(|C| + |TG|). — গণনা
- BFS দূরত্বের স্তর ধরে এগোয়, তাই “আগের” লেখা ধরে পেছনে গেলে যে পথ মেলে, তার দৈর্ঘ্য শুরু থেকে সবচেয়ে কম। Bad-এর কোনো সদস্য চিহ্নিত হলে সেটিই উত্তর, না হলে (২) অনুযায়ী Reach(W) ∩ Bad = ∅. Deadlock-এর জন্য প্রতিটি চিহ্নিত vertex-এ “শেষ অবস্থা নয় আর বের হওয়া তীর নেই” পরীক্ষা করলেই হয়। ∎
এটি পর্ব ২০-এর emptiness-এর algorithm-ই, নতুন নামে: “খারাপ configuration-কে accepting ধরলে যন্ত্রের language ফাঁকা কি না”। একটি সতর্কতা আছে, যা §৭-এ ফিরবে: |C| যন্ত্রের বর্ণনার আকারে রৈখিক নয়। k-টি অংশ, প্রতিটিতে nটি state, মিলিয়ে configuration nk পর্যন্ত হতে পারে। Algorithm দ্রুত, কিন্তু graph-টিই বিশাল হতে পারে।
এবার বাজারঘরে চালাই। নিচের ব্লকে configuration তিনটি মানের: (state, paid, shipped), যেখানে shipped মনে রাখে অর্ডার কখনো শিপ হয়েছিল কি না, যাতে “শিপের পরে বাতিল” একটি খারাপ configuration হিসেবে লেখা যায়। STATES-এ ইচ্ছা করে একটি বাড়তি state Returned রাখা হয়েছে, যার দিকে কোনো তীর নেই, যেমন অর্ধেক লেখা একটি spec-এ হয়। দুবার চালানো হয়: একবার spec-এর table-এ, একবার এমন একটি table-এ যেখানে (Shipped, cancel) ভুল করে খোলা।
from collections import deque
EVENTS = ["pay", "pack", "ship", "deliver", "cancel", "refund"]
SPEC = {("Placed", "pay"): "Paid", ("Paid", "pack"): "Packed",
("Packed", "ship"): "Shipped", ("Shipped", "deliver"): "Delivered",
("Placed", "cancel"): "Cancelled", ("Paid", "cancel"): "Cancelled",
("Packed", "cancel"): "Cancelled", ("Cancelled", "refund"): "Refunded"}
STATES = [s for s, _ in SPEC] + ["Delivered", "Refunded", "Returned"] # Returned: unreachable
FINAL = {"Delivered", "Refunded"}
def step(table, c, e): # c = (state, paid, shipped)
s, paid, shipped = c
n = table.get((s, e))
if n is None or (e == "refund" and not paid): return None
return (n, (paid or e == "pay") and e != "refund", shipped or e == "ship")
def explore(name, table, bad):
start = ("Placed", False, False)
path, q = {start: []}, deque([start])
while q: # breadth-first search
c = q.popleft()
for e in EVENTS:
n = step(table, c, e)
if n is not None and n not in path:
path[n] = path[c] + [e]; q.append(n)
print(f"[{name}] reachable configurations: {len(path)}")
print(" unreachable states:", sorted(set(STATES) - {c[0] for c in path}))
for c, p in path.items():
if c[0] not in FINAL and all(step(table, c, e) is None for e in EVENTS):
print(" deadlock:", c, "via", " ".join(p))
hits = [p for c, p in path.items() if bad(c)]
print(" shortest path to bad:", " ".join(min(hits, key=len)) if hits else "none")
bad = lambda c: c[0] in ("Cancelled", "Refunded") and c[2] # cancelled after ship
explore("spec", SPEC, bad)
explore("buggy", {**SPEC, ("Shipped", "cancel"): "Cancelled"}, bad)আসল আউটপুট (ব্রাউজারের Python):
[spec] reachable configurations: 8
unreachable states: ['Returned']
deadlock: ('Cancelled', False, False) via cancel
shortest path to bad: none
[buggy] reachable configurations: 10
unreachable states: ['Returned']
deadlock: ('Cancelled', False, False) via cancel
shortest path to bad: pay pack ship cancel
তিনটি প্রশ্নের তিনটি উত্তর। Returned-এ কখনো পৌঁছানো যায় না, যা আমরা জেনেশুনে বসিয়েছিলাম। Spec-এর table-এ খারাপ configuration নেই: উপপাদ্য ৬.২ অনুযায়ী এটি সব দৈর্ঘ্যের সব event-ক্রমের জন্য প্রমাণ, শুধু কয়েকটি test নয়। ভুল table-এ BFS সবচেয়ে ছোট পাল্টা-উদাহরণ দিয়েছে: pay pack ship cancel, আর reachable configuration ৮ থেকে ১০ হয়েছে ((Cancelled, T, T) আর (Refunded, F, T)). সবচেয়ে মজার লাইনটি deadlock: টাকা না দিয়ে বাতিল অর্ডার (Cancelled, F) থেকে কোনো event বৈধ নয়, অথচ spec বলেছে শেষ অবস্থা শুধু Delivered আর Refunded. এটি কোডের bug নয়, spec-এর ফাঁক: লিখিত নিয়মে বলা দরকার “টাকা না দিয়ে বাতিল অর্ডারও শেষ অবস্থা”। ৭টি state-এর একটি সরল workflow-এও যন্ত্রটি এমন একটি কথা খুঁজে পেল, যা মানুষ সহজে এড়িয়ে যায়।
নিচের stepper একই BFS ধাপে ধাপে দেখায়, তবে সংক্ষেপের জন্য শুধু (state, paid) নিয়ে, ঠিক যে ক্রমে Python কোড event দেখে (pay, pack, ship, deliver, cancel, refund).
1queue = [start]2pop (Placed, F)3pop (Paid, T)4pop (Cancelled, F)5pop (Packed, T)6pop (Cancelled, T)7pop (Shipped, T)8pop the last two
| নতুন configuration | |
| queue | |
| চিহ্নিত মোট | |
| পাওয়া গেল |
- শুরু। Queue-তে শুধু (Placed, F), সেটি চিহ্নিত। সম্ভাব্য configuration ৭ × ২ = ১৪টি; কোনগুলো পৌঁছানো যায়, BFS বলবে।
- (Placed, F) বের করা। ছয়টি event-এর মধ্যে pay দেয় (Paid, T), cancel দেয় (Cancelled, F). দুটিই নতুন, queue-তে ঢুকল।
- (Paid, T). pack দেয় (Packed, T), cancel দেয় (Cancelled, T): টাকা দেওয়া বাতিল। একই state Cancelled, কিন্তু paid আলাদা বলে আলাদা configuration.
- (Cancelled, F). ছয়টি event-ই অবৈধ: refund-এর guard মিথ্যা। State-টি F-এ নেই, তাই সংজ্ঞা ৬.১ অনুযায়ী এটি deadlock. পথ: শুরু থেকে শুধু “cancel”.
- (Packed, T). ship দেয় নতুন (Shipped, T). cancel দেয় (Cancelled, T), যা আগেই চিহ্নিত, তাই আবার queue-তে ঢোকে না। প্রতিটি vertex একবার: এ জন্যই সময় রৈখিক।
- (Cancelled, T). refund-এর guard সত্য, নতুন (Refunded, F). টাকা দেওয়া বাতিল অর্ডার আটকে থাকে না, তার একটি বের হওয়ার পথ আছে।
- (Shipped, T). শুধু deliver বৈধ, নতুন (Delivered, T). এখানে cancel অবৈধ, তাই “শিপের পরে বাতিল” কোনো পথেই আসে না।
- শেষ দুটি। (Refunded, F) আর (Delivered, T) শেষ অবস্থা, তীর নেই, কিন্তু সেটি deadlock নয়। Queue খালি: ১৪টির মধ্যে ৮টি পৌঁছানো, ঠিক Python-এর গণনার মতো, আর একটিমাত্র deadlock.
Language-এর চোখে: brute force এখানে প্রমাণ
উপপাদ্য ৬.২ graph দিয়ে উত্তর দেয়। একই প্রশ্ন language দিয়েও করা যায়: সব event-ক্রম তৈরি করে প্রতিটিতে যন্ত্র চালানো। সাধারণভাবে brute force শুধু সসীম অংশ দেখে, প্রমাণ নয়। কিন্তু এখানে একটি বিশেষ সুযোগ আছে। নিচের ব্লকে টাকা না দিয়ে বাতিলকে শেষ অবস্থা ঘোষণা করা হয়েছে (BFS-এর ধরা ফাঁক মেরামত), আর দৈর্ঘ্য 6 পর্যন্ত সব ক্রম পরীক্ষা করা হয়েছে, সঙ্গে দুটি safety নিয়ম: refund-এর আগে কোথাও pay, আর cancel-এর পরে কখনো ship নয়।
from itertools import product
EVENTS = ["pay", "pack", "ship", "deliver", "cancel", "refund"]
SPEC = {("Placed", "pay"): "Paid", ("Paid", "pack"): "Packed",
("Packed", "ship"): "Shipped", ("Shipped", "deliver"): "Delivered",
("Placed", "cancel"): "Cancelled", ("Paid", "cancel"): "Cancelled",
("Packed", "cancel"): "Cancelled", ("Cancelled", "refund"): "Refunded"}
FINAL = {"Delivered", "Refunded", "Cancelled"} # unpaid cancel declared final
def run(w): # None = some event was illegal
s, paid = "Placed", False
for e in w:
n = SPEC.get((s, e))
if n is None or (e == "refund" and not paid): return None
s, paid = n, (paid or e == "pay") and e != "refund"
return s, paid
legal = done = violations = total = 0
lifecycles = []
for k in range(7):
for w in product(EVENTS, repeat=k):
total += 1
r = run(w)
if r is None: continue
legal += 1
if "refund" in w and "pay" not in w[:w.index("refund")]: violations += 1
if "cancel" in w and "ship" in w[w.index("cancel"):]: violations += 1
if r[0] in FINAL and not (r[0] == "Cancelled" and r[1]):
done += 1; lifecycles.append(" ".join(w))
print("event sequences up to length 6:", total)
print("legal (every event allowed):", legal)
print("safety violations among legal:", violations)
print("complete lifecycles:", done)
for w in lifecycles: print(" ", w)আসল আউটপুট (ব্রাউজারের Python):
event sequences up to length 6: 55987
legal (every event allowed): 10
safety violations among legal: 0
complete lifecycles: 4
cancel
pay cancel refund
pay pack ship deliver
pay pack cancel refund
৫৫৯৮৭টি ক্রমের (১ + ৬ + ৬2 + … + ৬6) মধ্যে বৈধ মাত্র ১০টি: ε, pay, cancel, pay pack, pay cancel, pay pack ship, pay pack cancel, আর তিনটি দীর্ঘ জীবনচক্র। Ldone-এ ঠিক ৪টি string. এখানে brute force প্রমাণের কাজ করে, কারণ configuration graph-এ কোনো চক্র নেই: ৮টি vertex-এর চক্রহীন graph-এ সবচেয়ে লম্বা পথ বড়জোর ৭টি তীরের, আর বাস্তবে ৪টির। তাই দৈর্ঘ্য 6-এর বেশি কোনো বৈধ ক্রম নেই, আর Llegal সসীম language. যে workflow-এ চক্র আছে (যেমন চেকআউট বোতামের error → loading → error), সেখানে Llegal অসীম, আর তখন উপপাদ্য ৬.২-এর graph-পদ্ধতিই একমাত্র সম্পূর্ণ উত্তর।
সব প্রশ্ন অবশ্য “খারাপ কিছু কখনো ঘটবে না” ধরনের নয়। “টাকা দেওয়া প্রতিটি অর্ডার একসময় Delivered বা Refunded হবে” একটি liveness property: ভালো কিছু শেষ পর্যন্ত ঘটবেই। Safety ভাঙলে একটি সসীম পাল্টা-উদাহরণ থাকে (pay pack ship cancel); liveness ভাঙার প্রমাণ সাধারণত একটি অসীম run, যেমন একটি চক্রে চিরকাল ঘোরা। এর জন্য অসীম string-এর automaton আর temporal logic লাগে, যা পর্ব ৭৭ (Model checking — Büchi automaton আর temporal logic)-এর বিষয়। এই পর্বের BFS সেই বড় পদ্ধতির প্রথম আর সবচেয়ে বেশি ব্যবহৃত ধাপ।
৭ · বড় হলে — statechart, library আর typestate
বাস্তব workflow-এ সাতটি নয়, কয়েক ডজন state থাকে, আর একই অর্ডারের কয়েকটি দিক একসঙ্গে চলে: পণ্যের অবস্থা, টাকার অবস্থা, ক্রেতাকে SMS পাঠানোর অবস্থা। সমতল diagram তখন তীরের জঙ্গল হয়ে যায়। David Harel ১৯৮৭ সালে “Statecharts: A Visual Formalism for Complex Systems” প্রবন্ধে এর একটি সমাধান প্রকাশ করেন, যা পরে UML-এর state machine diagram-এর ভিত্তি হয়। Statechart-এর দুটি প্রধান সংযোজন:
Hierarchy (superstate)
Placed, Paid আর Packed-কে একটি superstate “বাতিলযোগ্য”-এর ভেতরে রাখলে cancel-এর তিনটি তীরের জায়গায় একটিই তীর লাগে: superstate-এর সীমানা থেকে Cancelled-এ। অর্থ: ভেতরের যেকোনো state-এ থাকলে cancel বৈধ।
Parallel region
একটি state-এর ভেতরে কয়েকটি orthogonal region একসঙ্গে সক্রিয় থাকে, যেমন অর্ডারের region আর SMS-এর region (Quiet, Sending, Sent). ছবিতে ৭ + ৩ = ১০টি state আঁকা হয়।
সমতল করার দাম
Parallel region-এর অর্থ product: সমতল যন্ত্রে state হলো জোড়, বড়জোর ৭ × ৩ = ২১টি। k-টি region, প্রতিটিতে niটি state হলে ছবিতে ∑ ni, কিন্তু সমতলে ∏ ni পর্যন্ত। এটিই state explosion.
ক্ষমতা বাড়ে না
Hierarchy আর সসীম region-এর statechart একটি সসীম যন্ত্রেই নামে, তাই নতুন language আসে না; আসে সংক্ষিপ্ততা। একই ঘটনা পর্ব ১০-এ দেখেছেন: NFA DFA-র চেয়ে শক্তিশালী নয়, কিন্তু সূচকীয়ভাবে ছোট হতে পারে।
Library-গুলো এই ধারণাগুলো বিভিন্ন মাত্রায় নেয়। XState statechart আর W3C-র SCXML (State Chart XML; ২০১৫ সালে W3C Recommendation হয় বলে জানা যায়) নির্দিষ্টকরণের ধারণা অনুসরণ করে। Python-এর transitions-এ hierarchy-র জন্য একটি আলাদা extension আছে, আর python-statemachine ঘোষণামূলক class-এ state আর event লিখতে দেয়। কোনটি ভালো, তা দলের ভাষা আর প্রয়োজনের ওপর নির্ভর করে; এই পর্বের মূল কথা হলো, library যা-ই হোক, ঘোষিত table-টি একটি গাণিতিক বস্তু, আর তাকে বের করে BFS চালানো যায়। একটি বাস্তব সতর্কতা: এসব library-র বড় version বদলালে API বদলায়, তাই অনলাইনে পাওয়া কোড আর AI-এর লেখা কোড নিজের version-এ চালিয়ে দেখতে হয়।
Typestate — অবৈধ transition-কে compile error বানানো
এ পর্যন্ত অবৈধ event ধরা পড়েছে চলার সময় (exception, ✗)। আরও এক ধাপ এগোনো যায়: অবৈধ event-কে লেখাই যাবে না। Typestate ধারণায় (Strom আর Yemini-র ১৯৮৬ সালের কাজের সঙ্গে যুক্ত বলে ধরা হয়) একটি বস্তুর type-এর মধ্যেই তার state থাকে: Order<Packed>-এর একটি ship() method আছে, যা Order<Shipped> ফেরত দেয়, আর Order<Shipped>-এ cancel() method-ই নেই। তাই “শিপের পরে বাতিল” লিখলে program compile-ই হয় না। Rust-এর মতো শক্তিশালী type system-এর ভাষায় এই ধাঁচটি প্রচলিত। দাম আছে: অর্ডারের state database থেকে পড়া হলে compile-এর সময় তা জানা যায় না, তাই typestate সাধারণত একটি কোড-অংশের ভেতরের নিয়ম পাকা করে, পুরো workflow নয়। গণিতের চোখে typestate হলো type checker-কে একটি DFA বানিয়ে দেওয়া, যা program-এর method-ডাকের ক্রম পড়ে।
৮ · মডেল থেকে test — model-based আর stateful testing
মডেল যত নিখুঁতই হোক, কোড আলাদাভাবে লেখা হয়, আর কোড মডেল মানে কি না তা আলাদা প্রশ্ন। Model-based testing-এ মডেল থেকে test বানানো হয়: প্রতিটি বৈধ transition অন্তত একবার, প্রতিটি অবৈধ ঘর একবার, পরপর দুটি transition-এর জোড়া। এই coverage মাপ আর তাদের গণনা সফটওয়্যার টেস্টিং কোর্সের পর্ব ১০-এ আছে। গণিতের দিক থেকে “সব transition অন্তত একবার ঢাকা সবচেয়ে ছোট পথ” একটি পুরোনো graph-সমস্যা (Chinese postman ধাঁচের), যা configuration graph-এর ওপর সমাধান করা হয়।
আরেকটি পথ হলো stateful testing: tool এলোমেলো event-ক্রম বানায়, প্রতিটি event কোড আর মডেল দুটিতেই পাঠায়, আর প্রতিটি ধাপের পরে দুটিকে মেলায়। কোথাও অমিল হলে tool ক্রমটিকে ছোট করে (shrinking), যতক্ষণ না সবচেয়ে ছোট ব্যর্থ ক্রম বাকি থাকে। Hypothesis-এর RuleBasedStateMachine এই কাজ করে; এর পূর্ণ পরিচয় সফটওয়্যার টেস্টিং কোর্সের পর্ব ৫৮-এ। নিচে একটি কোড-অংশ পরীক্ষা করা হচ্ছে, যাতে ইচ্ছা করে একটি bug বসানো (seeded bug): (Shipped, cancel) ঘরটি খোলা। সত্যিকারের run, Hypothesis 6.170.15 (MPL-2.0), Python 3.12, একই uv venv-এ; derandomize=True দিয়ে ফল প্রতিবার একই, আর database=None দিয়ে Hypothesis-এর উদাহরণ-সংরক্ষণ বন্ধ, তাই ব্যর্থ উদাহরণ কোথাও জমা থাকে না।
from hypothesis import settings, strategies as st
from hypothesis.stateful import RuleBasedStateMachine, rule, invariant, run_state_machine_as_test
SPEC = {("Placed", "pay"): "Paid", ("Paid", "pack"): "Packed",
("Packed", "ship"): "Shipped", ("Shipped", "deliver"): "Delivered",
("Placed", "cancel"): "Cancelled", ("Paid", "cancel"): "Cancelled",
("Packed", "cancel"): "Cancelled", ("Cancelled", "refund"): "Refunded"}
EVENTS = ["pay", "pack", "ship", "deliver", "cancel", "refund"]
class BuggyOrder: # code under test, one seeded bug
TABLE = dict(SPEC)
TABLE[("Shipped", "cancel")] = "Cancelled" # BUG: cell left open
def __init__(self): self.state, self.paid = "Placed", False
def handle(self, e):
nxt = self.TABLE.get((self.state, e))
if nxt is None or (e == "refund" and not self.paid): return False
self.paid = (self.paid or e == "pay") and e != "refund"
self.state = nxt; return True
class OrderMachine(RuleBasedStateMachine):
def __init__(self):
super().__init__()
self.sut, self.model, self.model_paid = BuggyOrder(), "Placed", False
@rule(e=st.sampled_from(EVENTS))
def send(self, e):
nxt = SPEC.get((self.model, e))
if e == "refund" and not self.model_paid: nxt = None
assert self.sut.handle(e) == (nxt is not None), f"{e} in {self.model}"
if nxt:
self.model_paid = (self.model_paid or e == "pay") and e != "refund"
self.model = nxt
@invariant()
def same_state(self): assert self.sut.state == self.model
try:
run_state_machine_as_test(OrderMachine, settings=settings(
max_examples=200, derandomize=True, database=None, deadline=None))
except AssertionError as err:
print("FAILED:", err)
for note in getattr(err, "__notes__", []): print(note)~/bazarghar-toc $ uv run python stateful_test.py
FAILED: cancel in Shipped
Failing test case: <state machine>
state = OrderMachine()
state.same_state()
state.send(e='pay')
state.same_state()
state.send(e='pack')
state.same_state()
state.send(e='ship')
state.same_state()
state.send(e='cancel')
state.teardown()
Hypothesis একটি event-ক্রম পেয়েছে যেখানে কোড cancel গ্রহণ করল অথচ মডেল (SPEC) বলছে Shipped-এ cancel অবৈধ। ছোট করার পরে ক্রমটি pay, pack, ship, cancel: ঠিক সেই চারটি event, যা §৬-এর BFS “shortest path to bad” হিসেবে দিয়েছিল। মাঝের same_state() লাইনগুলো প্রতিটি ধাপের পরের invariant পরীক্ষা। দুই পদ্ধতির পার্থক্যটি গুরুত্বপূর্ণ। BFS মডেলের সব configuration দেখে, তাই মডেল নিয়ে প্রমাণ দেয়; কিন্তু কোড দেখে না। Hypothesis কোড চালায়, তাই কোডের bug ধরে; কিন্তু এলোমেলো নমুনা নেয়, তাই “bug নেই” প্রমাণ করে না। বাস্তবে দুটিই লাগে: মডেলের ওপর BFS বা model checking, আর কোড আর মডেলের মিল যাচাইয়ে stateful testing.
সাধারণ ভুল
| ভুল | কেন ভুল, কী করবেন |
|---|---|
| শুধু বৈধ transition-এর test | খোলা থাকা অবৈধ ঘর (Shipped, cancel) ধরা পড়ে না; প্রতিটি অবৈধ ঘরও পাঠান |
| Guard-এর এক দিক পরীক্ষা | refund [paid]-এ paid = T আর paid = F দুটিই চালান |
| State-এর জায়গায় কয়েকটি flag | 2k মিশ্রণের অর্থহীন অংশ তৈরি হয়; একটি state variable রাখুন |
| শেষ অবস্থা অসম্পূর্ণভাবে ঘোষণা | BFS-এ deadlock হিসেবে আসে; spec-এ প্রতিটি থামার জায়গা লিখুন |
| দেরিতে আসা উত্তর ধরে state বদলানো | প্রতিটি অনুরোধের id রাখুন, পুরোনো উত্তর বাদ দিন; server-এ idempotency |
| “কয়েকটি test পাস, তাই নিরাপদ” | নিরাপত্তার দাবি সব পৌঁছানো configuration-এর ওপর; BFS দিয়ে পুরো graph দেখুন |
আরও গভীরে: উপপাদ্য ৬.২-এর শর্ত “configuration সসীম” খুব জরুরি। দুটি অসীম counter-যুক্ত সসীম যন্ত্রে (Minsky-র counter machine, ১৯৬০-এর দশক) reachability undecidable, কারণ এমন যন্ত্র Turing machine-এর সমান শক্তিশালী; এর ভিত্তি মডিউল ৯-এ আসবে। মাঝামাঝি মডেলেও বিস্ময় আছে: Petri net-এর reachability decidable (Mayr ১৯৮১, Kosaraju ১৯৮২), কিন্তু ২০২১ সালের দুটি স্বাধীন গবেষণায় দেখানো হয় যে এর জটিলতা Ackermann function-এর মাপের, যেকোনো সূচকীয় সীমার চেয়ে বহু গুণ বড়। Recursive program-এর মডেল pushdown system-এ (stack-সহ যন্ত্র, মডিউল ৬) reachability আবার বহুপদী সময়ে decidable বলে জানা যায়।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এমন প্রশ্ন প্রায়ই আসে:
- একটি অর্ডার বা ATM-এর state machine আঁকুন; অবৈধ event-এ কী হবে? State table-এ প্রতিটি ঘর পূরণ: বৈধ হলে নতুন state, অবৈধ হলে প্রত্যাখ্যান আর state অপরিবর্তিত।
- Deadlock আর শেষ অবস্থার পার্থক্য? দুটিতেই বের হওয়ার পথ নেই; শেষ অবস্থা ঘোষিত, deadlock অঘোষিত আটকে যাওয়া।
- Boolean flag-এর বদলে state machine কেন? k flag-এ 2k মিশ্রণ, যার অনেকগুলো অর্থহীন; state machine শুধু বৈধ অবস্থা রাখে।
- Double submit কীভাবে আটকাবেন? loading state-এ click অবৈধ, অনুরোধের id, আর server-এ idempotency key.
- সসীম state machine-এ খারাপ state-এ পৌঁছানো যায় কি না, কীভাবে বলবেন? Configuration graph-এ BFS, O(|C| + |T|), সঙ্গে সবচেয়ে ছোট পাল্টা-উদাহরণ।
৯ · AI-এর যুগে — AI-এর লেখা state machine যাচাই
“বাজারঘরের অর্ডারের জন্য একটি state machine লেখো” বললে AI সহকারী কয়েক সেকেন্ডে সুন্দর কোড আর ছবি দেয়। সমস্যা হলো, এখানে ভুলগুলো চোখে পড়ে না: একটি বাড়তি তীর, একটি ভুলে যাওয়া guard, একটি অঘোষিত শেষ অবস্থা। কয়েকটি ভুল বারবার দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
| অবৈধ event-এর আচরণ বলা নেই, বা “cancel যেকোনো সময়” ধরে নেওয়া | পুরো state × event table চান, প্রতিটি ঘরে নতুন state বা ✗ |
| Guard বাদ: টাকা না দিয়েও refund | (Cancelled, paid = F)-এ refund পাঠিয়ে দেখুন |
| কোনো state থেকে বের হওয়ার পথ নেই, কিন্তু শেষ অবস্থা বলাও নেই | Configuration graph-এ BFS চালিয়ে deadlock খুঁজুন |
| “এই মডেল যাচাই করা হয়েছে” দাবি, অথচ শুধু দুটি উদাহরণ | উপপাদ্য ৬.২-এর মতো সব পৌঁছানো configuration দেখা হয়েছে কি না দেখুন |
| Safety আর liveness গুলিয়ে ফেলা, বা liveness-এর “প্রমাণ” একটি সসীম test | “কখনো খারাপ নয়” বনাম “একসময় ভালো”; দ্বিতীয়টির পাল্টা-উদাহরণ অসীম run |
| Library-র এমন API লেখা, যা আপনার version-এ নেই | নিজের venv-এ চালান; version নম্বর মিলিয়ে নথি পড়ুন |
| বানানো ইতিহাস বা ভুল RFC নম্বর | মূল RFC, Harel-এর প্রবন্ধ আর বিশ্বস্ত বইয়ে মেলান |
AI-এর কাছে state machine চাইলে এমনভাবে চান, যাতে উত্তর নিজেই যাচাইযোগ্য হয়:
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
BFS কোনো ভুল দেখালে সেই পথটিই AI-কে ফেরত দিন (“pay pack ship cancel দিয়ে শিপ হওয়া অর্ডার বাতিল হয়”)। নির্দিষ্ট পাল্টা-উদাহরণ পেলে AI সাধারণত দ্রুত ঠিক করে। কিন্তু মনে রাখুন, BFS মডেল নিয়ে প্রমাণ দেয়; AI-এর লেখা কোড সেই মডেল মানে কি না, তা আলাদা যাচাই।
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Statechart কোন বাস্তব সমস্যা থেকে এসেছিল, আর সমতল state diagram সেখানে কেন যথেষ্ট ছিল না?
David Harel নিজের স্মৃতিচারণে লিখেছেন, ১৯৮০-এর দশকের শুরুতে তিনি ইসরায়েলের একটি যুদ্ধবিমান প্রকল্পের avionics দলের সঙ্গে পরামর্শক হিসেবে কাজ করছিলেন। প্রকৌশলীদের হাতে ছিল শত শত পাতার লিখিত বর্ণনা: কোন বোতাম চাপলে কোন পর্দা আসে, কোন অবস্থায় কোন সংকেত উপেক্ষা করতে হয়। লেখাগুলো পরস্পরবিরোধী আর অসম্পূর্ণ ছিল, আর সমতল state diagram-এ আঁকতে গেলে state-এর সংখ্যা সামলানোর বাইরে চলে যেত।
সমস্যার মূল ছিল দুটি কাঠামো, যা সমতল diagram প্রকাশ করতে পারে না। প্রথমটি “সাধারণ নিয়ম”: অনেক state-এ একই event-এর একই সাড়া, যেমন যেকোনো পর্দা থেকে একটি জরুরি বোতাম। সমতল diagram-এ এর জন্য প্রতিটি state থেকে একটি করে তীর লাগে। Hierarchy এটিকে একটি তীরে নামায়। দ্বিতীয়টি “স্বাধীন দিক”: রাডারের অবস্থা, অস্ত্রের অবস্থা আর পর্দার অবস্থা একসঙ্গে চলে। সমতল diagram-এ এগুলোর প্রতিটি মিশ্রণ একটি state, তাই সংখ্যা গুণফল। Parallel region প্রতিটি দিক আলাদা আঁকে, আর যোগফলে থামে।
Harel-এর ১৯৮৭ সালের প্রবন্ধটি এই দুটি ধারণা, সঙ্গে history (একটি superstate-এ ফিরলে শেষবার কোন ভেতরের state-এ ছিল তা মনে রাখা) আর broadcast event-এর একটি নির্দিষ্ট অর্থ দেয়। এখানে একটি গুরুত্বপূর্ণ সূক্ষ্মতা আছে: ছবির অর্থ নির্দিষ্ট না হলে দুটি tool একই ছবি দুইভাবে চালাতে পারে। পরের বছরগুলোতে statechart-এর অর্থ নিয়ে অনেক ভিন্ন রূপ প্রস্তাবিত হয়, আর পরের লেখায় বিভিন্ন tool-এর অর্থের এই পার্থক্যকে একটি বাস্তব সমস্যা হিসেবে আলোচনা করা হয়েছে বলে জানা যায়।
এই কোর্সের ভাষায়, statechart DFA-র চেয়ে বেশি language চেনে না; তার অবদান সংক্ষিপ্ততা আর পাঠযোগ্যতা। গণিতে এরই প্রতিফলন পাওয়া যায় succinctness নিয়ে গবেষণায়: parallel region-ওয়ালা বর্ণনা সমতল যন্ত্রের চেয়ে সূচকীয়ভাবে ছোট হতে পারে, ঠিক NFA আর DFA-র সম্পর্কের মতো।
মূল উপলব্ধি: Statechart এসেছিল বাস্তব avionics নির্দিষ্টকরণের জট থেকে; hierarchy আর parallel region ক্ষমতা বাড়ায় না, কিন্তু সমতল যন্ত্রের গুণফলের বিস্ফোরণকে ছবিতে যোগফলে নামায়।
প্র ০২TCP-র state machine চার দশকেরও বেশি পুরোনো। তবু protocol-এর state machine-এ ভুল এখনো কেন পাওয়া যায়?
TCP-র মূল নির্দিষ্টকরণ RFC 793 ১৯৮১ সালে প্রকাশিত হয়, আর তার ছবিতে ১১টি state. দেখতে ছোট, কিন্তু তিনটি কারণে বাস্তব যন্ত্রটি অনেক বড়। প্রথমত, ছবির state পুরো configuration নয়: sequence number, window, timer আর পথে থাকা packet সবই অবস্থার অংশ, অর্থাৎ এটি একটি বিশাল extended FSM. দ্বিতীয়ত, দুই প্রান্ত একসঙ্গে চলে, আর packet হারাতে, দেরি করতে বা ক্রম বদলাতে পারে, তাই মিলিত যন্ত্রের configuration দুই প্রান্তের state, timer আর network-এর বার্তার গুণফল। তৃতীয়ত, বিরল পথগুলো, যেমন দুই প্রান্ত একসঙ্গে খোলা বা একসঙ্গে বন্ধ করা (CLOSING state), সাধারণ test-এ প্রায় কখনো চলে না।
বছরের পর বছর অনেক সংশোধন আর ব্যাখ্যা আলাদা RFC-তে জমা হয়, আর ২০২২ সালে RFC 9293 এগুলোকে একত্র করে RFC 793-এর জায়গা নেয়। একই সময়ে গবেষকেরা model checking আর পর্ব ১২-এর ভাবনার প্রশ্নে বলা automata learning দিয়ে বিভিন্ন protocol implementation থেকে state machine বের করে নির্দিষ্টকরণের সঙ্গে মিলিয়েছেন, আর কিছু ক্ষেত্রে এমন transition পেয়েছেন যা নির্দিষ্টকরণে নেই, বলে প্রকাশিত গবেষণায় জানা যায়। এ ধরনের পরীক্ষা শুধু নিজের বা অনুমতিপ্রাপ্ত system-এ করা উচিত।
নিরাপত্তার দিক থেকে এই ভুলগুলো গুরুত্বপূর্ণ, কারণ অবৈধ transition প্রায়ই আক্রমণের দরজা। একটি state machine যদি “handshake শেষ হওয়ার আগে” কোনো বার্তা গ্রহণ করে, তবে প্রমাণীকরণ এড়ানোর পথ তৈরি হতে পারে। এই পর্বের বাজারঘরের “শিপের পরে বাতিল” তারই একটি নিরীহ রূপ: একটি খোলা ঘর।
এখান থেকে প্রকৌশলের শিক্ষা: protocol-এর ছবি দেখে নিশ্চিন্ত হওয়া যায় না। অবৈধ ঘরের পূর্ণ table, মিলিত যন্ত্রের BFS বা model checking, আর implementation থেকে শেখা যন্ত্রের সঙ্গে তুলনা, এই তিন স্তরের যাচাই লাগে।
মূল উপলব্ধি: Protocol-এর ছোট ছবির পেছনে variable, timer আর দুই প্রান্তের গুণফলে বিশাল configuration graph থাকে; বিরল পথ আর অবৈধ ঘরেই ভুল লুকায়।
প্র ০৩Model checking কীভাবে গবেষণার ধারণা থেকে শিল্পের হাতিয়ার হলো, আর state explosion-এর সঙ্গে লড়াই কীভাবে চলেছে?
১৯৮১–৮২ সালে দুটি দল স্বাধীনভাবে একই ধারণা প্রকাশ করে: একটি সসীম-অবস্থার system-এর সব configuration যন্ত্র দিয়ে ঘুরে দেখা, আর temporal logic-এ লেখা একটি দাবি সেখানে খাটে কি না পরীক্ষা করা। একটি দল Edmund Clarke আর E. Allen Emerson, অন্যটি Jean-Pierre Queille আর Joseph Sifakis. এই কাজের জন্য Clarke, Emerson আর Sifakis ২০০৭ সালের Turing Award পান। মূল algorithm-এর হৃদয় এই পর্বের উপপাদ্য ৬.২-এর মতোই: graph-এ খোঁজা।
প্রথম থেকেই শত্রু ছিল state explosion. ১০০টি boolean variable-এর একটি circuit-এর configuration 2100টি, যা একটি একটি করে গোনা অসম্ভব। ১৯৯০-এর দশকের শুরুতে symbolic model checking এল: configuration-এর সেটকে একটি একটি করে না রেখে binary decision diagram (BDD) নামের সংক্ষিপ্ত গঠনে রাখা, আর পুরো সেটের ওপর একসঙ্গে BFS-এর এক স্তর হিসাব করা। Kenneth McMillan-এর এই সময়ের কাজ এর সঙ্গে বিশেষভাবে যুক্ত। এরপর এল bounded model checking, যা “k ধাপের মধ্যে খারাপ configuration-এ পৌঁছানো যায় কি না” প্রশ্নকে একটি SAT সমস্যায় রূপান্তর করে (পর্ব ৭৩-এর SAT solver), আর partial-order reduction, যা স্বাধীন event-এর ক্রমভেদকে একবারই গোনে।
Hardware শিল্পে, বিশেষত processor নকশায়, ১৯৯০-এর দশকের মাঝামাঝি থেকে formal verification-এর ব্যবহার উল্লেখযোগ্যভাবে বাড়ে বলে সাধারণত বলা হয়। Software-এ SPIN-এর মতো tool protocol আর concurrent algorithm যাচাইয়ে বহু বছর ধরে ব্যবহৃত, আর TLA+-এর মতো নির্দিষ্টকরণ-ভাষা বড় distributed system-এর নকশা পরীক্ষায় কাজে লাগে।
তবু state explosion চিরতরে হারেনি; এটি তত্ত্বেরই ফল। সমান্তরাল k-টি অংশের system-এ reachability সাধারণভাবে PSPACE-complete, তাই কোনো পদ্ধতিই সব ক্ষেত্রে দ্রুত হবে বলে আশা করা যায় না (P ≠ PSPACE এখনো অজানা)। পর্ব ৭৭-এ এই গল্প temporal logic আর Büchi automaton দিয়ে এগোবে।
মূল উপলব্ধি: Model checking-এর মূল কাজ configuration graph-এ খোঁজা; চল্লিশ বছরের অগ্রগতির বেশিরভাগই state explosion-এর বিরুদ্ধে, symbolic সেট, SAT আর reduction দিয়ে।
প্র ০৪“অবৈধ অবস্থাকে প্রকাশ-অযোগ্য করুন” কথাটি কোডের নকশায় কী বোঝায়, আর তার সীমা কোথায়?
Functional programming-এর মহলে একটি বহুল উদ্ধৃত পরামর্শ আছে: “make illegal states unrepresentable”, অর্থাৎ data-র গঠন এমন হোক যে অবৈধ অবস্থা লেখাই না যায়। কথাটি সাধারণত Yaron Minsky-র সঙ্গে যুক্ত করা হয়। চেকআউট বোতামে তিনটি boolean flag ৮টি মিশ্রণ দেয়, যার ৪টি অর্থহীন। এর বদলে একটি “sum type” বা tagged union: মান হয় Idle, নয় Loading(requestId), নয় Success(orderCode), নয় Error(message). এখন “Loading আর Error একসঙ্গে” লেখার কোনো উপায় নেই, আর requestId শুধু Loading-এর সঙ্গে থাকে, তাই দেরিতে আসা উত্তর মেলানোর তথ্যও ঠিক জায়গায়।
গণিতের চোখে এটি একটি গণনা। k-টি স্বাধীন boolean-এর type-এর মান 2kটি, আর m-টি বিকল্পের sum type-এর মান mটি (প্রতিটির ভেতরের data বাদে)। বৈধ অবস্থা m-টি হলে sum type ঠিক তাদের ধরে, বাড়তি কিছু নয়। Typestate একই ধারণাকে transition-এ নিয়ে যায়: শুধু অবস্থা নয়, অবৈধ পরিবর্তনও লেখা যায় না।
সীমা তিনটি। প্রথমত, কিছু নিয়ম type-এ ধরা কঠিন বা অসম্ভব: “মোট টাকা ৫০০ টাকার কম হলে ডেলিভারি চার্জ” ধরনের সংখ্যাগত শর্ত সাধারণ type system-এ প্রকাশ করা যায় না; dependent type-এর মতো উন্নত ব্যবস্থা লাগে, যার দাম জটিলতা। দ্বিতীয়ত, বাইরের দুনিয়া থেকে আসা data (database, API, ব্যবহারকারীর ইনপুট) type মানে না; সীমানায় পরীক্ষা করে type-এ ঢোকাতে হয়। তৃতীয়ত, অবস্থা অনেক হলে type-গুলোও অনেক হয়, আর কোড ভারী হয়।
তাই বাস্তব নকশায় তিন স্তর মিলিয়ে কাজ করা হয়: type দিয়ে যতটা সম্ভব অবৈধ অবস্থা বাদ, একটি ঘোষিত state table দিয়ে চলার সময় অবৈধ event প্রত্যাখ্যান, আর মডেলের ওপর BFS বা model checking দিয়ে গুণ যাচাই।
মূল উপলব্ধি: Sum type আর typestate অবৈধ অবস্থা ও transition-কে লেখার আগেই বাদ দেয়, কিন্তু সংখ্যাগত শর্ত আর বাইরের data-র জন্য চলার সময়ের পরীক্ষা আর মডেল-যাচাই লাগেই।
প্র ০৫প্রতিটি program-কে কি একটি সসীম state machine হিসেবে দেখে সব প্রশ্নের উত্তর যন্ত্র দিয়ে বের করা যায়?
একটি অর্থে প্রতিটি বাস্তব কম্পিউটার সসীম: memory সসীম, তাই সম্ভাব্য configuration সসীম। তত্ত্বে তাই বলা যায়, একটি নির্দিষ্ট কম্পিউটারে একটি নির্দিষ্ট program-এর জন্য উপপাদ্য ৬.২ খাটে। কিন্তু সংখ্যাটি দেখুন: মাত্র এক কিলোবাইট memory-র configuration 28192টি, যা মহাবিশ্বের পরমাণুর আনুমানিক সংখ্যার চেয়েও অকল্পনীয়ভাবে বড়। “সসীম” কথাটি গণিতে সত্য, প্রকৌশলে অর্থহীন।
তাই তত্ত্ব program-কে অসীম-অবস্থার যন্ত্র হিসেবে দেখে, যেখানে variable যেকোনো বড় সংখ্যা নিতে পারে। তখন ছবি বদলে যায়। মডিউল ৯-এ দেখবেন, Turing machine থামবে কি না সেই প্রশ্ন undecidable (পর্ব ৫১), আর পর্ব ৫৩-এর Rice-এর theorem বলে program-এর আচরণ নিয়ে প্রায় প্রতিটি অর্থবহ প্রশ্ন undecidable. “এই program কখনো খারাপ অবস্থায় পৌঁছায় কি না” তাদের একটি। দুটি counter-যুক্ত সসীম যন্ত্রেই reachability undecidable হয়ে যায়, যা Minsky-র ফলের পরিণাম।
বাস্তবে এর তিনটি উত্তর আছে। প্রথম, abstraction: program থেকে একটি ছোট সসীম মডেল বানানো, যেমন এই পর্বে অর্ডারের ৭টি state আর একটি paid flag, আর আসল টাকার অঙ্ক বাদ দেওয়া। মডেলের প্রমাণ program-এর জন্য তখনই খাটে, যখন abstraction সঠিক; পর্ব ৭৮-এ abstract interpretation এই ধারণার গাণিতিক রূপ দেবে। দ্বিতীয়, সীমিত খোঁজ: k ধাপ পর্যন্ত সব দেখা (bounded model checking), যা ভুল খুঁজে পায় কিন্তু সব দৈর্ঘ্যের প্রমাণ দেয় না। তৃতীয়, testing আর stateful testing: কোড চালিয়ে নমুনা দেখা।
এই পর্বের বাজারঘরের উদাহরণ তাই একটি ইচ্ছাকৃত পছন্দ: workflow-এর স্তরে নিয়মগুলো সত্যিই সসীম, আর সেখানে প্রমাণ সম্পূর্ণ। এটিই state machine-এর সবচেয়ে বড় শক্তি: ঠিক স্তরে মডেল বানালে undecidable জগতের ভেতরেও একটি decidable দ্বীপ পাওয়া যায়।
মূল উপলব্ধি: বাস্তব program-এর configuration জ্যোতির্বিদ্যার মাপের, আর অসীম মডেলে প্রশ্নগুলো undecidable; সমাধান হলো সঠিক স্তরে সসীম abstraction বানানো, যেখানে BFS সম্পূর্ণ প্রমাণ দেয়।
অনুশীলন
আগে খাতায় করুন, তারপর উত্তর খুলে মেলান।
-
নকশা: বাজারঘর পণ্য ফেরতের নিয়ম যোগ করছে: Delivered অর্ডারে event return এলে state Returned, আর Returned-এ refund [paid] এলে Refunded. Delivered আর Refunded শেষ অবস্থা থাকবে, টাকা না দিয়ে বাতিলও শেষ অবস্থা। নতুন transition দুটি লিখুন, পৌঁছানো configuration (state, paid) গুনুন, আর Ldone-এর সব string লিখুন।
নতুন transition: T9 = (Delivered, return, সত্য, কিছু না, Returned), T10 = (Returned, refund, paid = T, paid := F, Refunded). Event-এর সেট এখন ৭টি।
পৌঁছানো configuration ৯টি: আগের ৮টি আর (Returned, T). (Refunded, F)-এ এখন দুই পথে পৌঁছানো যায়, কিন্তু configuration একই। বৈধ তীর ১০টি।
Ldone-এ ৫টি string: cancel; pay cancel refund; pay pack cancel refund; pay pack ship deliver; pay pack ship deliver return refund. Delivered শেষ অবস্থা হলেও এখন সেখান থেকে একটি তীর বের হয়: “শেষ অবস্থা” মানে “এখানে থামা বৈধ”, “এখান থেকে আর যাওয়া যায় না” নয়। বৈধ event-ক্রম মোট ১২টি। (scratch-এ BFS আর দৈর্ঘ্য 8 পর্যন্ত সব ক্রম গুনে মেলানো।)
-
প্রমাণ: একটি deterministic extended FSM W-এর configuration graph সসীম। প্রমাণ করুন (ক) Llegal(W) prefix-বন্ধ, আর (খ) Llegal(W) অসীম হলে শুরু থেকে পৌঁছানো যায় এমন একটি চক্র G(W)-তে আছে।
(ক)
- ধরুন w = xy ∈ Llegal. সংজ্ঞা অনুযায়ী w-এর run-এর প্রতিটি event তার মুহূর্তে বৈধ। — Llegal-এর সংজ্ঞা
- x-এর run হলো w-এর run-এর প্রথম |x|টি ধাপ, কারণ যন্ত্র deterministic আর প্রতিটি ধাপ শুধু আগের configuration-এর ওপর নির্ভর করে। — determinism
- তাই x-এর প্রতিটি event-ও বৈধ, x ∈ Llegal. ∎
(খ)
- ধরুন |Reach(W)| = N. Llegal অসীম, আর প্রতিটি দৈর্ঘ্যে string সসীম সংখ্যক (|E|n), তাই দৈর্ঘ্য ≥ N-এর একটি বৈধ w আছে। — অসীম সেট
- w-এর run-এ N + 1টি বা বেশি configuration, সবই Reach(W)-এ। — run-এর সংজ্ঞা
- Pigeonhole নীতিতে কোনো configuration দুবার আসে, ci = cj, i < j. — পর্ব ০৪-এর pigeonhole
- ci থেকে cj-এর পথটি একটি চক্র, আর ci পৌঁছানো যায়। ∎
উল্টোটাও সত্য (পৌঁছানো চক্রে চিরকাল ঘোরা যায়), তাই “Llegal অসীম ⇔ পৌঁছানো চক্র আছে”, আর এটি BFS/DFS দিয়ে decidable. এ জন্যই বাজারঘরের চক্রহীন workflow-এ দৈর্ঘ্য 6 পর্যন্ত brute force সম্পূর্ণ ছিল।
-
আউটপুট অনুমান: §৪-এর চেকআউট বোতামের state machine (NEXT table আর request id-সহ) এই event-ক্রমে চালানো হলো: click, fail#1, click, click, ok#2, fail#2. machine() ফাংশন কোন ছয়টি লাইন ছাপবে?
fsm click -> loading orders=1 fsm fail#1 -> error orders=1 fsm click -> loading orders=2 fsm click ignored in loading fsm ok#2 -> success orders=2 fsm fail#2 ignored in successপ্রথম click idle থেকে loading, id 1. fail#1-এর id মেলে, তাই error. Retry-এর click error থেকে loading, id 2. পরের click loading-এ অবৈধ। ok#2-এর id মেলে, success. শেষ fail#2: success-এর সারিতে কোনো event-এর পথ নেই, তাই id দেখার আগেই “ignored in success”. কোডে আগে table, পরে id পরীক্ষা হয়, তাই “stale reply” নয়, এই লাইনটি আসে। (event-ক্রম বদলে একই কোড node-এ চালিয়ে মেলানো।)
-
ভুল খুঁজুন: একজন লিখেছেন, “আমাদের test suite বাজারঘরের ৮টি বৈধ transition-এর প্রতিটি অন্তত একবার চালায় আর সব পাস করে। প্রতিটি transition ঠিক, তাই কোনো খারাপ configuration-এ পৌঁছানো অসম্ভব।” যুক্তির ভুল কোথায়? একটি নির্দিষ্ট কোড দিন, যেখানে ৮টি test পাস করে অথচ খারাপ configuration-এ পৌঁছানো যায়।
ভুল: বৈধ transition-এর test দেখায় যে মডেলের প্রতিটি তীর কোডে আছে; কিন্তু কোডে মডেলের বাইরের কোনো তীর নেই, তা দেখায় না। নিরাপত্তার দাবি কোডের configuration graph-এর সব পৌঁছানো vertex নিয়ে, আর একটি বাড়তি তীর graph-এ নতুন vertex আনতে পারে।
পাল্টা-উদাহরণ: §৮-এর BuggyOrder: table-এ মডেলের ৮টি ঘর হুবহু, সঙ্গে একটি বাড়তি (Shipped, cancel) → Cancelled. ৮টি বৈধ transition-এর test একই ফল দেয়, সব পাস। অথচ pay pack ship cancel খারাপ configuration (Cancelled, T, shipped = T)-এ নিয়ে যায়, যা §৬-এর BFS-এ “buggy” চালানোয় দেখা গেছে। ঠিক পরীক্ষা: অবৈধ ঘরগুলোও পাঠানো (all transitions coverage), বা কোডের table বের করে তার ওপর BFS, বা stateful testing.
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি লিখিত workflow-এর নিয়ম যন্ত্র দিয়ে যাচাইয়ের ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- লিখিত নিয়ম থেকে state, event, শুরু আর শেষ অবস্থার তালিকা করা
- পুরো state × event table লেখা, guard আর action-সহ
- Variable থাকলে configuration (state, variable) সংজ্ঞায়িত করা
- শুরুর configuration থেকে BFS চালানো
- পৌঁছানো configuration-এ deadlock আর খারাপ configuration খোঁজা
- পাওয়া পথটিকে test case বানানো আর spec বা কোড ঠিক করা
একটি workflow-এর configuration সসীম। শুরু থেকে একটি খারাপ configuration-এ পৌঁছানো যায় কি না, সেই প্রশ্ন সম্পর্কে কোনটি সঠিক?
- এটি undecidable
- এটি NP-complete, তাই শুধু অনুমান করা যায়
- Configuration graph-এর আকারে রৈখিক সময়ে BFS দিয়ে decidable
- শুধু অনেকগুলো এলোমেলো test চালিয়ে বলা যায়
একটি state machine-এর একটি পৌঁছানো configuration-এ কোনো event বৈধ নয়। এটিকে কখন deadlock বলা হয়?
- সবসময়, শেষ অবস্থা হলেও
- যখন তার state ঘোষিত শেষ অবস্থা নয়
- যখন সেটি unreachable
- যখন তাতে একটি self-loop আছে
একটি statechart-এ তিনটি parallel region, যাদের state যথাক্রমে 4, 3 আর 2টি। সমতল একটি সাধারণ state machine-এ লিখলে সর্বোচ্চ কয়টি state লাগতে পারে?
- 9
- 12
- 512
- 24
একটি দোকানের অর্ডার system সম্পর্কে নিচের কোন দাবিটি liveness property?
- টাকা দেওয়া প্রতিটি অর্ডার একসময় Delivered বা Refunded হবে
- শিপ হওয়া অর্ডার কখনো বাতিল হবে না
- কোনো অর্ডারে দুবার টাকা কাটা হবে না
- প্যাক হওয়ার আগে কোনো অর্ডার শিপ হবে না
একটি বোতামের state machine: idle --click--> loading, loading --ok--> success, loading --fail--> error, error --click--> loading; table-এ না থাকা event উপেক্ষিত। Event-ক্রম click, click, fail, click, ok এলে কয়টি অনুরোধ পাঠানো হয় (প্রতিটি গৃহীত click-এ একটি)?
- 1
- 2
- 3
- 4
একটি workflow-এর configuration graph-এ কোনো চক্র নেই আর তাতে ৮টি configuration. বৈধ event-ক্রমের language Llegal সম্পর্কে কোনটি সঠিক?
- এটি অসীম কিন্তু regular
- এটি সসীম, কিন্তু prefix-বন্ধ নয়
- এটি regular নয়
- এটি সসীম আর prefix-বন্ধ, প্রতিটি string-এর দৈর্ঘ্য বড়জোর 7
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- মডেল: workflow = extended FSM (S, V, E, T, s0, v0, F); V সসীম হলে configuration (s, v)-এর সাধারণ যন্ত্র, বড়জোর |S| · |V| state.
- অবৈধ event: language-এর চোখে না-থাকা transition (dead state); চলমান system-এ প্রত্যাখ্যান আর একই জায়গায় থাকা, অর্থাৎ ✗ output-এর Mealy self-loop.
- UI: k flag-এ 2k মিশ্রণ; explicit state, loading-এ click উপেক্ষা আর request id দিয়ে double click ও দেরিতে আসা উত্তরের race বন্ধ।
- যাচাই: সসীম configuration graph-এ BFS দিয়ে unreachable state, deadlock আর খারাপ configuration, রৈখিক সময়ে, সবচেয়ে ছোট পাল্টা-উদাহরণসহ; liveness-এর জন্য পর্ব ৭৭।
- বড় হলে: statechart ছবি ছোট রাখে কিন্তু সমতলে ∏ ni; typestate অবৈধ transition-কে compile error করে; stateful testing কোড আর মডেলের মিল যাচাই করে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর ১৪টি মডিউল।
- পর্ব ১২ · Mealy আর Moore machineপুনরালোচনাOutput-সহ যন্ত্র, চেকআউট কিয়স্ক আর প্রত্যাখ্যানের self-loop-এর ভিত্তি।
- পর্ব ২০ · Regular language-এর decision problemএকই algorithmEmptiness আর reachability: BFS দিয়ে সিদ্ধান্ত।
- সফটওয়্যার টেস্টিং · পর্ব ১০ · State-transition testingপ্রয়োগএকই অর্ডার মডেল থেকে coverage আর test case.
- সফটওয়্যার টেস্টিং · পর্ব ৫৮ · Property-based testingstatefulHypothesis, shrinking আর RuleBasedStateMachine.
- কম্পিউটার নেটওয়ার্ক · পর্ব ২৯ · TCP সংযোগprotocolThree-way handshake, ১১টি state আর সংযোগ বন্ধ করা।