এই পর্বে যা শিখবেন
- Nondeterminism-এর তিনটি ছবি: সঠিক অনুমান, যন্ত্রের কপি, আর সম্ভাব্য state-এর সেট
- NFA-র 5-tuple সংজ্ঞা (ε ছাড়া), δ̂-এর inductive সংজ্ঞা আর L(N)
- Computation tree আঁকা, আর একটি input-এ state-এর সেট ধরে NFA চালানো
- “ends with 01”, “ends with SALE” আর “শেষ থেকে k-তম চিহ্ন 1”-এর NFA নকশা ও সঠিকতার প্রমাণ
- ε ছাড়াই দুটি NFA-র union, concatenation আর star বানানোর ধারণা, আর brute force দিয়ে যাচাই
১ · অনুমান করতে পারা যন্ত্র — nondeterminism-এর ধারণা
বাজারঘর আমাদের কাল্পনিক অনলাইন দোকান। এবারের ঈদে নিয়ম হলো, যে coupon code-এর শেষে “SALE” আছে, সেটিতে ছাড় মিলবে: EID24SALE চলবে, SALEEID চলবে না। আগের দুই পর্বে আপনি DFA দেখেছেন (পর্ব ০৭: সংজ্ঞা, পর্ব ০৮: নকশা)। DFA প্রতিটি চিহ্ন পড়ে ঠিক একটি পরের state-এ যায়। “শেষে SALE” চিনতে DFA-কে সব সময় খেয়াল রাখতে হয় এখন পর্যন্ত SALE-এর কতটুকু মিলেছে, আর মাঝপথে মিল ভাঙলে কোথায় ফিরতে হবে। SASALE পড়তে গিয়ে দ্বিতীয় S-এ “SA” মিল ভেঙে আবার “S” থেকে শুরু করতে হয়। এই হিসাব ভুল করা খুব সহজ।
এবার একটি অদ্ভুত যন্ত্র কল্পনা করুন, যে অনুমান করতে পারে। সে চিহ্ন পড়তে থাকে আর কিছুই মনে রাখে না। কোনো এক S দেখে সে অনুমান করে: “এই S-ই শেষের SALE-এর শুরু।” তারপর সে যাচাই করে পরের তিনটি চিহ্ন ঠিক A, L, E কি না, আর তারপর input শেষ কি না। অনুমান ভুল হলে ক্ষতি নেই, কারণ নিয়মটা হলো: কোনো একটি অনুমান সফল হলেই code গৃহীত। যন্ত্রটির ঠিক এই ক্ষমতার নাম nondeterminism, আর এমন সসীম যন্ত্রের নাম nondeterministic finite automaton, সংক্ষেপে NFA.
ঢাকার একটি রিকশাওয়ালাকে ভাবুন, যাঁকে বলা হয়েছে “মিরপুর থেকে এমন কোনো রাস্তায় যান, যাতে শেষে কলাবাগান পৌঁছান।” প্রতিটি মোড়ে কয়েকটি গলি। একজন সাধারণ রিকশাওয়ালাকে একটি গলি বেছে নিতে হয়; ভুল হলে ফিরে আসতে হয়। এখন কল্পনা করুন, প্রতিটি মোড়ে রিকশাটি যতগুলো গলি, ততগুলো কপিতে ভাগ হয়ে যায়, আর প্রতিটি কপি একটি করে গলিতে ঢোকে। কোনো গলি কানা হলে সেই কপি সেখানেই থেমে যায়। শেষে কোনো একটি কপি কলাবাগানে পৌঁছালেই উত্তর “হ্যাঁ, পথ আছে”। NFA ঠিক এভাবে চলে, শুধু পথগুলো string-এর চিহ্ন দিয়ে আঁকা।
Nondeterminism বোঝার তিনটি সমতুল্য ছবি আছে, আর পুরো পর্বে তিনটিই কাজে লাগবে।
🔮 সঠিক অনুমান
যন্ত্র প্রতিটি মোড়ে “জাদুকরীভাবে” সঠিক পছন্দটি বেছে নেয়, যদি কোনো সঠিক পছন্দ থাকে। নকশা করার সময় এই ছবিটি সবচেয়ে কাজের।
নকশার জন্য👥 যন্ত্রের কপি
প্রতিটি পছন্দে যন্ত্র কপি হয়; প্রতিটি কপি একটি পথ ধরে। সব কপির পথ মিলে computation tree. প্রমাণের জন্য এই ছবি।
প্রমাণের জন্য🧺 সম্ভাব্য state-এর ঝুড়ি
প্রতিটি মুহূর্তে “এখন কোন কোন state-এ থাকা সম্ভব” তার একটি সেট রাখা হয়। Program লিখে NFA চালানোর জন্য এই ছবি।
চালানোর জন্যএকটি কথা শুরুতেই পরিষ্কার করি। NFA কোনো বাস্তব যন্ত্রের নকশা নয়, যেটি সত্যিই ভবিষ্যৎ দেখে অনুমান করে। এটি একটি গাণিতিক সংজ্ঞা: “w গৃহীত” মানে “একটি accepting পথ আছে”। এই “আছে” শব্দটিই nondeterminism-এর আসল অর্থ। অনুচ্ছেদ ৪-এ দেখবেন, সাধারণ deterministic program দিয়েই NFA হুবহু চালানো যায়।
২ · NFA-র formal definition
প্রথম উদাহরণ হিসেবে একটি ছোট language নিই, যা পুরো পর্বে বারবার আসবে: Σ = {0, 1}-এর ওপর L01 = {w : w-এর শেষ দুটি চিহ্ন 01}, অর্থাৎ যে string-এর suffix 01. এর NFA-তে তিনটি state: q0 মানে “অপেক্ষা করছি”, q1 মানে “আমার অনুমান, এই 0-টিই শেষ থেকে দ্বিতীয়”, q2 মানে “অনুমানের পরে 1 এসেছে, এখানেই শেষ হতে হবে”।
একটি nondeterministic finite automaton হলো একটি 5-tuple N = (Q, Σ, δ, q0, F), যেখানে
- Q একটি সসীম state-এর সেট;
- Σ একটি alphabet (সসীম, অশূন্য);
- δ: Q × Σ → P(Q) হলো transition function. P(Q) মানে Q-এর power set, অর্থাৎ Q-এর সব উপসেটের সেট। তাই δ(q, a) একটি state-এর সেট, যা ∅-ও হতে পারে;
- q0 ∈ Q শুরুর state;
- F ⊆ Q accept state-এর সেট।
DFA-র সঙ্গে পার্থক্য শুধু তৃতীয় লাইনে: DFA-তে δ: Q × Σ → Q, প্রতিটি জোড়ায় ঠিক একটি state.
L01-এর NFA-কে বলি N01 = ({q0, q1, q2}, {0, 1}, δ, q0, {q2}). এর δ একটি টেবিলে লেখা যায়, যেখানে প্রতিটি ঘরে একটি সেট থাকে। তীর (→) শুরুর state, তারা (∗) accept state.
| state | 0 | 1 |
|---|---|---|
| → q0 | {q0, q1} | {q0} |
| q1 | ∅ | {q2} |
| ∗ q2 | ∅ | ∅ |
টেবিলের তিনটি বৈশিষ্ট্য DFA-তে চলত না। δ(q0, 0) = {q0, q1}: একটি চিহ্নে দুটি পরের state. δ(q1, 0) = ∅: কোনো পরের state নেই, সেই পথ এখানেই মরে। আর q2-এর দুটি ঘরই ∅. DFA-তে এমন ফাঁকা ঘর থাকলে আমাদের একটি dead state যোগ করতে হতো (পর্ব ০৭-এর সম্পূর্ণতার নিয়ম); NFA-তে ∅ নিজেই “এই পথ শেষ” বোঝায়, তাই dead state লাগে না। খেয়াল করুন, প্রতিটি DFA-ও একটি NFA: শুধু প্রতিটি δ(q, a) = p-কে {p} লিখলেই হলো।
পুরো string-এর transition: δ̂
একটি চিহ্নের হিসাব δ দেয়। পুরো string w পড়ে কোন কোন state-এ থাকা সম্ভব, সেটি দেয় extended transition function δ̂ (কিছু বইয়ে δ∗)। DFA-র মতোই এটি string-এর দৈর্ঘ্যের ওপর induction দিয়ে সংজ্ঞায়িত (পর্ব ০৪-এর কৌশল), শুধু এবার মান একটি সেট।
প্রতিটি q ∈ Q, w ∈ Σ∗ আর a ∈ Σ-এর জন্য
অর্থাৎ w পড়ার পর যে state-গুলোতে থাকা সম্ভব, তাদের প্রত্যেকটি থেকে a-তে যেখানে যাওয়া যায়, সব মিলিয়ে নতুন সেট। N-এর language হলো
অর্থাৎ w পড়ার পরের সম্ভাব্য সেটে অন্তত একটি accept state থাকলেই w গৃহীত। এখানে ε হলো empty string (কিছু বই λ লেখে)।
সংজ্ঞাটির আরেকটি রূপ “পথ” দিয়ে, আর দুটি রূপ সমান। N একটি string w = a1a2⋯an গ্রহণ করে যদি state-এর এমন একটি ক্রম r0, r1, …, rn থাকে যে (১) r0 = q0, (২) প্রতিটি i-র জন্য ri+1 ∈ δ(ri, ai+1), আর (৩) rn ∈ F. এমন ক্রমকে বলে w-এর একটি computation path.
প্রতিটি w-এর জন্য δ̂(q0, w) = { r : q0 থেকে শুরু হয়ে w-এর চিহ্নগুলো পড়ে r-এ শেষ হয় এমন একটি পথ আছে }.
প্রমাণের রূপরেখা। |w|-এর ওপর induction. |w| = 0 হলে δ̂(q0, ε) = {q0}, আর দৈর্ঘ্য 0-এর একমাত্র পথ শুধু q0. এবার w = va ধরুন, আর v-এর জন্য দাবিটি সত্য। r-এ শেষ হওয়া va-র একটি পথ মানে v-এর একটি পথ, যা কোনো p-তে শেষ, তারপর r ∈ δ(p, a). Induction-এর অনুমানে এমন p ঠিক δ̂(q0, v)-এর সদস্যরা, তাই এমন r-এর সেট ঠিক ⋃p ∈ δ̂(q0, v) δ(p, a) = δ̂(q0, va). ∎
এই লেমার ফল সরাসরি: “কোনো একটি পথ F-এ শেষ হয়” আর “δ̂(q0, w) ∩ F ≠ ∅” একই কথা। প্রথমটি দিয়ে নকশা ও প্রমাণ সহজ, দ্বিতীয়টি দিয়ে program লেখা সহজ।
নিচের stepper N01-এর নকশা ধাপে ধাপে গড়ে, প্রতিটি তীরের পেছনের যুক্তিসহ। সবশেষে কয়েকটি string দিয়ে যাচাই।
- Language বোঝা। L01-এ আছে 01, 001, 101, 1101; নেই ε, 0, 1, 10, 0110. শুরুর state q0, যার অর্থ “এখনো কিছু অনুমান করিনি”।
- অপেক্ষার loop. শেষের 01-এর আগে যা খুশি আসতে পারে। তাই q0-তে 0 আর 1 দুটিতেই q0-তে ফেরা: যন্ত্রটি যতক্ষণ চায়, অপেক্ষা করতে পারে।
- অনুমানের তীর। কোনো 0 পড়ে যন্ত্র অনুমান করতে পারে “এটিই শেষ থেকে দ্বিতীয় চিহ্ন” আর q1-এ যায়। ফলে δ(q0, 0) = {q0, q1}: অপেক্ষা চালিয়ে যাওয়া আর অনুমান করা, দুটি পছন্দই খোলা।
- যাচাইয়ের তীর। অনুমান ঠিক হলে পরের চিহ্ন 1, তাই δ(q1, 1) = {q2}. q2 accept state, F = {q2}.
- ফাঁকা ঘর ইচ্ছাকৃত। q1-এ 0 এলে অনুমান ভুল, তাই δ(q1, 0) = ∅. q2-এর পরে আর কোনো চিহ্ন এলে “এটিই শেষ” অনুমানও ভুল, তাই q2 থেকে কোনো তীর নেই। ভুল অনুমানের পথ মরে যায়, বাকি পথ চলতে থাকে। কোনো dead state লাগেনি।
- যাচাই। 01 আর 101 গৃহীত (শেষ 0-তে অনুমান করলে পথ q2-এ শেষ)। 0110 বাতিল: q2-এ পৌঁছানো পথ শেষ 1 আর 0 পড়তে পারে না। ε বাতিল, কারণ q0 ∉ F. পুরো যন্ত্রে মাত্র ৪টি তীর; একই language-এর ক্ষুদ্রতম DFA-তে state ৩টি হলেও তীর লাগে ৬টি।
৩ · Computation tree আর গ্রহণের নিয়ম
“যন্ত্রের কপি” ছবিটিকে আঁকলে একটি গাছ পাওয়া যায়। গাছের মূল q0; গভীরতা i-এর প্রতিটি node একটি কপি, যা i টি চিহ্ন পড়ে সেই state-এ আছে; প্রতিটি node-এর সন্তান হলো পরের চিহ্নে তার যাওয়ার সব state. কোনো node-এর পরের সেট ∅ হলে সেই শাখা ✗ চিহ্নে মরে যায়। মূল থেকে গভীরতা |w| পর্যন্ত প্রতিটি শাখা একটি computation path.
- Accept: w-এর computation tree-তে গভীরতা |w|-এর অন্তত একটি পাতা F-এর state. বাকি সব শাখা ব্যর্থ হলেও কিছু যায় আসে না।
- Reject: গভীরতা |w|-এর কোনো পাতা F-এ নেই, অথবা সব শাখা আগেই মরে গেছে।
- মাঝপথে কোনো শাখা F-এ গেলে সেটি গণ্য নয়; শুধু পুরো string পড়ার পরের অবস্থা দেখা হয়।
এই নিয়মে একটি অসমতা আছে, যা পরে বারবার গুরুত্বপূর্ণ হবে: accept প্রমাণ করতে একটি পথ দেখালেই চলে, কিন্তু reject প্রমাণ করতে সব পথ বাদ দিতে হয়। “আছে” আর “সব” শব্দের এই পার্থক্যই পরে NP আর coNP-এর পার্থক্য হয়ে ফিরে আসবে (পর্ব ৫৮ ও ৬২)। নিচের stepper N01-কে input 1001-এ চালিয়ে গাছটি এক স্তর করে গড়ে।
- মূল। কিছু পড়ার আগে একটিই কপি, q0-তে। গভীরতা 0-এর সেট {q0}.
- প্রথম চিহ্ন 1. δ(q0, 1) = {q0}: কোনো পছন্দ নেই, একটিই সন্তান।
- দ্বিতীয় চিহ্ন 0. δ(q0, 0) = {q0, q1}: যন্ত্র দুই কপিতে ভাগ হলো। ডানের কপি অনুমান করেছে “এই 0-ই শেষ থেকে দ্বিতীয়”। সেট {q0, q1}.
- তৃতীয় চিহ্ন 0. বাঁয়ের q0 আবার দুই ভাগ: q0 আর q1. ডানের q1-এর জন্য δ(q1, 0) = ∅, তাই সেই কপি মরে গেল (✗): তার অনুমান ভুল ছিল। জীবিত সেট আবার {q0, q1}, যদিও এই q1 আগের q1 নয়।
- চতুর্থ চিহ্ন 1. q0 থেকে q0; q1 থেকে δ(q1, 1) = {q2}. পাতাগুলো q0 আর q2, সেট {q0, q2}.
- সিদ্ধান্ত। পথ q0 → q0 → q0 → q1 → q2 accept state-এ শেষ, তাই 1001 গৃহীত। অন্য পথটি q0-তে শেষ হয়ে reject, আর একটি পথ আগেই মরেছে; কিন্তু “অন্তত একটি” নিয়মে একটি সফল পথই যথেষ্ট।
গাছে মোট তিনটি শাখা: একটি সফল, একটি পুরো পড়ে ব্যর্থ, একটি মাঝপথে মৃত। লক্ষ করুন, প্রতিটি স্তরের জীবিত node-এর state-গুলো ঠিক stepper-এর নিচের সেট, যা লেমা ৯.১-এর কথা।
সত্যিকারের run: automata-lib দিয়ে একই NFA
নিজের হাতের হিসাব একটি স্বাধীন library দিয়ে মিলিয়ে নেওয়া ভালো অভ্যাস। Python-এর automata-lib (MIT লাইসেন্স) প্যাকেজে NFA একটি object; read_input_stepwise প্রতিটি চিহ্নের পরের state-সেট দেয়। নিচের আউটপুট আমাদের নিজের computer-এ সত্যিকারের run (automata-lib 9.2.0, Python 3.12):
from automata.fa.nfa import NFA
from automata.fa.dfa import DFA
ends01 = NFA(states={"q0", "q1", "q2"}, input_symbols={"0", "1"},
transitions={"q0": {"0": {"q0", "q1"}, "1": {"q0"}},
"q1": {"1": {"q2"}}, "q2": {}},
initial_state="q0", final_states={"q2"})
for w in ["1001", "0110"]:
steps = []
try:
for s in ends01.read_input_stepwise(w):
steps.append("{" + ",".join(sorted(s)) + "}")
print(w, "->", " ".join(steps), "ACCEPT")
except Exception as e:
print(w, "->", " ".join(steps), type(e).__name__ + ":", e)
for w in ["", "01", "101", "0110", "11101"]:
print(repr(w).ljust(8), ends01.accepts_input(w))
def kth_from_end(k):
t = {"q0": {"0": {"q0"}, "1": {"q0", "q1"}}}
for i in range(1, k):
t[f"q{i}"] = {"0": {f"q{i+1}"}, "1": {f"q{i+1}"}}
t[f"q{k}"] = {}
return NFA(states=set(t), input_symbols={"0", "1"}, transitions=t,
initial_state="q0", final_states={f"q{k}"})
for name, n in [("ends01", ends01), ("N_3", kth_from_end(3))]:
d = DFA.from_nfa(n, minify=True)
print(name, "NFA states:", len(n.states), " minimal DFA states:", len(d.states))$ uv run python nfa_lib.py
1001 -> {q0} {q0} {q0,q1} {q0,q1} {q0,q2} ACCEPT
0110 -> {q0} {q0,q1} {q0,q2} {q0} {q0,q1} RejectionException: the NFA stopped on all non-final states (q1, q0)
'' False
'01' True
'101' True
'0110' False
'11101' True
ends01 NFA states: 3 minimal DFA states: 3
N_3 NFA states: 4 minimal DFA states: 8
প্রথম লাইনের পাঁচটি সেট হুবহু stepper-এর পাঁচ স্তর। 0110-এর জন্য library একটি RejectionException ছোড়ে, যার বার্তা বলে শেষ সেট {q0, q1}-এর কোনো state final নয়; বন্ধনীর ভেতরে state-এর ক্রম Python-এর সেটের ক্রম, তাতে অর্থ বদলায় না। লক্ষ করুন, তৃতীয় সেটে q2 ছিল, কিন্তু পুরো string পড়া শেষ হয়নি বলে গণ্য হয়নি। শেষ দুই লাইন subset construction আর minimization চালিয়ে (পর্ব ১০ ও ১৯-এর বিষয়) ক্ষুদ্রতম DFA-র আকার বলে: L01-এ NFA আর DFA দুটিতেই ৩টি state, কিন্তু “শেষ থেকে তৃতীয় চিহ্ন 1”-এর ৪ state-এর NFA-র বদলে DFA-তে ৮টি লাগে। এই পার্থক্যের কারণ অনুচ্ছেদ ৫-এ।
৪ · State-এর সেট ধরে simulation
Computation tree বোঝার জন্য চমৎকার, কিন্তু চালানোর জন্য বিপজ্জনক। গাছের শাখার সংখ্যা input-এর দৈর্ঘ্যের সঙ্গে exponential হারে বাড়তে পারে। অথচ লেমা ৯.১ বলছে, সিদ্ধান্তের জন্য শুধু প্রতিটি স্তরের state-এর সেট দরকার, কোন পথে সেখানে এলাম তা নয়। দুটি কপি একই state-এ পৌঁছালে তাদের ভবিষ্যৎ হুবহু এক, তাই একটিকে মনে রাখলেই চলে। এভাবে চালানোকে বলে on-the-fly simulation:
- S ← {q0}.
- w-এর প্রতিটি চিহ্ন a-র জন্য: S ← ⋃q ∈ S δ(q, a). S ফাঁকা হলে সঙ্গে সঙ্গে reject করা যায়।
- শেষে S ∩ F ≠ ∅ হলে accept, নইলে reject.
প্রতিটি চিহ্নে বড়জোর |Q| টি state-এর প্রত্যেকটি থেকে বড়জোর |Q| টি state যোগ হয়, তাই মোট সময় O(|w| · |Q|2), আর memory শুধু একটি সেট, O(|Q|). Input লম্বা হলেও সময় শুধু রৈখিক হারে বাড়ে।
রেলের টিকিট কাউন্টারের একটি নোটবুক ভাবুন: প্রতি মিনিটে কর্মী শুধু লিখে রাখেন “এই মুহূর্তে কোন কোন কাউন্টারে লাইন আছে”, কে কোন পথে এসেছে তা নয়। পরের মিনিটের তালিকা এই তালিকা থেকেই বের হয়। নিচের stepper N01-কে input 0110-এ এভাবে চালায়; এবার উত্তর reject, আর মাঝপথের একটি ফাঁদ দেখা যাবে।
| পড়া অংশ | |
| এই চিহ্ন | |
| হিসাব | |
| S | |
| S ∩ F |
- শুরু। S = {q0}. ε পড়ার পর q0 ∉ F, তাই খালি string বাতিল, যা ঠিক: ε-এর শেষে 01 নেই।
- পড়া 0. S-এ শুধু q0; δ(q0, 0) = {q0, q1}. নতুন S = {q0, q1}.
- পড়া 1. δ(q0, 1) = {q0}, δ(q1, 1) = {q2}; S = {q0, q2}. এখন S-এ accept state আছে, কারণ “01” নিজে L01-এ। কিন্তু input শেষ হয়নি, তাই এখনই accept নয়।
- পড়া 1. δ(q0, 1) = {q0}, আর δ(q2, 1) = ∅: q2-এর কপিটি মরে গেল। S = {q0}. মাঝপথে F ছুঁয়ে যাওয়া কোনো কাজে আসেনি।
- পড়া 0. δ(q0, 0) = {q0, q1}; S = {q0, q1}.
- সিদ্ধান্ত। শেষ S = {q0, q1}, S ∩ F = ∅, তাই reject. সত্যিই 0110-এর শেষ দুটি চিহ্ন 10, 01 নয়।
এবার এই algorithm নিজে চালান। নিচের Pyodide ব্লক (আপনার ব্রাউজারে চলা আসল CPython) N01-কে একটি Python dict হিসেবে রাখে, যেখানে না-থাকা key মানে ∅. প্রথমে দুটি input-এর পূর্ণ trace ছাপে, তারপর দৈর্ঘ্য 0 থেকে 10-এর সব binary string-এ যন্ত্রের উত্তর Python-এর w.endswith("01")-এর সঙ্গে মেলায়, অর্থাৎ brute force যাচাই। প্রথমবার চালালে Python নামতে কয়েক সেকেন্ড লাগে।
from itertools import product
# NFA "ends with 01": a missing key means the empty set (that path dies)
delta = {("q0", "0"): {"q0", "q1"}, ("q0", "1"): {"q0"}, ("q1", "1"): {"q2"}}
start, F = "q0", {"q2"}
def show(S):
return "{" + ",".join(sorted(S)) + "}"
def run(w, trace=False):
cur = {start}
for a in w:
cur = {r for q in cur for r in delta.get((q, a), set())}
if trace:
print(f" read {a} -> {show(cur)}")
return bool(cur & F)
for w in ["1001", "0110"]:
print(w, "start", show({start}))
print(" verdict:", "ACCEPT" if run(w, True) else "reject")
bad, total = 0, 0
for n in range(11):
for t in product("01", repeat=n):
w = "".join(t)
total += 1
if run(w) != w.endswith("01"):
bad += 1
print("strings checked:", total, " mismatches:", bad)আসল আউটপুট (ব্রাউজারের Python):
1001 start {q0}
read 1 -> {q0}
read 0 -> {q0,q1}
read 0 -> {q0,q1}
read 1 -> {q0,q2}
verdict: ACCEPT
0110 start {q0}
read 0 -> {q0,q1}
read 1 -> {q0,q2}
read 1 -> {q0}
read 0 -> {q0,q1}
verdict: reject
strings checked: 2047 mismatches: 0
দুটি trace হুবহু দুই stepper-এর সেট। শেষ লাইনে 20 + 21 + ⋯ + 210 = 2047টি string-এ একটিও অমিল নেই। মনে রাখবেন, এটি প্রমাণ নয়: অসীম সংখ্যক string-এর মধ্যে মাত্র 2047টি দেখা হয়েছে। প্রমাণের কাজ অনুচ্ছেদ ৬-এ, আর brute force-এর কাজ হলো ভুল নকশা দ্রুত ধরা। run ফাংশনের মূল লাইনটি সংজ্ঞা ৯.২-এর δ̂ সূত্রের হুবহু অনুবাদ।
পথ গুনলে কত? সেট গুনলে কত?
পথ একে একে ঘুরে দেখার পদ্ধতি আর সেট-পদ্ধতির পার্থক্য সংখ্যায় দেখা যাক। নিচের JavaScript ব্লকের প্রথম অংশ N01-এর প্রতিটি পথ depth-first ক্রমে ছাপে; দ্বিতীয় অংশে একটি “কপি-যন্ত্র” আছে, যার দুটি state p আর r, আর a পড়লে দুটিই {p, r}-এ যায়। INPUT বদলে আবার চালিয়ে দেখুন।
// Every path of an NFA, one by one. Edit INPUT and press Run again.
const delta = { "q0,0": ["q0", "q1"], "q0,1": ["q0"], "q1,1": ["q2"] };
const accept = new Set(["q2"]);
const INPUT = "1001";
function paths(path, rest) { // depth-first: one clone per choice
const q = path[path.length - 1];
if (rest === "") return [path.join(">") + (accept.has(q) ? " ACCEPT" : " reject")];
const next = delta[q + "," + rest[0]] || [];
if (next.length === 0) return [path.join(">") + ">X dies"];
return next.flatMap(r => paths([...path, r], rest.slice(1)));
}
console.log("input " + INPUT + ":");
paths(["q0"], INPUT).forEach(p => console.log(" " + p));
// "clone" NFA on a^n: p and r both go to {p, r}. Paths double, the set does not.
const d2 = { p: ["p", "r"], r: ["p", "r"] };
console.log("n paths set size");
for (const n of [5, 10, 20, 30]) {
let count = { p: 1, r: 0 }; // number of paths ending in each state
for (let i = 0; i < n; i++) {
const c = { p: 0, r: 0 };
for (const q in count) for (const t of d2[q]) c[t] += count[q];
count = c;
}
const live = Object.keys(count).filter(q => count[q] > 0).length;
console.log(String(n).padEnd(4) + String(count.p + count.r).padEnd(13) + live);
}আসল আউটপুট (ব্রাউজারের JavaScript):
input 1001:
q0>q0>q0>q0>q0 reject
q0>q0>q0>q1>q2 ACCEPT
q0>q0>q1>X dies
n paths set size
5 32 2
10 1024 2
20 1048576 2
30 1073741824 2
প্রথম তিন লাইন computation tree-র তিনটি শাখা, একই ক্রমে। দ্বিতীয় অংশে পথের সংখ্যা ঠিক 2n: n = 30-এ একশো কোটির বেশি পথ, অথচ সেটের আকার সব সময় 2. পথগুলো গোনা হয়েছে প্রতিটি state-এ কতগুলো পথ শেষ হয় তার হিসাব রেখে, একটি একটি করে ঘুরে নয়; ঘুরে দেখলে n = 30-এ ব্রাউজার আটকে যেত। শিক্ষাটি সরল: NFA চালাতে পথ নয়, সেট গুনুন। Backtracking regex engine (পর্ব ২১) অনেক সময় ঠিক এই ভুলটিই করে, পথ একে একে চেষ্টা করে।
সেট-পদ্ধতি থেকে একটি গভীর ফল প্রায় বিনা খরচে আসে। প্রতিটি S হলো Q-এর একটি উপসেট, আর উপসেট আছে বড়জোর 2|Q|টি। তাহলে এই উপসেটগুলোকেই state ধরে একটি DFA বানানো যায়, যার transition হলো algorithm ৯.১-এর ধাপ ২। এটিই subset construction, যার নিয়মমাফিক রূপ, সঠিকতার প্রমাণ আর খরচের হিসাব পর্ব ১০-এর বিষয়। ফল: প্রতিটি NFA-র একটি সমতুল্য DFA আছে, তাই NFA-র চেনা language-ও ঠিক regular language.
৫ · NFA নকশা — অনুমান করুন, তারপর যাচাই করুন
NFA নকশার প্রায় সব কৌশল একটি ছকে পড়ে, যাকে বলা যায় guess and verify: যন্ত্র অপেক্ষার একটি loop-এ বসে থাকে, কোনো এক মুহূর্তে অনুমান করে “এখান থেকে আসল ঘটনা শুরু”, তারপর একটি ছোট deterministic শিকল দিয়ে অনুমানটি যাচাই করে। DFA-কে যেখানে প্রতিটি সম্ভাব্য শুরুর বিন্দু একসঙ্গে মনে রাখতে হয়, NFA সেখানে শুধু একটি শুরুর বিন্দু “বেছে নেয়”।
বাজারঘরের coupon: শেষে SALE
Coupon code-এর alphabet বড়, A–Z আর 0–9. নকশা ছোট রাখতে চিহ্নগুলোকে পাঁচটি দলে ভাবি: S, A, L, E, আর x মানে “অন্য যেকোনো চিহ্ন”। NFA NSALE: q0-তে সব চিহ্নে loop; q0 থেকে S-এ q1; q1 থেকে A-তে q2; q2 থেকে L-এ q3; q3 থেকে E-তে q4; F = {q4}, আর q4 থেকে কোনো তীর নেই। মোট ৯টি তীর, প্রতিটির অর্থ এক লাইনে বলা যায়। একই language-এর ক্ষুদ্রতম DFA-তেও ৫টি state লাগে (automata-lib-এর minimization-এ যাচাই করা), কিন্তু সেখানে 5 × 5 = 25টি তীর, আর প্রতিটি “মিল ভাঙলে কোথায় ফিরব” প্রশ্নের সঠিক উত্তর দিতে হয়। পর্ব ২৩-এ এই ফেরার নিয়মই KMP algorithm-এর failure function হয়ে আসবে। “Code-এর কোথাও SALE আছে” (substring) চাইলে শুধু q4-এ সব চিহ্নে একটি loop যোগ করুন।
শেষ থেকে k-তম চিহ্ন 1
এবার সেই language, যেখানে NFA আর DFA-র আকারের পার্থক্য নাটকীয়। Σ = {0, 1}-এর ওপর
যেমন L3-এ 100, 0110, 10100 আছে; 11, 011, 1001 নেই। NFA Nk-এর state q0, q1, …, qk: q0-তে 0 আর 1-এ loop; q0 থেকে 1-এ q1 (অনুমান: “এই 1-ই শেষ থেকে k-তম”); তারপর q1 থেকে q2, …, q(k−1) থেকে qk, প্রতিটি 0 বা 1-এ; F = {qk}; qk থেকে কোনো তীর নেই।
“শেষ থেকে k-তম চিহ্ন 1”-এর NFA Nk
q0-তে 1 পড়লে দুটি পছন্দ: অপেক্ষা, অথবা অনুমান। অনুমানের পর ঠিক k − 1টি চিহ্ন পড়ে qk-তে পৌঁছাতে হয়, আর ঠিক তখনই input শেষ হতে হয়।
এর DFA কেন বড়? DFA-কে কোনো অনুমান ছাড়াই, প্রতিটি মুহূর্তে, “শেষ k টি চিহ্ন কী ছিল” পুরোটা মনে রাখতে হয়, কারণ কোনটি শেষ থেকে k-তম হবে, তা input শেষ না হওয়া পর্যন্ত জানা যায় না। k বিটের 2kটি সম্ভাব্য সারি, আর পর্ব ১০-এ প্রমাণ হবে যে এদের যেকোনো দুটিকে একই DFA state-এ রাখা যায় না (দুটি সারি যে অবস্থানে আলাদা, সেখান থেকে ঠিক কয়েকটি 0 জুড়ে দিলে একটি গৃহীত, অন্যটি বাতিল হয়)। তাই যেকোনো DFA-তে অন্তত 2kটি state; উপরের সত্যিকারের run-এ k = 3-এ ক্ষুদ্রতম DFA-তে ঠিক 8টি পাওয়া গেছে।
নিচের Pyodide ব্লক k = 1 থেকে 5 পর্যন্ত Nk বানিয়ে দৈর্ঘ্য 12 পর্যন্ত সব string-এ সংজ্ঞার সঙ্গে মেলায়, আর simulation-এর সময় মোট কতগুলো আলাদা state-সেট দেখা দিল তা গোনে। সবশেষে NSALE-কে দৈর্ঘ্য 6 পর্যন্ত সব string-এ যাচাই করে।
from itertools import product
def nfa_kth_from_end(k): # states 0..k, start 0, accept k
d = {(0, "0"): {0}, (0, "1"): {0, 1}}
for i in range(1, k):
d[i, "0"] = d[i, "1"] = {i + 1}
return d, {k}
def run(d, F, w, seen=None):
cur = frozenset({0})
for a in w:
cur = frozenset(r for q in cur for r in d.get((q, a), ()))
if seen is not None:
seen.add(cur)
return bool(cur & F)
def words(sig, n): # all strings of length 0..n
return ["".join(t) for m in range(n + 1) for t in product(sig, repeat=m)]
for k in range(1, 6):
d, F = nfa_kth_from_end(k)
seen = {frozenset({0})}
want = lambda w: len(w) >= k and w[-k] == "1"
bad = sum(run(d, F, w, seen) != want(w) for w in words("01", 12))
print(f"k={k}: NFA states {k + 1}, mismatches {bad}, distinct state-sets {len(seen)}")
# coupon ends with SALE; x = any other symbol
SIG = "SALEx"
sale = {(0, a): {0} for a in SIG}
sale[0, "S"] = {0, 1}
sale[1, "A"], sale[2, "L"], sale[3, "E"] = {2}, {3}, {4}
ws = words(SIG, 6)
bad = sum(run(sale, {4}, w) != w.endswith("SALE") for w in ws)
print("SALE: strings", len(ws), "mismatches", bad)আসল আউটপুট (ব্রাউজারের Python):
k=1: NFA states 2, mismatches 0, distinct state-sets 2
k=2: NFA states 3, mismatches 0, distinct state-sets 4
k=3: NFA states 4, mismatches 0, distinct state-sets 8
k=4: NFA states 5, mismatches 0, distinct state-sets 16
k=5: NFA states 6, mismatches 0, distinct state-sets 32
SALE: strings 19531 mismatches 0
প্রতিটি k-তে অমিল 0, আর আলাদা state-সেটের সংখ্যা ঠিক 2k: k + 1 state-এর NFA চালাতে গিয়ে 2kটি ভিন্ন “ঝুড়ি” দেখা দেয়। প্রতিটি ঝুড়িতে q0 থাকেই, বাকি q1…qk-এর যেকোনো উপসেট সম্ভব। এরাই পর্ব ১০-এর subset construction-এ DFA-র state হবে। SALE-এর লাইনে 50 + 51 + ⋯ + 56 = 19531টি string, অমিল 0.
৬ · প্রমাণ — Nk ঠিক Lk চেনে
Brute force দৈর্ঘ্য 12 পর্যন্ত বিশ্বাস জাগায়; প্রমাণ সব দৈর্ঘ্যের জন্য নিশ্চয়তা দেয়। NFA-র সঠিকতা প্রমাণের আদর্শ ছক হলো দুই দিক: (⊆) প্রতিটি গৃহীত string language-এ আছে, আর (⊇) language-এর প্রতিটি string-এর একটি accepting পথ আছে। দ্বিতীয় দিকে nondeterminism আমাদের পক্ষে কাজ করে: পথটি আমরা নিজেরাই বেছে দিতে পারি।
প্রতিটি k ≥ 1-এর জন্য Nk = ({q0, …, qk}, {0, 1}, δ, q0, {qk}), যেখানে δ(q0, 0) = {q0}, δ(q0, 1) = {q0, q1}, 1 ≤ i < k হলে δ(qi, 0) = δ(qi, 1) = {q(i+1)}, আর δ(qk, 0) = δ(qk, 1) = ∅, তার জন্য L(Nk) = Lk.
প্রমাণ।
- Nk-এর তীরগুলো শুধু এই: q0 → q0 (0 আর 1-এ), q0 → q1 (শুধু 1-এ), আর qi → q(i+1) (1 ≤ i < k, 0 আর 1-এ)। q0-তে ঢোকার তীর শুধু q0 থেকে, আর qk থেকে কোনো তীর বের হয় না। — δ-এর সংজ্ঞা
- তাই q0 থেকে শুরু হওয়া যেকোনো পথ প্রথমে কয়েক ধাপ (শূন্যও হতে পারে) q0-তে থাকে; তারপর যদি q0 ছাড়ে, তবে একটি 1 পড়ে q1-এ যায়, এরপর প্রতিটি চিহ্নে এক ঘর করে এগোয়, আর কখনো q0-তে ফেরে না। qj-তে (j ≥ 1) থাকা মানে q1-এ ঢোকার পর ঠিক j − 1টি চিহ্ন পড়া হয়েছে। — ধাপ ১, পথের দৈর্ঘ্যের ওপর সরল induction
- (⊆) ধরুন w ∈ L(Nk). তাহলে w-এর একটি পথ qk-তে শেষ। ধাপ ২ অনুযায়ী পথটি কোনো অবস্থানে 1 পড়ে q1-এ ঢুকেছে, তারপর ঠিক k − 1টি চিহ্ন পড়ে qk-তে পৌঁছেছে; qk-তে পৌঁছানোর পর আর কোনো চিহ্ন পড়া সম্ভব নয়, তাই ঠিক তখনই w শেষ। অর্থাৎ w = x1y, যেখানে |y| = k − 1. — ধাপ ১–২
- w = x1y আর |y| = k − 1 মানে |w| ≥ k, আর শেষ থেকে k-তম চিহ্নটি সেই 1. তাই w ∈ Lk. — Lk-এর সংজ্ঞা
- (⊇) ধরুন w ∈ Lk. তাহলে w = x1y লেখা যায়, যেখানে |y| = k − 1 (শেষ থেকে k-তম চিহ্নটিকে আলাদা করে)। পথটি বেছে দিই: x-এর প্রতিটি চিহ্নে q0-তে থাকা (q0-তে 0 আর 1 দুটিতেই loop আছে), তারপর 1 পড়ে q1-এ যাওয়া, তারপর y-এর k − 1টি চিহ্নে q1 → q2 → ⋯ → qk. — δ-এর সংজ্ঞা, ধাপ ১
- এই পথ w-এর সব চিহ্ন পড়ে qk ∈ F-এ শেষ হয়, তাই w ∈ L(Nk). — গ্রহণের সংজ্ঞা
- দুই দিক মিলিয়ে L(Nk) = Lk. ∎
প্রমাণের ধাঁচটি লক্ষ করুন। (⊇) দিকে আমরা পথ বেছে দিয়েছি, অর্থাৎ “সঠিক অনুমান” ছবিটি ব্যবহার করেছি। (⊆) দিকে যেকোনো accepting পথের গঠন বিশ্লেষণ করেছি, অর্থাৎ যন্ত্রের সব কপির কথা ভেবেছি। প্রায় প্রতিটি NFA-র সঠিকতার প্রমাণ এই দুই অংশে লেখা হয়। একটি সাধারণ ভুল হলো শুধু (⊇) দিক দেখানো: “L-এর string গৃহীত হয়” প্রমাণ করলেও যন্ত্র হয়তো বাইরের string-ও গ্রহণ করে। L(N) ⊇ L দেখানো মানে শুধু অর্ধেক কাজ।
Complement-এর ফাঁদ। DFA-তে accept আর non-accept state অদলবদল করলে complement পাওয়া যায় (পর্ব ০৮, তবে DFA সম্পূর্ণ হতে হবে)। NFA-তে এই কৌশল চলে না। কারণ নিয়মটি “অন্তত একটি পথ”: অদলবদলের পর একটি string-এর একটি পথ নতুন F-এ আর আরেকটি পথ পুরোনো F-এ শেষ হতে পারে, তখন সেটি দুই যন্ত্রেই গৃহীত। N01-এ F = {q0, q1} করলে “01” তবুও গৃহীত হয় (পথ q0 → q0 → q0 শেষ হয় q0-তে)। NFA-র complement চাইলে আগে DFA-তে রূপান্তর (পর্ব ১০), তারপর অদলবদল।
৭ · দুটি NFA জোড়া — union, concatenation আর star
Nondeterminism-এর আরেকটি বড় সুবিধা: ছোট যন্ত্র জোড়া দিয়ে বড় যন্ত্র বানানো খুব সহজ। “কোন যন্ত্র চালাব” বা “কোথায় এক টুকরো শেষ হয়ে পরেরটি শুরু” — এই সিদ্ধান্তগুলো NFA শুধু অনুমান করে নেয়। সাধারণত এই জোড়া দেওয়া হয় ε-তীর দিয়ে (পর্ব ১১-এর ε-move, আর পর্ব ১৪-এর Thompson construction-এ নিয়মমাফিক)। এখানে ε ছাড়াই ধারণাটি দেখি; চাবিকাঠি হলো “শুরুর state-এর সারি কপি করা”। দুই যন্ত্র N1, N2-এর state-এর নাম আলাদা ধরা হলো।
| লক্ষ্য | নতুন তীর | accept state |
|---|---|---|
| L(N1) ∪ L(N2) | নতুন শুরু s; δ(s, a) = δ1(q01, a) ∪ δ2(q02, a) | F1 ∪ F2, আর s যদি q01 ∈ F1 বা q02 ∈ F2 |
| L(N1)L(N2) | প্রতিটি f ∈ F1-এ δ(f, a)-তে δ2(q02, a) যোগ | F2, আর ε ∈ L(N2) হলে F1-ও |
| L(N1)∗ | নতুন শুরু s; s আর প্রতিটি f ∈ F1-এ δ1(q01, a) যোগ | F1 ∪ {s} |
প্রতিটি নিয়মের পেছনে একটি অনুমান। Union-এ s-এর প্রথম চিহ্নেই যন্ত্র দুই শুরুর যেকোনোটির প্রথম পদক্ষেপ নিতে পারে, অর্থাৎ “কোন যন্ত্র” অনুমান করে। Concatenation-এ N1-এর কোনো accept state-এ পৌঁছানোর পর যন্ত্র অনুমান করতে পারে “প্রথম টুকরো এখানে শেষ”, আর পরের চিহ্নেই N2-এর শুরুর পদক্ষেপ নেয়। Star-এ নতুন s দরকার, কারণ ε ∈ L∗ সবসময়, অথচ পুরোনো q01-কে accept বানালে অন্য পথ q01-এ ফিরে এসে বাড়তি string গ্রহণ করতে পারে। নিচের stepper union-এর নিয়মটি দুটি ছোট যন্ত্রে প্রয়োগ করে।
| যন্ত্র | |
| δ(s, 0) | |
| δ(s, 1) | |
| F | |
| S |
- দুটি যন্ত্র। A = N01, state-এর নাম বদলে a0, a1, a2 (FA = {a2})। B হলো parity-যন্ত্র: e মানে এ পর্যন্ত জোড় সংখ্যক 1, o মানে বিজোড়; শুরু e, FB = {e}. B আসলে একটি DFA, কিন্তু প্রতিটি DFA-ই একটি NFA.
- s-এর 0-সারি। δ(s, 0) = δA(a0, 0) ∪ δB(e, 0) = {a0, a1} ∪ {e} = {a0, a1, e}. প্রথম চিহ্নেই যন্ত্র “A চালাব না B” দুটি সম্ভাবনাই খোলা রাখে।
- s-এর 1-সারি। δ(s, 1) = δA(a0, 1) ∪ δB(e, 1) = {a0} ∪ {o} = {a0, o}.
- s কি accept? ε-কে দুই যন্ত্রের কেউ গ্রহণ করে কি না দেখতে হবে। a0 ∉ FA, কিন্তু e ∈ FB: শূন্যটি 1 জোড় সংখ্যা। তাই s ∈ F, আর F = {a2, e, s}. নতুন যন্ত্রে 6টি state.
- পরীক্ষা: 11. {s} → 1 পড়ে {a0, o} → 1 পড়ে {a0, e}. e ∈ F, তাই গৃহীত: 11-এ দুটি 1, জোড়; যদিও এটি 01-এ শেষ হয় না।
- পরীক্ষা: 1. {s} → {a0, o}; কোনোটি F-এ নেই, তাই বাতিল। সত্যিই 1 শেষে 01 নয়, আর এতে বিজোড় সংখ্যক 1.
তিনটি নিয়মই এবার brute force দিয়ে যাচাই করুন। নিচের ব্লক A আর B দিয়ে union, concatenation আর A∗ বানায়, তারপর দৈর্ঘ্য 8 পর্যন্ত সব string-এ সংজ্ঞা থেকে সরাসরি লেখা predicate-এর সঙ্গে মেলায়। Concatenation-এর predicate সব ভাগ w = uv চেষ্টা করে; star-এর predicate একটি ছোট dynamic programming.
from itertools import product
A = ({("a0", "0"): {"a0", "a1"}, ("a0", "1"): {"a0"}, ("a1", "1"): {"a2"}}, "a0", {"a2"})
B = ({("e", "0"): {"e"}, ("e", "1"): {"o"}, ("o", "0"): {"o"}, ("o", "1"): {"e"}}, "e", {"e"})
row = lambda N, q, a: N[0].get((q, a), set()) # delta(q, a); missing key = empty set
def accepts(N, w):
cur = {N[1]}
for a in w:
cur = {r for q in cur for r in row(N, q, a)}
return bool(cur & N[2])
def union(N1, N2): # new start s copies both start rows
d = {**N1[0], **N2[0], **{("s", a): row(N1, N1[1], a) | row(N2, N2[1], a) for a in "01"}}
eps = N1[1] in N1[2] or N2[1] in N2[2]
return d, "s", N1[2] | N2[2] | ({"s"} if eps else set())
def concat(N1, N2): # accept states of N1 also copy N2's start row
d = {**N1[0], **N2[0], **{(f, a): row(N1, f, a) | row(N2, N2[1], a) for f in N1[2] for a in "01"}}
return d, N1[1], N2[2] | (N1[2] if N2[1] in N2[2] else set())
def star(N): # new accepting start s; accept states loop back
d = {**N[0], **{(q, a): row(N, q, a) | row(N, N[1], a) for q in [*N[2], "s"] for a in "01"}}
return d, "s", N[2] | {"s"}
inA = lambda w: w.endswith("01")
inB = lambda w: w.count("1") % 2 == 0
def inAstar(w): # ok[i]: w[:i] splits into pieces from A
ok = [True] + [False] * len(w)
for i in range(1, len(w) + 1):
ok[i] = any(ok[j] and inA(w[j:i]) for j in range(i))
return ok[-1]
tests = {"A u B": (union(A, B), lambda w: inA(w) or inB(w)),
"A . B": (concat(A, B), lambda w: any(inA(w[:i]) and inB(w[i:]) for i in range(len(w) + 1))),
"A*": (star(A), inAstar)}
words = ["".join(t) for n in range(9) for t in product("01", repeat=n)]
for name, (N, pred) in tests.items():
states = {q for q, _ in N[0]} | set().union(*N[0].values()) | {N[1]}
bad = sum(accepts(N, w) != pred(w) for w in words)
print(f"{name:6} states {len(states)}, strings {len(words)}, mismatches {bad}")
print("A* == {eps} u A:", all(inAstar(w) == (w == "" or inA(w)) for w in words))আসল আউটপুট (ব্রাউজারের Python):
A u B states 6, strings 511, mismatches 0
A . B states 5, strings 511, mismatches 0
A* states 4, strings 511, mismatches 0
A* == {eps} u A: True
তিন নির্মাণেই 511টি string-এ অমিল 0; union-এ ৬টি state, ঠিক stepper-এর হিসাব। শেষ লাইনটি একটি ছোট আবিষ্কার: A∗ = {ε} ∪ A. কারণ 01-এ শেষ হওয়া কয়েকটি টুকরো জুড়লে ফলও 01-এ শেষ হয়, আর উল্টোভাবে 01-এ শেষ হওয়া যেকোনো string নিজেই একটি টুকরো। Brute force কোনো দাবির প্রমাণ নয়, কিন্তু কোন দাবি প্রমাণ করার যোগ্য, তা দেখিয়ে দেয়। এই তিন নির্মাণ থেকেই আসে যে regular language union, concatenation আর star-এ বদ্ধ; পূর্ণ closure property-র তালিকা পর্ব ১৬-এ।
৮ · Nondeterminism কী নয় — randomness, সমান্তরালতা আর ইতিহাস
“Nondeterministic” শব্দটি শুনে অনেকে ভাবেন যন্ত্রটি এলোমেলোভাবে পথ বেছে নেয়, যেমন লুডুর ছক্কা। এটি ভুল ধারণা। একই NFA একই input-এ সবসময় একই উত্তর দেয়, কারণ উত্তরটি সংজ্ঞায় স্থির: “accepting পথ আছে কি না”। এখানে কোনো সম্ভাবনা বা শতাংশ নেই।
| প্রশ্ন | NFA (nondeterministic) | Probabilistic automaton |
|---|---|---|
| পছন্দ কীভাবে হয়? | সব পছন্দ একসঙ্গে বিবেচিত | প্রতিটি পছন্দের একটি সম্ভাবনা |
| Accept মানে | অন্তত একটি পথ সফল | সফল হওয়ার সম্ভাবনা একটি সীমার বেশি |
| একই input-এ আবার চালালে | সবসময় একই উত্তর | একটি run-এ উত্তর ভিন্ন হতে পারে |
| যাচাই কীভাবে | একটি accepting পথ দেখালেই হয় | সম্ভাবনার হিসাব লাগে |
| চেনা language | ঠিক regular | সীমার ধরনভেদে regular-এর বাইরেও যেতে পারে |
সমান্তরাল কম্পিউটার দিয়েও NFA-কে ঠিক বোঝানো যায় না। “প্রতিটি পছন্দে একটি নতুন processor” কল্পনা করলে processor-এর সংখ্যা পথের সংখ্যার মতোই exponential হারে বাড়ে। অনুচ্ছেদ ৪-এর সেট-পদ্ধতি দেখায়, finite automaton-এর ক্ষেত্রে এত processor লাগেই না: একই state-এর কপিগুলো এক হয়ে যায়। সব যন্ত্রে এত সহজ মিল হয় না, আর সেখান থেকেই complexity-র বড় প্রশ্নগুলো আসে।
Nondeterministic finite automaton-এর ধারণা সাধারণত Michael Rabin আর Dana Scott-এর ১৯৫৯ সালের প্রবন্ধ “Finite Automata and Their Decision Problems”-এর সঙ্গে যুক্ত করা হয়। সেখানে তাঁরা NFA সংজ্ঞায়িত করেন আর দেখান যে subset construction দিয়ে প্রতিটি NFA-কে DFA-তে রূপ দেওয়া যায়। ACM ১৯৭৬ সালে এই প্রবন্ধের জন্য, বিশেষ করে nondeterministic machine-এর ধারণা আনার জন্য, দুজনকে Turing Award দেয়। ধারণাটির কিছু আগের রূপ অন্যদের কাজেও ছিল বলে ইতিহাসবিদরা উল্লেখ করেন, তাই “একমাত্র উদ্ভাবক” না বলে “প্রভাবশালী প্রথম পূর্ণ রূপ” বলাই নিরাপদ। ১৯৬৮ সালে Ken Thompson regex খোঁজার জন্য সেট-পদ্ধতির একটি রূপ program-এ প্রয়োগ করেন, যা পর্ব ১৪ আর ২১-এ আসবে।
আরও গভীরে। Finite automaton-এ nondeterminism শক্তি বাড়ায় না, শুধু আকার কমায়, আর সেই আকার-পার্থক্য সবচেয়ে খারাপ ক্ষেত্রে exponential, যা সত্যিই ঘটে (Lk). Pushdown automaton-এ nondeterminism শক্তিও বাড়ায়: nondeterministic PDA এমন language চেনে যা কোনো deterministic PDA চেনে না (পর্ব ৩৫)। Turing machine-এ আবার শক্তি সমান (পর্ব ৪৬), কিন্তু polynomial সময়ে সমান কি না, সেটিই খোলা P বনাম NP প্রশ্ন (পর্ব ৬৩); অথচ logarithmic space-এ NL = coNL প্রমাণিত (Immerman ও Szelepcsényi, ১৯৮৭–৮৮), যদিও L বনাম NL খোলা (পর্ব ৬৬)। আরেকটি গবেষণার দিক: NFA-র state-সংখ্যা ক্ষুদ্রতম করা একটি PSPACE-complete সমস্যা বলে প্রমাণিত (Jiang ও Ravikumar-এর ১৯৯৩ সালের কাজ হিসেবে পরিচিত), অর্থাৎ DFA-র মতো দ্রুত minimization NFA-তে আশা করা যায় না, যদি না P = PSPACE.
পরীক্ষা ও ইন্টারভিউতে। এই প্রশ্নগুলো প্রায়ই আসে:
- “NFA আর DFA-র পার্থক্য কী?” — δ-এর মান একটি সেট (∅-সহ); গ্রহণ “অন্তত একটি পথে”; চেনার ক্ষমতা সমান, আকার ভিন্ন হতে পারে।
- “শেষ থেকে তৃতীয় চিহ্ন 1-এর NFA আঁকুন; DFA-তে কয়টি state?” — NFA-তে ৪টি; ক্ষুদ্রতম DFA-তে ৮টি।
- “এই NFA-তে input 0110 trace করুন” — প্রতিটি চিহ্নের পর state-এর সেট লিখুন, শেষে S ∩ F দেখুন।
- “NFA-তে accept state অদলবদল করলে কি complement হয়?” — না; আগে DFA বানাতে হয়।
- “Regex engine NFA কীভাবে চালায়?” — হয় সেট ধরে (নিশ্চিত রৈখিক সময়), নয়তো backtracking-এ পথ একে একে (দ্রুত, কিন্তু কিছু pattern-এ exponential).
৯ · AI-এর যুগে — NFA-র নকশা আর দাবি যাচাই
AI সহকারী NFA আঁকতে দ্রুত, আর উত্তর দেখতে নিখুঁত লাগে। কিন্তু এই বিষয়ে তার কয়েকটি ভুল খুব চেনা, আর সেগুলো চোখে না পড়ার মতো সূক্ষ্ম। ভালো খবর: NFA-কে Python dict-এ লিখে সব ছোট string-এ চালানো দুই মিনিটের কাজ, তাই প্রতিটি দাবি আপনি নিজেই যাচাই করতে পারেন।
| AI-এর ভুল | কেন ভুল | যাচাইয়ের উপায় |
|---|---|---|
| Accept state থেকে বাড়তি loop রেখে দেওয়া | “শেষে 01” হয়ে যায় “কোথাও 01” | 0110-এর মতো string-এ চালান |
| Off-by-one: শেষ থেকে k-তম-এ k টি বা k + 2টি state | Nk-এ ঠিক k + 1টি | দৈর্ঘ্য k − 1, k, k + 1-এর string পরীক্ষা |
| ε বা খালি string ভুলে যাওয়া | Star বা union-এ ε-এর উত্তর ভুল আসে | সবসময় "" দিয়ে আলাদা পরীক্ষা |
| NFA-তে accept state অদলবদলে complement | “অন্তত একটি পথ” নিয়মে কাজ করে না | দুই যন্ত্রেই গৃহীত একটি string খুঁজুন |
| “NFA, DFA-র চেয়ে শক্তিশালী” | চেনার ক্ষমতা সমান (subset construction) | পর্ব ১০-এর উপপাদ্য দেখুন |
| শুধু (⊇) দিকের প্রমাণ | বাইরের string-ও গৃহীত হতে পারে | (⊆) দিকটি আলাদা করে চান |
| বানানো রেফারেন্স বা সাল | উৎস হয়তো নেই | Sipser বা Hopcroft–Motwani–Ullman-এ মিলিয়ে দেখুন |
নিচের prompt-টি AI-কে এমন আকারে উত্তর দিতে বাধ্য করে, যা আপনি সরাসরি চালিয়ে যাচাই করতে পারেন: টেবিল আকারে δ, দুই দিকের প্রমাণ, আর একটি brute-force পরীক্ষা।
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১কোনো যন্ত্র তো সত্যিই “সঠিক অনুমান” করতে পারে না। তাহলে এমন অবাস্তব যন্ত্রের সংজ্ঞা দিয়ে লাভ কী?
লাভ তিনটি, আর তিনটিই বাস্তব। প্রথমটি বর্ণনার সহজতা। “শেষে SALE” বা “শেষ থেকে k-তম চিহ্ন 1” language-কে NFA প্রায় ইংরেজি বাক্যের মতো সরাসরি লেখে: অপেক্ষা, অনুমান, যাচাই। DFA লিখতে গেলে সব সম্ভাবনা একসঙ্গে হিসাব রাখতে হয়, যা ভুলের উৎস। আর যেহেতু subset construction যান্ত্রিকভাবে NFA-কে DFA বানায়, তাই সহজ বর্ণনা লিখে কঠিন অংশটি algorithm-কে দিয়ে দেওয়া যায়। Lexer generator ঠিক এভাবে কাজ করে: token-এর regex থেকে NFA, তারপর DFA (পর্ব ২২)।
দ্বিতীয়টি প্রমাণের সহজতা। Regular language union, concatenation আর star-এ বদ্ধ, এই কথাটি NFA দিয়ে কয়েক লাইনে প্রমাণ হয় (অনুচ্ছেদ ৭)। শুধু DFA দিয়ে concatenation-এর প্রমাণ লেখা অনেক জটিল, কারণ “প্রথম টুকরো কোথায় শেষ” সেই সিদ্ধান্ত DFA নিতে পারে না। Kleene-এর theorem-এর এক দিক (regex থেকে automaton, পর্ব ১৪) পুরোটাই এই সুবিধার ওপর দাঁড়িয়ে।
তৃতীয়টি ধারণার শক্তি। Rabin আর Scott ১৯৫৯ সালে যখন nondeterminism আনেন, তখন এটি একটি সুবিধাজনক কৌশল ছিল। পরে বোঝা গেল, “একটি সাক্ষী আছে কি না” প্রশ্নটি গণনার তত্ত্বের মূলে। NP শ্রেণি (পর্ব ৫৮) ঠিক এভাবে সংজ্ঞায়িত: যেসব সমস্যার হ্যাঁ-উত্তরের একটি ছোট সাক্ষী আছে, যা দ্রুত যাচাই করা যায়। NFA-র accepting পথ সেই সাক্ষীর সবচেয়ে সরল রূপ। একটি Sudoku-র সমাধান খুঁজে পাওয়া কঠিন, কিন্তু কেউ সমাধান দেখালে যাচাই সহজ; NFA-ও “পথটি দেখাও, আমি যাচাই করে দিই” ধাঁচের যন্ত্র।
লক্ষ করুন, এর কোনোটিতেই কোনো যন্ত্রকে সত্যিই অনুমান করতে হয় না। আমরা যখন NFA চালাই, deterministic program দিয়ে সেট ধরে চালাই। “অনুমান” শুধু সংজ্ঞার ভাষা, যার আসল অর্থ “∃ একটি পথ”।
মূল উপলব্ধি: NFA একটি বর্ণনার ভাষা ও প্রমাণের হাতিয়ার, বাস্তব যন্ত্রের নকশা নয়। “আছে কি না” প্রশ্নকে যন্ত্রের রূপ দিয়ে এটি পরে NP-এর মতো বড় ধারণার দরজা খুলেছে।
প্র ০২Nondeterminism আর randomness দুটিই “একাধিক সম্ভাবনা” নিয়ে কাজ করে। তাহলে probabilistic automaton কি NFA-রই আরেক নাম?
না, আর পার্থক্যটি গভীর। NFA-তে প্রশ্ন হলো “অন্তত একটি পথ সফল কি না”। একশো কোটি পথের মধ্যে একটিমাত্র সফল হলেও উত্তর হ্যাঁ। Probabilistic automaton-এ প্রতিটি পছন্দের একটি সম্ভাবনা থাকে, যেমন “০.৫ সম্ভাবনায় q1, ০.৫ সম্ভাবনায় q2”. তখন প্রশ্ন হয় “সফল হওয়ার সম্ভাবনা কত”, আর একটি সীমা λ ঠিক করে বলা হয়, সম্ভাবনা λ-এর বেশি হলে accept. একশো কোটির মধ্যে একটি সফল পথ থাকলে সম্ভাবনা প্রায় শূন্য, তাই probabilistic যন্ত্র reject করবে, যেখানে NFA accept করে।
Michael Rabin নিজেই ১৯৬৩ সালে “Probabilistic Automata” প্রবন্ধে এই মডেল নিয়ে কাজ করেন। একটি বিখ্যাত ফল: সীমা যদি “বিচ্ছিন্ন” হয় (অর্থাৎ প্রতিটি string-এর সম্ভাবনা λ থেকে একটি নির্দিষ্ট দূরত্বে থাকে), তাহলে এমন যন্ত্রও শুধু regular language চেনে। কিন্তু এই শর্ত না থাকলে probabilistic automaton regular-এর বাইরের language-ও চিনতে পারে, আর এর কিছু প্রশ্ন undecidable বলে জানা যায়। অর্থাৎ randomness সসীম যন্ত্রে কিছু ক্ষেত্রে সত্যিকারের নতুন ক্ষমতা আনে, যা nondeterminism আনে না।
Complexity তত্ত্বে এই পার্থক্য দুটি আলাদা শ্রেণি দেয়: NP (nondeterminism: একটি সাক্ষী আছে) আর BPP (randomness: বেশিরভাগ random পছন্দে উত্তর ঠিক)। BPP = P বলে অনেক গবেষক বিশ্বাস করেন, কিন্তু এটি প্রমাণিত নয়; আর NP-এর সঙ্গে BPP-এর সম্পর্কও অজানা (পর্ব ৬৯)। বাস্তবেও পার্থক্য স্পষ্ট: randomized algorithm (যেমন Miller–Rabin primality test) সত্যিই পয়সা ছুড়ে চালানো যায়, কিন্তু nondeterministic algorithm সরাসরি চালানো যায় না, শুধু simulate করা যায়।
একটি সহজ পরীক্ষা মনে রাখুন: একই input-এ যন্ত্রটি দুবার চালালে কি ভিন্ন আচরণ দেখা যেতে পারে? Probabilistic যন্ত্রে হ্যাঁ; NFA-র উত্তর সংজ্ঞায় স্থির, তাই না।
মূল উপলব্ধি: Nondeterminism হলো “∃ একটি পথ”, randomness হলো “বেশিরভাগ পথ”। প্রথমটি যাচাইয়ের ধারণা, দ্বিতীয়টি গণনার একটি বাস্তব কৌশল।
প্র ০৩NFA যদি DFA-র চেয়ে exponential হারে ছোট হতে পারে, তাহলে সব জায়গায় NFA ব্যবহার করি না কেন?
কারণ ছোট আকারের একটি দাম আছে, আর সেই দাম কয়েক জায়গায় দিতে হয়। প্রথম জায়গা চালানোর খরচ। DFA প্রতিটি চিহ্নে একটি টেবিল দেখে, O(1) কাজ। NFA-র সেট-simulation প্রতিটি চিহ্নে বড়জোর |Q| টি state-এর তীর দেখে, মোট O(|w| · |Q|2). বিশাল লেখায় বারবার খুঁজতে হলে (যেমন log ফাইলে একটি pattern) আগে DFA বানিয়ে নেওয়া লাভজনক; কিন্তু DFA বানাতে 2|Q| পর্যন্ত state লাগতে পারে। তাই বাস্তব engine প্রায়ই মাঝামাঝি পথ নেয়: চালানোর সময় যে state-সেটগুলো সত্যিই দেখা দেয়, শুধু সেগুলোর DFA state বানিয়ে cache করে (lazy DFA, পর্ব ১০ ও ২১)।
দ্বিতীয় জায়গা প্রশ্নের উত্তর দেওয়া। DFA-র জন্য complement তুচ্ছ, দুটি DFA সমান কি না দ্রুত বলা যায়, আর ক্ষুদ্রতম DFA-ও দ্রুত বের হয় (পর্ব ১৯)। NFA-তে এগুলো কঠিন। Complement-এর আগে DFA বানাতে হয় (অনুচ্ছেদ ৬-এর সতর্কতা)। দুটি NFA একই language চেনে কি না, বা একটি NFA সব string গ্রহণ করে কি না, এই প্রশ্নগুলো PSPACE-complete বলে প্রমাণিত; এই ফল সাধারণত ১৯৭০-এর দশকের শুরুতে Meyer ও Stockmeyer-এর কাজের সঙ্গে যুক্ত (পর্ব ২০ আর ৬৫)। ক্ষুদ্রতম NFA খোঁজাও PSPACE-complete. অর্থাৎ ছোট বর্ণনা পেতে গিয়ে আমরা সহজ প্রশ্নোত্তরের সুবিধা হারাই।
তৃতীয় জায়গা অনন্যতা। প্রতিটি regular language-এর ক্ষুদ্রতম DFA একটিই (state-এর নাম বাদে), যা Myhill–Nerode theorem থেকে আসে (পর্ব ১৮)। ক্ষুদ্রতম NFA একাধিক হতে পারে, তাই “এই language-এর আদর্শ যন্ত্র” বলে কিছু থাকে না।
তাই বাস্তবে নিয়মটি হলো: বর্ণনা আর নির্মাণে NFA, প্রশ্নোত্তর আর দ্রুত চালানোয় DFA. Compiler-এর lexer, regex engine আর model checker সবাই এই দুই রূপের মধ্যে দরকারমতো যাতায়াত করে।
মূল উপলব্ধি: NFA-র ছোট আকার বিনামূল্যে নয়; complement, equivalence আর minimization কঠিন হয়ে যায়। কোন রূপ কখন, সেই বাছাই-ই প্রকৌশল।
প্র ০৪Regex লাইব্রেরি কীভাবে NFA চালায়? পথ একে একে, নাকি সেট ধরে? আর এতে কী আসে যায়?
দুই পদ্ধতিই ব্যবহার হয়, আর পার্থক্য কখনো কখনো নাটকীয়। ১৯৬৮ সালে Ken Thompson তাঁর প্রবন্ধে regex থেকে একটি NFA বানিয়ে সেটি সেট ধরে চালানোর পদ্ধতি দেখান; Unix-এর প্রথম দিকের grep-এর মতো tool এই ঐতিহ্য থেকে আসে। এই পদ্ধতিতে সময় input-এর দৈর্ঘ্যের সঙ্গে রৈখিক, যেকোনো pattern-এ: অনুচ্ছেদ ৪-এর O(|w| · |Q|2) হিসাব।
অনেক জনপ্রিয় regex engine (Perl-ঘরানার, আর Python-এর re, JavaScript-এর RegExp-এর মতো) অন্য পথ নেয়: backtracking. এরা computation tree-র একটি শাখা ধরে এগোয়; ব্যর্থ হলে পিছিয়ে এসে পরের শাখা চেষ্টা করে, ঠিক JavaScript ব্লকের depth-first ফাংশনের মতো। বেশিরভাগ pattern-এ এটি দ্রুত, আর এতে backreference-এর মতো সুবিধা সহজে যোগ করা যায়, যা গাণিতিক regular language-এর বাইরে। কিন্তু কিছু pattern-এ, যেমন (a+)+b-এর মতো nested repetition, a দিয়ে ভরা কিন্তু b-ছাড়া input-এ শাখার সংখ্যা exponential হয়ে যায়। কপি-যন্ত্রের উদাহরণে পথ ছিল 2n; backtracking engine সত্যিই সেগুলো একে একে চেষ্টা করতে পারে।
এর একটি নিরাপত্তা-দিকও আছে, যার নাম ReDoS (regular expression denial of service): একটি দুর্বল pattern আর ছোট একটি দুষ্ট input দিয়ে server-এর CPU আটকে দেওয়া। প্রতিকার তিন রকম: pattern নতুন করে লেখা, সময়সীমা বসানো, অথবা automaton-ভিত্তিক engine (যেমন RE2-এর ঘরানা) ব্যবহার করা, যা backreference ছেড়ে দিয়ে রৈখিক সময়ের নিশ্চয়তা দেয়। পর্ব ২১-এ নিজের computer-এ নিরাপদভাবে এর সময় মেপে দেখা হবে; সাইবার নিরাপত্তা কোর্সেও প্রতিরক্ষার দিক থেকে বিষয়টি আছে।
মূল উপলব্ধি: “পথ একে একে” আর “সেট ধরে” একই NFA-র দুই চালানোর কৌশল। প্রথমটি সহজ আর বাড়তি সুবিধা দেয়, দ্বিতীয়টি সবসময় দ্রুত থাকার নিশ্চয়তা দেয়; তত্ত্ব জানলে কোন pattern বিপজ্জনক, তা আগেই বোঝা যায়।
প্র ০৫Finite automaton-এ nondeterminism কোনো নতুন language আনে না। বড় যন্ত্রেও কি তাই?
না, আর উত্তরটি যন্ত্রভেদে আলাদা, যা গণনার তত্ত্বের সবচেয়ে সুন্দর নকশাগুলোর একটি। Finite automaton-এ NFA = DFA, কারণ সম্ভাব্য state-এর সেটও সসীম, তাই সেটটিকেই একটি বড় DFA-র state বানানো যায়। খরচ শুধু আকারে।
Pushdown automaton-এ (stack-সহ যন্ত্র, পর্ব ৩২) এই কৌশল ভেঙে পড়ে, কারণ প্রতিটি কপির নিজের stack থাকে, আর stack-এর সম্ভাব্য বিষয়বস্তু অসীম। ফল: nondeterministic PDA কিছু language চেনে যা কোনো deterministic PDA চেনে না। উদাহরণ, even-length palindrome {wwR}: যন্ত্রকে “মাঝখান কোথায়” অনুমান করতে হয়, আর এই অনুমান ছাড়া চলে না (পর্ব ৩৫)। Programming language-এর parser deterministic রাখতে grammar-কে যে বিশেষ রূপে লেখা হয়, তার কারণ এটিই।
Turing machine-এ আবার শক্তি সমান: একটি deterministic TM computation tree-কে স্তর ধরে (breadth-first) ঘুরে nondeterministic TM-কে simulate করে (পর্ব ৪৬)। কিন্তু এই simulation-এ সময় exponential হারে বাড়তে পারে। Polynomial সময়ে এই বৃদ্ধি এড়ানো যায় কি না, অর্থাৎ P = NP কি না, সেটি আজও খোলা প্রশ্ন (পর্ব ৬৩)। Space-এর হিসাবে চিত্র ভিন্ন: Savitch ১৯৭০ সালে দেখান nondeterministic space f(n) (f(n) ≥ log n) deterministic space f(n)2-এ simulate করা যায়, তাই NPSPACE = PSPACE প্রমাণিত। আর Immerman ও Szelepcsényi ১৯৮৭–৮৮ সালে স্বাধীনভাবে প্রমাণ করেন NL = coNL, যদিও L = NL কি না জানা নেই (পর্ব ৬৪, ৬৬)।
অর্থাৎ “nondeterminism কি সাহায্য করে?” প্রশ্নের তিন রকম উত্তর: সসীম যন্ত্রে শক্তিতে না, আকারে হ্যাঁ; stack-যন্ত্রে শক্তিতেই হ্যাঁ; Turing machine-এ শক্তিতে না, কিন্তু সময়ে সম্ভবত হ্যাঁ, যা প্রমাণ হয়নি।
মূল উপলব্ধি: এই পর্বের ছোট প্রশ্ন “NFA কি DFA-র চেয়ে শক্তিশালী?” পুরো কোর্সে বড় হয়ে ফিরে আসবে; কোথায় উত্তর জানা আর কোথায় খোলা, সেই পার্থক্য স্পষ্ট রাখাই আসল দক্ষতা।
অনুশীলন
একটি নকশা, একটি ভুল-খোঁজা, একটি trace আর একটি প্রমাণ। আগে নিজে চেষ্টা করুন, তারপর উত্তর খুলুন।
-
NFA নকশা: Σ = {a, b}-এর ওপর Laba = {w : w-তে aba একটি substring}-এর জন্য ε ছাড়া একটি NFA নকশা করুন। কয়টি state লাগে? Transition table লিখুন আর ababa-র trace দেখান।
৪টি state: q0 “অপেক্ষা”, q1 “a দেখে অনুমান: এখান থেকে aba শুরু”, q2 “ab মিলেছে”, q3 “aba পাওয়া গেছে”। F = {q3}, আর q3-তে সব চিহ্নে loop, কারণ substring পাওয়ার পর বাকি যা-ই আসুক, string গৃহীত।
state a b → q0 {q0, q1} {q0} q1 ∅ {q2} q2 {q3} ∅ ∗ q3 {q3} {q3} ababa: {q0} → a → {q0, q1} → b → {q0, q2} → a → {q0, q1, q3} → b → {q0, q2, q3} → a → {q0, q1, q3}; শেষে q3 আছে, গৃহীত। যাচাই: একটি scratch script দৈর্ঘ্য 12 পর্যন্ত সব string-এ এই NFA-কে Python-এর
"aba" in w-এর সঙ্গে মিলিয়েছে, অমিল 0; automata-lib-এর minimization-এ ক্ষুদ্রতম DFA-তেও ৪টি state, তবে সেখানে প্রতিটি ব্যর্থ মিলের জন্য ফেরার তীর ঠিক করতে হয়। -
ভুল খুঁজুন (প্রমাণ): “দাবি: NFA N = (Q, Σ, δ, q0, F) থেকে N′ = (Q, Σ, δ, q0, Q − F) বানালে L(N′) = Σ∗ − L(N). প্রমাণ: w ∈ L(N) হলে w-এর পথ F-এ শেষ, তাই Q − F-এ নয়, তাই w ∉ L(N′). উল্টোভাবে w ∉ L(N) হলে পথ F-এ শেষ নয়, তাই Q − F-এ শেষ, তাই w ∈ L(N′). ∎” ভুলটি কোথায়? N01 দিয়ে একটি counterexample দিন।
ভুল “w-এর পথ” কথাটিতে: প্রমাণটি ধরে নিয়েছে প্রতিটি string-এর ঠিক একটি পথ আছে, যা DFA-তে সত্য, NFA-তে নয়। NFA-তে w-এর অনেক পথ থাকতে পারে, আবার কোনো পথই না থাকতে পারে (সব শাখা মৃত)।
- প্রথম অংশের ভুল: w ∈ L(N) মানে কোনো একটি পথ F-এ শেষ; অন্য একটি পথ Q − F-এ শেষ হতে পারে, তখন w ∈ L(N′)-ও।
- দ্বিতীয় অংশের ভুল: সব শাখা মাঝপথে মরে গেলে কোনো পথ Q − F-এ শেষ হয় না, তখন w দুই যন্ত্রেই বাতিল।
- Counterexample: N01-এ F = {q2}, তাই N′-এ F′ = {q0, q1}. Input 01: δ̂(q0, 01) = {q0, q2}. q2 ∈ F বলে 01 ∈ L(N); q0 ∈ F′ বলে 01 ∈ L(N′)-ও। অথচ complement-এ 01 থাকার কথা নয়। (Input 1 আর ε-তে N′ ঠিক উত্তর দেয়, তাই ভুলটি শুধু কয়েকটি string-এ ধরা পড়ে; brute force দিয়ে খুঁজলে সবচেয়ে ছোট counterexample 01.)
সঠিক পদ্ধতি: আগে subset construction-এ সম্পূর্ণ DFA (পর্ব ১০), তারপর accept state অদলবদল।
-
Trace (আউটপুট অনুমান করুন): ছবি ৯.১-এর N3 (state q0–q3, F = {q3}) input 10100 পড়ছে। প্রতিটি চিহ্নের পর state-এর সেট লিখুন। কোন কোন অবস্থানে সেটে q3 থাকে? শেষে উত্তর কী?
{q0} → 1 → {q0, q1} → 0 → {q0, q2} → 1 → {q0, q1, q3} → 0 → {q0, q2} → 0 → {q0, q3}.
q3 আসে তৃতীয় চিহ্নের পর (101-এর শেষ থেকে তৃতীয় চিহ্ন 1), চতুর্থ চিহ্নের পর চলে যায় (q3 থেকে কোনো তীর নেই, আর 1010-এর শেষ থেকে তৃতীয় চিহ্ন 0), আর পঞ্চম চিহ্নের পর আবার আসে। শেষ সেটে q3 আছে, তাই 10100 গৃহীত: শেষ তিনটি চিহ্ন 100, যার প্রথমটি 1. ক্রমগুলো scratch script আর
kth_from_end.py-এর একইrunফাংশন দিয়ে যাচাই করা। -
প্রমাণ করুন: ε-transition ছাড়া এমন একটি NFA নেই, যার accept state ঠিক একটি আর যার language L = {ε, a} (Σ = {a})। (ইঙ্গিত: ε কোথায় গৃহীত হয়?)
- ধরুন এমন NFA N আছে, F = {f}. — বিরোধের জন্য অনুমান
- ε ∈ L, আর δ̂(q0, ε) = {q0}, তাই q0 ∈ F, অর্থাৎ f = q0. — সংজ্ঞা ৯.২
- a ∈ L, তাই δ̂(q0, a) = δ(q0, a)-তে f = q0 আছে। — F = {q0}
- তাহলে q0 → q0 → q0 হলো aa-র একটি পথ, যা F-এ শেষ, তাই aa ∈ L(N). — ধাপ ৩ দুবার
- কিন্তু aa ∉ L: বিরোধ। তাই এমন N নেই। ∎
দুটি accept state থাকলে সমস্যা মেটে: q0 (accept) থেকে a-তে q1 (accept), q1-এর কোনো তীর নেই। আর ε-transition থাকলে যেকোনো NFA-কে এক accept state-এ আনা যায়: সব পুরোনো accept state থেকে একটি নতুন f-এ ε-তীর (পর্ব ১১)। Thompson construction ঠিক এই সুবিধা ব্যবহার করে।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি NFA-কে input w-এ state-এর সেট ধরে চালানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- সেট S-এ শুধু শুরুর state q0 রাখা
- w-এর পরের চিহ্ন a পড়া
- S-এর প্রতিটি state q-এর δ(q, a) মিলিয়ে নতুন S বানানো
- w শেষ না হওয়া পর্যন্ত আগের দুই ধাপ বারবার করা
- শেষ S-এ কোনো accept state থাকলে accept, নইলে reject
ε-transition ছাড়া একটি NFA N = (Q, Σ, δ, q0, F)-এর transition function δ-এর সঠিক রূপ কোনটি?
- δ: Q × Σ → Q
- δ: Q × Σ → P(Q)
- δ: Q × (Σ ∪ {ε}) → P(Q)
- δ: Q × Σ∗ → Q
NFA N-এর state q0, q1, q2; শুরু q0, F = {q2}; δ(q0, 0) = {q0, q1}, δ(q0, 1) = {q0}, δ(q1, 1) = {q2}, বাকি সব ∅. Input 0110 পড়ার পর state-এর সেট কী, আর উত্তর কী?
- {q0, q2}; accept
- {q0}; reject
- {q0, q1}; reject
- {q0, q1, q2}; accept
একটি NFA একটি string w-কে কখন reject করে?
- যখন w-এর অন্তত একটি পথ non-accept state-এ শেষ হয়
- যখন computation tree-র কোনো শাখা মাঝপথে মরে যায়
- যখন পড়ার মাঝপথে কোনো পথ কখনো F-এ যায়নি
- যখন w পুরো পড়ে F-এ শেষ হওয়া কোনো পথই নেই
Σ = {0, 1}-এর ওপর L4 = {w : w-এর শেষ থেকে চতুর্থ চিহ্ন 1}. ε-transition ছাড়া একটি NFA-তে কয়টি state যথেষ্ট, আর যেকোনো DFA-তে অন্তত কয়টি লাগে?
- NFA-তে 5টি; DFA-তে অন্তত 16টি
- NFA-তে 4টি; DFA-তে অন্তত 8টি
- NFA-তে 5টি; DFA-তে অন্তত 5টি
- NFA-তে 16টি; DFA-তে অন্তত 16টি
NFA আর probabilistic automaton সম্পর্কে কোন বক্তব্যটি সঠিক?
- NFA প্রতিটি মোড়ে এলোমেলোভাবে একটি পথ বেছে নেয়
- NFA গ্রহণ করে যখন অর্ধেকের বেশি পথ সফল হয়
- NFA গ্রহণ করে যদি অন্তত একটি পথ সফল হয়; probabilistic যন্ত্রে সফলতার সম্ভাবনা একটি সীমা ছাড়াতে হয়
- NFA চালাতে একটি random number generator লাগে
দুটি NFA N1 (শুরু p) আর N2 (শুরু r), state-এর নাম আলাদা, ε-transition নেই। L(N1) ∪ L(N2)-এর জন্য নতুন শুরুর state s বানানো হলো। δ(s, a) আর s-এর accept হওয়ার সঠিক নিয়ম কোনটি?
- δ(s, a) = δ1(p, a); s কখনো accept নয়
- δ(s, a) = δ1(p, a) ∪ δ2(r, a); s accept যদি p ∈ F1 বা r ∈ F2
- δ(s, a) = δ1(p, a) ∩ δ2(r, a); s accept যদি p ∈ F1 আর r ∈ F2
- δ(s, a) = δ1(p, a) ∪ δ2(r, a); s সবসময় accept
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- N = (Q, Σ, δ, q0, F), δ: Q × Σ → P(Q). একটি চিহ্নে শূন্য, এক বা একাধিক পরের state; ∅ মানে সেই পথ মৃত, dead state লাগে না।
- গ্রহণ = অন্তত একটি পথ পুরো w পড়ে F-এ শেষ; সমতুল্যভাবে δ̂(q0, w) ∩ F ≠ ∅. মাঝপথে F ছোঁয়া গণ্য নয়।
- চালাতে সেট গুনুন, পথ নয়। পথ 2n হতে পারে, সেট বড়জোর |Q|; সময় O(|w| · |Q|2).
- নকশা = অপেক্ষা, অনুমান, যাচাই। Lk-এর NFA-তে k + 1 state, DFA-তে অন্তত 2k; প্রমাণ দুই দিকে (⊆, ⊇)।
- NFA = DFA শক্তিতে, randomness নয়। Accept অদলবদলে NFA-র complement হয় না; union, concatenation, star সহজ।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ১০ · NFA থেকে DFA — subset construction আর state বিস্ফোরণপরবর্তী পর্বসেট-simulation থেকে পূর্ণ DFA, সঠিকতার প্রমাণ আর 2n-এর নিম্নসীমা।
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্বপুরো কোর্সের মানচিত্র আর শেখার পথ।
- পর্ব ০৪ · string-এর ওপর induction আর constructionপ্রমাণের কৌশলδ̂-এর মতো inductive সংজ্ঞা আর দুই দিকের প্রমাণের ছক।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৪ · Finite automatonপটভূমিDFA, NFA আর regex-এর এক পর্বে প্রথম পরিচয়।
- সফটওয়্যার টেস্টিং · পর্ব ১০ · State-transition testingপাশের ট্র্যাকState machine-কে পরীক্ষার দিক থেকে দেখা।